C - Náhradné cvičenie

Časový limit: 3s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Náš univerzitný informačný systém chceme doplniť o novú funkciu, ktorá by pomohla učiteľom nájsť vhodný termín pre konanie náhradných prednášok alebo písomiek. Kedže na vysokej škola má každý študent svoj vlastný študijný plán, nie je jednoduché nájsť termín, ktorý by vyhovoval všetkým študentom. Od nového systému očakávame, že učiteľ v ňom zadá dĺžku trvania písomky a zvolí deň, v ktorom chce písomku realizovať. Následne mu systém vypíše optimálny čas konania písomky.

Úloha

Daný je počet minút T, ktoré potrebuje vyučujúci na písomku. Ďalej je daný počet študentov N a ich rozvrh v príslušnom dni. Nájdite termín v ktorom sa písomka môže konať. Ak je možných termínov viac, vypíšte ten z nich, ktorého začiatok je najbližšie k času 12:00. Ak je stále termínov viac, vypíšte ten, ktorý začína skôr.

Vstup

Prvý riadok vstupu obsahuje počet testovacích sád Q, (1≤Q≤50). Ďalej bude nasledovať Q sád, každá v takomto tvare:

Prvý riadok testovacej sady obsahuje dve medzerou oddelené kladné celé čísla T N, (1≤T≤180),(1≤N≤100).
Ďalej bude nasledovať N riadkov popisujúcich rozvrhové akcie jednotlivých študentov.
Jeden takýto riadok bude obsahovať kladné celé číslo P (1≤P≤15) a za ním P časových intervalov vo formáte HH:MM-HH:MM , oddelených medzerou.

Študent vo svojom rozvrhu môže mať aj predmety, ktoré sa časovo prekrývajú. Začiatok aj koniec každej výučby bude v intervale 06:00-18:00.

Výstup

Pre každú sadu zo vstupu vypíšte termín, v ktorom sa náhradné cvičenie môže konať. Môžete predpokladať, že vždy bude existovať termín pre náhradné cvičenie (najneskôr teda so začiatkom o 18:00).

Príklad

Vstup

3
90 2
2 07:00-09:00 11:00-15:00
1 08:00-09:30
90 3
3 09:00-10:30 13:00-14:00 15:00-16:00
2 09:30-11:00 13:00-14:00
2 08:30-10:00 15:00-16:00
45 3
3 09:00-10:30 13:00-14:00 15:00-16:00
2 09:30-11:00 13:00-14:00
2 08:30-10:00 15:00-16:00

Výstup

09:30-11:00
11:30-13:00
12:00-12:45

03 Finále 1