빨래 말리기

겨울에는 빨래가 잘 마르지 않아서, Jane은 라디에이터로 건조 속도를 높이려고 한다. 라디에이터는 작아서 한 번에 옷 한 벌만 올려놓을 수 있다.

방금 빤 옷이 $n$벌 있고, $i$번째 옷은 물을 $a_i$만큼 머금고 있다. 매 분마다 아직 마르지 않은 모든 옷의 물의 양이 $1$씩 줄어든다. 물의 양이 $0$이 되는 순간 그 옷은 다 말라서 갤 수 있게 된다.

또한 매 분마다 Jane은 옷 한 벌을 라디에이터 위에 올려놓을 수 있다. 그 분 동안 라디에이터에 올린 옷은 평소의 $1$ 대신 물이 $k$만큼 줄어든다(단, $0$ 미만으로는 내려가지 않으며, 남은 물이 $k$보다 적으면 물의 양은 $0$이 된다).

라디에이터를 최대한 효율적으로 사용하여, 모든 옷이 마를 때까지 걸리는 최소 시간(분)을 구하여라.

첫째 줄에 정수 $n$이 주어진다 ($1 \le n \le 100\,000$).

둘째 줄에 $n$개의 정수 $a_1, a_2, \ldots, a_n$이 공백으로 구분되어 주어진다 ($1 \le a_i \le 10^9$).

셋째 줄에 정수 $k$가 주어진다 ($1 \le k \le 10^9$).

모든 옷을 말리는 데 필요한 최소 시간(분)을 정수 하나로 출력한다.