OI题库

奶牛们最讨厌黑暗。为了更换牛棚顶部的电灯泡，Bessie必须要用外面一捆捆的干草搭建一个塔爬上去，才能够得到。一共有N(1 <= N <= 100,000)捆干草，编号依次为1~N，它们按顺序放在传送带上运进牛棚里来，第i捆干草的宽度为w_i(1 <= w_i <= 10,000)，所有干草的长度和高度均为1。

建塔的时候Bessie必须要把这N捆干草都用上，并要按照它们被运进来的顺序安放，在建第一层（地基）的时候，她可以想放多少捆就放多少捆，必须把它们紧紧地码成一行。她可以把接下来的一些干草码在之前干草的上面以便新建一层，上面的层不能比它下面的层宽，使用这种方法堆叠，直到把所有的干草捆用光。注意，她必须按干草被运进来的顺序来码放它们，建塔的时候也必须从下往上一层一层地进行，比如，假定上一捆干草是放在第二层的，那以后的干草就不可以再放到第一层（即塔基）。

Bessie的目标是要尽可能建一个最高的塔，她事先知道每一捆被放在传送带上运进来的干草的宽度，那么，她究竟可以搭到多高呢？

输入格式：
第1行，一个整数N；
第2~N+1行，第i+1行包含一个整数w_i；

输出格式：
一行，一个整数，即最多可以建多高。

输入输出样例：
tower.in
3
1
2
3

tower.out
2

输出样例解释：
用前两捆做地基，宽度为1+2=3，用第三捆（宽度为3）做第二层，塔高为2。

+----------+
|     3    |
+---+------+
| 1 |   2  |
+---+------+