Farmer John хочет достаточно воды для коров и рисует $N$ труб ($1 \le N \le 700$), соединяющих колодец и коровник. Он удивлён хаотичной сетью труб разного размера и хочет вычислить поток.
Две последовательные трубы пропускают минимум их пропускных способностей. Трубы 5 и 3 эквивалентны одной 3:
+---5---+---3---+ -> +---3---+
Параллельные трубы пропускают сумму способностей:
+---5---+
---+ +--- -> +---8---+
+---3---+Тупиковую трубу можно удалить: она не добавляет к общему потоку:
+---5---+
---+ -> +---3---+
+---3---+--Все лабиринты труб можно свести этими правилами к единой пропускной способности.
По схеме найдите способность между колодцем (A) и коровником (Z).
Пример с буквенными именами узлов:
+-----------6-----------+
A+---3---+B +Z
+---3---+---5---+---4---+
C DBC и CD объединяются:
+-----------6-----------+
A+---3---+B +Z
+-----3-----+-----4-----+
DBD и DZ объединяются:
+-----------6-----------+
A+---3---+B +Z
+-----------3-----------+Две ветви BZ объединяются:
B
A+---3---+---9---+ZAB и BZ объединяются до общего потока 3:
A+---3---+Z
Напишите программу чтения труб с двумя концами и расчёта потока от 'A' до 'Z'. Все тестовые сети сводятся указанными правилами.
Труба $i$ соединяет разные $a_i$, $b_i$ (оба в 'A-Za-z') с потоком $F_i$ ($1 \le F_i \le 1,000$). Имена в верхнем и нижнем регистре различны.
Для первых 50 отправок система даёт дополнительную информацию о тестах.
Входные данные
- Строка 1: целое $N$.
- Строки $2,\ldots,N+1$: строка $i+1$ описывает трубу $i$ двумя буквами и целым через пробел: $a_i$, $b_i$, $F_i$.
Выходные данные
- Строка 1: целое, максимальный поток из колодца ('A') в коровник ('Z').
Примеры
Входные данные 1
5 A B 3 B C 3 C D 5 D Z 4 B Z 6
Выходные данные 1
3
Автор задачи: Rob Kolstad, 2008