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\le T\le 10^5$ de euros de presupuesto, y el número $K$ de platos distintos. La línea siguiente contiene $K$ números entre 1 y $10^5$, 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$.

• TestB:   Resolver casos con $K=2$.

• TestC:   Resolver casos con $K=3$.

• TestD:   Resolver casos con $K\le 10$.