How Much?

This financial crisis! Even MI6’s technology department does not escape the consequences. With all those constraints on the budget, how can R be expected to supply our spies with cars equipped with all the technological gadgets and weaponry they need to save the world? As if it is not hard enough to put all those tracking systems, oil sprayers, guns, bullets and missiles in one car, now R has to worry about the costs as well.

The management insists, though: before R is allowed to order a car and all the parts he needs, he will first need to determine the exact amount of money that he needs. Management will then decide whether he gets to realize his vision or not.

This sort of bureaucratic nonsense is not something that R wants to waste any time on. He therefore wants you to help him. Given the price of the car, a listing of the parts R wants to install, and the price per piece of each part, work out what the total cost is of the project.

Input

On the first line one positive number: the number of test cases, at most 100. After that per test case:

• one line with an integer s (1 ≤ s ≤ 100000): the stock price of the car.

• one line with an integer n (0 ≤ n ≤ 1000): the number of different parts to be installed.

• n lines with two space-separated integers q[i] and p[i] (1 ≤ q[i] ≤ 100 and 1 ≤ p[i] ≤ 10000): for each different part i, the number of pieces q[i] required of such part, and the price p[i] for a single piece.

Output

For each test case print one line with an integer: the total amount of money needed to buy the car and all the parts.

Examples