#PUSACO11DecBro3. 逃离农场

逃离农场

逃离农场

题目描述

奶牛们决定采取一个大胆的计划来逃脱农夫约翰的魔掌。他们设法买了一只小型充气筏,在夜幕的掩护下,一群牛登上木筏,划到农场的边界地带。这个计划似乎很完美,直到 奶牛意识到他们的小型充气筏可能无法承受很大的重量!N只牛(1 <= n <= 20)的重量分别为 w_1 … w_n。为了弄清楚一组奶牛是否足够轻,以避免翻船,奶牛们将该组的所有重量加起来。不幸的是,奶牛在算术上是出了名的差,如果在一个组中增加奶牛的重量会发生进位(使用10进制计算),奶牛就会放弃,并得出结论,这个组太重了会翻船。某组的重量相加不产生任何进位的则该组被认为足够轻,筏能承受这样的重量。请帮助奶牛确定最大的组的大小,他们相信可以登筏逃离(即最大的组,所有重量加在一起没有进位)。

输入格式

第1行:奶牛的只数,N(1 <= N <= 20)。第2..N+1行:每一行包含一个整数,表示一只奶牛的重量,范围是1....100,000,000。

输出格式

第1行:最多的奶牛只数前提是它们的重量相加不会产生进位。

数据范围

(原站未提供,导入后需人工补齐)

样例

5
522
6
84
7311
19
3

提示

输入描述:这里有5只奶牛,重量分别是522,6,84,7311,19。

输出描述:这样的3只奶牛 522,6,7311,加在一起不会产生进位:

![1.gif](file://f8c1e09150.gif)