Background

Translated from ROI 2024 D1T3.

Problem Description

An airline offers a new type of business class, where the seats on the plane are arranged along the aisle. Suppose the total number of seats is $n$, and the seat positions are numbered from $1$ to $n$.

Each passenger has a drink preference. There are $k$ types of drinks, numbered from $1$ to $k$. Each passenger chooses exactly one drink. On the plane, drinks must be distributed to passengers from a small cart.

Each drink is stored in bottles. One bottle can serve $p$ passengers. In other words, one bottle has capacity $p$. The cart can carry at most $m$ bottles. It is guaranteed that $k \le m$.

Passengers are served in order of seat number from $1$ to $n$. The cart starts moving from the starting point in front of the seats (position $0$) and eventually reaches the ending point (position $n + 1$). While serving passengers, the cart may need to go to a storeroom to load new drinks. The storeroom may be located at the front starting point, or at the rear ending point, or at both ends.

If the cart is at seat position $i$, the distance to the storeroom at the starting point is $i$, and the distance to the storeroom at the ending point is $n + 1 - i$. During the trip, the cart may need to refill drinks. If the cart reaches a storeroom, it can unload empty bottles and load new ones. It is not allowed to unload bottles that still contain drinks. After refilling, the cart should return to the position of the first passenger who has not been served yet, and then continue serving forward.

You need to compute the minimum total distance the cart moves from $0$ to $n + 1$ in order to provide all passengers with their required drinks.

Input Format

The first line contains four integers $n$, $m$, $k$, and $p$, representing the number of seats, the cart's maximum number of bottles, the number of drink types, and the capacity of each bottle.

The second line contains an integer $c$, indicating the storeroom location. $c$ ranges from $1$ to $3$. $c=1$ means the storeroom is only at the ending point; $c=2$ means the storeroom is only at the starting point; $c=3$ means the storerooms are at both the starting and ending points.

The third line contains $n$ integers $a_i$, where $a_i$ is the type of drink required by the passenger at seat $i$.

Output Format

Output one integer, the minimum total distance the cart needs to move while serving all passengers.

5 2 2 1
1
1 2 1 2 1

14

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

17

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

15

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

Hint

In the first sample, the cart can carry $m = 2$ bottles, and each bottle contains $p = 1$ serving. The storeroom is located at the end of the cabin.

• First, the cart needs to load drinks $1$ and $2$. These will be distributed to the passengers at seats $1$ and $2$. The cart needs to travel a distance of $2$ from the starting point $0$ to position $2$, so $d_1=2$.
• Next, the cart needs to go to the storeroom at the end of the cabin (distance $4$), load drinks $1$ and $2$, and then return to seat $3$ (the cart needs to move a distance of $3$). Thus $d_2=4+3=7$.
• Then, the cart provides drinks $1$ and $2$ to the passengers at seats $3$ and $4$ (the cart moves a distance of $1$ between seats $3$ and $4$). Thus $d_3=1$.
• Finally, the cart needs to go to the storeroom again (the distance from seat $4$ to the storeroom is $2$), load drink $1$, return from the storeroom to seat $5$ (distance $1$), and after serving that passenger, move a distance of $1$ to the end of the cabin. Thus $d_4=2+1+1=4$.

The total distance is $d_1+d_2+d_3+d_4=2+7+1+4=14$.

In the second sample, the cart can carry $m = 3$ bottles, and each bottle contains $p = 2$ servings. The storeroom is at the front of the cabin. The cart needs to fully load $3$ bottles of drink $1$ and serve the passengers at seats $1$ to $4$. After that, $2$ bottles of drink $1$ will be used up, so it needs to immediately go to the storeroom to fill $2$ bottles of drink $2$, and then serve the passengers at seats $5$ to $8$ (if it goes back to the storeroom after serving passenger $5$ to refill, the travel distance will be longer).

In the third sample, the cart can carry $m = 3$ bottles, and each bottle contains $p = 2$ servings, with storerooms at both ends of the cabin. To serve the passengers, it needs $2$ bottles of drink $2$, and $1$ bottle each of drinks $1$ and $3$, so it must go to a storeroom to replace empty bottles. The best plan is to go to the front storeroom to exchange for drink $2$ after serving the passenger at seat $3$.

In the fourth sample, the cart needs to load $1$ bottle of each drink type, and since each bottle contains $2$ servings, it can serve all passengers without any extra refill.

In the fifth sample, two refills are needed. After serving passenger $3$, the cart needs to return to the front storeroom for the first refill, and the second refill happens after serving passenger $6$, when it goes to the rear storeroom.

The original problem has twelve subtasks, but due to Luogu limits they cannot all be uploaded here.

Constraints: for $100\%$ of the data, $3\le n\le 10^6,1\le p\le 10^6,1\le a_i\le k\le m\le 10^6,1\le c\le3$。

Translated by ChatGPT 5