Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3554
A Miser Boss

Time Limit: 2 Seconds      Memory Limit: 65536 KB

There are three different lathes in a factory namely A,B,C. They are all able to work on all kinds of workpieces. And there are n workpieces to be processed, denoted by 1,2,..,n.

Due to different internal implemetations, for a specific workpiece i, it costs A a[i] seconds to finish the job on it while B takes b[i] and C takes c[i] seconds. Each lathe can work on at most one workpiece a time.

Additionally, the Boss is so stingy that he didn't want his lathes to be disengaged at any time before the end of the work. That is:
1. there should not be a time when one of the lathes is in leisure.
2. all lathes should stop simultaneously,and start from time 0.

Your task is to find if there exists an arrangement meeting with the constraints above. if there is,output the minimal time needed to process all the workpieces. Output a line NO else.


There are multiple test cases. The first line of each case is an integer N(0 < N ≤ 40 ) , followed by N lines. In the following N lines, line i contains three integer,a[i],b[i],c[i] (0 < a[i],b[i],c[i] ≤ 120 && 0 < sum(a[i]),sum(b[i]),sum(c[i]) ≤ 120 ) indicating the seconds A,B,C takes to process workpiece i.


Output one line the minimal seconds it takes to process all workpieces within the constraints if there is an arrangement. Print NO if not.

Sample Input

7 1 2
1 7 1
1 3 7
1 2 3
3 2 1

Sample Output


Author: LI, Wenchao
Contest: ZOJ Monthly, October 2011
Submit    Status