题目背景

大数学家高斯小时候偶然间发现一种有趣的自然数集合 $\verb|Ba|$，对于以 $a$ 为基的集合 $\verb|Ba|$ 定义如下：

1. $a$ 是集合 $\verb|Ba|$ 的基，且 $a$ 是 $\verb|Ba|$ 的第一个元素；
2. 如果 $x$ 在集合 $\verb|Ba|$ 中，则 $2x+1$ 和 $3x+1$ 也都在集合 $\verb|Ba|$ 中；
3. 没有其他元素在集合 $\verb|Ba|$ 中了。

这里对 Blah 数集扩充到超 Blah 数集 $\verb|SBa|$ 如下：

有若干一次函数 $F_i(x) = k_ix+b_i$（$k_i>0，b_i \geq 0$）,对于以 $a$ 为基的集合 $\verb|SBa|$ 定义如下：

1. $a$ 是集合 $\verb|SBa|$ 的基，且 $a$ 是 $\verb|SBa|$ 的第一个元素；
2. 如果 $x$ 在集合 $\verb|SBa|$ 中，则 $F_i(x)$ 也都在集合 $\verb|SBa|$ 中；
3. 没有其他元素在集合 $\verb|SBa|$ 中了。

题目描述

提供基 $a$ 和 $n$，将集合 $\verb|SBa|$ 中元素按照升序排列，第 $n$ 个元素会是多少？

需要特别注意的是，集合中没有重复的元素。

输入格式

第一行是两个正整数 $p,q$，$p$ 是一次函数的数量；

接下来有 $p$ 行，每行两个整数 $k_i,b_i$，对应一个一次函数；

再接下来有 $q$ 行，每行是两个用一个空格隔开的正整数 $a,n$，分别表示集合的基 $a$ 和所求元素序号 $n$。

输出格式

有 $q$ 行，每行对应输入要求解的集合 $\verb|SBa|$ 的第 $n$ 个元素值。

输入输出样例

2 2
2 1
3 1
1 100
28 5437

418
900585

说明/提示

👀️ 对于$100\%$的数据，$1 \leq p,q \leq 100, k_i,b_i,a \leq 50000000,1 \leq n \leq 10000$，集合中的元素的位数不超过 $38$。