学习除法

【题目描述】

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

现在牛牛有很多个除数可以选择，给定一个长度为 𝑛𝑛 的序列 𝑏𝑏。表示除数 𝑖𝑖 的花费是 𝑏𝑏𝑖𝑖，

牛牛可以用这个除数把 𝑥𝑥 变为� 𝑥𝑥

𝑖𝑖 �。每种除数可以使用无限次。

多组询问，每组询问输入两个数 𝑥𝑥, 𝑦𝑦，表示牛牛需要使用若干次除法把 𝑥𝑥 变得不超过 𝑦𝑦，

对于每一组询问你都要输出一个答案表示求最小花费，保证题目一定有解。

大样例：sample.zip

【输入格式】

输入包含 𝑞𝑞 + 2 行。

第一行输入两个正整数 𝑛𝑛, 𝑞𝑞。

第二行输入 𝑛𝑛 个正整数，第 𝑖𝑖 个数表示 𝑏𝑏𝑖𝑖。

接下来 𝑞𝑞 行，每行两个正整数 𝑥𝑥, 𝑦𝑦，如题意所示。

【输出格式】

输出 𝑞𝑞 行。

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

【样例 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