Kevin loves bananas, but he hates it when one tree has too many bananas compared with the others. He has found a forest with ~n~ banana trees. The ~i~-th tree initially has ~a_i~ bananas.

Kevin has exactly ~h~ hours to eat before he must go home. To keep the trees as balanced as possible, he follows this strategy during each hour:

1. He chooses a tree that currently has the maximum number of bananas. If several trees are tied for the maximum, he may choose any of them.
2. He eats ~k~ bananas from that tree. If it contains fewer than ~k~ bananas, he eats all of its remaining bananas instead, leaving it with ~0~ bananas.
3. The hour ends, and Kevin repeats the process for the next hour.

If every tree is empty before the ~h~ hours have passed, all trees remain empty for the remaining hours.

Given the initial number of bananas on each tree, determine the maximum number of bananas on any tree after exactly ~h~ hours.

Input

The first line contains three integers ~n~, ~h~, and ~k~ (~1 \leq n \leq 10^5~, ~1 \leq h \leq 10^5~, ~1 \leq k \leq 10^9~): the number of trees, the number of hours Kevin has, and the maximum number of bananas he eats per hour.

The second line contains ~n~ integers ~a_1,a_2,\dots,a_n~ (~1 \leq a_i \leq 10^9~), where ~a_i~ is the initial number of bananas on the ~i~-th tree.

Output

Output a single integer: the maximum number of bananas remaining on any tree after exactly ~h~ hours.

Examples

Input 1

3 3 4
7 10 3

Output 1

3

Kevin eats ~k=4~ bananas per hour:

• Hour 1: ~[7,10,3]\rightarrow[7,6,3]~.
• Hour 2: ~[7,6,3]\rightarrow[3,6,3]~.
• Hour 3: ~[3,6,3]\rightarrow[3,2,3]~.

After ~3~ hours, the maximum number of bananas on a tree is ~3~.

Input 2

2 5 10
15 12

Output 2

0

Kevin eats ~k=10~ bananas per hour:

• Hour 1: ~[15,12]\rightarrow[5,12]~.
• Hour 2: ~[5,12]\rightarrow[5,2]~.
• Hour 3: ~[5,2]\rightarrow[0,2]~.
• Hour 4: ~[0,2]\rightarrow[0,0]~.
• Hour 5: ~[0,0]\rightarrow[0,0]~.

Therefore, the maximum number of bananas remaining on a tree is ~0~.

Input 3

4 2 5
10 10 10 10

Output 3

10

Kevin reduces two of the trees from ~10~ bananas to ~5~. The resulting counts are ~[5,5,10,10]~, so the maximum is still ~10~.