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

A shop sells $N$ types of products numbered from $1$ to $N$. The price of product $i$ is $C_i$. Two customers, Alice and Bob, will visit the shop separately. When Alice purchases product $i$, she gains satisfaction $U_i$. When Bob purchases it, he gains satisfaction $V_i$. Initially, Alice has $A$ units of money, and Bob has $B$ units of money. Before they visit, you, a shop clerk, choose an ordering of the $N$ 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.

The input consists of a single test case in the following format. ```text N A B C_1 U_1 V_1 C_2 U_2 V_2 ... C_N U_N V_N ``` The integer $N$ is the number of product types ($1\le N\le 200$). The integers $A$ and $B$ are the initial amounts of money held by Alice and Bob, respectively ($1\le A,B\le 120$). For each $i=1,\ldots,N$, the integer $C_i$ is the price of product $i$ ($1\le C_i\le 120$). The integers $U_i$ and $V_i$ are the satisfaction gained by Alice and Bob, respectively, when they purchase product $i$ ($1\le U_i,V_i\le 10^9$).

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

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