题目描述

Hanks 博士有 $N$ 种细胞，第 $i$ 种细胞每秒分裂为 $S_i$ 个同种细胞。他需要选择一种细胞培养，当细胞总数能平均分入 $M = m_1^{m_2}$ 个试管时停止培养并开始实验。要求选择细胞使得实验开始时间最早。

输入格式

第一行一个整数 $N$，表示细胞种类数。
第二行两个整数 $m_1, m_2$，表示 $M = m_1^{m_2}$。
第三行 $N$ 个整数 $S_i$，表示每种细胞的分裂个数。

输出格式

一个整数，表示最早实验时间（秒）。如果无法满足，输出 $-1$。

1
2 1
3

-1

2
24 1
30 12

2

提示

样例 1 说明

细胞个数始终为奇数，无法均分到 $2$ 个试管，输出 $-1$。

样例 2 说明

• 第一种细胞：$3$ 秒后才能均分入 $24$ 个试管
• 第二种细胞：$2$ 秒后即可均分（$12^2 = 144$，$144 / 24 = 6$）
  最早开始时间为 $2$ 秒。

数据规模与约定

对于全部的测试点，保证 $1 \leq N \leq 10 ^ 4$，$1 \leq m_1 \leq 3 \times 10^4$，$1 \leq m_2 \leq 10^4$，$1 \leq S_i \leq 2 \times 10^9$。

本题改编自 NOIP 2009 普及组 T3