[149A] Viaje de negocios

Enlace a Codeforces

Que alegría! Los padres de Petya se fueron a un viaje de negocios por todo el año y el pequeño travieso fue dejado a sus anchas. Petya se puso absolutamente feliz. Saltó en la cama y lanzó cojines durante todo el día, hasta que...

Hoy, Petya abrío el armario y encontró una nota de miedo allí. Sus padres le habían dejado deberes: debe regarles su flor favorita todo el año, y cada día, en la mañana, en la tarde y en la noche. «Espera un segundo!» pensó Petya. Él sabe que si cumple la tarea de sus padres en el i-ésimo ($1 \leq i \leq 12$) mes del año, entonces la flor crecerá $a_i$ centímetros, y si no riega la flor en el i-ésimo mes, entonces no crecerá ese mes. Petya también sabe que como sea que lo intente, sus padres no creerán que ha estado regando la flor si crece estrictamente menos de $k$ centímetros.

Ayuda a Petya a elegir el mínimo de meses en los que regar la flor, de modo que crezca no menos de $k$ centímetros.

Entrada

La primera línea contiene un entero $k$ ($0 \leq k \leq 100$). La siguiente línea contiene doce enteros separados por espacios: el i-ésimo número ($1 \leq i \leq 12$) de la línea representa a $a_i$ ($0 \leq a_i \leq 100$).

Salida

Imprime un entero - el mínimo de meses en los que Petya debe regar la flor, de modo que crezca no menos de $k$ centímetros. Si la flor no puede crece $k$ centímetros en un año, imprime -1.

Ejemplos

input:
5
1 1 1 1 2 2 3 2 2 1 1 1

output:
2

input:
0
0 0 0 0 0 0 0 1 1 2 3 0

output:
0

input:
11
1 1 4 1 1 5 1 1 4 1 1 1

output:
3

Nota

Consideremos el primer ejemplo. Allí es suficiente regar la flor durante el séptimo y noveno mes. De este modo la flor crecerá exactamente cinco centímetros.

En el segundo ejemplo, los padres de Petya le creerá incluso si la flor no crece del todo ($k = 0$). Por lo tanto, Petya puede no regar la flor.