1876: 逃脱农场

内存限制:256 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:24 通过:8

题目描述

奶牛们决定采取一个大胆的计划来逃离农夫约翰的魔掌。 
他们设法弄来了一个小型充气筏,在夜色的掩护下,一群奶牛将登上充气筏,划过与农场接壤的河流。 
这个计划似乎很完美,但奶牛们意识到他们的小充气筏可能无法承受太大的重量!
N 头奶牛(1 <= N <= 20)的重量为 w_1 ... w_N。 
为了弄清楚一群奶牛的重量是否足以避免筏子沉没,奶牛们将这群奶牛的所有重量加起来。 
不幸的是,奶牛在算术方面出了名的糟糕。
如果将一组奶牛的重量相加导致任何进位发生(使用标准的基数 10 加法),那么奶牛会认为该组无法使用木筏。 
任何可以在没有任何进位的情况下增加重量的组都被认为足够轻以适合木筏。 
请帮助奶牛确定它们认为可以装在筏子上的最大群体的大小(即可以将重量加在一起不发生进位)。

输入格式

第一行为正整数N,1≤N≤20。
接下来N行,每行一个数字表示第i头奶牛的重量w_i,1≤w_i≤100000000

输出格式

输出一个数字表示答案。

输入样例 复制

5
522
6
84
7311
19

输出样例 复制

3

数据范围与提示

三头牛重量相加不发生进位:522、6、7311。
来源:USACO 2011.12