该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有 n+1 个杯子，编号 0..n。杯子 1..n 的容积与当前果汁体积固定：第 i 个杯子的容积为 a_i，其中装有 b_i 的果汁；杯子 0 的容积可视为无限（本题设为 1e9），其初始果汁体积由询问给出。

定义操作 i 为：将杯子 i-1 中的全部果汁倒入杯子 i。若杯子 i 的果汁体积超过其容积 a_i，则溢出到恰好等于 a_i。

给出 q 次询问。每次询问给出 v, p，表示杯子 0 初始装有 v 的果汁，依次执行操作 1,2,...,p 后，问杯子 p 内的果汁体积为多少。不同询问相互独立。

输入格式

• 第一行：两个整数 n, q。
• 接下来 n 行：每行两个整数 a_i, b_i。
• 接下来 q 行：每行两个整数 v, p。

输出格式

输出 q 行，每行一个整数，为对应询问的答案。

数据范围

• 1 ≤ n ≤ 2e5，0 ≤ q ≤ 2e5；
• 0 ≤ b_i ≤ a_i ≤ 1e9；
• 0 ≤ v ≤ 1e9，1 ≤ p ≤ n。

输入输出样例 #1

输入 #1

3 3
4 0
9 8
13 8
5 1
0 2
3 3

输出 #1

4
8
13

输入输出样例 #2

输入 #2

5 3
3 1
6 2
9 3
7 2
8 0
4 3
0 4
1 5

输出 #2

8
7
7