B. A Boring Game
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

GuapiStarOier hates junk advertisements.

One day GuapiStarOier sees a junk advertisement about a boring game. However, he comes up with a simple idea.

The game has a tower with $$$n$$$ floors and each floor with an enemy. The strength of the enemy in $$$i$$$-th floor is $$$a_i$$$ and the experience the player can get is $$$b_i$$$, and the player's goal is to defeat all enemies. If the player is on the $$$y$$$-th floor, he can move to $$$(y+1)$$$-th or $$$(y-1)$$$-th floor (if it exists).

Every time he moves to a new floor that he never visited before, he will fight against the enemy on this floor. Assume the strength of the player is $$$x$$$, the strength of the enemy is $$$y$$$ and the experience is $$$z$$$, if $$$x \geq y$$$, the player defeats the enemy and his strength becomes $$$x+z$$$, otherwise the player loses the game.

There are $$$q$$$ rounds, and in each round the player will initially be on a certain floor $$$p$$$ with strength $$$v$$$ (also he has to fight against the enemy on that floor initially). GuapiStarOier wonders about the maximal strength he can get during the game in each round. Since this problem is too easy for him, GuapiStarOier gives it to you and asks you to solve it.

Input

The first line contains a single integer $$$T$$$ ($$$1\le T\le 100$$$), denoting the number of test cases.

For each test case, the first line contains two integers $$$n,q$$$ ($$$1\le n\le 10^5$$$, $$$1\le q\le 10^5$$$), indicating the number of floors and the number of queries.

Each of the following $$$n$$$ lines contains two integers $$$a_i,b_i$$$ ($$$0\le a_i,b_i\le 10^{12}$$$), denoting the strength of the enemy and the experience the play can get.

Each of the following $$$q$$$ lines contains two integers $$$p,v$$$ ($$$1\le p\le n,0\le v\le 10^{12}$$$), denoting the query in which the player is on the floor $$$p$$$ with strength $$$v$$$.

It is guaranteed that the sum of $$$n$$$ and $$$q$$$ over all test cases won't exceed $$$10^6$$$.

Output

For each query, output an integer denoting the maximal strength the player can get.

Example
Input
2
6 5
3 6
1 2
9 10
2 2
7 1
4 2
2 1
3 1
3 9
4 5
6 4
6 5
3 6
1 2
13 10
2 2
7 1
4 3
2 1
3 1
3 9
4 5
6 4
Output
24
1
32
28
6
9
1
9
11
10