Dark Game (Pgrune)

Problem Background

Special for beginners, ^_^

Problem Description

In the dark game, equipment directly determines a character's power. You can use Pg and Rune to buy items. Each item in the dark market has a different price (in Pg and Rune), a power value, and a maximum purchasable quantity.

Kid, a player on the dark battle.net, of course wants to use as little Pg and Rune as possible to buy better equipment, so as to obtain the highest power value. Please help compute the maximum power value obtainable within his current budget.

Input Format

Line 1: three integers $N,P,R$ — the number of item types in the market, the Pg budget, and the Rune budget.

Lines $2\dots N+1$: each line has four integers. The first two are the Pg and Rune cost of the item; if the third integer is $0$, the item can be bought unlimited times; otherwise it is the maximum number $S$ of this item that can be bought; the fourth integer is the item's power value.

Output Format

One line with a single integer — the maximum obtainable power value.

Sample Input

3 10 10
5 3 0 110
4 3 4 120
2 3 1 130

Sample Output

370

Constraints

Time limit 1s, memory limit 1024KiB for each test case.

Sample Explanation

Buy 2 of the second item and 1 of the third item.

Data Scale

For $30\%$ of the data, $0<N\le 50,\ 0<P\le 30,\ 0<R\le 30,\ 0\le S\le 8$.

For $70\%$ of the data, $0<N\le 80,\ 0<P\le 65,\ 0<R\le 65,\ 0\le S\le 16$.

For $100\%$ of the data, $0<N\le 150,\ 0<P\le 100,\ 0<R\le 100,\ 0\le S\le 32$.