Informatica Online Judge

  빨래하기 (Small) [2086 / 0826]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 33   Total Tried : 36


The Champion of this Problem (C++) : gs16051 - 0ms / 362byte
My Best Submission (C++) : N/A

[]

Background

어느덧 또 다시 추운 겨울이 다가오고 있다.

겨울이 되면 기숙사에서 생활하는 경곽이에게는 자신이 직접한 빨래를 건조 시키는 것이 늘 고민으로 다가온다.

독립심이 강한 경곽이는 개의 빨래를 스스로 한다.

빨래가 끝나면 각각의 빨래는 만큼의 수분을 포함하고 있게 된다.

빨래대에 널린 모든 빨래는 분당 수분이 1씩 감소를 하게 되며, 수분의 양이 0 이 되면 빨래는 마른 것으로 간주한다. 이와 같은 과정을 자연 건조라고 하자.

이번 겨울 빨래를 조금 더 빠르게 건조 시키기 위하여 경곽이는 자신이 직접 만든 “특수 건조기”를 이용하기로 했다.

이 건조기는 분당 하나의 빨래를 건조 시킬 수 있으며 최대 k만큼의 수분을 감소시킬 수
있다. 단 건조기로 말리는 동안에는 자연 건조는 일어나지 않는다.

입력으로 빨래의 수, 빨래가 포함하고 있는 수분의 양, 특수 건조기의 건조 능력이 입력될 때 모든 빨래가 모두 마르게 되는 최소 시간을 구하는 프로그램을 작성하여 잘 마른 옷을 입고 학교생활을 열심히 하는 경곽이가 되게 도와주자.

Input

첫 줄에 빨래의 수를 나타내는 정수 $n$이 입력된다.

두 번째 줄부터 각 빨래의 수분의 양 $a_i$가 입력이 된다.

세 번째 줄에는 건조기의 분당 건조 능력을 나타내는 정수 $k$가 입력이 된다.

[입력값의 정의역]

$1 ≤ n ≤ 2,000 ; 1 ≤ a_i ≤ 100,000 ; 1 ≤ k ≤ 100,000$

Output

모든 빨래가 건조가 되는 최소 시간을 출력한다.

IO Example

입력
3
2 3 6
5

출력
2

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]