eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Рисохранилище

Рисохранилище

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

В сельской местности находится длинная прямая дорога, которая известна как Рисовый Путь. Вдоль этой дороги расположены R рисовых полей. Каждое поле имеет целочисленную координату от 1 до L включительно. Рисовые поля задаются в порядке неубывания их координат. Формально, обозначим для 0i < R координату рисового поля с номером i как x[i]. Гарантируется, что 1x[0] ≤ ... ≤ x[R-1]L.

Отметим, что несколько рисовых полей могут иметь одинаковую координату.

Планируется построить одно рисохранилище, в которое требуется завезти с полей как можно больше риса. Как и рисовые поля, рисохранилище должно иметь целочисленную координату от 1 до L включительно. Рисохранилище разрешается строить в любой целочисленной координате, в том числе и в координате, в которой уже есть одно или более рисовых полей.

С каждого рисового поля в течение каждого сезона снимают урожай, который помещается ровно в 1 грузовике. Чтобы доставить урожай в рисохранилище, необходимо нанять водителя грузовика. Стоимость работы водителя по перевозке груза на единицу расстояния составляет 1 бат. Другими словами, стоимость транспортировки риса от заданного поля до рисохранилища равна модулю разности их координат.

К сожалению, бюджет рассматриваемого сезона ограничен: нельзя потратить более B бат на транспортировку. Необходимо построить рисохранилище в таком месте, чтобы можно было завезти в него как можно больше риса.

Входные данные

В первой строке три целых числа R, L и B, R - количество рисовых полей, поля пронумерованы от 0 до R - 1, L - максимальная координата, B - бюджет (1R10^5, 1L10^9, 0B2 *10^15).

В следующих R строках задано R целых чисел X[i] - координата i-го поля, все числа отсортированы в порядке неубывания.

Выходные данные

Выведите максимальное количество грузовиков риса, которые могут быть перевезены в рисохранилище, не превышая заданный бюджет.

Пример

Входные данные #1
16 93 1
5
10
15
20
25
31
35
40
45
50
55
59
65
70
75
80
Выходные данные #1
1
Источник 2011 IOI, Тайланд, День 1, Июль 22 - 29