Task Scheduling with Precedence Constraints

You are given n tasks and two machines A and B. Every task i needs to be processed on both machines, and it requires a_i time on machine A and b_i time on machine B. However, due to restrictions some tasks must be processed following a fixed order while others are free to choose the order. In particular, the tasks are divided into three categories:

• Category 1: The task i must be processed on machine A first then on machine B. In other words, its operations must be executed in the order: A then B.
• Category 2: The task i must be processed on machine B first then on machine A. That is, its operations must be executed in the order: B then A.
• Category 3: The task i has no ordering restriction – you may process it in either order (A→B or B→A). When scheduling, you are free to choose the order for each such task.

The two machines work in parallel but each machine can process at most one operation at a time. Moreover, for a task the second operation cannot start until its first operation completes. Your goal is to determine the minimum total time needed to finish all tasks while respecting these ordering constraints.

Note: For tasks with a fixed order (Category 1 or 2) the operations must be scheduled consecutively according to their prescribed order. However, tasks from different categories may be interleaved arbitrarily on the two machines as long as the machine capacity and precedence constraints are respected.

It turns out that an optimal schedule can be obtained by partitioning the Category 3 (free) tasks into two groups – one group to be scheduled as if they were Category 1 tasks and the other as if they were Category 2 tasks – and then ordering the tasks in each group optimally using a Johnson‐like rule. (See, for example, the classical two–machine flow shop scheduling problem.) In this problem the input size is small so that you can try all possible partitions of the free tasks.

The optimal overall finish time is at least the following lower bounds:

• The total processing time on machine A, i.e. \( S_A = \sum_{i=1}^{n} a_i \).
• The total processing time on machine B, i.e. \( S_B = \sum_{i=1}^{n} b_i \).
• For each task, its processing time (since its two operations in the forced order must be executed consecutively), i.e. \( \max_{1\le i \le n} (a_i+b_i) \).

An optimal schedule will combine these bounds appropriately. In this problem the number of tasks (n) is small (say, n up to 20) so that you can enumerate over all \(2^{k}\) ways of partitioning the free tasks (Category 3) between the two orders. For each partition, the tasks with fixed orders (Category 1 and Category 2) and the free tasks assigned to each order are scheduled using the classical Johnson algorithm (see below):

For tasks to be processed in the order A→B:

1. Divide the tasks into two sets: those with \(a_i \le b_i\) and those with \(a_i > b_i\).
2. Sort the first set in non‐decreasing order of \(a_i\) and the second set in non–increasing order of \(b_i\); then schedule the first set followed by the second set.

For tasks to be processed in the order B→A:

1. Divide the tasks into two sets: those with \(b_i \le a_i\) and those with \(b_i > a_i\).
2. Sort the first set in non‐decreasing order of \(b_i\) and the second set in non–increasing order of \(a_i\); then schedule the first set followed by the second set.

After simulating the schedule for each chain (by accumulating the processing times and taking into account waiting times so that for each task the second operation does not start before the first finishes), the overall finish time is the maximum among:

• Total processing time on machine A, \(S_A\).
• Total processing time on machine B, \(S_B\).
• The completion time of the chain scheduled as A→B.
• The completion time of the chain scheduled as B→A.

Your task is to compute and output the minimum possible overall finish time among all possible partitions of the free tasks.

inputFormat

The first line contains a single integer n (n ≤ 20), the number of tasks. Each of the next n lines contains three integers. The first integer is the task type: 1, 2, or 3. The next two integers are a_i and b_i (1 ≤ a_i,b_i ≤ 10⁴), representing the processing times on machines A and B, respectively.

Note: A task of type 1 must be processed in the order A→B; a task of type 2 must be processed in the order B→A; and a task of type 3 has no order restriction.

outputFormat

Output a single integer: the minimum total time needed to complete all tasks while respecting the given constraints.

sample

2
1 10 1
2 1 10

11