Byteland 的出租车费用相当昂贵，但好在出租车空间宽敞，因此拼车非常流行。共有 $n$ 家出租车公司，每家公司由三个参数决定： 每辆出租车的最大载客量 $c_i$； 行程首公里的价格 $s_i$； * 行程后续每公里的价格 $p_i$。

每家公司可以提供任意数量的出租车，但同一公司的所有出租车都是相同的。

Johnny 注意到了这个市场商机，决定成为一名出租车预订中介。他需要处理如下形式的请求：“为 $m$ 名乘客预订出租车，行程距离为 $d$ 公里”，并需要找到满足该请求的最便宜的出租车组合，前提是乘客在行程中不愿意更换出租车。他的想法大获成功，业务迅速变得非常受欢迎，现在他有太多的请求无法手动处理。你被雇佣来帮助自动化这一过程。

输入格式

输入的第一行包含两个整数 $n$ ($1 \le n \le 10^5$) 和 $q$ ($1 \le q \le 10^5$)，用空格分隔，分别表示出租车公司的数量和需要处理的请求数量。

接下来的 $n$ 行，每行包含三个用空格分隔的整数。第 $i$ 行的整数分别为 $c_i, s_i, p_i$ ($1 \le c_i \le 15, 0 \le s_i, p_i \le 10^6$)，分别表示单辆出租车的载客量、首公里价格和后续每公里价格。

接下来的 $q$ 行，每行包含两个用空格分隔的整数。第 $i$ 行的整数分别为 $m_i$ 和 $d_i$ ($1 \le m_i \le 10^6, 1 \le d_i \le 10^6$)，分别表示第 $i$ 个请求中的乘客人数和行程距离。

输出格式

输出应包含恰好 $q$ 行，每行对应一个请求。

每行输出一个整数，表示满足该请求的最小可能费用，顺序与输入中的请求顺序一致。

样例

输入 1

3 3
4 8 4
4 15 2
3 6 3
1 12
11 3
7 20

输出 1

37
44
106

说明

对于第一个请求（1 名乘客，12 公里），最便宜的方式是预订第二家公司的一辆出租车，价格为 $15 + 11 \cdot 2 = 37$。

对于第二个请求（11 名乘客，3 公里），最便宜的方式是预订第一家公司的两辆出租车（载 8 名乘客），以及第三家公司的一辆出租车（载剩余的 3 名乘客），总价格为 $2 \cdot (8 + 2 \cdot 4) + (6 + 2 \cdot 3) = 44$。

对于第三个请求（7 名乘客，20 公里），最便宜的方式是预订第二家公司的两辆出租车，价格为 $2 \cdot (15 + 2 \cdot 19) = 106$。