Rice Hub

Time limit1sMemory limit256 MB

Summary

Given sorted field positions on a line and a budget B, choose an integer hub position maximizing how many fields can be reached within total transport cost B.

Level: Medium7 of 10
Topics: Two pointers, Prefix sum, Binary search, Greedy
Solved: No attempts yet

Problem

Along a long straight road called the "Rice Road" there are $R$ rice fields. Each field sits at an integer coordinate between $1$ and $L$ inclusive, and the fields are given in non-decreasing order of coordinate. That is, for $0 \le i < R$ , field $i$ is at coordinate $X_i$ , so $1 \le X_0 \le X_1 \le \dots \le X_{R-1} \le L$ . Several fields may share the same coordinate.

You plan to build a single rice hub to store the harvested rice. The hub must also be placed at an integer coordinate between $1$ and $L$ inclusive, and it may be built anywhere, including a spot where a field is located.

At harvest time each field produces exactly one truckload of rice. To move the rice to the hub you must hire truck drivers, and moving one truckload one unit of distance costs 1 baht. In other words, the cost of moving one field's rice to the hub equals the absolute difference between the field's coordinate and the hub's coordinate.

Unfortunately this year's budget is limited, so you may spend at most $B$ baht in total on transport. Choose the hub position that maximizes the number of fields whose rice can be gathered within the budget $B$ , and output that maximum number of fields (equivalently, the number of truckloads).

The budget $B$ can be very large, so 64-bit integers are recommended during the computation.

Input

The first line contains three integers: the number of fields $R$ , the maximum coordinate $L$ , and the budget $B$ , separated by spaces. Each of the next $R$ lines contains one field coordinate $X_i$ , given in non-decreasing order.

Output

Print, on a single line, the maximum number of fields whose rice can be gathered at one hub within the budget $B$ .

Hint

The illustration above shows the case $R = 5$ , $L = 20$ , $B = 6$ with fields at coordinates 1, 2, 10, 12, 14. Here the hub can be placed at any integer coordinate between 10 and 14, allowing the rice from the three fields at 10, 12, and 14 to be gathered with a total transport cost of at most 6 baht. No hub position can gather rice from more than three fields, so the answer is 3. The figure shows one of the optimal positions.

Examples3

Example 1
Input
```
5 20 6
1
2
10
12
14
```
Expected output
```
3
```
Example 2
Input
```
1 10 0
5
```
Expected output
```
1
```
Example 3
Input
```
4 10 0
3
3
3
3
```
Expected output
```
4
```