Problema número 524

Compe y Tencia

Tiempo máximo: 1,000-3,000 sMemoria máxima: 4096 KiB
Fachada con tienda

Hasta hace bien poco la vida era sencilla en mi pequeño pueblo situado en la serranía de Cuenca. Un bar, un colmado y una farmacia eran los únicos negocios presentes en la localidad, que disfrutaban de sus respectivos monopolios poniendo unos precios quizá un poco excesivos pero merecidos. Al fin y al cabo que te traigan desde la capital los productos que quieres hay que pagarlo.

Sin embargo, hace unos pocos meses la vida se torció para Doña Compe, la dueña del colmado. La culpable es la Señora Tencia, que ha decidido abrir una tienda en la otra esquina del pueblo.

Pero el trastorno no se queda en CompeTencia. También a nosotros los aldeanos nos ha trastocado la paz que disfrutábamos desde hacía generaciones. Ahora cuando vamos a comprar, tenemos que decidir a qué tienda vamos.

Mi objetivo, como el de todos, es pagar lo menos posible. Para eso he cogido los catálogos de precios de cada una de las tiendas y he planificado mis siguientes compras. Para cada una de ellas he establecido a cuánto ascendería mi cuenta en ambas tiendas, de forma que me ayude a decidir a cuál de las dos voy en cada momento. Eso sí, en aras de la paz y armonía de nuestro pueblo, me he marcado un número mínimo de visitas a cada una de las tiendas, para que ninguna de las dos empresarias se moleste conmigo (¡las dos son amigas de la infancia!).

Entrada

La entrada está compuesta por distintos casos de prueba, cada uno representando la planificación de una serie de compras.

Cada caso de prueba comienza con el número N de compras planificadas (como mucho 10.000). En la siguiente línea aparecen dos números, CT, indicando el número mínimo de veces que tengo que ir a la tienda de Compe y Tencia respectivamente para que no se enfaden (C + T ≤ N). Por último aparecerán dos líneas con N números cada una, indicando el precio de la cesta de cada compra en la tienda de CompeTencia respectivamente. Se garantiza que todas las cantidades son enteras entre 1 y 1.000.

La entrada termina con un 0, que no debe procesarse.

Salida

Por cada caso de prueba se escribirá una línea con el gasto mínimo en las compras.

Entrada de ejemplo

6
2 2
1 2 3 4 5 6
6 5 4 3 2 1
5
2 2
6 6 6 6 6
1 2 3 4 5
0

Salida de ejemplo

12
18