33258번 - 상현이의 수학 공부 대작전

문제

KSA의 모 선생님은 수학 공부를 많이 하는 학생을 좋아하기 때문에 앞으로 학생들에게 $N$일 동안 수학공부를 굉장히 많이 시키기로 결심했다. 선생님은 학생들이 $i$일차에 $A_i$개의 수학문제를 풀기를 원하고, 각 학생에 대한 호감도는 해당 학생이 수학공부를 얼마나 많이 풀었는지에 따라 달라진다. 어떤 학생이 $i$일차에 $x$개의 수학 문제를 풀었다면, 해당 학생에 대한 호감도는 $$f_i(x) = \begin{cases} x & \text{if } x \ge A_i, \\ 2(x - A_i) & \text{if }x < A_i \end{cases}$$만큼 증가한다.

상현이는 규칙적인 공부를 원하기 때문에 $N$일 동안 매일 동일한 양의 수학문제를 풀기로 마음먹었다. 처음에 상현이에 대한 선생님의 호감도가 0ドル$이며, 상현이는 $N$일 이후 $L$ 이상의 호감도를 얻고 싶다. 이때 하루에 풀어야 하는 수학 문제 수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 정수 $N$$(1 \le N \le 10^5)$이 주어진다.

두 번째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(1 \le A_i \le 10^4)$

세 번째 줄에 정수 $L$$(1 \le L \le 10^9)$이 주어진다.

출력

상현이가 하루에 풀어야 하는 수학 문제 수의 최솟값을 출력한다.

제한

힌트