Humanity's Last Code Exam / 2022_S / 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:

1. First, the two fastest walkers cross in 2 minutes.
2. Second, the fastest walker crosses back in 1 minute.
3. Third, the two slowest walkers cross in 10 minutes.
4. Fourth, the second-fastest walker crosses back in 2 minutes.
5. Fifth, the two fastest walkers cross in 2 minutes.

### Input

The first line of input contains two integers n and c, where 2≤n≤10⁴ is the number of walkers, and 2≤c≤10⁴ is the number of walkers the bridge can hold at a time.

Then follows a line containing n integers t₁,t₂,…,t_(n) (1≤t_(i)≤10⁹ for all i). The i-th walker takes time t_(i) to cross.

### Output

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

### Sample Input 1

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:

1. First, the two fastest walkers cross in 2 minutes.
2. Second, the fastest walker crosses back in 1 minute.
3. Third, the two slowest walkers cross in 10 minutes.
4. Fourth, the second-fastest walker crosses back in 2 minutes.
5. Fifth, the two fastest walkers cross in 2 minutes.

### Input

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

Then follows a line containing \( n \) integers \( t_1, t_2, \ldots, t_n \) (\( 1 \leq t_i \leq 10^9 \) for all \( i \)). The \( i \)-th walker takes time \( t_i \) to cross.

### Output

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

### Sample Input 1