题目描述

牛牛上二年级了，今天学习了除法，他想要通过若干次除法将一个数字 $x$ 变得不超过 $y$。

现在牛牛有很多个除数可以选择，给定一个长度为 $n$ 的序列 $b$。表示除数 $i$ 的花费是 $b_i$，牛牛可以用这个除数把 $x$ 变为 $\lfloor \frac{x}{i} \rfloor$。每种除数可以使用无限次。

多组询问，每组询问输入两个数 $x, y$，表示牛牛需要使用若干次除法把 $x$ 变得不超过 $y$，对于每一组询问你都要输出一个答案表示求最小花费，保证题目一定有解。

输入文件 division.in

输入包含 $q+2$ 行。

第一行输入两个正整数 $n, q$。

第二行输入 $n$ 个正整数，第 $i$ 个数表示 $b_i$。

接下来 $q$ 行，每行两个正整数 $x, y$，如题意所示。

输出文件 division.out

输出 $q$ 行。

每行输出一个数，表示对应询问的答案。

5 3
4 3 2 2 4
4 3
1 4
5 1

2
0
2

5 3
1 4 3 5 2
2 1
4 5
1 4

2
0
0

提示

样例 3 见附加文件。

• 对于所有的测试点，$1≤ b_i ≤10^9$。
• 对于测试点 $1 \sim 2$：$1 ≤ n, q, x, y ≤ 100$。
• 对于测试点 $3 \sim 4$：$1≤n, q, x, y ≤ 1000$。
• 对于测试点 $5 \sim 10$：$1≤n, q, x, y ≤ 10^5$。