#P18204. A Brand New Geometric Problem

A Brand New Geometric Problem

A Brand New Geometric Problem

你是一位高维空间中的魔术师,初始有一个 nn 维长方体,各维的边长依次为 a1,a2,…,ana_1,a_2,\ldots,a_n。

对于一个 dd 维长方体,定义其边长之和为 ∑i=1dai\sum_{i=1}^{d}a_i,超体积为 ∏i=1dai\prod_{i=1}^{d}a_i。

你希望得到一个边长之和为 SS、超体积为 MM 的长方体。为此,可以对当前长方体进行以下两种操作:

  • 降维:删除一个维度。
  • 升维:新增一个维度,其边长可以是任意正整数。

两种操作每次都很费力。求达到目标所需的最少操作次数;如果无法达到目标,输出 −1-1。

输入格式

第一行包含三个整数 n,S,Mn,S,M。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,表示初始各维的边长。

输出格式

输出一个整数,表示最少操作次数;如果无法达到目标,输出 −1-1。

数据范围

  • 1≤n≤1051\le n\le 10^5;
  • 1≤S,M≤10101\le S,M\le10^{10};
  • 1≤ai≤10101\le a_i\le10^{10}。

输入只有一组数据。

样例一

输入:

2 5 6
1 2

输出:

2

解释:一种方案是先删除边长为 11 的维度,再新增边长为 33 的维度。

样例二

输入:

3 6 5
1 2 3

输出:

3

样例三

输入:

2 114514 735134400
114 514

输出:

20

样例四

输入:

2 4 7
1 3

输出:

-1