Schedule

Not all jokes land, but every solution submitted during today's competition will be evaluated after the event, not during it as is typically done.

Imagine you have submitted $N$ solutions, each labeled with a unique integer from $1$ to $N$. The system processes these solutions in groups. Solutions with consecutive numbers can be grouped in one or more sets, and the system checks these groups in order, starting with the first. The evaluation begins at time $0$. The system first checks all solutions in the initial 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 in the same manner. This process continues until all solutions are checked and results are disclosed.

Each solution $i$ takes $T_i$ seconds to check, and the author's anticipation level for the result is $C_i$. Before checking each group, the system requires $K$ seconds for configuration. All values $T_i$, $C_i$, and $K$ are integers.

For instance, if solutions numbered $i,i+1,\dots ,i+j$ are checked as a group starting at $Z$ seconds, the results for this group will be available at $Z+K+(T_i+T_{i+1}+\dots +T_{i+j})$ seconds. It's important to note that authors receive the results simultaneously and instantly.

If the result for the $i$-th solution is known at the $P_i$-th second, the author's anxiety level increases by $C_i\ast P_i$. The goal is to minimize the total anxiety level for all participants.

Input Data

The first line contains $t$ ($1\le t\le 100$) – the number of test cases. For each test case, two numbers are provided: $N$ ($1\le N\le 2\ast 10^5$), ($\sum N\le 2\ast 10^5$) and $K$ ($0\le K\le 50$) – representing the number of solutions and the configuration time for the system. Following this, $N$ lines are given, each containing two integers $T_i$ ($1\le T_i\le 100$) and $C_i$ ($1\le C_i\le 100$) – the time in seconds to check the $i$-th solution and the author's anticipation level for this solution.

Output Data

For each test case, output the minimum total level of anxiety. Each result should be printed on a new line.

Subtasks

This task includes the following $8$ subtasks:

Example Analysis

Consider an example with $t=1$ test case. In this test, there are $N=5$ solutions, and $K=1$ second is required for system configuration. The values are given as $(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 $3$ groups as follows: $1,2,3,4,5$

In this scenario, the results are known at $(P_1,P_2,P_3,P_4,P_5)=(5,5,10,14,14)$ seconds, and the anxiety levels for each author become $(15,10,30,42,56)$. The total anxiety level is $15+10+30+42+56=153$. In this example, it is not possible to achieve a total anxiety level lower than $153$.

Examples