You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

lzx 有一个由 $n$ 个方块排成一排的玩具，每个方块上的长条 $i$ 可以覆盖 $[\max(1,i-a_i),\min(i+a_i,n)]$

对于分别能覆盖 [$x_1,y_1$] 和 [$x_2,y_2$] 的两个长条，如果 $y_1 \ge x_2$ 且 $y_2 \ge x_1$ 那么它们能合并成同一根，同时新长条可覆盖 $[\min(x_1,x_2),\max(y_1,y_2)]$ 并且合并过的新长条还可以继续合并。

求用最多 $k$ 个长条合并出的一根长条可以覆盖多长的方块。

特别的，如果没有合并，答案是能覆盖方块最长的长条所能覆盖的方块个数。

输入格式

第一行：$2$ 个正整数 $n,k$

第二行：$n$ 个非负整数 $a_i$

输出格式

一行一个整数，表示答案

5 2
1 0 0 1 0

3

5 2
0 1 1 0 0

4

样例 #1 解释

位置 $1$ 上的长条可以覆盖 [$1,2$]

位置 $4$ 上的长条可以覆盖 [$3,5$]

它们不能合并，答案为最长的一根长条 $4$ 所能覆盖的方块个数—— $3$

样例 #2 解释

位置 $2$ 上的长条可以覆盖 [$1,3$]

位置 $3$ 上的长条可以覆盖 [$2,4$]

它们可以合并，且合并后的长条可以覆盖 [$1,4$] 所以答案为 $4$

数据范围