Bóas is constructing a new university building and is planning out a room to store chairs in. This room can be as tall as he pleases but due to how the other rooms are planned out it must be exactly $w$ meters wide. The chairs he intends to store are all identical apart from their colour. They are all one meter wide and they can be stacked on top of one another. If $k$ chairs are stacked on top of one another the stack ends up being $k$ meters tall.

Bóas wants the storage room to be organized, so all the chairs in a given stack must be the same colour. There is also only space for $w$ stacks of chairs since the stacks have to be against the $w$ meter wide wall. Bóas not only wants the storage room to be organized, he wants it to look organized. Bóas measures disorganization as being the area of the wall behind the chairs minus the front area of the chairs. Can you find the smallest least disorganized stacking of the chairs if he stacks the chairs according to the rules above?

A possible solution to sample input $1$. The disorganization score is the area of the white sections, $3 + 2 + 1 + 3 = 9$.


The first line of the input contains two integers, $1 \leq n \leq 10^5$ and $n \leq w \leq 10^9$ where $n$ is the number of colours Bóas’s chairs have and $w$ is the width of the storage room in meters. The second and last line of the input contains $n$ integers $1 \leq e_ i \leq 10^9$, where $e_ i$ is the number of chairs in Bóas has in the $i$-th colour.


The only line of the output should contain the minimum disorganization Bóas can achieve.

Sample Input 1 Sample Output 1
5 23
21 14 24 7 17
Sample Input 2 Sample Output 2
5 23
13 19 19 30 1
CPU Time limit 1 second
Memory limit 1024 MB
Languages English, Íslenska
Bergur Snorrason and Atli Fannar Franklín
Source Forritunarkeppni Háskóla Íslands 2019
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in