Problema número 251

Parkímetros

Tiempo máximo: 3,000-4,000 sMemoria máxima: 8192 KiB
Parkímetro antiguo con bajas prestaciones

Debido a su afán recaudatorio, el alcalde del pueblecito de la sierra Pese Taspamí ha decido poner parkímetros en la zona centro. Toda la oposición está en contra, y consideran que la medida es una demostración más de la poca inteligencia del alcalde: la zona centro es peatonal desde hace años.

Además, por ahorrarse dinero, los parkímetros los ha adquirido de saldo y son muy malos; no sólo no devuelven cambio, algo habitual en este tipo de aparatos, sino que además sólo permiten pagar con un número máximo de monedas. Si un ciudadano, al ir a pagar, introduce más monedas de las que el parkímetro es capaz de gestionar, éste comienza a devolverlas y no las admite.

Al descubrir esta limitación, el alcalde se ha quedado muy preocupado porque significa que el número de pagos posibles está limitado, lo que restringe los precios que puede cobrar.

Entrada

La entrada comenzará con un número indicando la cantidad de casos de prueba que vendrán a continuación.

Cada caso de prueba estará compuesto de dos líneas. La primera tendrá dos números mayores que 0 indicando la cantidad de monedas diferentes que están en uso en el pueblo, y el número máximo de monedas simultáneas que los parkímetros son capaces de procesar. Ninguno de los dos valores será mayor que 10.

A continuación, se indicará, en la segunda línea del caso de prueba, el valor de las diferentes monedas existentes, medidas en céntimos. El valor de la moneda más alta no superará nunca los 200 céntimos.

Salida

Por cada caso de prueba, el programa indicará el número de posibles precios distintos que se pueden pagar en los parkímetros.

Entrada de ejemplo

4
8 1
1 2 5 10 20 50 100 200
4 2
1 2 5 10
8 2
200 100 50 20 10 5 2 1
3 3
1 2 5

Salida de ejemplo

8
12
39
13