시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
30 초 (추가 시간 없음) | 1024 MB | 26 | 16 | 14 | 63.636% |
Duda the rock monster lives in the enchanted forest and has collected N energy stones for lunch. Since he has a small mouth, he eats energy stones one at a time. Some stones are tougher than others! The i-th stone takes him Si seconds to eat.
Duda eats energy stones to get energy. Different stones give him different amounts of energy. Furthermore, the stones lose energy over time. The i-th stone initially contains Ei units of energy and will lose Li units of energy each second. When Duda starts to eat a stone, he will receive all the energy the stone contains immediately (no matter how much time it takes to actually finish eating the stone). The stone's energy stops decreasing once it hits zero.
What is the largest amount of energy Duda could receive from eating his stones?
The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line containing the integer N, the number of energy stones Duda has. Then, there are N more lines, the i-th of which contains the three integers Si, Ei and Li, as described above.
For each test case, output one line containing Case #x: y
, where x
is the test case number (starting from 1) and y
is the maximum amount of energy Duda could receive from eating stones.
2 3 10 4 1000 10 3 1000 10 8 1000 2 10 2 0 10 3 0
Case #1: 8 Case #2: 5
In Sample Case #1, there are N = 3 stones. No matter which stone Duda eats, the other two will have no energy left once he is done eating. So he should eat the third stone, giving him 8 units of energy.
2 4 20 10 1 5 30 5 100 30 1 5 80 60 2 12 300 50 5 200 0
Case #1: 105 Case #2: 500
In Sample Case #1, there are N = 4 stones. One possible order Duda can eat stones is:
This gives him 105 units of energy, which is the best he can do. So the answer is 105.
In Sample Case #2, there are N = 2 stones. Duda can:
So the answer is 500.
Contest > Google > Kick Start > Google Kick Start 2019 > Round B B번