Pepe Casanova
Pepe Casanova es un ligón de los de antaño, que intenta encandilar a las chicas con canciones románticas. A tal efecto, y de cara al veraneo en una playa del sur, decide conseguir una cinta para el radiocasete de su coche con las mejores canciones de amor.
Pepe es muy peculiar en sus gustos, y además anda algo escaso de dinero, por lo que en lugar de comprar una de tantas recopilaciones que circulan por el mercado discográfico, quiere grabársela él mismo. Rebuscando entre sus viejos vinilos, ha confeccionado una lista con sus canciones favoritas, apuntando la duración individual de cada una. Lamentablemente, su cinta de dos caras no tiene capacidad suficiente para contener todas las canciones, así que Pepe ha otorgado una puntuación a cada canción (cuanto más le gusta, mayor es la puntuación).
¿Puedes ayudar a Pepe a conseguir la mejor cinta (aquella cuya suma de puntuaciones de las canciones grabadas sea lo mayor posible), teniendo en cuenta que no puede repetir canciones, las escogidas han de caber enteras y no es admisible que una canción se corte a la mitad al final de una cara de la cinta?
Entrada
La entrada está formada por una serie de casos de prueba. Cada caso comienza con el número N de canciones (1 ≤ N ≤ 30) en la lista de Pepe. Después aparece la duración de cada una de las dos caras de la cinta, y a continuación aparecen N líneas cada una con dos números enteros que representan la duración y la puntuación de cada una de las canciones. Ninguna de las duraciones de la entrada supera los 1.000, y las puntuaciones nunca son mayores de 10.000.
La entrada termina con un 0.
Salida
Para cada caso de prueba se escribirá una línea con la puntuación total máxima conseguida al grabar algunas canciones completas en las dos caras de la cinta.
Entrada de ejemplo
4 90 50 80 40 20 40 50 60 10 0
Salida de ejemplo
150