Max Change

Problem code: ENCD01

Sam lives in a country "CoinLand" where there are n different types of coin. He wants to collect as many different types of coin as he can. Now if he wants to withdraw X amount of money from a Bank, the Bank will give him this money according to the following rule: lets say sam needs to withdraw money 'x'.
1. if X=0 no money withdrawn.
2. Let Y be the highest valued coin that does not exceed X. Give the customer Y valued coin. Now he has to withdraw remaining X-Y amount.
3. go to step 1.
this goes on until x becomes = 0.
Now Sam can withdraw any amount of money from the Bank. He should maximize the number of different coins that he can collect in a single withdrawal.

Input

Each of the test cases starts with n (1 n 1000), the number of different types of coin. Next line contains n integers C1, C2, ... , Cn the value of each coin type. C1 < C2 < C3 < < Cn < 1000000000.
C1 equals to 1.
Terminate the input with n=0.

Output

For each test case output one line denoting the maximum number of coins that Sam can collect in a single withdrawal. He can withdraw infinite amount of money from the Bank.

Example

Input:
6
1 2 4 8 16 32
6
1 3 6 8 15 20
0

Output:
6
4

Author: rscrbv
Date Added: 16-01-2010
Time Limit: 4 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC


Comments

The statements are now

admin @ 24 Jan 2010 03:23 PM

The statements are now visible.

Hint: A greedy problem

mangalsingh29 @ 24 Jan 2010 09:02 PM

Hint: A greedy problem

Hint: A greedy problem

mangalsingh29 @ 24 Jan 2010 09:05 PM

Hint: A greedy problem

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions