Drying

Interview

Time limit2sMemory limit64 MB

Summary

Given drying times per cloth that decrease by 1 each minute (or by k for one chosen cloth per minute on a radiator), find the minimum total minutes to dry all clothes, solved via binary search on time.

Level: Medium5 of 10
Topics: Binary search, Greedy
Solved: No attempts yet

Problem

Drying clothes in winter is slow, so Jane speeds it up with a radiator. The radiator is small and can hold only one item at a time.

There are $n$ freshly washed clothes, and cloth $i$ holds $a_i$ units of water. Each minute, the water in every cloth that is not yet dry decreases by $1$ . The moment a cloth's water reaches $0$ it is dry and ready to be packed.

Each minute Jane may also place one cloth on the radiator. During that minute the chosen cloth loses $k$ units of water instead of the usual $1$ (never dropping below $0$ : if it holds fewer than $k$ units, its water becomes $0$ ).

Using the radiator as effectively as possible, compute the minimum number of minutes needed until every cloth is dry.

Input

The first line contains a single integer $n$ ( $1 \le n \le 100\,000$ ).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ separated by spaces ( $1 \le a_i \le 10^9$ ).

The third line contains a single integer $k$ ( $1 \le k \le 10^9$ ).

Output

Output a single integer: the minimum number of minutes required to dry all the clothes.

Examples5

Example 1
Input
```
3
2 3 9
5
```
Expected output
```
3
```
Example 2
Input
```
3
2 3 6
5
```
Expected output
```
2
```
Example 3
Input
```
1
10
3
```
Expected output
```
4
```
Example 4
Input
```
4
1 1 1 1
10
```
Expected output
```
1
```
Example 5
Input
```
5
1 2 3 4 5
2
```
Expected output
```
3
```