[IOI2011] ricehub

题目描述

乡间有一条笔直而长的路称为“米道”。沿着这条米道上$R$ 块稻田,每块稻田的坐标均为一个 $1$ 到 $L$ 之间(含 $1$ 和 $L$ )的整数。这些稻田按照坐标以不减的顺序给出,即对于 $0 \le i < R$,稻田 $i$ 的坐标 $X[i]$ 满足 $1 \le X[0] \le \cdots \le X[R-1] \le L$。 注意:可能有多块稻田位于同一个坐标上。 我们计划建造一个米仓用于储存尽可能多的稻米。和稻田一样,米仓将建在米道上,其坐标也是一个 $1$ 到 $L$ 之间的整数(含 $1$ 和 $L$)。这个米仓可以建在满足上述条件的任一个位置上,包括那些原来已有一个或多个稻田存在的位置。 在收获季节,每一块稻田刚好出产一滿货车的稻米。为了将这些稻米运到米仓,需要雇用一位货车司机来运米。司机的收费是每一满货车运送一个单位的距离收取 $1$ 元。換言之,将稻米从特定的稻田运到米仓的费用在数值上等于稻田坐标与米仓坐标之差的绝对值。 不幸的是,今年预算有限,我们至多只能花费 $B$ 元运费。你的任务是要帮我们找出一个建造米仓的位置,可以收集到尽可能多的稻米。

输入输出格式

输入格式


第一行 三个整数 $R,L,B$; 接下来 $R$ 行 每行一个整数 表示 $X[i]$。

输出格式


一个整数,表示最多稻米数

输入输出样例

输入样例 #1

5 20 6
1
2
10
12
14

输出样例 #1

3

说明

对于 $100\%$ 的数据,$1 \le R \le 10^5$,$1 \le L \le 10^9$,$ 0 \le B \le 2 \times 10^{15}$。