Рисохранилище
Рисохранилище
В сельской местности находится длинная прямая дорога, которая известна как Рисовый Путь. Вдоль этой дороги расположены R рисовых полей. Каждое поле имеет целочисленную координату от 1 до L включительно. Рисовые поля задаются в порядке неубывания их координат. Формально, обозначим для 0 ≤ i < R координату рисового поля с номером i как x[i]
. Гарантируется, что 1 ≤ x[0]
≤ ... ≤ x[R-1]
≤ L.
Отметим, что несколько рисовых полей могут иметь одинаковую координату.
Планируется построить одно рисохранилище, в которое требуется завезти с полей как можно больше риса. Как и рисовые поля, рисохранилище должно иметь целочисленную координату от 1 до L включительно. Рисохранилище разрешается строить в любой целочисленной координате, в том числе и в координате, в которой уже есть одно или более рисовых полей.
С каждого рисового поля в течение каждого сезона снимают урожай, который помещается ровно в 1 грузовике. Чтобы доставить урожай в рисохранилище, необходимо нанять водителя грузовика. Стоимость работы водителя по перевозке груза на единицу расстояния составляет 1 бат. Другими словами, стоимость транспортировки риса от заданного поля до рисохранилища равна модулю разности их координат.
К сожалению, бюджет рассматриваемого сезона ограничен: нельзя потратить более B бат на транспортировку. Необходимо построить рисохранилище в таком месте, чтобы можно было завезти в него как можно больше риса.
Giriş verilənləri
В первой строке три целых числа R, L и B, R - количество рисовых полей, поля пронумерованы от 0 до R - 1, L - максимальная координата, B - бюджет (1 ≤ R ≤ 100000, 1 ≤ L ≤ 10^9
, 0 ≤ B ≤ 2 *10^15
).
В следующих R строках задано R целых чисел X[i]
- координата i-го поля, все числа отсортированы в порядке неубывания.
Çıxış verilənləri
Выведите максимальное количество грузовиков риса, которые могут быть перевезены в рисохранилище, не превышая заданный бюджет.
Nümunə
16 93 1 5 10 15 20 25 31 35 40 45 50 55 59 65 70 75 80
1