Plan zajęć

Limit pamięci: 32 MB

Pan Wojciech postanowił rozkręcić nowy biznes i ma zamiar otworzyć Sobotnią Szkółkę Hakowania (SSH), której będzie dyrektorował. Napisał już stosowny program nauczania, który zatwierdziło ministerstwo, zatrudnił nauczycieli, wynajął sal wykładowych w pobliskiej remizie strażackiej i nie pozostało mu nic innego jak ogłosić nabór do klas.

Problem w tym, że trzeba najpierw ułożyć plan zajęć dla SSH. Pan Wojciech już próbował, ale niestety nie jest usatysfakcjonowany ze swojej pracy. Jest świadomy tego, że jako dyrektor będzie musiał siedzieć w szkole od samego rana do czasu, aż ostatni uczeń opuści mury remizy. A z planu, który sobie przygotował, wynikało, że będzie musiał siedzieć tam cały dzień. Twoim zadaniem jest pomóc panu Wojciechowi i przygotować optymalny plan zajęć.

W szkole będzie nauczanych przedmiotów. Każdy przedmiot ma przypisanego nauczyciela, który będzie go wykładał, oraz klasę, która będzie na te wykłady uczęszczała. Każdej soboty na przedmiot ma być przeznaczona jedna godzina lekcyjna.

W danej chwili nauczyciel może prowadzić tylko jeden przedmiot, klasa może słuchać tylko jednego nauczyciela, a w sali mogą odbywać się tylko jedne zajęcia.

Przykład

Załóżmy, że w SSH jest zatrudnionych dwóch nauczycieli, są dwie klasy oraz sześć przedmiotów: (1,1), (1,1), (1,2), (2,2), (2,2), (2,2). Tutaj przedmioty opisujemy jako pary (numer nauczyciela, numer klasy). Zauważmy, że dany nauczyciel może wykładać dla danej klasy więcej niż jeden przedmiot.

Jeśli mamy do dyspozycji tylko jedną salę wykładową, to pan Wojciech będzie musiał siedzieć w szkole przez 6 godzin (żadne zajęcia nie będą mogły odbywać się równolegle, a mamy ich sześć). Ale już dysponując dwoma salami, będzie można skrócić ten czas do czterech godzin. Optymalny plan może wyglądać następująco:

Zadanie

• wczyta liczbę zasobów w ludziach i nieruchomościach jakimi dysponuje pan Wojciech oraz napisany przez niego program nauczania;
• obliczy minimalną liczbę godzin, które pan Wojciech będzie musiał przeznaczyć na zarządzanie szkołą każdej soboty, oraz stosowny plan zajęć;
• wypisze wynik.

Wejście

W pierwszym wierszu wejścia znajdują się cztery liczby całkowite oddzielone pojedynczymi odstępami (). Oznaczają one kolejno: liczbę nauczycieli w szkole, liczbę klas, liczbę nauczanych przedmiotów oraz liczbę dostępnych sal wykładowych. W kolejnych wierszach opisane są przedmioty. -szy wiersz zawiera dwie liczby całkowite opisujące -ty przedmiot (, ). Oznaczają one odpowiednio: nauczyciela, który będzie uczył -tego przedmiotu, oraz klasę, która będzie uczęszczała na ten przedmiot.

Wyjście

W pierwszym wierszu wyjścia należy zapisać jedną liczbę całkowitą oznaczającą minimalną liczbę godzin, które dyrektor będzie musiał spędzić w szkole każdej soboty. (Nigdzie nie jest powiedziane, że godzina lekcyjna w SSH trwa 45 minut, więc może być całkiem duże.) W kolejnych wierszach należy zapisać plan zajęć realizowalny w godzinach. W -szym wierszu należy wypisać jedną dodatnią liczbę całkowitą nie większą niż oznaczają godzinę lekcyjną, w której będzie się odbywało nauczanie -tego przedmiotu.

Jeśli istnieje więcej niż jedno rozwiązanie, Twój program może wypisać dowolne z nich.

Przykład

Dla danych wejściowych:

2 2 6 2
1 1
1 1
1 2
2 2
2 2
2 2

poprawną odpowiedzią jest:

4
4
3
1
4
3
2

Autor zadania: Tomasz Idziaszek.