Problem 2: Piercing

In the near future, a game called "Piercing" is popular in Singapore. The rules are simple. A wedge-shaped airship must move through an $N \times M$ tunnel from left to right. There are $N$ green barriers in the tunnel that obstruct the airship's forward movement. Barriers are located on the left wall of each column, and a barrier that exists continuously across multiple columns is considered a single barrier. For convenience, if we denote the forward direction of the airship as the $x$-axis and the direction perpendicular to it as the $y$-axis, there is only one barrier for any given $x$-coordinate.

For example, the figure below shows an $11 \times 6$ tunnel with 11 barriers. The leftmost barrier is a single barrier extending from $(0, 2)$ to $(0, 5)$, and the rightmost barrier is a single barrier extending from $(10, 1)$ to $(10, 5)$.

The airship can perform one of two types of movements in each column. The first movement is teleportation. Teleportation moves the airship to any arbitrary cell with the same $x$-coordinate as the current cell. In this case, it always costs $A$, regardless of the position of the cell being moved to. For example, the figure below shows an airship at $(0, 1)$ teleporting to $(0, 5)$, which costs $A$.

The second movement of the airship is moving forward. The cost is $0$. Even if there is a barrier in the direction the airship is moving, the airship can pierce through it. However, in this case, it costs $B$. For example, the figure below shows an airship at $(6, 5)$ moving forward to $(7, 5)$; since there is a barrier at $(7, 5)$, it costs $B$.

The game ends when the airship completely passes through the tunnel, and the game score is given as the sum of the costs incurred while passing through the tunnel. Naturally, a lower score is better. The gamer can choose the $y$-coordinate of the airship at the start of the game without any cost, and the $y$-coordinate of the airship when the game ends does not matter.

Even if the size of the tunnel and the positions of the barriers are the same, the game score can change if the costs $A$ and $B$ change, and the movement of the airship to obtain the minimum game score can also change. You must implement the following two functions to find the lowest possible game score whenever the costs $A$ and $B$ change, using the given tunnel size and barrier positions.

• void init(int N, int M, int Y1[], int Y2[]): This function is called initially and is called only once. $N$ and $M$ represent the size of the tunnel, $N \times M$. $Y1$ and $Y2$ are arrays of size $N$ representing the positions of the barriers; if there is a barrier from $(i, Y1[i])$ to $(i, Y2[i])$, the values are $Y1[i]$ and $Y2[i]$.
• long long minimize(int A, int B): $A$ is the cost for the airship to teleport once, and $B$ is the cost for the airship to pierce a barrier once. Use this to find and return the minimum cost required to pass through the tunnel.

Implementation Details

You must submit a single file named breakthru.cpp. This file must implement the following functions:

• void init(int N, int M, int Y1[], int Y2[])
• long long minimize(int A, int B)

These functions must operate as described above. You may create and use other functions internally. The submitted code must not perform any input/output or access other files.

Constraints

• $1 \le N \le 10,000$
• $1 \le M \le 10^9$
• $1 \le Q \le 10^6$
• $0 \le Y1 \le Y2 \le M-1$
• $0 \le A, B \le 10^9$

Subtasks

• Subtask 1 [7 points]: $Q=1, N \le 3,000, M \le 3,000$
• Subtask 2 [22 points]: $Q \le 50$
• Subtask 3 [19 points]: $N \le 500$
• Subtask 4 [21 points]: $N \le 2,500$
• Subtask 5 [31 points]: No additional constraints.

Examples

Input 1

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

Output 1

1
3

Note 1

The table below shows the function calls and their results for Example 1.