Description

There are $n$ tasks and two machines, A and B. Each task must be processed on both machines.

The $i$-th task requires time $a_i$ on machine A and time $b_i$ on machine B. The goal is to finish all tasks on both A and B while minimizing the total time to complete all tasks. However, some tasks have restrictions on whether they must be processed on A first or on B first. Based on this, all tasks are divided into three categories:

1. The task must be processed on machine A first, then on machine B.
2. The task must be processed on machine B first, then on machine A.
3. The task has no restriction and may be processed on machine A first or on machine B first.

Given each task’s category and its processing times on machines A and B, find the minimum total time required to finish all tasks according to the rules.

Input Format

The first line contains a single positive integer $n$, the number of tasks.

Each of the next $n$ lines contains three space-separated positive integers $t_i, a_i, b_i$, denoting the category of task $i$ (categories $1$, $2$, and $3$ are as defined above) and the processing times of task $i$ on machines A and B, respectively.

Output Format

Output a single integer, the minimum total time required to finish all tasks.

3
3 5 7
1 6 1 
2 2 6

14

Hint

Sample 1 Explanation:

One optimal scheduling plan is:

On machine A, schedule the tasks in order: Task $1\ (0\to 5)$, task $2\ (5\to 11)$, task $3\ (11\to 13)$;

On machine B, schedule the tasks in order: Task $3\ (0 \to 6)$, task $1\ (6 \to 13)$, task $2\ (13 \to14)$,

so the total time required to finish all tasks is $14$.

Constraints:

For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 20$, $1 \le a_i \le 10^3$, $1 \le t_i \le 3$, and the number of tasks with $t_i = 3$ does not exceed $10$.

Translated by ChatGPT 5