[Ioi2011]ricehub
乡间有一条笔直而漫长的道路,称为“米道”。沿途分布着 块稻田,每块稻田的坐标都是 到 之间的整数,且按照坐标非递减的顺序给出:
可能有多块稻田位于同一坐标。
现在计划在米道上建造一座米仓,以储存尽可能多的稻米。米仓的坐标同样必须是 到 之间的整数,可以建在任意符合条件的位置,包括已有一块或多块稻田的位置。
收获季节中,每块稻田恰好产出一满货车的稻米。将一满货车的稻米运输一个单位距离需要花费 元,因此,将某块稻田的稻米运到米仓的费用,等于该稻田坐标与米仓坐标之差的绝对值。
运输预算至多为 元。请确定米仓的建造位置以及要收集稻米的稻田,使收集到的稻米数量尽可能多。
输入格式
第一行包含三个整数 、、,分别表示稻田数量、米道的坐标上限和运输预算。
接下来 行,第 行包含一个整数 ,表示第 块稻田的坐标。
输出格式
输出一个整数,表示在预算范围内最多能够收集稻米的稻田数量。
样例输入
5 20 6
1
2
10
12
14
样例输出
3
数据范围
- ;
- ;
- ;
- 。
来源与许可
本题为 IOI 2011 试题「ricehub」,题面与测试数据整理自 BZOJ。
样例 1
输入
5 20 6
1
2
10
12
14
输出
3