[HNOI2011]任务调度
题号：NC20087
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

有 N 个任务和两台机器 A 与 B。每个任务都需要既在机器 A 上执行，又在机器 B 上执行，第 i 个任务需要在机器 A 上执行时间 Ai，且需要在机器 B 上执行时间 Bi。最终的目标是所有任务在 A 和 B 上都执行完，且希望执行完所有任务的总时间尽量少。当然问题没有这么简单，有些任务对于先在机器 A 上执行还是先在机器 B 上执行有一定的限制。据此可将所有任务分为三类：

  1. 任务必须先在机器 A 上执行完然后再在机器 B 上执行。

  2. 任务必须先在机器 B 上执行完然后再在机器 A 上执行。

  3. 任务没有限制，既可先在机器 A 上执行，也可先在机器 B 上执行。

现在给定每个任务的类别和需要在机器A和机器B上分别执行的时间，问使所有任务都能按规定完成所需要的最少总时间是多少。

输入描述:

从文件input.txt中读入数据，输入文件的第一行只有一个正整数N(1≤N≤20)，表示任务的个数。
接下来的N行，每行是用空格隔开的三个正整数Ti, Ai, Bi(1≤Ti≤3, 1≤Ai, Bi≤1000)，分别表示第i个任务的类别(类别1, 2, 3的定义如上)以及第i个任务需要在机器A和机器B上分别执行的时间。

输出描述:

输出文件 output.txt 仅包含一个正整数，表示所有任务都执行完所需要的最少总时
示例1

输入

复制 
3
3 5 7
1 6 1 
2 2 6

输出

复制 
14

说明

样例解释：一种最优任务调度方案为：机器A上执行的各任务依次安排如下：任务1(0 - 5), 任务2(5 - 11), 任务3(11 - 13)；机器B上执行的各任务依次安排如下：任务3(0 - 6), 任务 1(6 - 13), 任务2(13 - 14)，这样，所有任务都执行完所需要的总时间为14。

备注:

对于100%的数据，保证  的不超过10个。