Description

A factory has two machines, A and B. Any product can be completed by either machine alone, or jointly by both machines. Due to machine performance and product characteristics, the time needed for different machines to process the same product differs; if both machines process a product simultaneously, the completed workload also differs.

One day, the factory receives $n$ product processing tasks, each with a different workload.

Your task: given the time $t_1$ to process a task on machine A, the time $t_2$ on machine B, and the time $t_3$ when both machines jointly process it, schedule the tasks to minimize the total time to finish all $n$ tasks.

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain three non-negative integers $t_1,t_2,t_3$, representing for the $i$-th task the time required on machine A, on machine B, and when both machines jointly process it, respectively. If the given time $t_1$ or $t_2$ is $0$, it means the task cannot be processed on that machine. If $t_3$ is $0$, it means the task cannot be jointly processed by both machines.

Output Format

Output a single integer on one line, the minimum total time to complete all $n$ tasks.

5                            
2 1 0
0 5 0
2 4 1
0 0 3
2 1 1

9

Hint

For all testdata, $1\le n\le 6\times 10^3$, $0\le t_1,t_2,t_3\le 5$.

Translated by ChatGPT 5