|Online Judge||Problem Set||Authors||Online Contests||User|
Lambert wants to carry several kinds of items with a knapsack. Items of each kind have integral size and infinite supply. The knapsack also has an integral capacity. Lambert discovers an interesting fact that for any sufficiently large knapsack, its capacity can always be fulfilled. For example, for any knapsack of capacity at least 24, it can always be completely filled using items of sizes 4, 9 and 13. Given n kinds of items, what is the capacity of the largest knapsack that cannot be fulfilled?
The input contains multiple test cases. Each test case begins with a line containing n (1 ≤ n ≤ 500). Then comes a line containing the sizes of different kinds of items, each not exceeding 5000. The input ends once EOF is met.
For each test case, output one line containing the capacity of the largest knapsack that cannot be fulfilled. If there is not such largest knapsack, output “INF”.
3 4 9 13 2 2 4
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator