Маленький, но гордый мышонок решил съесть все
ягоды с дерева вишни. Вишня — это обычное дерево, ветки
которого разветвляются и не срастаются снова. Из точки, где
заканчивается ветка, могут начинаться другие ветки или может
расти некоторое количество ягод.
Ветки дерева настолько длинные, что силы мышонка
заметно истощаются, когда он ползет по веткам. Когда мышонок
проползает по ветке один метр, он теряет единицу запаса
полезных веществ (ПВ), которые содержатся в его организме.
Съедание одной вишни пополняет запас ПВ на единицу. Если запас
ПВ становится отрицательным, мышонок погибает.
Задание
Напишите программу CHERRY, которая по информации
о дереве определяет минимальное количество единиц ПВ которое
мышонок должен иметь, чтобы съесть все ягоды с дерева и
вернуться на землю. При этом, на протяжении движения текущий
запас ПВ не может быть отрицательным.
Движение всегда начинается и заканчивается в
начале ветки с номером 1, которая соответствует стволу.
Входные данные
В первой строке входного файла CHERRY.DAT
содержится целое число N (1£N£100) — количество веток в
дереве. Дальше идут N строк, которые описывают дерево.
Каждая (i+1)-ая строка файла задает информацию про
i-ую вершину. Первым в строке идет целое число L
(1£L£30 000), которое
задает длину ветки. Вторым — количество веток K,
которые начинаются с конца i-ой ветки. Далее следует
K чисел — номера этих веток. Если число K для
ветки равно нулю, то третье число задает количество ягод
V (0£V£30 000), которые
растут на конце ветки.
Выходные данные
В единственной строке файла CHERRY.SOL должно
находится целое число — минимальное количество единиц ПВ,
которое должен иметь мышонок, для восхождения на дерево,
съедания всех ягод и возвращения на землю.
Пример входных данных
8
5 3 6 5 7
5 0 10
9 0 1
4 0
19
11 0 50
5 2 2 4
3 2 8 3
4 0 0
Пример выходных данных
