Problem K. Kit of circuits

Author:А. Щуров   Time limit:2 sec
Input file:Standard input   Memory limit:512 Mb
Output file:Standard output  

Statement

You are to make a circuit using ni = 1ki given parts, so that circuit has the maximum possible number of free outputs.

There are n different types of parts: each type is characterized by the number of inputs (a) and outputs (b). Any input can be connected to any output. Unused outputs are called free outputs. When connecting a part to the circuit it is mandatory to use all inputs of this part.

The final circuit must have exactly one input so that you can connect the circuit to a single output source.

Input format

The first line contains an integer n — the number of part types.

The next n lines contain three integers ki ai bi — the number of parts of i-th type and a description of these parts.

Output format

Output must contain a single integer: the maximum possible number of free outputs after assembly and connection of the circuit to the source. The final circuit may not contain any parts, then only the source output is free.

Constraints

0 ≤ n ≤ 106

1 ≤ k, a, b ≤ 106

Sample tests

No. Standard input Standard output
1
4
1 3 4
2 1 2
1 7 8
1 1 3
6
2
3
1 3 4
1 5 6
3 7 7
1

0.059s 0.008s 13