Задача K. Kit of circuits ≡

Условие

Необходимо из ∑ni = 1k_i заданных деталей составить такую схему, у которой количество свободных выходов максимально.

Существует n различных типов деталей: каждый тип характеризуется количеством входов (a) и выходов (b). Любые входы можно подключать к любым выходам. Неиспользуемые выходы называются свободными. При подключении детали к схеме нужно обязательно использовать все входы этой детали.

У итоговой схемы должен быть ровно один вход, чтобы можно было подключить схему к источнику с одним выходом.

Формат входных данных

В первой строке входные данные содержат целое число n — количество типов деталей.

В следующих n строках содержится по три целых числа k_i a_i b_i — количество деталей i-го типа и описание этих деталей.

Формат выходных данных

Нужно вывести одно целое число: максимальное количество свободных выходов после сборки и подключения схемы к источнику. Итоговая схема может не содержать деталей, тогда свободным будет только выход источника.

Ограничения

0 ≤ n ≤ 10⁶

1 ≤ k, a, b ≤ 10⁶

Примеры тестов

4
1 3 4
2 1 2
1 7 8
1 1 3

6

3
1 3 4
1 5 6
3 7 7

1