Cassete P65849

Tenéis una cassete con $t$ segundos de duración, y $n$ canciones con duraciones $d_1, d_2, \dots, d_n$. Vuestro objetivo es guardar el máximo número de canciones enteras en la cassete. Debéis tener en cuenta que las canciones deben grabarse con un segundo de separación entre ellas.

Entrada

La entrada consiste en una serie de casos separados con una línea en blanco. Cada caso consiste en dos líneas: La primera tiene $t$ y $n$. La segunda tiene $n$ números: $d_1, d_2, \dots, d_n$. Podéis asumir $1 \le t \le 10^8$, $n \ge 1$, y que para cada $i$, $1 \le d_i \le 10^6$.

Salida

Para cada caso de la entrada, hay que escribir el número máximo de canciones que caben enteras en la cassete, teniendo en cuenta que deben separarse con un segundo.

Puntuación

• TestA:   En algunos juegos de pruebas se cumplirá $n \le 100$.

• TestB:   Otros juegos de pruebas incluirán casos con $n \le 10^5$.