Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_06_08 - Egzamin

Tak, to już dziś! Egzamin ze "Wstępu do algorytmów". Profesor Algobit przygotował zestaw trudnych i bardzo trudnych zadań dla swoich podopiecznych. Jest on człowiekiem, który swoją wiedzę z algorytmów wykorzystuje często w życiu codziennym i jest tak też i tym razem. Oprócz egzaminu, studenci muszą się stawić na odpowiednią godzinę, która nie jest przedstawiona wprost. 

Przed egzaminem, profesor postawił kilka warunków, do których uczniowie muszą się dostosować. Oto one:

  • każdy student wybiera sam długość czasu, w jakim chce pisać egzamin. Im krótszy czas, tym łagodniej będzie oceniany
  • zdający wchodzą według listy w dzienniku
  • na egzamin wchodzi maksymalnie tyle osób, ile jest miejsc na sali
  • egzamin rozpoczyna się o tej samej godzinie dla wszystkich uczestników danej grupy. Studenci, którzy zadeklarowali krótszy czas na pisanie egzaminu odkładają długopisy i grzecznie czekają, aż wszyscy z sali skończą pisać. 
  • gdy skończy pisać ostatnia osoba z danej grupy, na salę wchodzą następne osoby (czas zamiany grup jest pomijalnie mały)

Profesor jest osobą, która bardzo szanuje swój czas, dlatego też znając czasy pisania egzaminu kolejnych studentów dobiera tak grupy, aby całkowity czas był najkrótszy.

Twoim zadaniem nie jest zdanie tego egzaminu, tylko określenie godziny, w której on się skończy.

Uwaga! Egzamin może trwać wiele dni ale nas interesuje tylko godzina jego zakończenia. Rozpatrujemy format 24 godzinny.

Wejście

W pierwszym wierszu jedna liczba t określająca ilość zestawów danych (t < 1000).

Dla każdego zestawu danych:

Najpierw dwie liczby s i n określające odpowiednio ilość studentów na liście oraz pojemność sali (0 < s ≤ 100000, 0 < n < 1000) i godzina rozpoczęcia egzaminu w formacie hh:mm np. 08:30.

W drugim wierszu każdego zestawu s liczb naturalnych dodatnich nie większych niż 1000, określających zadeklarowane czasy (w minutach) na egzamin przez kolejnych studentów.

Wyjście

Dla każdego zestawu godzina zakończenia egzaminu w formacie: gg:mm 

Przykład

Wejście:
1
7 2 08:00
5 6 4 3 6 7 8

Wyjście:
08:24

Dodane przez:Marcin Kasprowicz
Data dodania:2013-05-01
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.