问题：뚫기 2

在不久的将来，新加坡流行着一款名为“뚫기”的游戏。游戏规则很简单：一个楔形的飞行船需要从左向右穿过一个大小为 $N \times M$ 的隧道。隧道中存在 $N$ 个用于阻碍飞行船前进的绿色屏障。屏障位于各个格子的左侧墙壁上，若在多个格子中连续存在，则视为同一个屏障。为方便起见，将飞行船的前进方向记为 $x$ 轴，与其垂直的方向记为 $y$ 轴，则在相同的 $x$ 坐标处只会存在一个屏障。

例如，下图表示在一个大小为 $11 \times 6$ 的隧道中存在 11 个屏障的情况。最左侧的屏障是从 $(0,2)$ 到 $(0,5)$ 连续的一个屏障，最右侧的屏障是从 $(10,1)$ 到 $(10,5)$ 连续的一个屏障。

飞行船在每一个格子中可以进行以下两种移动之一。

第一种移动是瞬间移动。瞬间移动是指将飞行船从当前所在格子移动到具有相同 $x$ 坐标的任意一个格子。无论移动到哪个格子，所需费用始终为 $A$。例如，下图中飞行船从 $(0,1)$ 瞬间移动到 $(0,5)$，费用为 $A$。

第二种移动是前进。前进的费用为 $0$。即使在飞行船前进的方向上存在屏障，飞行船也可以将其穿透并继续前进，但此时需要额外支付费用 $B$。例如，下图中飞行船从 $(6,5)$ 前进到 $(7,5)$，而 $(7,5)$ 处存在屏障，因此需要支付费用 $B$。

当飞行船完全通过隧道后，游戏结束。游戏得分为通过隧道过程中产生的总费用。显然，得分越低越好。游戏开始时，飞行船的 $y$ 坐标可以由玩家自由选择且不产生任何费用；游戏结束时，飞行船的 $y$ 坐标也不受限制。

即使隧道的大小和屏障的位置相同，当费用 $A$ 和费用 $B$ 改变时，游戏得分以及获得最小得分所需的飞行船移动方式也可能不同。你需要利用给定的隧道大小和屏障位置，在每次费用 $A$ 和费用 $B$ 改变时，计算可能得到的最小游戏得分。为此，你必须实现以下两个函数。

实现细节

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

该函数在最初被调用，且只会被调用一次。$N$ 和 $M$ 表示隧道的大小 $N \times M$。$Y1$ 和 $Y2$ 是长度为 $N$ 的数组，用于表示屏障的位置。若在 $x=i$ 处存在一个从 $y=Y1[i]$ 到 $y=Y2[i]$ 的屏障，则 $Y1[i]$ 和 $Y2[i]$ 的值分别为该区间的起点和终点。

long long minimize(int A, int B);

$A$ 表示飞行船进行一次瞬间移动的费用，$B$ 表示飞行船穿透一次屏障的费用。该函数需要返回飞行船通过隧道所需的最小总费用。

你需要提交一个名为 breakthru.cpp 的文件，其中必须实现以下函数：

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

这些函数必须按照上述说明正确工作。你可以自行实现并使用其他内部函数。提交的代码不得进行输入输出操作，也不得访问其他文件。

输入格式（grader 示例）

grader 按如下格式读取输入：

• 第 1 行：$N\ M\ Q$ （$N \times M$：隧道大小，$Q$：询问次数）
• 第 $2$ 行到第 $N+1$ 行：$Y1\ Y2$ （表示 $x=i$ 处的屏障在 $y=Y1$ 到 $y=Y2$ 之间）
• 第 $N+2$ 行到第 $N+Q+1$ 行：$A\ B$ （$A$：瞬间移动费用，$B$：穿透屏障费用）

grader 会对每个询问调用 minimize()，并将返回值逐行输出。

限制

• $1 \le N \le 200000$
• $1 \le M \le 10^5$
• $1 \le Q \le 200000$
• $1 \le Y1[i] \le Y2[i] \le M$
• $1 \le A, B \le 10^5$

子任务

子任务 1 [7 分]

$N \le 10000,\ M \le 10000$

子任务 2 [22 分]

$N \le 10^5$

子任务 3 [19 分]

$N \le 200000,\ M \le 20000$

子任务 4 [21 分]

$N \le 200000,\ M \le 50000$

子任务 5 [31 分]

无额外限制。

样例数据

输入

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

输出

1
3

下表展示了样例 1 中函数调用及其返回结果：

init(3, 5, {2, 0, 1}, {4, 2, 3})
minimize(2, 1) -> 1
minimize(3, 5) -> 3