Rice Hub
In the countryside, you can find a long straight road known as the Rice Way. Along this road there are R rice fields. Each field is located at an integer coordinate between 1 and L inclusive. The rice fields will be presented in non-decreasing order of their coordinates. Formally, for 0 ≤ i < R, rice field i is at coordinate X[i]. You may assume that 1 ≤ x[0] ≤ ... ≤ x[R-1] ≤ L.
Please note that multiple rice fields may share the same coordinate.
We plan to construct a single rice hub as a common place to store as much of the harvest as possible. As with the rice fields, the hub has to be at an integer coordinate between 1 and L, inclusive. The rice hub can be at any location, including one that already contains one or more rice fields.
Each rice field produces exactly 1 truckload of rice every harvest season. To transport the rice to the hub, the city has to hire a truck driver. The driver charges 1 Baht to transport a truckload of rice per unit of distance towards the hub. In other words, the cost of transporting rice from a given field to the rice hub is numerically equal to the difference between their coordinates.
Unfortunately, our budget for this season is tight: we may only spend at most B Baht on transportation.Your task is to help us strategically place the hub to gather as much rice as possible.
Input
First line contains three integers R, L and B, R - the number of rice fields, the fields are numbered from 0 till R - 1, L - the maximum coordinate, B - the budget (1 ≤ R ≤ 100000, 1 ≤ L ≤ 10^9, 0 ≤ B ≤ 2 *10^15).
In the next R lines given R integers X[i] - the coordinate of i-th field, all integers are sorted in nondecreasing order.
Output
Print the maximum number of truckloads of rice that can be transported to the hub within the budget.