题目描述

小青蛙住在一条河边，它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。 河里的石头排成了一条直线，小青蛙每次跳跃必须落在一块石头或者岸上。 不过，每块石头有一个高度，每次小青蛙从一块石头起跳，这块石头的高度就会下降1。 当石头的高度下降到0 时小青蛙不能再跳到这块石头上（某次跳跃后使石头高度下降到0 是允许的）。 小青蛙一共需要去学校上x 天课，所以它需要往返2x 次。 当小青蛙具有一个跳跃能力y 时，它能跳不超过y 的距离。 请问小青蛙的跳跃能力至少是多少才能用这些石头上完x 次课。

输入格式

输入的第一行包含两个整数n, x，分别表示河的宽度和小青蛙需要去学校的天数。 请注意2x 才是实际过河的次数。 第二行包含n - 1 个非负整数H1, H2, ... , Hn-1。 其中Hi > 0 表示在河中与小青蛙的家相距i 的地方有一块高度为Hi 的石头，Hi = 0 表示这个位置没有石头。 30%的测试数据：n≤100 60%的测试数据：n≤1000 100%的测试数据：1≤n≤100000，1≤x≤10^9，0≤Hi≤10^4

输出格式

输出一行，包含一个整数，表示小青蛙需要的最低跳跃能力。

输入样例

5 1
1 0 1 0

输出样例

4

数据范围与提示

由于只有两块高度为1 的石头，所以往返只能各用一块。 第1 块石头和对岸的距离为4，如果小青蛙的跳跃能力为3 则无法满足要求。 所以小青蛙最少需要4 的跳跃能力。