药水（简单版）

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

这是该问题的简单版本。唯一的区别在于本版本中 $n \leq 2000$。只有当你同时解决了两个版本的问题时，才能进行 hack。

有 $n$ 个药水排成一行，药水 $1$ 在最左边，药水 $n$ 在最右边。每个药水喝下后会使你的生命值增加 $a_i$。$a_i$ 可能为负数，表示该药水会减少你的生命值。

你初始时生命值为 $0$，并且你会从左到右依次经过每个药水。每到一个药水处，你可以选择喝下它或者忽略它。你必须保证你的生命值始终不为负数。

你最多能喝下多少瓶药水？

输入格式

第一行包含一个整数 $n$（$1 \leq n \leq 2000$），表示药水的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^9 \leq a_i \leq 10^9$），表示每瓶药水喝下后生命值的变化量。

输出格式

输出一个整数，表示在保证生命值始终不为负的情况下，最多能喝下的药水数量。

样例输入 1

6
4 -4 1 -3 1 -3

样例输出 1

5

数据范围

对于所有数据，$1\le n\le2000$，$-10^9\le a_i\le10^9$。计算生命值时应使用 64 位整数。