## DMOPC '21 Contest 7 P4 - Rocket Race

View as PDF

Points: 17 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types

Tyler is a competitive rocket racer. Unlike in normal foot racing, rocket racers use their own collection of rockets to move instead of their feet. Tyler's collection consists of single-use rockets. The -th rocket propels him meters forwards, but sends him meters backwards immediately after. Of course, rocket technology is constantly evolving, and racers need to update their collection frequently to ensure optimal performance. As Tyler's coach, you must handle of the following events, each starting with a value :

• If then an integer follows, and you must tell Tyler the minimum number of rockets he needs to complete an meter race. Note that the race is completed if Tyler reaches or passes the finish line at the meter mark at any point. Also, all rockets may only be used in the forward direction (i.e. initially towards the finish line).
• If then two integers and follow, indicating that Tyler replaces the -th rocket with one that propels him meters forwards but sends him meters backwards immediately after.

#### Input Specification

The first line contains an integer .

The next lines each contain integers and .

The next line contains an integer .

The next lines each contain the description of an event on a single line, as described in the statement.

#### Output Specification

For each event with output the answer on its own line, or if it is impossible to complete that race.

#### Sample Input

10
2 1
5 7
4 1
5 4
7 3
9 4
1 6
6 4
5 2
4 5
6
0 15
0 8
6 7 5
0 11
0 8
0 100

#### Sample Output

3
1
2
2
-1

#### Explanation

For the first event, Tyler should use his -th, -th, and -th rockets in that order. This reaches a maximum forward distance of meters, which is just enough to complete the race.

For the fifth event, Tyler should use his -th rocket and then his -nd rocket. This reaches a maximum forward distance of meters, enough to complete the race.

For the sixth event, it is impossible for Tyler to complete the race regardless of which rockets he chooses to use.