#10534. 任务调度

有 个任务和两台机器 A 与 B。每个任务都需要既在机器 A 上执行，又在机器 B 上执行.

第 i 个任务需要在机器 A 上执行时间 ，且需要在机器 B 上执行时间 。最终的目标是所有任务在 A 和 B 上都执行完，且希望执行完所有任务的总时间尽量少。

当然问题没有这么简单，有些任务对于先在机器 A 上执行还是先在机器 B 上执行有一定的限制。据此可将所有任务分为三类：

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

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

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

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

输入的第一行只有一个正整数 ，表示任务的个数。

接下来的 行，每行是用空格隔开的三个正整数 ，分别表示第 i 个任务的类别（类别 1，2，3 的定义如上）以及第 个任务需要在机器 A 和机器 B 上分别执行的时间。

输出仅包含一个正整数，表示所有任务都执行完所需要的最少总时间。

输入 #1

3
3 5 7
1 6 1 
2 2 6

输出 #1

14

样例 1 解释

一种最优任务调度方案为：

机器 A 上执行的各任务依次安排如下：

任务 1 (0→5)，任务 2 (5→11), 任务 3 (11→13)；

机器 B 上执行的各任务依次安排如下：

任务 3 (0→6), 任务 1 (6→13), 任务 2 (13→14)，

这样，所有任务都执行完所需要的总时间为 14。

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