Woburn Challenge 2018-19 Round 4 - Senior Division

Billy has been having a great time playing a demo of Nintendo's next highly-anticipated 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\le N\le 250000)$ platforms in it, with the $i$-th one at position $P_i$ $(0\le P_i\le {10}^9)$ and at a height of $H_i$ $(1\le H_i\le {10}^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\le M\le 250000)$ 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\le E_i\le 3)$.

• If $E_i=1$, then the lava's height will increase by $X_i$ $(-{10}^9\le X_i\le {10}^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_i=2$, then $X_i$ $(1\le X_i\le 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_i=3$, then similarly $X_i$ $(1\le X_i\le 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\le K\le 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 $1000000007$.

Subtasks

In test cases worth $6/39$ of the points, $N\le 2000$, $M\le 2000$, and $K=1$.
In test cases worth another $16/39$ of the points, $K=1$.

Input Specification

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_i$, for $i=1\dots N$.
$M$ lines follow, the $i$-th of which consists of two space-separated integers, $E_i$ and $X_i$, for $i=1\dots M$.

Output Specification

Output a single integer, the total number of units of energy which Luigi will expend (modulo $1000000007$), 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 following sequence of positions:

• Event 1: $4\to 5$
• Event 3: $5\to 0$
• Event 5: $0\to 4\to 5\to 10\to 13$
• Event 7: $13\to 10\to 0$

In total, these jumps require $32$ units of energy (which is equal to $32$ modulo $1000000007$). 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.