A Karel le gustan los cupones de descuento. Recientemente consiguió un bloc con varios cupones. Los cupones del bloc funcionan de la siguiente manera:

• Cada cupón tiene un número, llamémosle a ese número \(C\).
• El cupón te permite comprar \(C\) artículos y llevarte gratis el de menor costo.

Es decir, si tu cupón tiene el número \(3\) y compras artículos que valen \(\$30\), \(\$20\) y \(\$50\) pesos, entonces el artículo de \(\$20\) pesos (por ser el más barato) no tienes que pagarlo y pagarías únicamente \(\$80\) pesos por los tres artículos.

Karel quiere comprar varios artículos usando sus cupones. Karel sabe el precio de todos los artículos. Por supuesto, el precio que pague Karel por todos los artículos dependerá de la forma en la que use los cupones. Ayuda a Karel a determinar cuál es el precio mínimo que tiene que pagar por todos los artículos si utiiza sus cupones de forma óptima.

En la fila \(1\) del mundo habrá montones de zumbadores que representan el precio de los artículos que quiere comprar Karel. Karel debe comprar TODOS los artículos.

En la fila \(2\) del mundo habrá montones de zumbadores que representan los números \(C\) de los cupones de Karel. Karel siempre tendrá al menos \(1\) cupón.

Problema

Escribe un programa que determine cuál es el menor precio que Karel debe pagar por todos los artículos y deje un montón de zumbadores igual a ese número en la posición \((1, 1)\).

Ejemplos

Entrada

Salida

Explicación

Karel tiene dos cupones, el primero le permite comprar \(2\) artículos sin pagar el más barato y otro \(3\) artículos sin pagar el más barato.

Karel puede utilizar el primer cupón con los dos artículos de precio \(8\) y ahorrarse uno de ellos.

Luego puede utilizar el segundo cupón con los artículos de precio \(7\), \(5\) y \(5\) ahorrándose uno de los de \(5\).

El costo total de los artículos restantes sería: \(5 + 3 + 2 + 7 + 8 = 25\)

Consideraciones

• Karel inicia en la posición \((1, 1)\) orientado al norte.
• Karel lleva infinitos zumbadores en la mochila.
• El mundo de Karel es rectangular sin paredes internas.
• No hay espacios entre los montones de zumbadores de la primera y segunda fila.
• Ni los artículos ni los cupones están ordenados.
• No importa la posición ni la orientación final de Karel.
• Únicamente importan los zumbadores que dejes en la casilla \((1, 1)\).

Subtareas

• (7 puntos): Todos los cupones tienen \(C = 1\), es decir, te permiten comprar un producto gratis. Los artículos están ordenados por precio de menor a mayor.
• (8 puntos): Karel sólo tiene un cupón. Los artículos están ordenados por precio de menor a mayor.
• (12 puntos): Todos los cupones tiene la misma \(C\). Los artículos están ordenados por precio de menor a mayor.
• (28 puntos): Todos los artículos cuestan lo mismo.
• (45 puntos): Sin restricciones adicionales.

Fuente: OMIPS 2022 (César Cepeda)