The "Flagship Fleet of Tatarstan" airline offers a new type of business class on its aircraft. The aircraft cabin consists of $n$ seats arranged in a single row along the aisle. We introduce a coordinate line along the cabin such that the distance between seats is 1, and the seats have coordinates from 1 to $n$.
During the flight, a steward needs to walk through the plane and distribute drinks to all passengers. There are $k$ different types of drinks, numbered from 1 to $k$. Each passenger receives one serving of one drink; the passenger orders their preferred type of drink when booking the ticket, so all passenger preferences are known in advance.
Drinks are bottled, with each bottle holding $p$ servings of one drink type. The drink cart can hold at most $m$ bottles of any drink types; it is guaranteed that $m \geqslant k$.
Passengers are served in increasing order of their seat numbers. Initially, the cart is at the beginning of the cabin at point 0, and it can be filled with any types of drinks before service begins. After service is completed, the cart must arrive at point $n+1$. At points 0 and $n+1$, there may be storage rooms: either one storage room at one end of the cabin, or two storage rooms at both ends, which have a sufficient supply of each type of drink. In these storage rooms, empty bottles can be unloaded from the cart and full bottles can be loaded.
As service progresses, drinks will be consumed, so from time to time it becomes necessary to replenish the supply of drinks on the cart in one of the storage rooms. If at the current moment the cart is opposite seat $i$, then to reach the storage room at point 0, it is necessary to travel a distance of $i$, and to reach the storage room at point $n+1$, it is necessary to travel a distance of $n+1-i$. In the storage rooms, one can unload empty bottles from the cart and load bottles of any drink types into the empty spaces. The bottles being unloaded must be empty; it is not allowed to unload bottles that still contain drinks, or to pour out drinks. It is not allowed to transfer remaining drinks between different bottles. It is allowed to load more than one bottle of the same type onto the cart. After this, the cart must travel the distance from the storage room to the seat of the first unserved passenger to continue service.
Determine the minimum distance the cart must travel to move from point 0 to point $n+1$ and serve all passengers.
Input
The first line of the input contains four integers $n, m, k, p$ ($3 \leqslant n \leqslant 10^6$, $1 \leqslant p \leqslant 10^6$, $1 \leqslant k \leqslant m \leqslant 10^6$) — the number of seats in the cabin, the capacity of the cart, the number of drink types, and the capacity of each bottle, respectively.
The next line contains an integer $c$ ($1 \leqslant c \leqslant 3$) — a parameter describing the presence of storage rooms in the cabin. If $c=1$, the storage room is located only at point $n+1$. If $c=2$, the storage room is located only at point 0. If $c=3$, storage rooms are located at both ends of the cabin.
The next line contains $n$ integers $a_i$ ($1 \leqslant a_i \leqslant k$) — the types of drinks ordered by the passengers.
Output
The program must output a single integer — the minimum distance the cart must travel.
Examples
Input 1
5 2 2 1 1 1 2 1 2 1
Output 1
14
Input 2
8 3 2 2 2 1 1 1 1 1 2 2 2
Output 2
17
Input 3
8 3 3 2 3 1 2 2 3 2 3 2 1
Output 3
15
Input 4
8 6 6 2 2 1 2 3 4 3 5 6 1
Output 4
9
Input 5
7 3 3 1 3 1 2 3 2 2 1 3
Output 5
16