Description
League of Legends(LoL) is a dota game that players should control their heroes to destory the hostile main fort.There are five players in one team ,but only three lines for hero to go.
Some heroes ,called Jungler will go to jungle which is fighting wild monsters for money and experience let the heroes on-line get more experience.Hero spends TEi secs to fight with Monsteri and gets Ci money. If the Monsteri been killed, it would rebirth after TRi secs. Moving between A and B should spend DAB secs. If A, B are connected and B, C are connected, you can go to C from A in DAB+DBC secs.
Write a program to count the most money junger can gain in T secs(T is count from the fisrt birth time of wild monsters, all wild monsters have same fisrt birth time).
Because there are full time before the wild monster first birth, you can start from any wild monster when T=0.
Example:
Map
.jpg)
Monster infromation:
| Monster | TE | C | TR |
| 1 | 3 | 6 | 4 |
| 2 | 2 | 5 | 3 |
| 3 | 3 | 5 | 3 |
| 4 | 7 | 11 | 8 |
| 5 | 6 | 10 | 8 |
D15 = 3,D52 = 3,D23 = 7,D34 = 3 and T = 50;
If jungler fight wild monsters by the order 1: 1->2->3->4->5, he needs to spend TE1 + D12 + TE2 + D23 + TE3 + D34 + TE4 +D45 + TE5 = 3+(3+3)+2+7+3+3+7+(3+7+3)+6 = 50 secs and he can gain 6+5+5+11+10 = 37.
If jungler fight wild monsters by the order 2: 1->5->2->5->1->5->2, he needs to spend TE1 + D15 + TE5 + D52 + TE2 + D25 + TE5 +D51 + TE1 + D15 + TE5 + D52 + TE2 = 3+3+7+3+2+3+7+3+3+3+7+3+2 = 49 secs and he can gain 6+10+5+10+6+10+5 = 52. If jungler fight wild monsters by the order 2: 1->5->2->5->1->5->2, he needs to spend TE1 + D15 + TE5 + D52 + TE2 + D25 + TE5 +D51 + TE1 + D15 + TE5 + D52 + TE2 = 3+3+7+3+2+3+7+3+3+3+7+3+2 = 49 secs and he can gain 6+10+5+10+6+10+5 = 52.
If jungler fight wild monsters by the order 3: 2->2->2->2->2->2->2->2->2->2, he needs to spend TE2 + TR2 + TE2+ TR2 + TE2+ TR2 + TE2+ TR2 + TE2+ TR2 + TE2+ TR2 + TE2+ TR2 + TE2+ TR2 + TE2 = 2+3+2+3+2+3+2+3+2+3+2+3+2+3+2+3+2+3+2 = 47 secs and he can gain 5*10 = 50.
We know order 2 is better than order 1 and order 3.
Input
The input consists of several test cases. Each test case begins with 3 integers in a line: The time T (1<=T<=500), the number of wild monsters N (1<=N<=50) and the number of road between wild monsters M ((N-1)<=M<=N2).
The following N lines describe the wild monsters' information. The i-th line contains three integers: the time need to fight the monster TEi(2<=TEi<=50) and money gain after fighting monster Ci(1<=Ci<=1000) and the rebirth time TRi(1<=TRi<=8) of the i-th monster.
The following M lines describe the road between wild monsters.Each line contains three integers: NO of monsterA and NO of monsterB and the moving time between A and B DAB (3<=DAB<=20)
Hint:
For any wild monster A,B: DAB + TEB + DBA >= TRA
Road between two wild monsters might more than one.
Output
Output the most money junger can gain in T secs.