J. Washing Machine
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Finally, the electricity is back on and will last for $$$H$$$ hours before it goes out again. You have clothes to wash. You have $$$N$$$ different colors of clothes. For each color $$$i$$$, an integer $$$A_i$$$ represents the number of items of that color.

You have a washing machine. In each washing cycle (which takes one hour), you can wash:

  • At most $$$P$$$ different colors of clothes.
  • For each color, at most $$$K$$$ items.

Can you determine the minimum number $$$P$$$ that will allow you to wash all the clothes before the power goes out? If it is impossible, output $$$-1$$$.

Input

The first line contains three integers $$$N$$$, $$$K$$$, $$$H$$$ ($$$1 \le N \le 10^6$$$, $$$1 \le K \le 10^6$$$, $$$1 \le H \le 10^9$$$) — the length of the array, the maximum allowed items per color, the number of hours, respectively.

The second line contains $$$N$$$ integers $$$A_1, A_2, \dots, A_N$$$ ($$$1 \le A_i \le 10^9$$$) — the elements of the array.

Output

Print a single integer, the minimum $$$P$$$ that allows you to wash all clothes within $$$H$$$ hours. If it is impossible, print $$$-1$$$.

Examples
Input
1 2 5
10
Output
1
Input
3 1 5
3 3 3
Output
2
Input
1 1 3
5
Output
-1