Gifts

Background

Special for beginners, ^_^

Problem Description

You have now received many gifts and want to put them into a bag. You have only one bag that can hold items of volume at most $V$, so you cannot put everything in. You also cannot carry everything because of the weight; you estimate the maximum weight you can carry to be $G$.

Now you know the perfection value, weight, and volume of each gift. Naturally, you want to maximize the total perfection value of the gifts put into the bag, so you have to plan it out.

Input Format

First line: $V$ and $G$, the maximum volume and maximum weight.

Second line: $N$, meaning you received $N$ gifts.

Lines $3$ to $N+2$: each line has $3$ numbers $T_i, V_i, G_i$, the perfection value, weight, and volume of each gift.

Output Format

Output one number: the maximum perfection value that can be obtained.

Sample Input 1

6 5 
4 
10 2 2 
20 3 2 
40 4 3 
30 3 3

Sample Output 1

50

Constraints

1s, 1024KiB for each test case.

For $20\%$ of the data, $N, V, G, T_i, V_i, G_i \le 10$;

For $50\%$ of the data, $N, V, G, T_i, V_i, G_i \le 100$;

For $80\%$ of the data, $N, V, G, T_i, V_i, G_i \le 300$;

The data from $80\%$ to $100\%$ are discrete random data with $N, V, G, T_i, V_i, G_i \le 380$.