e-olymp
Problems

Rice Hub

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 0i < R, rice field i is at coordinate Xi. You may assume that 1x0 ≤ ... ≤ xR-1L.

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 (1R100000, 1L109, 0B2 *1015).

In the next R lines given R integers Xi - 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.

Time limit 1 second
Memory limit 64 MiB
Input example #1
16 93 1
5
10
15
20
25
31
35
40
45
50
55
59
65
70
75
80
Output example #1
1
Source 2011 IOI, Thailand, Day 1, July 22 - 29
Гонки
Подземный город крокодилов