题目描述

某加工厂有 $A$ 、 $B$ 两台机器，来加工的产品可以由其中任何一台机器完成，或者两台机器共同完成。由于受到机器性能和产品特性的限制，不同的机器加工同一产品所需的时间会不同，若同时由两台机器共同进行加工，所完成任务又会不同。

某一天，加工厂接到 $n$ 个产品加工的任务，每个任务的工作量不尽一样。你的任务就是：已知每个任务在 $A$ 机器上加工所需的时间 $t_1$ ， $B$ 机器上加工所需的时间 $t_2$ 及由两台机器共同加工所需的时间 $t_3$ ，请你合理安排任务的调度顺序，使完成所有 $n$ 个任务的总时间最少。

输入格式

输入共 $n+1$ 行：

第 $1$ 行为 $n$ ，表示任务总数；

第 $i+1$ 行为 $3$ 个非负整数 $t_1,t_2,t_3$ ，分别表示第 $i$ 个任务在 $A$ 机器上加工、 $B$ 机器上加工、两台机器共同加工所需要的时间。如果所给的时间 $t_1$ 或 $t_2$ 为 0 表示任务不能在该台机器上加工，如果 $t_3$ 为 0 表示任务不能同时由两台机器加工。

输出格式

一个整数，代表最少完成时间。

样例输入

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

样例输出

9

数据规模与约定

对于 $100\%$ 的数据，$1\le n\le 6000$，$0\le t_1,t_2,t_3\le 5$。