printРабочее место участника

printЗадачи

1311. Веревочные мосты

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

Эльфы для скрытного передвижения по лесу установили веревочные мосты, соединяющие последовательно несколько деревьев. Каждый мост имеет максимальную прочность, которая ограничивает число эльфов, одновременно находящихся на нем. Для быстрого перемещения большой группы эльфов по этим мостам, они придерживаются следующих правил:
  • Если два или больше эльфа могут перейти по мосту, они двигаются по нему вместе группой, не превышающей ограничения по прочности моста, следуя шаг в шаг, чтобы предотвратить раскачивание моста. По той же причине на мосту в каждый момент времени может быть только одна группа (группа может состоять из одного эльфа).
  • Как только мост освобождается, на него вступает следующая группа, ожидающая перехода через этот мост, не дожидаясь других эльфов, которые переходят предыдущий мост.
Напишите программу, которая вычисляет время перехода по указанным правилам для `P` эльфов по заданному набору мостов.
В первой строке ввода содержатся два целых числа `B` и `P` (`1\ ≤\ B,\ P\ ≤\ 20`) – количество мостов и количество эльфов. В следующих `B` строках содержатся по два целых числа `C_i` и `T_i` (`1\ ≤\ C_i\ ≤\ 5`, `1\ ≤\ T_i\ ≤\ 100`) – ограничение на количество эльфов на `i`-ом мосте и время перехода в секундах через `i`-й мост.
Вывести одно целое число – общее время перехода всех эльфов через последовательность мостов.

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

1 8
3 25

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

75
Сначала мост переходит группа из 3 эльфов за 25 секунд, затем еще одна группа из 3 эльфов, а затем группа из оставшихся 2 эльфов.

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

4 8
1 8
4 30
2 10
1 12

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

162
loading