UOFTBB  Attack of the Bloons
The Bloons (not to be confused with balloons) are attacking! They are attempting to navigate your course of $L$ ($1 \leq L \leq 1000$) cells, laid out in a row and numbered from $1$ to $L$. You don't know what they'll do to you if they manage reach the end, and you don't want to find out! To that end, you've constructed some defensive towers along the course. You might say that this is a Bloons Tower Defense.
There are $N$ ($1 \leq N \leq 1000$) towers ready to take out any Bloons that get close. The $i$th tower is located next to cell $C_i$ ($1 \leq C_i \leq L$), and can launch darts at any Bloons that are no more than $R_i$ ($0 \leq R_i \leq 1000$) cells away  that is, Bloons in cells $C_iR_i$ to $C_i+R_i$, inclusive. Every second, it will do $D_i$ ($1 \leq D_i \leq 10^9$) HP worth of damage to any Bloons in this range.
$M$ ($1 \leq M \leq 1000$) Bloons will attempt to float through your course, one after another. The $i$th Bloon begins with $H_i$ ($1 \leq H_i \leq 10^9$) HP, and will pop as soon as it has taken at least that much damage in total. Each Bloon starts in cell 1, and moves along the course at a speed of 1 cell per second. If a Bloon moves past cell $L$, it safely exits the course and can no longer be popped.
There are $T$ ($1 \leq T \leq 20$) scenarios as described above. For each, you'd like to determine how far along the course each of the $M$ Bloons will make it.
Input
First line: 1 integer, $T$
For each scenario:
First line: 2 integers, $L$ and $N$
Next $N$ lines: 3 integers, $C_i$, $R_i$, and $D_i$, for $i = 1..N$
Next line: 1 integer, $M$
Next $M$ lines: 1 integer, $H_i$, for $i = 1..M$
Output
For each scenario:
$M$ lines: If the $i$th Bloon will survive the course, the string "Bloon leakage" (without quotes)  otherwise, 1 integer, the furthest cell which the $i$th Bloon will reach, for $i = 1..M$
Example
Input:
1
10 3
3 3 1
4 0 4
10 2 2
4
1
20
9
11
Output:
1
Bloon leakage
5
8
Explanation of Sample:
The following diagram illustrates which cells each tower can hit:
The first Bloon, having only 1 HP, will go down to the first tower in cell 1.
The second Bloon will manage to clear the course, surviving past cell 10 with 4 HP remaining.
The third Bloon will lose its final HP while at cell 5, having taken 5 damage from the first tower, and 4 from the second.
The final Bloon will survive past cell 6 with 1 HP remaining, but will then go down at cell 8 when it takes 2 damage from the third tower.
hide comments
Shivam:
20141002 14:11:35
so many WAs because of not initializing with 0... wasted 2 hours in debugging... :( 

Sameer:
20140206 12:13:18
minimum ans is 1 not zero :) 

:
20130812 16:43:42
Easy dp... 

Dragan MarkoviĆ¦:
20130731 18:53:05
@vijay


Rishabh Dugar:
20130730 10:53:00
terrible tym debugging for an "="..rest simple problem 

BLANKRK:
20130712 18:13:33
Error jus due to silly mistakes always hurts.....:P 

Jignesh:
20130706 16:21:14
printing 'Bloon Leakage' instead of 'Bloon leakage' cost me 4 WA's, I hate it when I do such mistakes, but finally AC :) 

pika_pika:
20130702 09:15:01
i dynamically calculated the damage pts at each cell and it gave me TLE(on a 3GHZ machine) and when i precalculate it it gets AC with 0.00s time... just shifted some lines and that big a difference o_O


Agam Gupta:
20130630 17:32:15
You gotta be kidding me..... :p

Added by:  SourSpinach 
Date:  20130517 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own problem, used in the 2012 UofT ACM Tryouts 