Programacion Competitiva Bolivia

En algún lugar del país, tu puedes encontrar una extraordinaria carretera conocida como La Ruta del Arroz. 
A lo largo de esta carretera existen R campos de arroz. Cada campo está localizado en unas coordenadas 
enteras entre 1 y L, inclusive. Los campos de arroz serán presentados en un orden no decreciente de sus 
coordenadas. Formalmente, para 0 ≤ i < R, donde el campo de arroz i esta en una coordenada X[i].

Puedes asumir que 1 ≤ X[0] ≤ ... ≤ X[R-1] ≤ L.

Por favor debe tomar nota respecto a que varios campos de arroz pueden compartir la misma coordenada.

Nosotros planificaremos la construcción de un depósito de arroz como un lugar común para almacenar la mayor
cantidad de cosecha posible. Así como en los campos de arroz, el depósito debe tener una coordenada entera 
entre 1 y L, inclusive. El depósito del arroz puede estar en cualquier ubicación, incluido una que también 
contenga uno o más campos de arroz.


Cada campo de arroz produce exactamente una carga de camión de arroz en cada temporada de cosecha. Para 
transportar el arroz al depósito, la ciudad va a contratar un conductor de camión. Este conductor cobrará 
1 Baht para transportar una carga de camión de arroz por la distancia entre el campo y el depósito. En otras 
palabras, el costo de transportar el arroz desde un campo dado hasta el depósito es numéricamente la 
diferencia entre sus respectivas coordenadas.

Desafortunadamente nuestro presupuesto para esta temporada de cosecha es bajo: debemos gastar a lo sumo B Baht 
en costo de transporte. Tu tarea es ayudarnos a ubicar estratégicamente el depósito de forma de recoger la 
mayor cantidad de arroz posible.

Problema

Escribir un procedimiento besthub(R,L,X,B) que tome los siguientes parámetros:

* R: el número de campos de arroz. Los campos están enumerados desde 0 hasta R-1.
* L: la coordenada máxima.
* X: un arreglo unidimensional de enteros ordenados ascendentemente. Por cada 0 ≤ i < R, el campo i está localizado en X[i].
* B: el presupuesto.

Tu procedimiento debe encontrar una ubicación optima del depósito y retornar el máximo número de cargas de camión 
que pueden ser transportados dentro del límite del presupuesto.

Debe tomar en cuenta que el costo total de transportar el arroz puede ser muy alto. El presupuesto (B) debe 
ser una variable entera de 64 bits, recomendamos que utilices variables enteras de 64-bit en todos tus 
cálculos. En C/C++, usa el tipo de variable long long; en Pascal, usa el tipo de variable Int64.

Ejemplo

Considera el caso donde R=5, L=20, B=6, y
              
   1            
   2                      
X= 10                       
   12                    
   14                    

  

Para este caso, existen múltiples ubicaciones óptimas para el depósito: puedes ubicarlo entre las localizaciones 
10 y 14, inclusive. La figura de arriba muestra una de esas posibles ubicaciones óptimas. Por tanto puedes transportar 
el arroz desde los campos a las coordenadas 10, 12, y 14. Para cualquier ubicación optima del depósito, el costo total 
del transporte no debe ser superior a 6 Baht. Puede notarse que ninguna ubicación del depósito nos permitirá obtener 
arroz de más de 3 campos, por tanto esta solución es óptima y besthub debe retornar 3.

Las competencias en la IOI no requieren lectura/salida de datos estándar. Sin embargo,
el problema fue adaptado a la lectura de datos por entrada estándar.
El programa debe leer un único caso de prueba.
El pseudo-código para leer los datos de entrada es el siguiente:
	leer(R,L,B)
	for(i=0; i<R; i++){
		leer(X[i])
	}
La respuesta es impresa como siempre, por salida estándar.

Nota: A diferencia de otros problemas binarios de este juez, es decir, Aceptado/No Aceptado,
este problema tiene puntaje parcial sobre 100 puntos. Un algoritmo por fuerza bruta, obtendra unos
cuantos pero no muchos y un programa óptimo, recibirá la totalidad de los puntos.

A continuación se describe la distribución de los puntos para diferentes casos de prueba.

Subtareas
Subtarea 1 (17 puntos)
* 1 ≤ R ≤ 100
* 1 ≤ L ≤ 100
* 0 ≤ B ≤ 10.000
* No dos (2) campos de arroz pueden compartir la misma coordenada (se aplica solo para esta subtarea).
Subtarea 3 (26 puntos)
* 1 ≤ R ≤ 5.000
* 1 ≤ L ≤ 1.000.000
* 0 ≤ B ≤ 2.000.000.000
Subtarea 2 (25 puntos)
* 1 ≤ R ≤ 500
* 1 ≤ L ≤ 10.000
* 0 ≤ B ≤ 1.000.000
Subtarea 4 (32 puntos)
* 1 ≤ R ≤ 100.000
* 1 ≤ L ≤ 1.000.000.000
* 0 ≤ B ≤ 2.000.000.000.000.000