University of Toronto ACM-ICPC Tryouts 2013

D: 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 ≤ N ≤ 100) awesome ones in mind. All of them happen to be horror movies.

A given movie is D (1 ≤ D ≤ 10⁹) minutes long, and has M (0 ≤ M ≤ 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⁶ ≤ F_i ≤ 10⁶). If her fright level would become negative, it instead becomes 0. The moments are given in chronological order, so 0 ≤ T₁ < T₂ < … < T_M ≤ 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 ≤ H < L ≤ 10⁹). 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, output 1 integer, the minimal number of minutes for which Bob needs to hold Alice's hand.

Sample 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

Sample 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.

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 64M
Added: Jul 08, 2014
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

[quote]For each movie, outout 1 integer, the minimal number of minutes for which Bob needs to hold Alice's hand.[/quote] 
I think there is a mistake and instead of outout, you meant output.

Thanks, it's been fixed!

Can someone post my error message? I can't find my mistake.

Thanks,

I consider your error trivial enough that I think it would be more beneficial to you if you figure it out yourself.

Read the question statement again carefully. If you give it an honest try and still can't figure it out, I might give a hint. (Or maybe somebody wants to be more helpful than me! :P)

Right, got it, thanks.