e-olymp
Məsələlər

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

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

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

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

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

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

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

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

В первой строке три целых числа R, L и B, R - количество рисовых полей, поля пронумерованы от 0 до R - 1, L - максимальная координата, B - бюджет (1R100000, 1L109, 0B2 *1015).

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

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
16 93 1
5
10
15
20
25
31
35
40
45
50
55
59
65
70
75
80
Çıxış verilənləri #1
1
Mənbə 2011 IOI, Тайланд, День 1, Июль 22 - 29
Гонки
Подземный город крокодилов