Comedor escolar P52658
El encargado de un comedor escolar tiene que equilibrar el presupuesto para poder servir comidas a tantos niños como sea posible. Por ejemplo, si el presupuesto consta de T=1000 euros, una ensalada cuesta 2 euros y un bistec cuesta 6 euros, el encargado puede usar el presupuesto para comprar 500 ensaladas y 0 bistecs, o 497 ensaladas y 1 bistec, o 494 ensaladas y 2 bistecs, o 2 ensaladas y 166 bistecs, etc. Sabiendo que cada niño necesita una ración de cada uno de los platos, se te pide que calcules para cuántos niños da el presupuesto. En el ejemplo anterior la respuesta es 125, puesto que es posible servir 125 ensaladas y 125 bistecs (en este ejemplo no sobra ningún euro, pero en general puede sobrar dinero).
Entrada
Una línea con el número N>0 de casos. La primera línea de cada caso contiene el número 0≤ T≤ 105 de euros de presupuesto, y el número K de platos distintos. La línea siguiente contiene K números entre 1 y 105, con el coste de una ración de cada uno de los K platos.
Salida
Escribe una línea para cada caso, con el número máximo de raciones completas (con un plato de cada tipo) que es posible servir con el presupuesto dado.
Puntuación
- TestA: Resolver casos con K=1. 20 Puntos
- TestB: Resolver casos con K=2. 20 Puntos
- TestC: Resolver casos con K=3. 25 Puntos
- TestD: Resolver casos con K≤ 10. 35 Puntos
Input
1 200 1 57
Output
3
Input
3 1000 2 2 6 1000 2 17 21 1000 2 1 100
Output
125 26 9
Input
1 99000 5 7 1025 30 1 150
Output
81
- Author
- Omer Giménez
- Language
- Spanish
- Official solutions
- C++
- User solutions
- C++