I. A Brand New Geometric Problem
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are a magician in a high-dimensional space, and you have an initial $$$n$$$-dimensional hypercube with edge lengths $$$a_1, a_2, \dots, a_n$$$. For a $$$d$$$-dimensional hypercube, the edge length sum is defined as $$$\sum_{i=1}^d a_i$$$, and its hypervolume is $$$\prod_{i=1}^d a_i$$$.

You want to obtain a hypercube with edge length sum $$$S$$$ and hypervolume $$$M$$$. To achieve this, you can perform both dimensional reduction and dimensional expansion operations on the current hypercube.

  • Dimensional Reduction: Remove a dimension.
  • Dimensional Expansion: Add a new dimension, with its edge length being any positive integer.

Both operations are very exhausting, so you want to determine the minimum number of operations required to obtain a hypercube with edge length sum $$$S$$$ and hypervolume $$$M$$$.

Input

The first line contains three integers $$$n, S, M$$$ ($$$1\le n \le 10^5$$$, $$$1 \le S, M \le 10^{10}$$$).

The second line contains $$$n$$$ integers, representing the initial edge lengths $$$a_i$$$ of the hypercube ($$$1 \le a_i \le 10^{10}$$$).

Output

Output a single integer representing the minimum number of operations required. If it is impossible to obtain a hypercube that meets the conditions, output $$$-1$$$.

Examples
Input
2 5 6
1 2
Output
2
Input
3 6 5
1 2 3
Output
3
Input
2 114514 735134400
114 514
Output
20
Input
2 4 7
1 3
Output
-1
Note

For the first sample, one possible approach: first delete the dimension with edge length $$$1$$$, and then add a dimension with edge length $$$3$$$.