Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Knapsack II
Time Limit: 10000MSMemory Limit: 131072K
Total Submissions: 1628Accepted: 400
Case Time Limit: 3000MS

Description

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?

Input

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.

Output

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”.

Sample Input

3
4 9 13
2
2 4

Sample Output

23
INF

Source

[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