009 - ばらばら饅頭

問題

会津若松市にある和菓子屋・友栗堂の店長さんは、とても腕のいい職人さんなのにちょっと気分屋なのが玉にキズです。店長さんの作る饅頭はとても美味しいのですが、その時の気分によって大きさがまちまちになってしまいます。

見かねた店長さんの奥さんは、この大きさと重さがばらばらな饅頭を袋に詰めて売り出すことを思いつきました。一定の重さになるように饅頭を袋に詰めて売れば、一つ一つの大きさはばらばらでも一定の値段で売り出すことが出来ますし、どんな饅頭が入っているのか開けるまでわからないというサプライズも売りになるかもしれません。 「ばらばら饅頭」という名前で売りだしたところ、新しいアイディアが話題となり友栗堂はたちまち評判となりました。しかし、問題もあり、袋に入れる饅頭の組み合わせ方によって作れる「ばらばら饅頭」の数が変わり、無駄が発生してしまうことがありました。アルバイトで友栗堂に来ていたあなたは無駄なく袋に詰めるためにプログラムをつくることにしました。

饅頭の重さは1から9の9種類あります。袋に詰める時には、饅頭の重さの合計がぴったり10になるように詰め込みます。饅頭の組み合わせ方は1+1+2+4+2=10や1+1+1+1+1+5=10などで、同じ重さの饅頭をいくつ使っても構いません。

作られる饅頭の個数nと饅頭の重さの情報を入力とし、作ることのできる「ばらばら饅頭」の最大の数を出力とするプログラムを作成してください。ただし、nは2以上100以下の整数とします。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつで示されます。各データセットは以下の通りです。

1行目 饅頭の個数 n（整数；半角空白区切り）
2行目 各饅頭の重さ m₁ … m_n（すべて整数；半角空白区切り）

Output

入力データセットごとに、詰め込むことのできた「ばらばら饅頭」の最大の数を出力します。

Sample Input

5
4 9 1 3 8
10
8 5 3 6 2 1 4 5 4 5
9
5 7 3 8 2 9 6 4 1
0

Sample Output

1
4
4