Plan de formación
En la próxima edición de una conocida competición de programación los organizadores han decidido que publicarán de antemano las categorías a las que pertenecerá cada problema, para que los participantes puedan saber qué temas prepararse. Tras unas cuantas jornadas decidiendo, ya saben cuántos problemas quieren poner de cada una de las categorías.
Se enfrentan ahora al problema de seleccionar los problemas de entre todos los que han ido pensando desde la edición anterior (lo que familiarmente llaman "problemas en la incubadora"). En una situación ideal esta parte sería fácil. Si se parte una colección de problemas posibles y se conoce la categoría a la que pertenece cada uno, para cada categoría de problema que aparece en el plan de formación hay que mirar cuántos problemas de esa categoría hay pensados y:
- Si hay más problemas disponibles que necesarios, elegir algunos en base a su nivel de dificultad.
- Si en la incubadora hay exactamente los mismos problemas disponibles que los que necesitamos para el plan de formación, cogerlos todos.
- Si hay menos problemas disponibles que los que queríamos poner, reducir los problemas de esa categoría y ponerlos todos. El plan de formación quedará, claro, más corto de lo previsto inicialmente.
El problema es que las situaciones ideales pocas veces se dan. En el mundo real los problemas suelen pertenecer a varias categorías (por ejemplo, un problema puede encajar en la categoría "ordenación" y también en "algoritmos voraces"). Por lo tanto el procedimiento anterior necesita algunos ajustes. De momento nos conformamos con saber si podremos poner tantos problemas como habíamos propuesto originalmente o tendremos que conformarnos con poner alguno menos.
Entrada
La entrada está formada por distintos casos de prueba, cada uno ocupando varias líneas.
La primera línea de cada caso contiene dos números: la cantidad de categorías seleccionadas en el plan de formación (1 ≤ C ≤ 30) y el tamaño de la incubadora de problemas (1 ≤ P ≤ 1000). La segunda línea tiene C números con la cantidad de problemas que se quiere que la competición tenga de cada categoría (su suma no será mayor que P). A continuación aparecen P líneas, una por problema, con la lista de categorías a las que pertenece cada uno. La lista viene dada como una secuencia de números entre 1 y C terminada con un 0 y, si tiene elementos, nunca aparecerán repetidos.
Salida
Por cada caso de prueba se escribirá una línea con el número de problemas que, como mucho, podrá tener el plan de formación de modo que no se exceda el número de problemas asignados a cada categoría.
Entrada de ejemplo
3 3 1 1 1 1 2 0 2 3 0 3 0 3 3 1 1 1 3 1 2 0 2 0 2 0
Salida de ejemplo
3 2