题目描述

烤乐滋前些日子做了许多体力活，还险些被炸飞，他决定调养一下身子。

他面前有 $n$ 碗汤, 每碗汤都有一个营养值 $P_i$, 可能有汤的营养值是负数。烤乐滋为了方便想要喝连续的一段汤，喝连续一段汤得到的营养总和为喝的每一碗汤的营养值加和。

但烤乐滋手中有一包神秘水, 它将这包神秘水加到任意一碗汤里后, 那碗汤的营养值就会瞬间变成 $M$ 。烤乐滋不想浪费，所以这包神秘水必须用掉，且恰好用在一碗汤里。

烤乐滋想要让你告诉他, 将神秘水用掉之后能够得到的最大营养总和。也就是说, 将其中一碗汤的营养值改成 $M$ 之后, 喝连续一段汤的最大营养总和是多少。

输入格式

第一行两个数 $n, M$, 意义如题面中所述。 第二行 $n$ 个数第 $i$ 个数 $P_i$, 表示第 $i$ 碗汤的营养值。

输出格式

一行一个数, 表示答案。注意, 你可以一碗汤都不喝。

样例1

4 3
4 -3 2 -4

9

样例解释

• 原始序列： $4,-3,2,-4$
• 我们可以选择将任意一碗汤的营养值改为 3 。让我们尝试每一种可能：

1．将第1碗改为 3 ：序列变为 $3,-3,2,-4$

• 最大子序列和为 3

2．将第 2 碗改为 3 ：序列变为 $4,3,2,-4$

• 最大子序列和为 9

3．将第3碗改为 3 ：序列变为 $4,-3,3,-4$

• 最大子序列和为 4

4．将第4碗改为 3 ：序列变为 $4,-3,2,3$

• 最大子序列和为 6

• 因此，最大的营养总和是 9 ，对应将第 2 碗汤改为 3 的情况。

数据范围

对于 $30 \%$ 的数据, $n \leq 100$ 。

对于 $70 \%$ 的数据, $n \leq 10^3$ 。

对于 $100 \%$ 的数据, $n \leq 10^5,\left|P_i\right|,|M| \leq 10^9$ 。

大样例下载