El Granjero Juan está en el Mercado para comprar insumos para su granja. El tiene en su monedero ~K~ monedas ~(1 \leq K \leq 16)~, cada una con un valor en el rango ~1..100,000,000~. A GJ le gustaría hacer una secuencia de ~N~ compras ~(1 \leq N \leq 100,000)~, donde la compra ~I~ ésima cuesta ~c(i)~ unidades de dinero ~(1 \leq c(i) \leq 10,000)~. Conforme él va haciendo su secuencia de compras, él puede periódicamente parar y pagar, con una sola moneda, todas las compras hechas desde su ultimo pago (por supuesto, la sola moneda que él usa debe tener valor suficientemente alto para pagar todas esas compras). Desafortunadamente, los vendedores del Mercado no tienen nada de cambio, entonces cuando GJ usa una moneda cuyo valor es mayor que la cantidad de dinero que él debe, él tristemente no recibe nada de cambio.

Por favor, calcule la cantidad máxima de dinero con la que puede terminar GJ después de hacer sus ~N~ compras en secuencia. Dé como salida ~-1~ si es imposible que GJ haga todas sus compras.

Entrada

• Línea 1: Dos enteros, ~K~ y ~N~.
• Líneas 2..1+K: Cada línea contiene la cantidad de dinero de una de las monedas de GJ.
• Líneas K+2..1+N+K: Esas ~N~ líneas contienen los costos de las compras que piensa hacer GJ.

Salida

La máxima cantidad de dinero con que GJ puede terminar o ~-1~ si GJ no puede hacer todas sus compras

Ejemplo de Entrada

3 6
12
15
10
6
3
3
2
3
7

Deatalles de la Entrada: GJ tiene tres monedas con valores ~12, 15~ y ~10~. El debe hacer compras en secuencia de valores ~6, 3, 3, 3, 2, 3~ y ~7~.

Ejemplo de Salida

12

Deatalles de la Salida: GJ gasta su moneda de ~10~ unidades en las primeras dos compras, luego la moneda de ~15~ unidades en las compras restantes. Esto lo deja con la moneda de ~12~ unidades.

USACO 2013 November Contest, Gold Problem 3. No Change.