Problem K. Kit of circuits ≡

Statement

You are to make a circuit using ∑ni = 1k_i 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 k_i a_i b_i — 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 ≤ 10⁶

1 ≤ k, a, b ≤ 10⁶

Sample tests

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