311361: CF1974E. Money Buys Happiness

E. Money Buys Happinesstime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Being a physicist, Charlie likes to plan his life in simple and precise terms.

For the next $m$ months, starting with no money, Charlie will work hard and earn $x$ pounds per month. For the $i$-th month $(1 \le i \le m)$, there'll be a single opportunity of paying cost $c_i$ pounds to obtain happiness $h_i$.

Borrowing is not allowed. Money earned in the $i$-th month can only be spent in a later $j$-th month ($j>i$).

Since physicists don't code, help Charlie find the maximum obtainable sum of happiness.

Input

The first line of input contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first line of each test case contains two integers, $m$ and $x$ ($1 \le m \le 50$, $1 \le x \le 10^8$) — the total number of months and the monthly salary.

The $i$-th of the following $m$ lines contains two integers, $c_i$ and $h_i$ ($0 \le c_i \le 10^8$, $1 \le h_i \le 10^3$) — the cost and happiness on offer for the $i$-th month. Note that some happiness may be free ($c_i=0$ for some $i$'s).

It is guaranteed that the sum of $\sum_i h_i$ over all test cases does not exceed $10^5$.

Output

For each test case, print a single integer, the maximum sum of happiness Charlie could obtain.

ExampleInput

7
1 10
1 5
2 80
0 10
200 100
3 100
70 100
100 200
150 150
5 8
3 1
5 3
3 4
1 5
5 3
2 5
1 5
2 1
5 3
2 5
2 4
4 1
5 1
3 4
5 2
2 1
1 2
3 5
3 2
3 2

Output

0
10
200
15
1
9
9

Note

In the first test case, Charlie only gets paid at the end of the month, so is unable to afford anything.

In the second test case, Charlie obtains the free happiness in the first month.

In the third test case, it's optimal for Charlie to buy happiness in the second month. Even with money left at the end, Charlie could not go back in time to obtain the happiness on offer in the first month.

题目大意：
这个题目是关于查理如何通过工作赚钱来购买幸福的故事。查理将在接下来的m个月里，从没有钱开始，每个月赚取x英镑。对于第i个月（1≤i≤m），有一次机会支付ci英镑来获得hi的幸福。不允许借款，第i个月赚的钱只能用于之后的第j个月（j>i）。由于物理学家不编程，需要帮助查理找到可以获得的最大幸福总和。

输入数据格式：
输入的第一行包含一个整数t（1≤t≤1000）——测试用例的数量。
每个测试用例的第一行包含两个整数，m和x（1≤m≤50，1≤x≤10^8）——总月数和每月薪水。
接下来的m行中的第i行包含两个整数，ci和hi（0≤ci≤10^8，1≤hi≤10^3）——第i个月的成本和提供的幸福。注意，某些幸福可能是免费的（ci=0对于某些i）。保证所有测试用例的∑hi之和不超过10^5。

输出数据格式：
对于每个测试用例，打印一个整数，即查理可以获得的最大幸福总和。

公式（LaTeX格式）：
对于每个月i，查理的幸福感hi和成本ci的关系可以表示为：
\[ h_i = \text{幸福值} \]
\[ c_i = \text{成本值} \]
查理的目标是最大化总幸福值，即最大化：
\[ \sum_{i=1}^{m} h_i \]
在满足以下条件的情况下：
\[ \sum_{i=1}^{j-1} x - \sum_{i=1}^{j-1} c_i \geq c_j \]
对于所有j（j>i）。题目大意： 这个题目是关于查理如何通过工作赚钱来购买幸福的故事。查理将在接下来的m个月里，从没有钱开始，每个月赚取x英镑。对于第i个月（1≤i≤m），有一次机会支付ci英镑来获得hi的幸福。不允许借款，第i个月赚的钱只能用于之后的第j个月（j>i）。由于物理学家不编程，需要帮助查理找到可以获得的最大幸福总和。 输入数据格式： 输入的第一行包含一个整数t（1≤t≤1000）——测试用例的数量。 每个测试用例的第一行包含两个整数，m和x（1≤m≤50，1≤x≤10^8）——总月数和每月薪水。 接下来的m行中的第i行包含两个整数，ci和hi（0≤ci≤10^8，1≤hi≤10^3）——第i个月的成本和提供的幸福。注意，某些幸福可能是免费的（ci=0对于某些i）。保证所有测试用例的∑hi之和不超过10^5。 输出数据格式： 对于每个测试用例，打印一个整数，即查理可以获得的最大幸福总和。 公式（LaTeX格式）： 对于每个月i，查理的幸福感hi和成本ci的关系可以表示为： \[ h_i = \text{幸福值} \] \[ c_i = \text{成本值} \] 查理的目标是最大化总幸福值，即最大化： \[ \sum_{i=1}^{m} h_i \] 在满足以下条件的情况下： \[ \sum_{i=1}^{j-1} x - \sum_{i=1}^{j-1} c_i \geq c_j \] 对于所有j（j>i）。