Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

En las afueras hay una carretera muy larga y en línea recta conocida como la Vía del Arroz. En esta carretera hay $R$ campos de arroz. Todos ellos están situados en coordenadas enteras entre $1$ y $L$, ambas incluidas. Los campos de arroz aparecen ordenados por sus coordenadas en orden no decreciente. Más formalmente, para $0 \leq i \lt R$, el campo de arroz $i$ tiene coordenadas $X[i]$. Puedes suponer que $1 \leq X[0] \leq ... \leq X[R-1] \leq L$ . Observa que puede haber más de un campo de arroz diferente en una misma coordenada.

Hemos decidido construir un único depósito de arroz (rice hub) en un sitio común para almacenar tanto arroz como sea posible. Al igual que los campos de arroz, el depósito tendrá coordenadas enteras entre $1$ y $L$, ambas incluidas. El depósito puede situarse en cualquier posición, incluso en una ya ocupada por uno o más campos de arroz.

Cada campo de arroz produce exactamente $1$ truckload (carga de camión) en cada cosecha. Para transportar el arroz al depósito, la ciudad ha decidido contratar a un conductor de camiones. El conductor cobra $1$ Baht por transportar $1$ truckload una unidad de distancia hacia el depósito. En otras palabras, el coste de transportar arroz de un campo al depósito equivale numéricamente a la diferencia entre sus coordenadas.

Desafortunadamente nuestro presupuesto para esta cosecha es reducido: solo podemos gastar como mucho $B$ Baht. Tu tarea consiste en ayudar a situar de manera estratégica el depósito para reunir en él tanto arroz como sea posible con esa cantidad de dinero.

Tarea
Escribe un programa que lea de la entrada estándar los siguientes parámetros: $R$ – el número de campos de arroz, los campos están numerados de $0$ a $R-1$, $L$ – la coordenada máxima, $B$ – el presupuesto y las coordenadas de los campos de arroz ordenadas de menor a mayor.

Su programa debe encontrar una situación óptima para el depósito e imprimir el número máximo de truckloads de arroz que se pueden transportar al depósito respetando el presupuesto. Ten en cuenta que el coste total de transportar el arroz puede ser muy grande. El presupuesto se da como un entero de 64 bits, y se recomienda que uses enteros de 64 bits en tus cálculos. En C/C++ usa el tipo long long; en Pascal usa el tipo Int64.

Línea 1 : Tres enteros separados por espacio $R$, $L$ y $B$ $(1 \leq R \leq 10^5, 1 \leq L \leq 10^9, 0 \leq B \leq 2*10^15)$.

Línea 2 : $R$ enteros separados por espacio $X_0, X_1,…, X_{R-1}$ en el rango $[1, L]$ representando las posiciones de los campos de arroz. Las posiciones están ordenadas de menor a mayor.

Línea 1 : Un solo entero, el número máximo de truckloads de arroz que se pueden recolectar teniendo en cuenta las especificaciones anteriores.