题目描述

译自 ROI 2024 Day1 T3. Кейс на рейс

在塔塔尔斯坦的旗舰航空公司，飞机上推出了一种新型的商务舱服务。客舱由一排沿着过道的座位组成，共有 $n$ 个座位。我们可以沿着客舱引入一个坐标轴，使得每个座位之间的距离为 $1$，座位编号从 $1$ 到 $n$。

在飞行过程中，空乘要走过飞机，为所有乘客提供饮料。饮料有 $k$ 种不同的类型，编号从 $1$ 到 $k$。每位乘客都会收到一份他们在预订机票时选择的饮料，因此所有乘客的偏好都是提前知道的。

饮料装在瓶子里，每瓶可以装 $p$ 份饮料。餐车最多可以装载 $m$ 瓶任意类型的饮料，保证 $m \ge k$。

乘客按照座位号的升序接受服务。最初，餐车位于客舱的起点（坐标为 $0$），并且可以在服务前装载任意类型的饮料。服务结束后，餐车需要到达坐标 $n+1$ 的位置。在坐标 $0$ 和 $n+1$ 的位置可能有储藏室：要么是客舱一端的一个储藏室，要么是两端各有一个储藏室，储藏室里有足够的各种饮料。在这些储藏室里，可以从餐车上卸下空瓶子并装载满瓶子。

随着服务的进行，饮料会被消耗，因此有时需要在某个储藏室中补充餐车上的饮料。如果当前餐车正对着编号为 $i$ 的座位，那么要到达坐标 $0$ 的储藏室需要移动 $i$ 的距离，而要到达坐标 $n+1$ 的储藏室需要移动 $n+1-i$ 的距离。在储藏室中，可以从餐车上卸下空瓶子，并在空位上装载任意类型的饮料瓶子。卸下的瓶子必须是空的，不能卸下还有饮料的瓶子或倒掉饮料。也不能将饮料从一个瓶子转移到另一个瓶子。可以在餐车上装载多于一瓶的同种饮料。之后，餐车需要从储藏室移动到第一个未服务乘客的座位，以继续服务。

请确定餐车从坐标 $0$ 移动到坐标 $n+1$ 并服务所有乘客所需移动的最短距离。

输入格式

输入的第一行包含四个整数 $n, m, k, p\ (3 \leq n \leq 10^6, 1 \leq p \leq 10^6, 1 \leq k \leq m \leq 10^6)$，分别表示客舱中的座位数量，餐车的容量，饮料类型的数量，每瓶饮料的容量。

下一行包含一个整数 $c\ (1 \leq c \leq 3)$，描述客舱中储藏室的存在情况。如果 $c=1$，则储藏室只在坐标 $n+1$ 处。如果 $c=2$，则储藏室只在坐标 $0$ 处。如果 $c=3$，则储藏室位于客舱的两端。

下一行包含 $n$ 个整数 $a_i\ (1 \leq a_i \leq k)$，表示乘客订购的饮料类型。

输出格式

程序应输出一个整数，表示餐车所需移动的最短距离。

5 2 2 1
1
1 2 1 2 1

14

餐车可以装载 $2$ 瓶饮料，每瓶 $1$ 份。储藏室位于车厢的尽头。最初，需要在餐车上装载 $1$ 号和 $2$ 号饮料瓶，这些饮料将被提供给 $1$ 号和 $2$ 号座位的乘客，餐车从 $0$ 移动到 $2$ 的距离为 $2$。之后，餐车需要移动到车厢尽头的储藏室（距离为 $4$），在餐车上装载 $1$ 号和 $2$ 号饮料瓶，然后返回到 $3$ 号座位（餐车移动距离为 $3$）。$3$ 号和 $4$ 号座位的乘客将获得 $1$ 号和 $2$ 号饮料（餐车从 $3$ 号座位移动到 $4$ 号座位的距离为 $1$）。之后，餐车需要再次前往储藏室（从 $4$ 号座位到储藏室的距离为 $2$），从储藏室返回到 $5$ 号座位（距离为 $1$），然后移动 $1$ 到车厢尽头。总移动距离为 $2+4+3+1+2+1+1=14$。

8 3 2 2
2
1 1 1 1 1 2 2 2

17

餐车可以装载 $3$ 瓶饮料，每瓶 $2$ 份。储藏室位于车厢起始端。需要在餐车上装载三瓶 $1$ 号饮料，服务 $1$ 号到 $4$ 号座位的乘客。之后，两瓶 $1$ 号饮料将被用完，需要立即前往储藏室，装载两瓶 $2$ 号饮料，然后服务 $5$ 号到 $8$ 号座位的乘客。

8 3 3 2
3
1 2 2 3 2 3 2 1

15

餐车可以装载 $3$ 瓶饮料，每瓶 $2$ 份，储藏室位于车厢两端。为了服务乘客，需要两瓶 $2$ 号饮料和各一瓶 $1$ 号和 $3$ 号饮料，因此需要一次前往储藏室，以便更换空的 $2$ 号饮料瓶。最好是在服务 $3$ 号座位的乘客后，餐车前往车厢起始端的储藏室。

8 6 6 2
2
1 2 3 4 3 5 6 1

9

餐车需要装载每种饮料一瓶，由于每瓶饮料可以提供两份，这将允许服务所有乘客，无需额外补充饮料。

7 3 3 1
3
1 2 3 2 2 1 3

16

餐车需要补充两次饮料，一次是在服务 $3$ 号座位的乘客后，餐车需要返回车厢起始端的储藏室，另一次是在服务 $6$ 号座位的乘客后，餐车需要前往车厢尽头。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。

子任务	分值	$c$ 的限制	$n$ 的限制	附加限制	子任务依赖
$1$	$5$	$c = 1$	$n \le 15$	$k \leq 15$
$2$	$8$		$n \le 2000$		$1$
$3$	$4$			$p = 1$
$4$	$7$				$1, 2, 3$
$5$	$8$	$c = 2$	$n \le 15$	$k \leq 15$
$6$	$10$		$n \le 2000$		$5$
$7$	$6$			$p = 1$
$8$	$9$				5, 6, 7
$9$	$10$	$c = 3$	$n \le 15$	$k \leq 15$
$10$	$13$		$n \le 2000$		$9$
$11$	$9$			$p = 1$
$12$	$11$				$9, 10, 11$