### Woburn Challenge 2018-19 Round 4 - Senior Division

## Problem 4: Super Luigi Odyssey

Billy has been having a great time playing a demo of Nintendo's next highly-anticpated 3D platforming game, *Super Luigi Odyssey*.

One challenge in the game sees Luigi trapped in a long hallway, which can be represented as a number line with positions increasing towards the rightwards direction. There are `N` (1 ≤ `N` ≤ 250,000) platforms in it, with the `i`-th one at position `P _{i}` (0 ≤

`P`≤ 10

_{i}^{9}) and at a height of

`H`(1 ≤

_{i}`H`≤ 10

_{i}^{9}) metres. No two platforms are at the same position. Luigi begins on platform 1 (note that this is not necessarily the leftmost platform).

Much to Luigi's concern, the hallway is filled with some deadly lava. Initially, the lava reaches up to a height of 0.5 metres. At any point, a platform is considered to be submerged in lava if the lava's height exceeds the platform's height.

A sequence of `M` (1 ≤ `M` ≤ 250,000) events will then occur, each having one of three possible types. The type of the `i`-th event is described by the integer `E _{i}` (1 ≤

`E`≤ 3).

_{i}- If
`E`= 1, then the lava's height will increase by_{i}`X`(−10_{i}^{9}≤`X`≤ 10_{i}^{9}) metres. It's guaranteed that this will not cause the lava's height to become negative. If this causes Luigi's current platform to become submerged, then he will immediately perish. - If
`E`= 2, then_{i}`X`(1 ≤_{i}`X`≤_{i}`N`) lasers in a row will be fired at Luigi. Each laser will force him to jump to the next non-submerged platform to the left of his current one. If there's no such platform, then he'll instead be forced to jump into the lava and perish. - If
`E`= 3, then similarly_{i}`X`(1 ≤_{i}`X`≤_{i}`N`) lasers in a row will be fired at Luigi, with each one forcing him to jump to the next non-submerged platform (if any) to the right rather than the left.

Luigi is not allowed to move between platforms aside from being forced to by type-2 or type-3 events.

Even if Billy manages to keep Luigi alive through all `M` events, he may not be out of the woods yet — his success in later challenges will depend on how much of Luigi's energy has been spent. Whenever Luigi jumps from platform `i` to platform `j`, he expends |`P _{i}` −

`P`|

_{j}^{K}(1 ≤

`K`≤ 2) units of energy. Note that the amount of energy required doesn't depend on the platforms' relative heights.

Help Billy determine how much energy Luigi will expend throughout all `M` events (if he will even survive that long). As this may amount to quite a few units of energy, you only need to determine the total modulo 1,000,000,007.

### Subtasks

In test cases worth 6/39 of the points, `N` ≤ 2000, `M` ≤ 2000, and `K` = 1.

In test cases worth another 16/39 of the points, `K` = 1.

### Input Format

The first line of input consists of three space-separated integers, `N`, `M`, and `K`.

`N` lines follow, the `i`-th of which consists of two space-separated integers, `P _{i}` and

`H`, for

_{i}`i`= 1..

`N`.

`M`lines follow, the

`i`-th of which consists of two space-separated integers,

`E`and

_{i}`X`, for

_{i}`i`= 1..M.

### Output Format

Output a single integer, the total number of units of energy which Luigi will expend (modulo 1,000,000,007), or −1 if he will be forced to touch the lava and perish at any point.

### Sample Input 1

5 7 1 4 4 5 5 13 6 0 8 10 8 3 1 1 4 2 1 1 -1 3 4 1 2 2 2

### Sample Output 1

32

### Sample Input 2

2 2 2 0 2 1 1 1 1 3 1

### Sample Output 2

-1

### Sample Explanation

In the first case, Luigi will be forced to jump along the follow sequence of positions:

- Event 1: 4 → 5
- Event 3: 5 → 0
- Event 5: 0 → 4 → 5 → 10 → 13
- Event 7: 13 → 10 → 0

In total, these jumps require 32 units of energy (which is equal to 32 modulo 1,000,000,007). If `K` were equal to 2 rather than 1, then 186 units of energy would be required instead.

In the second case, after the lava's height is raised to 1.5 metres, Luigi will have no non-submerged platform to jump to on his right, and so will be forced to jump into the lava and perish.

All Submissions

Best Solutions

**Point Value:** 25 (partial)

**Time Limit:** 7.00s

**Memory Limit:** 128M

**Added:** Mar 22, 2019

**Author:** SourSpinach

**Languages Allowed:**

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

## Comments (Search)

It's quiet in here...