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

You can perform several (possibly 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 $i$-th soldier's health 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 gained 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, and the final health of the $i$-th soldier is $c_i$. Let $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$. You are required 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.

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$, representing the initial 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 that can be obtained among all possible strategies.

Examples

Input 1

3
5 1
3 13
4 25
5 14
6 33
7 51
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]$, and $[4, 4]$. 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 the output is $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]$.

Subtasks

Let $\sum n$ denote the sum of $n$ over all test cases in a single test point. For all test data, 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$ * $\forall 1 \le i \le n, 1 \le a_i \le 10^9, -10^9 \le b_i \le 10^9$