Bessie’s Bribery

Bessie wants to watch the documentary Cow Genomics, but she doesn’t want to go alone. Unfortunately, her friends are not as enthusiastic as she is! So Bessie needs to bribe her friends to accompany her to the cinema. Her bribery arsenal contains two types of commodities: moo-ni (a kind of currency) and ice cream cones.

Bessie has N friends (1 \le N \le 2000). However, not all friends are equal! Friend \(i\) has a popularity value \(P_i\) (1 \le P_i \le 2000). Bessie wants to maximize the sum of the popularities of the friends who accompany her.

Each friend \(i\) will only go with Bessie if she receives exactly \(C_i\) moo-ni (1 \le C_i \le 2000). However, if Bessie also gives friend \(i\) some ice cream cones, she can get a discount: for every \(X_i\) ice cream cones given (1 \le X_i \le 2000), friend \(i\) will subtract 1 moo-ni from the bribery cost. Formally, if Bessie decides to use a discount of \(d\) (an integer, \(0 \le d \le C_i\)) for friend \(i\), then she must provide \(d \times X_i\) ice cream cones and she will only have to pay \(C_i - d\) moo-ni. Note that Bessie cannot get a discount so high that the cost would become negative.

Bessie has a total of \(A\) moo-ni and \(B\) ice cream cones available (0 \le A, B \le 2000). Help Bessie determine the maximum total popularity she can achieve by carefully choosing which friends to bribe and how many ice cream cones to use for discounts.

The key constraints can be summarized in the following formulas:

• For each friend \(i\), choose an integer \(d_i\) (discount) such that \(0 \le d_i \le C_i\) and the ice cream cones required is \(d_i \times X_i\).
• The moo-ni cost for friend \(i\) becomes \(C_i - d_i\).
• The total moo-ni spent must not exceed \(A\) and the total ice cream cones spent must not exceed \(B\).

Determine the maximum sum of \(P_i\) over all bribed friends under these constraints.

inputFormat

The first line contains three integers \(N\), \(A\), and \(B\) separated by spaces.

Then \(N\) lines follow, each containing three integers \(P_i\), \(C_i\), and \(X_i\), describing friend \(i\)'s popularity, required moo-ni, and the ice cream cone discount factor respectively.

\(1 \le N \le 2000\), \(0 \le A, B \le 2000\), \(1 \le P_i, C_i, X_i \le 2000\).

outputFormat

Output a single integer: the maximum total popularity Bessie can achieve by bribing some of her friends while not exceeding her available moo-ni and ice cream cones.

sample

3 5 5
4 3 2
5 4 5
3 2 1

9