Minimum Flight Service Trolley Movement Distance

An airline has introduced a new business class with seats arranged along a single aisle, numbered 1 to n (from front to back). Each passenger has a beverage preference among k types (numbered 1 to k). Each passenger will only receive the drink of his/her choice.

Beverages are provided on a trolley that starts at position 0 (in front of the first seat) and finishes at position n+1 (behind the last seat). Drinks come in bottles, and each bottle can serve p passengers. The trolley can carry at most m bottles at any time (and it is guaranteed that k ≤ m, so the trolley can initially hold at least one bottle for each drink type).

As the trolley moves along the row and serves the passengers in order, the bottles get consumed. When a bottle becomes empty and there are still upcoming passengers who require that beverage, the trolley must go to a storage room to reload. There are storage rooms at the front (at position 0) and at the rear (at position n+1). If the trolley is at seat i, the distance to the front storage is i and to the rear storage is n+1-i.

When a reload is needed, the trolley travels from the current seat position i to the chosen storage room, drops off the empty bottle(s) (note that bottles containing any drink cannot be removed), reloads the beverage, and then returns back to the first passenger that has not yet been served. The reloading cost for that event is therefore 2 × min(i, n+1-i) extra distance. In addition, the trolley always travels from position 0 to n+1 for serving the passengers.

Your task is to compute the minimum total travel distance the trolley must move in order to serve drinks to all passengers.

Note: For each drink type, if the passengers who choose that drink appear at positions i₁, i₂, ..., i_t in increasing order, then every time a bottle is used up (i.e. every p servings for that drink, except after the last serving), a reload is required. Concretely, if a drink type is requested by cnt passengers, then the number of reload events for that drink is ⌊(cnt-1)/p⌋, and the reload occurs at the position where the bottle’s capacity is just exhausted.

The total distance is then:

[ \text{Total Distance} = (n+1) + \sum_{\text{drink}=1}^{k} \sum_{j=1}^{\lfloor (cnt_{\text{drink}}-1)/p \rfloor} 2 \min(i_{j\cdot p}, n+1-i_{j\cdot p}) ]

inputFormat

The first line contains four integers n, k, p, and m:

• n — the number of seats (and thus passengers),
• k — the number of beverage types,
• p — the number of passengers that one bottle can serve,
• m — the maximum number of bottles that the trolley can carry.

The second line contains n integers, each between 1 and k, representing the beverage preference for each passenger in order.

outputFormat

Output a single integer representing the minimum total distance the trolley must travel to serve drinks to all passengers.

sample

5 2 2 3
1 2 1 1 2

12