University of Toronto ACM-ICPC Tryouts 2013
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
awesome ones in mind. All of them happen to be horror movies.
A given movie is
minutes long, and has
key moments. The
-th moment occurs
minutes into the movie, and causes Alice's fright level (which starts at
0) to instantly increase by
. If
her fright level would become negative, it instead becomes 0. The
moments are given in chronological order, so
.
As soon as the movie ends, Alice's fright level is
instantly reset to 0.
During each movie, Alice has two fright thresholds, and
. Whenever her fright level is at least
, Bob is
obligated to hold her hand. However, as soon as her fright level is at
least
, 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 Specification
Line 1: 1 integer,
For each movie:
Line 1: 4 integers, ,
,
, and
Next lines: 2 integers,
and
, for
Output Specification
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 between moments
and
, and between moments
and
. Therefore,
Bob will need to hold her hand for
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
and
, at which point her fright level will become
, and she'll have
to leave the theatre.
Comments