这是问题的简单版本。唯一的区别是在这个版本中$$$n \leq 2000$$$。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。
一行中有$$$n$$$药水,最左边是$$$1$$$药水,最右边是$$$n$$$药水。喝醉后,每种药水都会使你的生命值增加 $$$a_i$$$。 $$$a_i$$$ 可以为负数,这意味着药水的生命值会减少。
你从 $$$0$$$ 生命值开始,你将从左到右,从第一瓶药水走到最后一瓶。每喝一瓶药水,你都可以选择喝掉它或忽略它。您必须确保您的健康状况始终为非负值。
你最多可以喝多少药水?
输入
第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2000$$$) — 药剂的数量。
下一行包含 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ... ,$$$a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$) 代表饮用该药水后健康状况的变化。
输出
输出一个整数,即在生命值不会变为负数的情况下你可以喝的最大药水数量。
示例
输入 #1
6 4 -4 1 -3 1 -3
输出 #1
5
注意
对于样品,您可以通过服用药水$$$1$$$、$$$3$$$、$$$4$$$、$$$5$$$和$$$6$$$来喝$$$5$$$药水。不可能喝完所有 $$$6$$$ 药水,因为你的健康状况会在某个时刻变为负数