【问题描述】 Captain在隧道坍塌前走出了洞穴,他意外的发现了很多金币。有一个数轴,上面的每个点都是整数,上面有N枚金币,第i枚金币所在的位置为x[i](注意可能会有多个金币在同一位置),现在Captain想要拿其中的一些金币,他首先要在数轴上选择一个位置建造存放点,然后要选择一些金币,把他们取走并将其带回存放点,由于金币太重,他一次只能携带一枚金币,并且他在携带一枚金币时,走1单位距离会消耗一点体力,换言之,他将一枚金币带回存放点消耗的体力为金币和货仓之间的距离,而他总共只有T点体力。请问他最多能拿多少枚金币。
【输入描述】第一行输入三个正整数N L T。接下来n行每行输入一个正整数表示x[i]给定数据满足(1<=x[1]<=x[2]<=…<=x[n]<=L)【输出描述】输出一行一个整数表示最多拿到的金币数量。
【样例输入】5 14 6
1 2 10 12 14
【样例输出】3
【样例解释】可以将存放点建在12处,那么拿到10 12 14三个位置的金币总共需要4点体力,所以最多拿到3枚金币。
【数据范围】对于前20%的测试数据N<=100。
对于前40%的测试数据N<=1000
对于另外20%的测试数据L<=2000
对于100%的测试数据N<=100000,L<=10^9,T<=2*10^15