you have n instant cup noodles pack. The ith pack takes ci minutes to cook after hot water is added to it, and it satisfies your hunger by an amount of hi. Now, you are running late for your college and you have only m minutes left to cook the noodles. You wish to satisfy your hunger to a maximum level. But in one minute, you can add hot water to one cup only. You have to find the maximum level of hunger that you can satisfy in m minutes. Consider that adding hot water and eating the noodles doesn't require any time.

• constraints;
• 1<=t<=10
• 1<=n<=10000
• 1<=m<=100000
• 1<=ci<=100000
• 1<=hi<=10000

• sample:

• 1
• 3 5
• 5 5 3
• 5 10 2
• output — 12

I thought of applying dp but the constraints are too large. Can anyone suggest a better greedy approach.