Problem Description

What a tragedy... Liuctic's iPhone is out of battery when he was in the subway. So he comes up with a problem to make a happier trip. There is a subway station. A piece of record, namely a pair of integers (t, N), would mean that N passengers entered the subway station at the t-th second. There are X trains, each of which has a maximum capacity of 2000 people. And for safety reasons, the time interval between any two trains' arrival at the station would not be lesser than 60 seconds.
Give M pieces of record and X (the number of trains), your task is to calculate the minimum waiting time in sum for all passengers.

Input

The integer in the first line indicates the number of test cases. For each test case, the first line will contain two integers M (0<M<=300) and X (0<X<=300). Then there comes M lines of records. The i-th records will contain two integers t(i) and N(i). And you can assume 0<=t(1)<t(2)<...<t(M).

Output

For each test case, print the minimum waiting time in sum, or "INF" if it is impossible to pick up all the passengers, in a single line.
To make the problem more concise, we assume that passengers will line up in the order of arrival to get on the train. And for every piece of entering record (t, N), the N passengers will either get on the train or wait together. The train is always empty when entering the station. You may not use all of the trains, But only the last train to be used can arrive later than t(M).

2
3 2
0 1998
15 2
40 5
3 2
0 1998
20 3
100 1999

190
INF

Hint

Case 1: The first train arrives at 0-th second. The second arrive at 60-th second. The waiting time in sum would be 2*(60-15) + 5*(60-40) = 190
Case 2: According to the restrictions, the two trains cannot manage to pick all the passengers away. So the output is "INF".