The Army of Computing Men (ACM) is one the strongest armies in the world. They are well-equipped and have trained and armed programmers They fight to spread creativity teamwork and innovation among peo- ple. The last victory of the ACM against knowledge mo- nopolies brought them wealthy spoils. The supply arms have located position of N crates along a straight line in the jungle. Some trucks are to carry the crates to the army base. Since the jungle is so dense, it is costly for a truck to cut through and bring the crates back. There- fore commanders have decided to group the crates to- gether in points and use the minimum number of trucks. For each such gathering point we should use a truck. Each truck has a maximum capacity of K crates and has required fuel to bring only one shipment. The army men wany to obey their commanders with minimum effort. Each crate has a weight. The effort needed to handle a crate along the line can be formulized by the weight of the crate multiplied by the distance it is carried. It is important not to change the order of crates while there are carried. You are appointed to manage the shipping procedures. Higher ranked commanders asked you for a report o minimum needed resources. You should first consider minimizing the number of trucks and then the army effort. Write your report as soon as possible. Input In the first line there will be T (T ≤ 50), number of tests. Each test begins with an integer N and K (1 ≤ N ≤ 105, 1 ≤ K ≤ 100). It is followed by N pairs of integers pi and wi (1 ≤ pi,wi ≤ 106), position and the weight of i-th crate. Crates appear in the input in increasing order of their position. No two crates occupy the same position in the beginning. Output For each test print the minimum number of trucks and the minimum effort needed to collect all crates in a single line separated by a single space. Hint: In the first sample test, we need at least 3 trucks to carry the crates. the optimal solution is to carry crate number (1), (2, 3), (4, 5) in separate trucks with costs 0, 2 (for carrying crate 2 to the position of crate 3) and 8 (for carrying crate 5 to the position of crate 4) respec vely. Sample Input 2 52 11 42
2/2 5 10 6 10 10 2 55 11 42 5 10 6 10 10 2 Sample Output 3 10 1 26