There are $n$ soldiers standing in a row. Initially, the health of the $i$-th soldier is $a_i$.

You can perform several (or zero) attacks. In each attack, you can choose an interval $[l, r]$ ($1 \le l \le r \le n$) and reduce the health of all soldiers in this interval by 1. Each attack costs $m$.

After all attacks are completed, if the health of the $i$-th soldier is no more than 0, you gain a profit of $b_i$. Since the soldiers include both friends and enemies, $b_i$ can be negative. Note that the profit for each soldier is obtained at most once.

You need to find an attack strategy that maximizes the total profit minus the total cost. Formally, suppose you perform $k$ attacks in your strategy, the final health of the $i$-th soldier is $c_i$, and $p_i = 1$ if $c_i \le 0$ and $p_i = 0$ otherwise. You need to maximize $\sum_{i=1}^n p_i \times b_i - m \times k$. Finally, you need to output the maximum value of the total profit minus the total cost.

Input

The first line contains a positive integer $T$, representing the number of test cases.

The following lines contain the test cases. For each test case:

The first line contains two integers $n$ and $m$, representing the number of soldiers and the cost of a single attack, respectively.

The next $n$ lines each contain two integers $a_i$ and $b_i$, describing the health and profit of each soldier.

Output

For each test case, output a single integer representing the maximum value of the total profit minus the total cost among all possible strategies.

Examples

Input 1

3
5 1
1 3
2 5
1 4
3 3
5 1
3 2
1 5
1 -100
1 5
3 2
1 5
1 -1
1 5

Output 1

12
6
7

Note

In the first test case, an optimal strategy is to attack three times, choosing intervals $[1, 5], [2, 4], [4, 4]$ respectively. The final health sequence is $(0, 0, -1, 0, 4)$, the profit is $b_1 + b_2 + b_3 + b_4 = 15$, and the cost is $3 \times 1 = 3$. It can be proven that no strategy is better than this one, so output $15 - 3 = 12$.

In the second test case, an optimal strategy is to attack twice, choosing intervals $[1, 1]$ and $[3, 3]$.

In the third test case, an optimal strategy is to attack once, choosing interval $[1, 3]$.

Constraints

Let $\sum n$ denote the sum of $n$ over all test cases. For all test cases, it is guaranteed that:

• $1 \le T \le 5 \times 10^5$;
• $1 \le n, \sum n \le 5 \times 10^5$, $1 \le m \le 10^9$;
• For any $1 \le i \le n$, $1 \le a_i \le 10^9$, $-10^9 \le b_i \le 10^9$.

Special Property A: For any $1 \le i \le n$, $b_i \ge 0$.

Special Property B: For any $1 \le i \le n$, $a_i \le 5,000$.