31893번 - Bridging the Gap 다국어

문제

A group of walkers arrives at a river in the night. They want to cross a bridge, which can hold a limited number of walkers at a time. The walkers have just one torch, which needs to be used when crossing the bridge. Each walker takes a certain time to cross; a group crossing together must walk at the slowest walker’s pace. What is the shortest time it takes for all walkers to cross the bridge?

For example, Sample Input 1 assumes the bridge can hold 2ドル$ walkers at a time and there are 4ドル$ walkers with crossing times 1ドル$ minute, 2ドル$ minutes, 5ドル$ minutes and 10ドル$ minutes, respectively. The shortest time of 17ドル$ minutes can be achieved by the following sequence of crossings. First, the two fastest walkers cross in 2ドル$ minutes. Second, the fastest walker crosses back in 1ドル$ minute. Third, the two slowest walkers cross in 10ドル$ minutes. Fourth, the second-fastest walker crosses back in 2ドル$ minutes. Fifth, the two fastest walkers cross in 2ドル$ minutes.

입력

The first line of input contains two integers $n$ and $c,ドル where $n$ (2ドル≤n≤10^4$) is the number of walkers, and $c$ (2ドル≤c≤10^4$) is the number of walkers the bridge can hold at a time.

Then follows a line containing $n$ integers $t_1,\dots ,t_n$ (1ドル≤t_i≤10^9$ for all $i$). The $i$th walker takes time $t_i$ to cross.

출력

Output the minimum total time it takes for the entire group to cross the bridge.

제한

힌트