33OJ
登录 注册

#P17544. [JAG 2026 Summer Camp #2] Two Greedy Customers

[JAG 2026 Summer Camp #2] Two Greedy Customers

题目描述

一家商店出售 NN 种商品,编号为 11 到 NN。第 ii 种商品的价格为 CiC_i。

两位顾客 Alice 和 Bob 将分别来到商店。Alice 购买第 ii 种商品可以获得 UiU_i 的满意度,Bob 购买它则可以获得 ViV_i 的满意度。初始时,Alice 有 AA 单位的钱,Bob 有 BB 单位的钱。

在他们到来之前,作为店员的你要为这 NN 种商品确定一个排列顺序。每位顾客都会独立地按照这个顺序逐一考虑各类商品,并遵循以下规则购物。

  • 顾客从左到右逐一查看商品。
  • 如果当前商品的价格不大于顾客此时拥有的钱数,顾客就一定会购买一件该商品,并支付相应价格。
  • 否则,顾客不购买该商品。

每种商品的库存都足够充足,Alice 和 Bob 的购买行为互不影响。

每位顾客的得分为其购买的所有商品带来的满意度之和。通过恰当地排列商品,求 Alice 和 Bob 的得分之和的最大可能值。

输入格式

输入仅包含一组测试数据,格式如下。

N A B
C_1 U_1 V_1
C_2 U_2 V_2
...
C_N U_N V_N

整数 NN 为商品种类数(1≤N≤2001\le N\le 200)。整数 A,BA,B 分别为 Alice 和 Bob 初始拥有的钱数(1≤A,B≤1201\le A,B\le 120)。

对于每个 i=1,…,Ni=1,\ldots,N,整数 CiC_i 为第 ii 种商品的价格(1≤Ci≤1201\le C_i\le 120)。整数 Ui,ViU_i,V_i 分别为 Alice 和 Bob 购买第 ii 种商品时获得的满意度(1≤Ui,Vi≤1091\le U_i,V_i\le 10^9)。

输出格式

在一行中输出 Alice 和 Bob 的得分之和的最大可能值。

2 6 8
3 10 1
5 8 10
21
2 1 1
1 5 1
1 1 10
11
3 5 6
4 1 100
3 100 1
2 10 10
220

提示

在第一个样例中,若将商品按 1,21,2 的顺序排列,Alice 只购买第 11 种商品,得分为 1010;Bob 购买两种商品,得分为 1111。总得分为 2121,这就是最大可能值。