UOFTCD  A Frightening Evening
Bob is taking Alice out for an evening at the movies! He'll be deciding what movies they see, of course, and he's got $N$ ($1 \leq N \leq 100$) awesome ones in mind. All of them happen to be horror movies.
A given movie is $D$ ($1 \leq D \leq 10^9$) minutes long, and has $M$ ($0 \leq M \leq 100$) key moments. The $i$th moment occurs $T_i$ minutes into the movie, and causes Alice's fright level (which starts at 0) to instantly increase by $F_i$ ($10^6 \leq F_i \leq 10^6$). If her fright level would become negative, it instead becomes 0. The moments are given in chronological order, so $0 \leq T_1 < T_2 < \dots < T_M \leq D$. As soon as the movie ends, Alice's fright level is instantly reset to 0.
During each movie, Alice has two fright thresholds, $H$ and $L$ ($1 \leq H < L \leq 10^9$). Whenever her fright level is at least $H$, Bob is obligated to hold her hand. However, as soon as her fright level is at least $L$, she'll be scared enough to leave the theatre  at which point, Bob will stay inside and finish the movie, and will of course no longer need to hold her hand.
Bob enjoys brilliant films such as Night of the Dead Living and Return of the Revenge of the Attack of the Killer Foxen, and he'd prefer to not be distracted. As such, he'd like to minimize the amount of time he spends holding Alice's hand. To help with this, he may choose to cover her eyes during at most one key moment in each movie. Alice's fright level will be unaffected by this key moment.
Input
Line 1: 1 integer, $N$
For each movie:
Line 1: 4 integers, $D$, $M$, $H$, and $L$
Next $M$ lines: 2 integers, $T_i$ and $F_i$, for $i=1..M$
Output
For each movie:
1 integer, the minimal number of minutes for which Bob needs to hold Alice's hand
Example
Input:
2
90 5 5 50
12 8
14 4
40 6
45 11
73 50
105 3 5 20
33 15
39 1
52 5
Output:
30
19
Explanation of Sample:
While watching the first movie, Bob should cover Alice's eyes during the third key moment. With this strategy, Alice's fright level will be at least 5 between moments 1 and 2, and between moments 4 and 5. Therefore, Bob will need to hold her hand for $2+28=30$ minutes.
While watching the second movie, Bob should cover Alice's eyes during the second moment. He will then need to hold her hand between moments 1 and 3, at which point her fright level will become 20, and she'll have to leave the theatre.
hide comments
Kshitij Agarwal:
20150705 12:39:42
@Frendy Yeah It should be 1 if Bob dosen't protect her any moment. Last edit: 20150705 19:08:58 

Fendy:
20150418 18:26:34
in this testcase:


Ashwini:
20140301 18:46:39
one more thing you should have said after 3rd moment i,e from 53 min onwards. cost me like 4 wa due to this.. anyways ac finally. thanks again 

Ashwini:
20140301 17:49:19
thanx 

Ashwini:
20140228 21:18:53
shouldn't the answer of 2nd case be 0. close her eyes during the very first moment?????


newbie:
20140218 18:37:12
should't it be 2 in place of 3 for value of N in given test case

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