ZOJ Problem Set - 3554
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:
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.
3 7 1 2 1 7 1 1 3 7 2 1 2 3 3 2 1
Author: LI, Wenchao
Contest: ZOJ Monthly, October 2011