题目描述

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

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

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

输入格式

输入包含 $q + 2$ 行。

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

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

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

输出格式

输出 $q$ 行。

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

样例输入1

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

样例输出1

2
0
2

样例输入2

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

样例输出2

2
0
0

备注

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