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

现在小Z 有很多个除数可以选择，给定一个长度为n的序列b｡表示除数i的花费是 b{i}。

小Z 可以用这个除数把 x 变为 |\frac{x}{i}| ，下取整｡每种除数可以使用无限次｡ 

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

输入包含 q+2 行。输入包含q+2行。

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

第二行输入 n 个正整数,第 i 个数表示 b_{i} 。

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

输出 q 行。

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

- 对于所有的测试点, 1 ≤b_{i} ≤10^{9}。

- 对于测试点1 ∼2: 1 ≤n,q,x, y ≤10^{2}。

- 对于测试点3 ∼4: 1 ≤n,q,x,y ≤10^{3}。

- 对于测试点5 ∼10:1≤1,g,x,y ≤10^{5}。