Schedule#10677
Not all jokes land, but every solution submitted during today's competition will be evaluated after the event, rather than during it as is typically done.
Suppose you have submitted solutions, each labeled with a unique integer from to . The system processes these solutions in groups. Solutions with consecutive numbers can be grouped into one or more sets, and the system checks these groups in order, starting with the first. The evaluation begins at time . The system first checks all solutions in the first group, and the authors receive the results for this group simultaneously and instantly. If there is a subsequent group, it is checked next, and the results are revealed for that group in the same manner. This process continues until all solutions are checked and results are disclosed.
Each solution takes T_i seconds to check, and the author's anxiety level for the result is C_i. Before checking each group, the system requires seconds for configuration. All values T_i, C_i, and are integers.
For example, if solutions numbered i, i + 1, \ldots, i + j are checked as a group starting at seconds, then the results for this group become available at Z + K + (T_i + T_{i + 1} + \ldots + T_{i + j}) seconds. It is important to note that authors receive the results simultaneously and instantly.
If the result for the -th solution is known at second P_i, the author's anxiety increases by C_i \times P_i. Your goal is to minimize the total anxiety across all participants.
The first line contains (1 \leq t \leq 100) — the number of test cases. For each test case, two numbers are given: (1 \leq N \leq 2\times 10^{5}), (\sum N \leq 2\times 10^{5}) and (0 \leq K \leq 50) — representing the number of solutions and the configuration time for the system. After this, there are lines, each containing two integers T_i (1 \leq T_i \leq 100) and C_i (1 \leq C_i \leq 100) — the time in seconds to check the -th solution and the author's anxiety level for this solution.
For each test case, output the minimum possible total anxiety level. Print each answer on a new line.
Example 1
Consider an example with t=1 test case. In this test, there are N=5 solutions and K=1 second is required for configuration. The values are (T_1, T_2, T_3, T_4, T_5) = (1, 3, 4, 2, 1) and (C_1, C_2, C_3, C_4, C_5) = (3, 2, 3, 3, 4). Suppose we divide the solutions into groups as follows: \{1, 2\}, \{3\}, \{4, 5\}.
In this arrangement, the results are known at times (P_1, P_2, P_3, P_4, P_5) = (5, 5, 10, 14, 14). The anxiety for each author is (15, 10, 30, 42, 56). The total anxiety is 15 + 10 + 30 + 42 + 56 = 153. In this example, it is not possible to achieve a lower total anxiety.
This problem includes the following subtasks:
