Diving Tools Optimization

With the help of the Monkey King, little A has finally escaped from the barren mountains, only to be confronted by a raging river without any boat. Fortunately, little A possesses n diving tools. However, due to his heavy backpack, he can only carry tools with a total weight of at most m, and because his strength is limited and the river is wide, the tools he carries must also have a total resistance of at most v. Under the river lies extremely important data, so he wants to maximize his underwater staying time. Each diving tool is described by three parameters: its weight w_i, its resistance r_i, and the diving time it provides t_i.

The task is to select a subset of these tools such that the total weight \(\sum w_i\) is at most \(m\) and the total resistance \(\sum r_i\) is at most \(v\), while maximizing the total diving time \(\sum t_i\). Output the maximum total diving time achievable.

inputFormat

The input begins with a single line containing three integers, n, m, and v (the number of diving tools, the maximum total weight, and the maximum total resistance respectively). Then follow n lines, each containing three space-separated integers: w_i, r_i, and t_i, representing the weight, resistance, and diving time of the ith tool respectively.

outputFormat

Output a single integer: the maximum total diving time achievable under the given constraints.

sample

3 10 10
5 5 10
4 6 12
3 3 6

18