상현이의 수학 공부 대작전

시간 제한1초메모리 제한1024 MB

요약

상현이가 매일 같은 수의 문제를 풀 때, N일 뒤 호감도가 L 이상이 되는 하루 문제 수의 최솟값을 구한다.

난이도: 보통10점 중 5점
유형: 이분 탐색, 수학, 완전 탐색
정답자: 아직 제출이 없습니다

문제

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)$ 이 주어진다.

출력

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

예제1

예제 1
입력
```
2
5 4
6
```
예상 출력
```
5
```