题目描述

敌人的 $n$ 个碉堡排成一行，每个碉堡在数轴上的坐标 $a_i$. 你一共有 $m$ 颗炸弹，如果炸弹的爆炸直径为 $x$,则可以轰炸连续长度为 $x$ 的区间位置。 你的目标是用这 $m$ 颗炸弹轰炸掉所有的碉堡。 最开始生产炸弹时需要设定炸弹的爆炸直径，且一旦设定无法更改。 现在在已经生产了 $y$ 颗炸弹的情况下炸弹工艺提升了，使得剩下的炸弹爆炸直径翻倍了。 求最开始最小需要设定爆炸直径为多少。 注：本题所有的数字均为整数。

输入输出格式

输入格式：

第一行三个正整数 $n, m, y$，含义见题目。

第二行 $n$ 个正整数表示碉堡坐标。

输出格式：

一个整数表示最开始设定的爆炸直径最小值。

输入输出样例

输入样例#1：

4 3 1
1 3 5 6

输出样例#1：

1

补充说明

【样例说明】 共 $3$ 颗炸弹，$1$ 颗爆炸范围设定为 $1$，工艺提升后炸弹范围就变成 $2$，也就是 $2$ 颗炸弹爆炸范围为 $2$。对于碉堡 $1,3,5,6$，可以在区间 $[1, 1]$ 用掉一颗范围为 $1$ 的炸弹，在区间 $[3, 4]$ 和 $[5, 6]$ 用掉 $2$ 颗范围为 $2$ 的炸弹能把所有碉堡都覆盖掉。

【数据规模】

对于 $60\%$ 的数据，$1\le n\le 100$, $1\le y<m\le 100$, $1\le a_i\le 1000$.

特别的，对于 $10\%$ 的数据有 $m \ge n$.

有另外 $20\%$ 数据有 $a_i = a_{i-1}+1$.

对于 $100\%$ 的数据，$1\le n\le 2000, 1\le y<m\le 1e6, 1\le ai\le 1e9$.

时间限制：1s 空间限制：256M