There are $N$ tasks and two machines, A and B. Each task must be executed on both machine A and machine B. The $i$-th task requires $A_i$ time on machine A and $B_i$ time on machine B. The final goal is to complete all tasks on both machines while minimizing the total time required to finish all tasks. The problem is complicated by constraints on the order of execution for some tasks. Based on this, all tasks can be divided into three categories:

1. The task must be executed on machine A first, then on machine B.
2. The task must be executed on machine B first, then on machine A.
3. There are no restrictions; the task can be executed on machine A first or on machine B first.

Given the category and the required execution time on machine A and machine B for each task, find the minimum total time required to complete all tasks according to the regulations.

Input

The first line of the input contains a single positive integer $N$ ($1 \le N \le 20$), representing the number of tasks. The following $N$ lines each contain three space-separated positive integers $T_i, A_i, B_i$ ($1 \le T_i \le 3, 1 \le A_i, B_i \le 1000$), representing the category of the $i$-th task (as defined above) and the time required for the $i$-th task on machine A and machine B, respectively.

Output

Output a single positive integer representing the minimum total time required to complete all tasks.

Examples

Input 1

3
3 5 7
1 6 1
2 2 6

Output 1

14

Note

One optimal task scheduling scheme is: Tasks on machine A are scheduled in the order: Task 1 (0 - 5), Task 2 (5 - 11), Task 3 (11 - 13). Tasks on machine B are scheduled in the order: Task 3 (0 - 6), Task 1 (6 - 13), Task 2 (13 - 14). Thus, the total time required to complete all tasks is 14.