Crossing the Tunnel

In the not‐so‐distant future, a game called "Crossing" becomes popular in Singapore. In this game, you control a wedge‐shaped spaceship that must traverse an N×M tunnel from left to right. The tunnel has N green obstacles. Each obstacle is located on the left wall of the grid cells in its column, and if several adjacent cells are continuously blocked, they are considered as one obstacle. For convenience, we use an x-axis (the forward direction) and a y-axis (perpendicular to the forward direction). There is at most one obstacle per column. Specifically, for every column x (with 0 ≤ x ≤ N-1), an obstacle occupies the cells from (x, Y_1[x]) to (x, Y_2[x]) (inclusive).

The spaceship has two types of moves inside a cell:

1. Teleportation: The spaceship can instantly move to any cell within the same column. This move always costs A.
2. Forward Move: The spaceship moves from column x to column x+1 while staying at the same y coordinate. This move costs 0 if the destination cell is not blocked; if the destination cell is blocked by an obstacle, it costs an extra B as the spaceship has to pass through the obstacle.

The game begins with you choosing an initial y coordinate at column 0 without any cost. The final y coordinate when the spaceship exits the tunnel is irrelevant. Your task is to implement the following two functions:

void init(int N, int M, int Y1[], int Y2[]);

• This function is called once at the beginning. The tunnel size is N×M, and for each column x (0 ≤ x ≤ N-1) an obstacle occupies cells from (x, Y_1[x]) to (x, Y_2[x]).

long long minimize(int A, int B);

• A is the cost of a teleportation move and B is the cost incurred when a forward move lands on a cell occupied by an obstacle.
• This function should return the minimum total cost for the spaceship to cross the tunnel from column 0 to column N-1.

Note about movement:

When moving from column i to column i+1:

• If you do nothing (i.e. keep your current row), you incur a cost of B if the cell in column i+1 is blocked; otherwise, the cost is 0.
• You may also choose to teleport (at cost A) to a different y before moving; if you teleport to a cell that is not blocked in column i+1, then moving forward costs 0.

For each column i > 0, if there exists at least one cell that is not blocked (i.e. a safe cell exists so that either Y1[i] > 0 or Y2[i] < M-1), the optimal additional cost to cross column i is min(A, B). If the obstacle in column i covers the entire column (i.e. Y1[i] == 0 and Y2[i] == M-1), then you must pay B for that column. There is no cost incurred for column 0 due to the free initial placement.

inputFormat

Although the submitted functions do not perform standard input/output, the testing framework will simulate multiple queries. The input format for a test case is as follows:

N M Q
Y1[0] Y1[1] ... Y1[N-1]
Y2[0] Y2[1] ... Y2[N-1]
A[1] B[1]
A[2] B[2]
...
A[Q] B[Q]

Here, Q is the number of queries. For each query, the function minimize(A, B) is called and its return value is checked.

outputFormat

For each query, the function minimize should return a single long long integer representing the minimum total cost for the spaceship to cross the tunnel.

sample

3 5 2
1 0 2
3 4 3
5 3
2 7

6
9

</p>