题目背景

请使用 C++17 或 C++20 提交本题

你需要在程序开头加入如下代码：

#include <vector>

void init(int N, int M, std::vector<int> Y1, std::vector<int> Y2);
long long minimize(int A, int B);
  

题目译自 2020년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사 T2「 뚫기」

题目描述

在不久的将来，新加坡流行一种叫做「穿越」的游戏。游戏规则很简单：玩家需要控制一个楔形飞船从左到右穿过一个 $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, Y_1[X])$ 到 $(X, Y_2[X])$ 有一个障碍物，则 $Y1[X]$ 和 $Y2[X]$ 分别表示 $Y_1$ 和 $Y_2$。

long long minimize(int A, int B);

• 参数 $A$ 是飞船瞬移一次的费用，$B$ 是飞船穿过一次障碍物的费用。该函数返回飞船穿过隧道所需的最小费用。

你需要提交一个代码，该代码中实现以下函数：

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

这些函数应按照上述描述工作。当然，你可以创建其他函数并在内部使用。提交的代码不应执行输入输出操作或访问其他文件。

输入格式

示例评测程序按以下格式读取输入：

• 第 $1$ 行：$N\,M\,Q$（$N \times M$：隧道的大小，$Q$：查询的数量）
• 第 $2+i\ (0 \leq i \leq N-1)$ 行：$Y_1\,Y_2$（$x$ 坐标为 $i$ 的障碍物的 $y$ 坐标位置从 $Y_1$ 到 $Y_2$）
• 第 $2+N+i\ (0 \leq i \leq Q-1)$ 行：$A\,B$（$A$：瞬移费用，$B$：穿过障碍物的费用）

输出格式

示例评测程序对每个查询调用你的代码中的 minimize() 函数，并输出返回值。

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$

数据范围

对于所有输入数据，满足：

• $1 \leq N \leq 10^4$
• $1 \leq M \leq 10^{9}$
• $1 \leq Q \leq 10^{6}$
• $0 \leq Y_1 \leq Y_2 \leq M-1$
• $0 \leq A, B \leq 10^{9}$

详细子任务附加限制及分值如下表所示。

子任务编号	分值	子任务附加限制
$1$	$7$	$Q=1, N \leq 3,000, M \leq 3,000$
$2$	$22$	$Q \leq 50$
$3$	$19$	$N \leq 500$
$4$	$21$	$N \leq 2,500$
$5$	$31$	无附加限制