Fernando 是 Stark 公司会计部门的一名专业人员，负责公司每日营业额的控制与分析。Fernando 记录了公司连续 $N$ 天的营业额。由此，他生成了一个大小为 $N$ 的列表 $V$，其中 $V_i$ 表示公司在第 $i$ 天赚取的金额。注意，若 $V_i < 0$，则表示公司当天亏损。

Fernando 的任务之一是将一份记录了某段时间内营业额的列表交给他的上司 Tony。但 Fernando 知道，如果他提交的列表中存在某一天 $i$，使得前 $i$ 天的营业额之和为负数（表示公司亏损），Tony 就会对下属非常生气。由于 Fernando 希望他的上司对他感到满意，他在将列表 $V$ 发送给 Tony 之前会对其进行一些修改。这种修改包括从列表开头移除若干天，以及从列表末尾移除若干天。

Fernando 将列表 $V$ 的“幸福度”定义为他可以发送的子列表数量，以使 Tony 感到满意。形式化地，列表 $V$ 的幸福度是指满足以下条件的整数对 $(p, q)$（其中 $p, q \ge 0$ 且 $p + q < N$）的数量：如果 Fernando 从 $V$ 中移除前 $p$ 天和最后 $q$ 天，则对于结果列表中的每一个 $i$，其前 $i$ 个值的和均为非负数。

Fernando 在思考幸福度时，又出现了一个额外的问题。公司的 IT 人员报告称，计算公司每日营业额的系统存在故障。他们发现，在 $N$ 天中的某一天，系统计算出的营业额与实际营业额相差 $X$。也就是说，存在某一天 $i$，该天的实际营业额应为 $V_i + X$ 而非 $V_i$。Fernando 本可以深入调查并找出错误发生的具体日期，但他太懒了。因此，他决定在某一天加上 $X$，使得修改后的 $V$ 的幸福度尽可能高。

作为 Fernando 的朋友，你决定帮助他。给定故障值 $X$ 和营业额列表 $V$，你必须在考虑必须将 $X$ 加到其中一个营业额上的前提下，求出 $V$ 的最大幸福度。

输入格式

第一行包含两个整数 $X$ ($-10^9 \le X \le 10^9$) 和 $N$ ($1 \le N \le 5 \times 10^5$)，分别表示故障值和营业额列表中的天数。 第二行包含 $N$ 个整数 $V_1, V_2, \dots, V_N$ ($-10^9 \le V_i \le 10^9$，对于 $i = 1, 2, \dots, N$)，描述该列表。

输出格式

输出一行一个整数，表示在必须将 $X$ 加到 $V$ 中某一个营业额上的前提下，所能达到的最大幸福度。

样例

样例输入 1

1 6
1 1 -2 1 3 -5

样例输出 1

13

样例输入 2

-1 6
1 1 -2 1 3 -5

样例输出 2

9