“鞑靼斯坦旗舰舰队”航空公司在其飞机上提供一种新型商务舱。飞机客舱由 $n$ 个座位组成，沿过道排成一排。我们沿客舱建立一条坐标轴，使得座位之间的距离为 $1$，且座位坐标从 $1$ 到 $n$。
在飞行过程中，乘务员需要穿过客舱为所有乘客分发饮料。饮料共有 $k$ 种，编号为 $1$ 到 $k$。每位乘客获得一份某种饮料，乘客在预订机票时会预订其偏好的饮料种类，因此所有乘客的偏好都是预先知道的。
饮料装在瓶子里，每瓶可容纳 $p$ 份同种饮料。饮料推车最多可装载 $m$ 瓶任意种类的饮料，保证 $m \geqslant k$。
乘客按座位号递增的顺序接受服务。最初，推车位于客舱起点的 $0$ 点，在开始服务前，可以将其装满任意种类的饮料。服务结束后，推车必须到达 $n+1$ 点。在 $0$ 点和 $n+1$ 点处可能设有储藏室：要么在客舱的一端设有一个储藏室，要么在两端各设有一个储藏室，储藏室内存有充足的各种饮料。在这些储藏室中，可以从推车上卸下空瓶并装上满瓶。
在服务过程中，饮料会被消耗，因此有时需要前往其中一个储藏室补充推车上的饮料储备。如果当前推车位于 $i$ 号座位对面，则前往 $0$ 点处的储藏室需要行驶距离 $i$，而前往 $n+1$ 点处的储藏室需要行驶距离 $n+1-i$。在储藏室中，可以从推车上卸下空瓶，并在空位上装载任意种类的饮料瓶。卸下的瓶子必须是空的，不能卸下尚有剩余饮料的瓶子，也不能倾倒饮料。不允许在不同瓶子之间转移剩余饮料。可以在推车上装载多于一瓶的同种饮料。此后，推车必须从储藏室行驶到第一位未受服务乘客的座位，以继续服务。
请确定推车从 $0$ 点移动到 $n+1$ 点并为所有乘客提供服务所需行驶的最小距离。
输入格式
输入的第一行包含四个整数 $n, m, k, p$ ($3 \leqslant n \leqslant 10^6, 1 \leqslant p \leqslant 10^6, 1 \leqslant k \leqslant m \leqslant 10^6$)，分别表示客舱座位数、推车容量、饮料种类数和每瓶饮料的容量。
下一行包含一个整数 $c$ ($1 \leqslant c \leqslant 3$)，描述客舱内储藏室的分布情况。若 $c=1$，则储藏室仅位于 $n+1$ 点。若 $c=2$，则储藏室仅位于 $0$ 点。若 $c=3$，则两端均设有储藏室。
下一行包含 $n$ 个整数 $a_i$ ($1 \leqslant a_i \leqslant k$)，表示乘客预订的饮料种类。
输出格式
程序应输出一个整数，即推车必须行驶的最小距离。
样例
样例 1
输入
5 2 2 1 1 1 2 1 2 1
输出
14
样例 2
输入
8 3 2 2 2 1 1 1 1 1 2 2 2
输出
17
样例 3
输入
8 3 3 2 3 1 2 2 3 2 3 2 1
输出
15
样例 4
输入
8 6 6 2 2 1 2 3 4 3 5 6 1
输出
9
样例 5
输入
7 3 3 1 3 1 2 3 2 2 1 3
输出
16
说明
在第一个样例中，推车容量为 $m=2$ 瓶，每瓶 $p=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$。
在第二个样例中，推车容量为 $m=3$ 瓶，每瓶 $p=2$ 份。储藏室位于客舱起点。需要装载三瓶 $1$ 类饮料，为 $1$ 到 $4$ 号座位的乘客提供服务。之后两瓶 $1$ 类饮料耗尽，需要立即前往储藏室装载两瓶 $2$ 类饮料，然后为 $5$ 到 $8$ 号座位的乘客提供服务。
在第三个样例中，推车容量为 $m=3$ 瓶，每瓶 $p=2$ 份，储藏室位于客舱两端。为乘客提供服务需要两瓶 $2$ 类饮料和各一瓶 $1$ 类及 $3$ 类饮料，因此需要前往储藏室一次，将空的 $2$ 类饮料瓶更换为满瓶。最好在为 $3$ 号座位乘客提供服务后进行，推车应前往客舱起点的储藏室。
在第四个样例中，推车需要装载每种饮料各一瓶，由于每瓶可容纳两份饮料，这使得无需额外补充推车即可为所有乘客提供服务。
在第五个样例中，需要两次补充推车，一次是在为 $3$ 号座位乘客提供服务后，推车必须返回客舱起点的储藏室；第二次是在为 $6$ 号座位乘客提供服务后，返回客舱末端的储藏室。