Tienes monedas de \(k\) valores distintos, con una cantidad ilimitada de cada uno. ¿Cuál es la menor cantidad de monedas que suman exactamente \(x\)? Si no se puede, la respuesta es \(-1\). (Con \(x = 0\) la respuesta es \(0\).)

Entrada

La primera línea tiene \(T\) \((1 \le T \le 10)\). Cada caso viene en dos líneas: \(k\) y \(x\) \((1 \le k \le 12,\ 0 \le x \le 10^4)\), y los \(k\) valores \((1 \le c_i \le 2^{31} - 1)\).

Salida

Para cada caso, la menor cantidad de monedas o \(-1\).

Ejemplo 1

Entrada

3
3 11
1 2 5
1 3
2
1 0
1

Salida

3
-1
0

Ejemplo 2

Entrada

1
2 7
2 4

Salida

-1

Basado en el problema 322 de LeetCode, Coin Change, adaptado a entrada y salida estándar; enunciado redactado para este juez. Es parte de la lista Grind 75 de Yangshun Tay.