Minimum Setup Time

Sasha is organizing a local concert with n microphones, where each microphone i requires a setup time \(b_i\) minutes. There are k available crew members and each can set up one microphone at a time. The crew members can work simultaneously on different microphones. The objective is to minimize the time when the last microphone is set up.

In other words, given n integers \(b_1, b_2, \ldots, b_n\) representing the setup times and k crew members, determine the minimum total time required to set up all the microphones if the tasks are optimally distributed.

Note: If there is only one microphone, its setup time is the total time even if there are more than one crew members.

inputFormat

The input is read from standard input (stdin) and has the following format:

n k
b1 b2 ... bn

where:

• n is the number of microphones.
• k is the number of crew members.
• b1, b2, \ldots, bn are the setup times for the microphones.

outputFormat

Output a single integer to standard output (stdout) representing the minimum required time to set up all the microphones.

4 2
3 1 5 7

8