ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

6659: Money Buys Happiness

内存限制：256 MB 时间限制：2 S
题面：传统 评测方式：文本比较 上传者：
提交：2 通过：2
提交提交记录统计Web Board

题目描述

# Money Buys Happiness
## 题面翻译

你是一个物理学家。一开始你没有钱，每个月的末尾你会得到 $x$ 英镑。在第 $i$ 个月里，你可以付出 $c_i$ 英镑，获取 $h_i$ 的幸福。

在任何时刻你都不能欠钱，问你在 $m$ 个月过后最多能获得多少幸福。

保证 $\sum h_i \leq 10^5$。

## 题目描述

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.

## 输入格式

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 $ .

## 输出格式

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

## 样例 #1

### 样例输入 #1

```
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
```

### 样例输出 #1

```
0
10
200
15
1
9
9
```

## 提示

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.

输入格式

第一行输入包含一个整数$ t $ ( $ 1 \le t \le 1000 $ )  — 测试用例的数量。
每个测试用例的第一行包含两个整数，$ m $ and $ x $ ( $ 1 \le m \le 50 $ , $ 1 \le x \le 10^8 $ ) --总月数和月薪。
以下m行中的第i行包含两个整数，$ c_i $ and $ h_i $ ( $ 0 \le c_i \le 10^8 $ , $ 1 \le h_i \le 10^3 $ ) --第个月的成本和幸福感。请注意，有些幸福可能是免费的。


The first line of each test case contains two integers, — 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 $ .

输入样例 复制 

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

输出样例 复制 

0
10
200
15
1
9
9

分类标签