Background

Special for beginners, ^_^

Description

有N个任务和两台机器A与B。每个任务都需要既在机器A上执行，又在机器B上执行，第i个任务需要在机器A上执行时间A， 且需要在机器B上执行时间B。最终的目标是所有任务在A和B上都执行完，且希望执行完所有任务的总时间尽量少。当然问题没有这么简单，有些任务对于先在机器A上执行还是先在机器B上执行有一定的限制。据此可将所有任务分为三类： 1.任务必须先在机器A上执行完然后再在机器B上执行。 2.任务必须先在机器B上执行完然后再在机器A上执行。 3.任务没有限制，既可先在机器A上执行，也可先在机器B上执行。 现在给定每个任务的类别和需要在机器A和机器B上分别执行的时间，问使所有任务都能按规定完成所需要的最少总时间是多少。

Format

Input

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

Output

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

Samples

3
357
I6I
226

14

Limitation

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