Подразделы

Другие разделы

Дата и время

19/12/2024 19:42:09

Авторизация

2400. Делёж

Делёж

Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Али-баба решил раздать сокровища из пещеры разбойников бедным. Али-Баба достает предметы из пещеры по одному и отдает их самым бедным среди присутствующих (с наименьшей суммарной стоимостью уже полученных предметов). Если есть несколько человек с одинаковой минимальной суммарной стоимостью предметов, то очередной предмет отдается человеку с наименьшим номером среди них.

Напишите программу, которая определяет конечное распределение сокровищ среди бедняков.

Первая строка ввода содержит два целых числа – количество предметов в пещере `N` (`1\ ≤\ N\ ≤\ 10^5`) и количество бедняков `K` (`1\ ≤\ K\ ≤\ 10^5`). Вторая строка ввода содержит `N` целых чисел в диапазоне от 1 до 10000 – стоимость предметов в пещере в порядке распределения.

Для каждого человека вывести на отдельной строке по два целых числа – количество предметов, которое достанется ему при дележе, и суммарную стоимость предметов. В `i`-й строке нужно вывести результат для `i`-го человека.

Пример ввода

6 3
10 1 2 3 20 30

Пример вывода