Problema 2
Oferta
oferta.pas, oferta.c, oferta.cpp

Es muy común ver en las tiendas departamentales ofertas del tipo 3×2, la cual consiste en que compras 3 artículos, llevándote el de menor precio gratis. En este tipo de ofertas el cliente debe de agrupar cuidadosamente los artículos que quiere de cierta forma, que al dárselos al cajero(a) le haga el mayor descuento posible.
Supongamos se quieren comprar seis artículos cuyo precio es $1.00, $2.00, $3.00, $4.00, $5.00 y $6.00 respectivamente, podemos hacer varias combinaciones pagando diferente cantidad:
Si un paquete contiene los artículos que cuentan $1.00, $4.00 y $5.00 y en el otro paquete los de precio $2.00, $3.00 y $6.00 se pagaría:
$1.00+$4.00+$5.00-$1.00=$9.00 por el primer paquete.
$2.00+$3.00+$6.00-$2.00=$9.00, por lo que se pagaría un total de $18.00.
Por otro lado, si un paquete contiene los artículos de $1.00, $2.00, $4.00 y el otro con $3.00, $5.00 y $6.00 se pagaría:
$1.00+$2.00+$4.00-$1.00=$6.00 del primer paquete.
$3.00+$5.00+$6.00-$3.00=$11.00, por lo que pagarías un total de $17.00.
Por lo cual le convendría más hacer el segundo paquete, pero existe un acomodo en el cual se podría pagar ¡solamente $16.00!

Problema
El problema que debes resolver es un poco más complicado: teniendo una oferta del tipo n×k, debes decir cual es la cantidad que pagaría el cliente, si hace el mejor acomodo de los artículos.

Entrada
La entrada consistirá de dos líneas. En la primera estará el número n y el número k, 0 ≤ kn ≤ 1000.
En la segunda línea comenzará con un entero p, (la cantidad de artículos que quieres comprar, siempre será un múltiplo de k). Después habrá p enteros positivos, indicando los precios de cada uno de los p artículos, 0 ≤ p ≤ 1000.

Salida
Un solo entero, la cantidad mínima que podría pagar el cliente.

Ejemplo

entrada salida
3 2
6 1 2 3 5 4 6
16

 


Concurso: 12a OMI, Aguascalientes - Examen de Selección (2a parte). 5/Mayo/2007
Propuesto por: Dulce Irene Valdivia Martínez
Ayuda: entradas, salidas, sugerencias
Soluciones: oferta.pas, oferta.c, oferta.cpp


World of πer