SP12557 CDC12_B - Basic Routines
题目描述
Ronny 刚下班，经历了糟糕的交通状况。他放下车钥匙，决定躺下来思考一下要做的事情。他很快意识到，每项活动所需的能量不同。Ronny 计划了 $N$ 项活动，每项活动都有一个名称和消耗的能量值。此外，每完成一项活动，他会根据已经完成的活动数量恢复能量。例如，Ronny 有 80 点能量，如果活动 X 消耗 Y 点能量，那么他完成后会有 $80 - Y + 1$ 点能量。如果他再做一项消耗 Z 点能量的活动，他的能量会变为 $(80 - Y + 1) - Z + 2$ 点。Ronny 的能量不能低于 0 点。
Ronny 意识到他可能无法完成所有的活动。你的任务是帮他选择一组可以完成的活动，并让他的能量不低于 0 点。详细的要求请参见后续输出格式说明。
输入格式
第一行是一个整数 $T$，表示测试用例的数量。接下来是 $T$ 组测试用例的描述。每组测试用例首先包含两个整数 $N$ 和 $E$，分别表示 Ronny 计划的活动数量和他的初始能量。接下来的 $N$ 行中，每行有一个字符串 $A$ 和一个整数 $V$，分别表示活动的名称和消耗的能量。
数据从标准输入读取。
输出格式
对于每个测试用例，输出两行。第一行格式为 `Scenario #i: `，其中 $i$ 是测试用例编号（从 1 开始）。紧跟其后是 Ronny 能够完成的最大活动数量。第二行是按名称排序的活动列表（实际执行顺序可以不一样），每个名称后面要有空格。
如果有多种可能的解，输出消耗能量最少的活动子集。如果仍然有多个解，则输出字母序最小的活动序列。
输出结果写入标准输出。
说明/提示
- $1 \le T \le 10$
- $1 \le N \le 20$
- $1 \le E \le 1000$
- $1 \le V \le 100$
**示例输入**
```
2
5 80
CleanClothes 45
MakeFood 40
Shower 10
EatFood 20
WatchTv 5
4 80
Gaming 20
TVShow 30
ScoreSomeCoke 20
DrinkCoke 10
```
**示例输出**
```
Scenario #1: 4
EatFood MakeFood Shower WatchTv
Scenario #2: 4
DrinkCoke Gaming ScoreSomeCoke TVShow
```
**本翻译由 AI 自动生成**