P0969

[Ioi2011]ricehub

[Ioi2011]ricehub

乡间有一条笔直而漫长的道路,称为“米道”。沿途分布着 RR 块稻田,每块稻田的坐标都是 11 到 LL 之间的整数,且按照坐标非递减的顺序给出:

1≤X0≤X1≤⋯≤XR−1≤L。1\le X_0\le X_1\le\cdots\le X_{R-1}\le L。

可能有多块稻田位于同一坐标。

现在计划在米道上建造一座米仓,以储存尽可能多的稻米。米仓的坐标同样必须是 11 到 LL 之间的整数,可以建在任意符合条件的位置,包括已有一块或多块稻田的位置。

收获季节中,每块稻田恰好产出一满货车的稻米。将一满货车的稻米运输一个单位距离需要花费 11 元,因此,将某块稻田的稻米运到米仓的费用,等于该稻田坐标与米仓坐标之差的绝对值。

运输预算至多为 BB 元。请确定米仓的建造位置以及要收集稻米的稻田,使收集到的稻米数量尽可能多。

输入格式

第一行包含三个整数 RR、LL、BB,分别表示稻田数量、米道的坐标上限和运输预算。

接下来 RR 行,第 i+1i+1 行包含一个整数 XiX_i,表示第 ii 块稻田的坐标。

输出格式

输出一个整数,表示在预算范围内最多能够收集稻米的稻田数量。

样例输入

5 20 6
1
2
10
12
14

样例输出

3

数据范围

  • 1≤R≤1051\le R\le 10^5;
  • 1≤L≤1091\le L\le 10^9;
  • 0≤B≤2×10150\le B\le 2\times 10^{15};
  • 1≤X0≤X1≤⋯≤XR−1≤L1\le X_0\le X_1\le\cdots\le X_{R-1}\le L。

来源与许可

本题为 IOI 2011 试题「ricehub」,题面与测试数据整理自 BZOJ。

样例 1

输入

5 20 6
1
2
10
12
14

输出

3