题目描述

你是一个高维空间魔术师，手上有一个最初维度为 $n$ 维的超立方体，给定每一维的边长为 $a_1, a_2, \dots, a_n$。对于一个 $d$ 维的超立方体，定义其各维度边长和为 $\sum_{i=1}^d a_i$，超体积为 $\prod_{i=1}^d a_i$。

你想得到一个各维度边长和为 $S$，超体积为 $M$ 的超立方体，于是决定将手上现有的超立方体进行降维操作和升维操作。

• 降维操作：删去一个维度。
• 升维操作：加入一个维度，该维度边长可以是任意的正整数。

无论升维还是降维操作都非常消耗精力，因此你想知道最少需要通过多少次操作，才能得到一个各维度边长和为 $S$，超体积为 $M$ 的超立方体。

输入格式

第一行三个整数 $n, S, M$ ($1\le n \le 10^5$, $1 \le S, M \le 10^{10}$)。

第二行 $n$ 个整数，表示初始超立方体的每个维度的边长 $a_i$ ($1 \le a_i \le 10^{10}$)。

输出格式

输出一个整数，表示最小操作次数。如果无法得到满足条件的立方体，输出 $-1$。

2 5 6
1 2

2

3 6 5
1 2 3

3

2 114514 735134400
114 514

20

2 4 7
1 3

-1

提示

对于第一个样例，一种可行的方法是：先删去边长为 $1$ 的维度，然后加入一个边长为 $3$ 的维度。