Задача C. Chaos
Розставляти кiстки домiно i спостерiгати за їх падiнням - недостатньо цiкаве заняття для Дока Брауна. Тому вiн придумав бiльш математичне розвага. На дошцi знаходяться N чисел. Док багато разiв застосовує наступний алгоритм:
- Вибирає K будь-яких чисел, написаних на дошцi, i стирає їх.
- З цих K чисел обирає будь-яких K − 1 число i обчислює їх середнє арифметичне, округлюючи донизу.
- Потiм вiн записує на дошку отримане середнє арифметичне рiвно K − 1 разів.
Док припиняє виконувати алгоритм, коли у нього занадто мало чисел для виконання алгоритму.
До прикладу, розглянемо випадок, коли K = 3. Нехай було обрано числа 1,2 та 4. Док може записати двiчi число 1 (середнє арифметичне чисел 1 та 2, округлене донизу), двiчi число 2 (середнє арифметичне чисел 1 та 4, округлене донизу) або ж двiчi записати число 3 (середнє арифметичне чисел 2 та 4).
Одного разу Мартi спостерiгав за цiєю забавою, яка схожа на послiдовнiсть випадкових дiй. В кiнцi Док зауважив, що найбiльше з чисел, що залишились на дошцi, вийшло максимально можливим. Мартi не вiрить Доку, але вiн запам’ятав числа, якi спочатку були написанi на дошцi. Вiн просить вас написати програму, яка визначить максимальне можливе значення чисел, якi могли залишитися на дошцi пiсля виконання алгоритму.
Технiчнi умови
Програма Chaos читає два цiлих числа N,K(1 ≤ N,K ≤ 106) кiлькiсть чисел, записаних на дошцi та кiлькiсть чисел, якi Док щоразу обирає для застосування алгоритму. Далі програма читає N цiлих чисел, кожне з яких не перевищує 109 за абсолютною величиною - числа, з самого початку записанi на дошцi.
Програма має виводити єдине число - максимальне число, що може залишитися на дошцi пiсля виконання необхiдної кiлькостi крокiв алгоритму.
|
Введення |
Виведення |
|
3 3 1 4 2 |
3 |
|
5 4 7 7 7 7 7 |
7 |