TROOPS - Troops of Sand Monsters


Under the command of the Evil Vizier there are N unique troops of sand monsters, where each  troop contains Ci sand monsters. The Vizier in his desperate battle against the Prince of Persia has ordered all his troops to attack him simultaneously.
 
The Prince realizes that he cannot defeat all of the sand monsters, as they are invincible  when they are active. So he uses the Eye of the Storm spell to freeze all the sand monsters of all troops. Now the Prince can kill any monster by stabbing each monster once using the Dagger of Time. Once the monster is killed, it can never become active again and releases a certain quantity of the Sands of Time. It takes one unit of time to kill any monster.
 
Each troop i, consits of Ci similar monsters, all with the same spell resistance time Ti - after which it becomes active again and therefore invulnerable - and Sand Si - which can be taken by the Prince after killing it.
 
The spell lasts only for a limited duration of time. So, the Prince has to kill as many sand monsters as possible and take maximum sand from the monsters before they become active again. It is not necessary for The Prince to kill all the monsters in a troop before moving on to next troop.

Input

The first line contains K <=70  the number of testcases. Each testcase begins with 'N' (<=1000) the number of troops of monsters. Next N lines contain 3 integers Ci, Ti, Si. 1<i<=N,  1<=Ci<=15000, 1<=Ti<=1000000, 1<=Si<=100,

Output

Single Line containing the maximum amount of sand that Prince can get if he kills some or all the monsters.

Example

Input:
1
4
2 1 2
2 3 6
2 5 5
2 7 8

Output:
40

Explanation

(time, troop, sand)
(0,1,2) (1,2,6) (2,2,6) (3,3,5) (4,3,5) (5,4,8) (5,4,8) = 40

 



hide comments
adir: 2016-06-16 09:06:29

the tag for this problem is misleading..

eightnoteight: 2015-09-04 22:41:51

i'm getting TLE, my complexity is O(max(Ti)*k), what is the expected complexity??

Last edit: 2015-09-04 22:42:33
Arpit Mittal: 2015-06-27 15:53:56

What's the solution for test case
4
2 1 2
2 3 6
2 5 5
2 5 4. It should be 26 right?

Last edit: 2015-06-27 15:55:17
shubham sinha: 2015-05-20 12:54:50

does prince has to kill at least one monster from all the troops or there be a case where he can leave a troop as it is?

Luka Hrabar: 2013-08-13 16:23:48

In addition to the problem statement:
The Prince doesn't necessarily have to attack the troops in the order given in the input.

Master Wad7a: 2013-03-18 10:02:00

WA.. can u give me some tricky tests??

:D: 2010-03-21 15:53:39

It seems that the Prince is skilled enough to avoid attacks from awakened monsters :). You can kill any number of monsters in any order. You have to leave the second one from the first troop in the test case, because it will be active after you stab the first one.

You are right about the explanation, it should be (6,4,8).

~ adieus ~: 2010-01-21 13:16:54

I think there is a mistake in your explanation your have (5,4,8) twice ? is the last one supposed to be (6,4,8) ?

And why did the Prince leave the second sand monster in the first troop ??

once the Prince leaves a troop , no monster belonging to the troop is going to attack Prince ?

Last edit: 2010-01-21 13:18:38

Added by:arun
Date:2010-01-15
Time limit:0.449s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:Kurukshetra OPC 2010