In some online games, property of character is important. One of the famous way to increase your money is commerce. More precisely, we can buy something in lower price and then sell it by higher price. Because of the difference between two prices, player can make money easily.
In Amusement Commerce Game, player can buy some items from a commerce port and sell it in a big city. There are many items that is sold by supplier and the amount of each item is limited. Moreover, player can put at most M items on character. Give the profit of each item, what is the maximum profit can achieve in a single journey from port to city?
There is an integer T representing the number of test cases, which is followed by T test cases. Each test case begins with two integers N, M, and then the next N lines are N items' information. Each line has two numbers, n_i and p_i, representing the amount and the price per quantity for i_th item. You can assume that there are at most 1,000 cases and at most 10,000 items for each case. Also n_i and p_i are both non-negative integers.
For each test case, output the maximum profit can be made. The maximum profit would not exceed 2,147,483,647.