|
Транспортные потоки на улицах города можно смоделировать движением жидкости. Имеется
набор трасс, соединенных между собой P перекрестками, перенумерованными, начиная с 1. Для
каждой трассы задана пропускная способность – количество воды, пропускаемой в единицу времени.
Заданные пропускные способности являются натуральными числами, не превышающими 10000.
Необходимо вычислить пропускную способность всей системы при подаче воды в точке 1 и
отборе в точке P и выдать рекомендации по увеличению пропускной способности всей сети как
минимум на N единиц минимальными затратами. Считается, что цена увеличения пропускной
способности любого элемента сети на M единиц равна M рублей.
Input
В первой строке заданы количество перекрестков 1<P<=30 и число 1<N<=100.
В каждой из следующих P строк файла содержатся описания перекрестков: количество трасс R,
которые соединяет этот перекресток с другими перекрестками, затем R пар чисел – номер
перекрестка, с которым он соединен трассой, и пропускная способность этой трассы. Все трассы
являются двусторонними, т.е. поток возможен в оба направления. Пара перекрестков напрямую
может быть связана не более, чем одной трассой. Все числа в строках файла целые и разделены
пробелами.
Общее количество трасс не более 100, количество трасс, сходящихся в одном перекрестке – не
более 10.
В случае, если модифицировать сеть или проложить путь невозможно - вывести 0 0
Output
Необходимо вывести два числа, разделенных
пробелом, – пропускную способность системы и минимальную стоимость модернизации.
Примечание 1. Красным цветом выделено уточнение, которого не было в оригинальной задаче
Примечание 2. Тесты не оригинальные
Sample
| Input | Output |
|---|
Пример 1. Вход:
5 10
0
1 1 100
1 2 4
1 3 100
1 4
| Пример 1. Выход:
4 20
|
Пример 2. Вход:
6 14
0
1 1 5
1 1 6
1 1 20
1 4 20
3 5 8 3 5 2 5
| Пример 2. Выход:
18 15
|
| 