检修计划

【题目描述】

小灰灰的机器人需要按顺序完成 $n$ 项检修，初始能量为 $E$．

开始第 $i$ 项检修前，机器人的能量必须至少为 $h_i$．这项检修有两种方案：选择方案 A 后，能量增加 $a_i$；选择方案 B 后，能量增加 $b_i$．增加量可以为负，负数表示消耗能量．

每项检修必须选择且只能选择一种方案，不能跳过或调整顺序．完成每项检修后，能量都不能为负，可以恰好为 $0$．机器人的能量没有容量上限．

一个方案用长度为 $n$ 的字符串表示，第 $i$ 个字符表示第 $i$ 项检修选择的方案．请找到能完成全部检修的方案中字典序最小的一个；如果不存在这样的方案，输出 -1．

这里规定 A 小于 B．比较两个不同方案时，从左向右找到第一个不同的字符，该位置为 A 的方案字典序更小．

【输入描述】

第一行输入两个整数 $n,E$．

接下来 $n$ 行，第 $i$ 行输入三个整数 $h_i,a_i,b_i$，分别表示第 $i$ 项检修的最低启动能量，以及选择两种方案后的能量增加量．

【输出描述】

输出一行，为字典序最小的可行方案；如果无解，输出 -1．

【样例 1】

【样例 1 输入】

3 3
0 -2 2
5 -1 0
0 -4 -3

【样例 1 输出】

BAA

【样例 1 解释】

第一项若选择 A，能量会变为 $1$，不足以启动第二项．选择 B 后，能量变为 $5$．

接下来依次选择 A、A，能量分别变为 $4$、$0$，能够完成全部检修．因此答案为 BAA．

【样例 2】

【样例 2 输入】

2 1
0 0 1
3 0 0

【样例 2 输出】

-1

【样例 2 解释】

完成第一项后，能量最多为 $2$，无法达到第二项要求的 $3$．

【数据规模与约定】

对于所有数据，$1\le n\le2\times10^5$，$0\le E,h_i\le10^9$，$-10^9\le a_i,b_i\le10^9$．

本题采用捆绑测试．只有通过一个子任务的全部测试点，才能获得该子任务的分数．

子任务编号	分数	附加限制
1	15	$n\le18$
2	20	$n\le2000$
3	10	对所有 $i$，$a_i\ge b_i$
4	20	对所有 $i$，$h_i=0$，$a_i\le0$，$b_i\le0$
5	35	无

【下发样例】

• Data/sample1.in 与 Data/sample1.ans：样例 1．
• Data/sample2.in 与 Data/sample2.ans：样例 2．
• Data/sample3.in 与 Data/sample3.ans：满足子任务 1 的限制．
• Data/sample4.in 与 Data/sample4.ans：满足子任务 2 的限制．
• Data/sample5.in 与 Data/sample5.ans：满足子任务 3 的限制．
• Data/sample6.in 与 Data/sample6.ans：满足子任务 4 的限制．
• Data/sample7.in 与 Data/sample7.ans：该样例无特殊限制．
• Data/sample8.in 与 Data/sample8.ans：该样例无特殊限制．

点击下载本题选手目录