思路

首先将题目转化为塔子完成整个关卡最少损失多少生命值，这时每个回合用不用塔子起飞所造成的贡献相对独立。

考虑第 $i$ 个回合用塔子起飞，会少损失 $v_i$ 点体力，并在之后的 $n-i$ 个关卡中每关增加 $1$ 点恢复，但是会少增加$cnt_i$点体力。 这里的 $cnt_i$ 代表之前用过的塔子起飞次数。

所以选择第$i$回合所带来的增益就是 $v_i+n-i-cnt_{i-1}$ 。由于每个位置的选择是独立的(也就是说你选第1个和你选第2个是没关系的。没规定你选了第1个必须选第2个。也没规定你选了第1个就不能选第2个)。所以我们就是要求:

$$\Large max\ \sum_{i \in \{i_1,i_2,...,i_x\}}^{} v_i+n-i-cnt_{i-1} \\ \Large = \sum_{i \in \{i_1,i_2,...,i_x\}}^{} v_i-i + \sum_{i \in \{i_1,i_2,...,i_x\}}^{} n -cnt_{i-1}$$

题目内容

塔子最近在玩一款闯关游戏,其共有 $m$ 个回合，塔子有个技能：塔子起飞。总共可以使用 $x$ 次， 以下是对这个技能的简介:

1.每回合使用不超过一次。

2.如果在某一个回合使用了塔子起飞，那么塔子免疫该回合受到的所有伤害，并且在之后没有使用该技能的回合中每回合恢复 $1$ 点体力值

3.技能的效果可以叠加

以下是对塔子起飞技能的案例说明:

前两个回合都释放了一次塔子起飞，那么第三个回合就会恢复 $2$ 点体力。

通关条件:

塔子只需要在 $m$ 个回合后体力大于等于 $0$ ，即可通关。

问题定义:

请问塔子初始最少需要多少体力。(初始体力应该大于等于 $1$ , 过程中允许部分时刻体力小于 $0$ )

输入描述

输入第一-行包含两个整数 $m$ 和 $x$ ，分别表示回合数和塔子起飞使用次数。$(1 \leq m,x \leq 10^5)$

输入第二行包含 $m$ 个整数，分别表示在第 $1$ 个回合到第 $m$ 个回合中，塔子受到伤害，每回合造成的伤害不超过 $10^5$。

输出描述

输出仅包含一个整数，即最少需要的体力值。

样例

输入

5 2
7 3 2 6 5

输出

6