33OJ
登录 注册

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

[JAG 2026 Summer Camp #2] Two Greedy Customers

Problem Description

A shop sells NN types of products numbered from 11 to NN. The price of product ii is CiC_i.

Two customers, Alice and Bob, will visit the shop separately. When Alice purchases product ii, she gains satisfaction UiU_i. When Bob purchases it, he gains satisfaction ViV_i. Initially, Alice has AA units of money, and Bob has BB units of money.

Before they visit, you, a shop clerk, choose an ordering of the NN product types. Each customer independently considers the product types one by one in the chosen order and makes purchases according to the following rules.

  • The customer inspects the products one by one from left to right.
  • If the price of the current product is not greater than the amount of money the customer has at that moment, the customer always purchases one item of that product and pays its price.
  • Otherwise, the customer does not purchase that product.

Each product is available in sufficient quantity, and the purchases made by Alice and Bob do not affect each other.

The score of each customer is the sum of the satisfaction gained from the products purchased by that customer. Determine the maximum possible sum of the scores of Alice and Bob by arranging the products appropriately.

Input Format

The input consists of a single test case in the following format.

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

The integer NN is the number of product types (1≤N≤2001\le N\le 200). The integers AA and BB are the initial amounts of money held by Alice and Bob, respectively (1≤A,B≤1201\le A,B\le 120).

For each i=1,…,Ni=1,\ldots,N, the integer CiC_i is the price of product ii (1≤Ci≤1201\le C_i\le 120). The integers UiU_i and ViV_i are the satisfaction gained by Alice and Bob, respectively, when they purchase product ii (1≤Ui,Vi≤1091\le U_i,V_i\le 10^9).

Output Format

Output the maximum possible sum of the scores of Alice and Bob in one line.

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

Hint

If the products are arranged in the order 1,21,2 in the first sample, Alice purchases only product 11 and gets a score of 1010, while Bob purchases both products and gets a score of 1111. The total score is 2121, which is the maximum possible.