\(3^{rd}\) round, December \(15^{th}\), 2012

The Croatian delegation, consisting of M people, is travelling to IOI 2013 in Australia^{1}. They are
currently waiting in a queue for che\(ck-in\) at the airport. There are N che\(ck-in\) desks open. Some
officials work more efficiently than others, so the desks operate at different speeds. At the \(k-th\) desk,
T_{k} seconds are required to finish che\(ck-in\) of a single passenger, and members of our delegation happen
to know the exact numbers.
In the beginning, all desks are ready to accept the next passenger, and the delegation members are the
only people in the queue. A person can only occupy (start che\(ck-in\) at) an available desk when all people
in front of that person in the queue have left the queue (started, not necessarily finished, che\(ck-in\))
already. At that moment, the person can immediately occupy an available desk (if there is one), but can
also choose to wait for another (faster) desk to become available. Our delegation members, being
computer science geeks, make this decision in such a way that the moment when all of them have
finished che\(ck-in\) is as soon as possible. Your task is finding that moment in time.
Let us describe the scenario from the first example below. There are two desks, with processing times
of 7 and 10 seconds, respectively. Out of the six people in the delegation, the first two immediately
occupy the two desks. At time 7, the first desk is freed, and the third person occupies it. At time 10, the
fourth person occupies the second desk. At time 14, the fifth person occupies the first desk. At time 20,
the second desk is freed again, but the sixth person decides to wait another second (time 21) for the
first desk to become available, and then occupy it. This way, the che\(ck-in\) is completed by time 28. If
the sixth person hadn't waited for the faster desk, the che\(ck-in\) would have taken a total of 30 seconds.

In test data worth a total of 75 points, the number M will be at most 300 000.

^{1} Assuming, of course, that the Apocalypse didn't happen.
\(3^{rd}\) round, December \(15^{th}\), 2012

The first line of input contains two positive integers, N (\(1 \le N \le 100\,000\)), the number of desks, and
M (\(1 \le M \le 1\,000\,000\,000\)), the number of people in the delegation.
Each of the following N lines contains a number T_{k} from the problem statement (\(1 \le T_{k} \le 10^{9}\)).

The first and only line of output must contain the required minimum time in seconds.

생성자가 기록되지 않았습니다.

출처 COCI 2012/2013 Contest 3