Piscina (2) P44496

Com que en una certa piscina es fan un munt d’activitats dirigides, les normes d’ús són molt estrictes:

• Les franges lliures només són d’un minut.

• Si es fa servir una franja lliure, cal esperar com a mínim $x$ segons fins a poder-ne usar una altra.

Disposeu d’una llista amb les franges lliures, i voleu banyar-vos $m$ minuts, com a mínim. Quina és la màxima $x$ que ho permet?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre de minuts $m$ i el nombre de franges $n$, seguit de $n$ triplets $H$:$M$:$S$, que indiquen que hi ha un carril lliure durant un minut començant a les $H$:$M$:$S$. Assumiu $2 \le m \le n \le 1000$, que les hores estan entre les $00$:$00$:$00$ i les $23$:$59$:$00$, i que no hi ha solapaments entre franges. El final de l’entrada es marca amb un cas especial amb $m = n = 0$.

Sortida

Per a cada cas, escriviu la màxima $x$ que permet un temps total de bany de $m$ minuts o més.