暂无测试数据。

DD 现在要去购物，她手上有着 $n$ 种不同的硬币，每种硬币都有着无数个，其中第 $i$ 种的面额是 $money_i$，她现在要去 $m$ 家超市，第 $j$ 家超市她需要买价值为 $c_j$ 的东西，而第 $j$ 家超市同时有着限制只能使用前 $l_j$ 种硬币，DD 现在想要知道她在每家超市最少需要多少枚硬币来购买商品并且不需要找零。

输入格式

第一行两个整数分别表示 $n, m$。

第二行 $n$ 个整数分别表示每种硬币的面额 $money_i$。

接下来 $m$ 行表示 $c_j,l_j$。

输出格式

共 $m$ 行，如果能够购买则输出最少需要的硬币数量，否则输出 $-1$。

数据范围

对于 $30\%$ 的数据, $1 \leq n \leq 20$

对于 $60\%$ 的数据, $1 \leq n \leq 500$

对于 $100\%$ 的数据, $1 \leq l_j \leq n \leq 2000, 1 \leq m \leq 10^5, 1 \leq money_i,c_j \leq 10^4$

6 3
7 10 15 2 3 24
107 3
12 4
24 2

8
2
3