Españistán P86901

¡Que ardilla tan bonita! ¡Y que bosques! ¿Porque no aprovechamos para construir unos cuantos apartamentos por la zona?

Un terreno consiste en una secuencia de números, con las alturas de cada parcela de terreno. Para construir los apartamentos necesitamos allanar un subsecuencia consecutiva de parcelas (un solar) moviendo tierra de una parcela a otro del solar, hasta conseguir que todas las parcelas tengan la misma altura. El siguiente ejemplo muestra como formar un solar de 5 parcelas en un terreno de 9 parcelas.

Para allanar un solar sólo puedes mover unidades de tierra de las parcelas que pertenece al mismo, y retirar tierra del solar. Este último proceso es muy caro (y los malditos ecologistas se te tiran al cuello) por lo que interesa tener que retirar la mínima cantidad de unidades de tierra. Si en el ejemplo anterior hubiéramos intentado allanar el solar situado dos parcelas más a la izquierda, hubiéramos tenido que mover una 1 unidad y retirar otras 3.

Te pedimos que hagas un programa que, dadas las alturas de un terreno de tamaño n, descubra cuál es el mejor lugar para formar un solar de tamaño s. En concreto, buscamos aquel solar tal que:

• Haya que transportar fuera del solar la menor cantidad de tierra posible.
• En caso de empate, que se tenga que mover dentro del solar la menor cantidad de unidades de tierra.
• En caso de empate, que el solar esté tan a la izquierda del terreno como sea posible.

Entrada

Cada entrada contiene un único caso de prueba, formado por dos líneas. La primera línea contiene el tamaño n del terreno, el tamaño 0<s<n del solar que queremos construir, y una altura t mayor que las alturas de todas las parcelas. La segunda línea contiene n números enteros entre 0 y t−1 (ambos inclusive) con las alturas de las n parcelas.

Salida

Escribe dos líneas. En la primera línea, escribe los índices de la primera y la última parcela del mejor solar de tamaño s (empezando a contar por 1), y en la segunda, el número de unidades de tierra que es necesario retirar del solar propuesto, y el número de unidades de tierra que hay que mover de un sitio a otro del solar para que éste quede llano.

Puntuación

• Test1:  20 Puntos 

  Resolver varias entradas donde n, s≤ 100, t≤ 2.

• Test2:  20 Puntos 

  Resolver varias entradas donde n, s≤ 100, t≤ 10.

• Test3:  20 Puntos 

  Resolver varias entradas donde n≤ 100000, s≤ 100, t≤ 10.

• Test4:  20 Puntos 

  Resolver varias entradas donde n, s≤ 100000, t≤ 10.

• Test5:  20 Puntos 

  Resolver varias entradas donde n, s, t≤ 100000.