题目内容

小蓝正在攻略一款地牢探险游戏，游戏共有 n 个阶段。每个阶段中，他会受到一定的伤害。小蓝拥有一个特殊技能“灵能护盾”，该技能最多可使用 k 次，且每阶段最多使用 1 次。 在某阶段使用灵能护盾后，该阶段将完全免疫伤害，并且在之后每个未使用技能的阶段中，灵能护盾会为他持续恢复体力：每阶段恢复 1 点。该效果可以叠加——若在当前阶段之前已经使用过 c 次灵能护盾，那么当前阶段如果未使用技能，将恢复 c 点体力；若使用了技能，则不受伤害也不触发恢复。 通关的条件是：在全部 n 个阶段结束后，小蓝的体力不低于 0。允许中途部分时刻体力暂时小于 0。初始体力必须至少为 1。请你计算，在最优使用技能的策略下，初始最少需要多少体力才能保证通关。

数据范围：阶段数 n 和技能次数 k 满足 $1 \le n, k \le 10^5$，每个阶段的伤害值均为不超过 10^5 的非负整数。

输入描述

第一行包含两个整数 n 和 k，分别表示阶段的数量和技能的使用次数上限。 第二行包含 n 个整数，依次表示第 1 到第 n 个阶段受到的伤害，每个伤害值不超过 10^5。