Description

A delegation of a certain country, consisting of $m$ people, is traveling to Australia to participate in IOI 2013. They are currently waiting in line at the airport to check in. There are $n$ check-in counters open. Some officers work more efficiently than others, so the counters operate at different speeds. At the $k$-th counter, it takes $t_k$ seconds to complete the check-in for one passenger, and the delegation members happen to know these exact numbers.

At the beginning, all counters are ready to accept the next passenger, and now only the members of our delegation are allowed to queue. A person can take an available counter and start checking in only after everyone in front of them has left the queue (started check-in, not necessarily finished). At that moment, the person may immediately take an idle counter (if there is one), but they may also choose to wait for another counter with faster processing time to become idle.

The delegation members are computer science geniuses, and they decide to have everyone finish check-in as early as possible. Your task is to find the minimum time needed to finish check-in.

Input Format

The input has a total of $n+1$ lines.

The first line contains two integers $n, m$, representing the number of counters and the number of people in the delegation.
The next $n$ lines each contain one integer $t_k$, meaning the time needed for the $k$-th counter to process one passenger’s check-in.

Output Format

Output only one line with one integer, indicating the minimum time needed to finish check-in (in seconds).

2 6
7
10

28

7 10
3
8
3
6
9
2
4

8

Hint

[Sample 1 Explanation]

For Sample $1$, there are two counters with processing times $7$ seconds and $10$ seconds. Among the six people in the delegation, the first two people immediately take these two counters. At second $7$, the first counter becomes idle, and the third person takes it. At second $10$, the fourth person takes the second counter. At second $14$, the fifth person takes the first counter. At second $20$, the second counter becomes idle again, but the sixth person decides to wait one more second (until second $21$) so that the first counter becomes idle, and then takes it. In this way, check-in can be completed in $28$ seconds. If the sixth person did not wait for the faster counter, check-in would take $30$ seconds.

[Constraints]

There are $8$ test points in total. The constraints for each test point are shown in the table below:

[Source]

This problem comes from COCI 2012-2013 CONTEST 3 T4 AERODROM. With the original testdata configuration, the full score is $120$ points.

Translated and整理 (zhěnglǐ: compiled/edited) by Eason_AC.

Translated by ChatGPT 5