Biuro podróży

Limit pamięci: 64 MB

Z uwagi na nadchodzące wakacje wiele osób zaczyna planować wyjazdy. Aby zapewnić sobie towarzystwo, każdy chce wybrać się na wycieczkę w grupie ze swoimi znajomymi. Biuro podróży ma w swej ofercie różne wycieczki adresowane do grup o określonej liczebności - dla każdej wycieczki podany jest dolny i górny limit na liczbę osób, które mogą na nią pojechać. Każda grupa może wybrać tylko jedną wycieczkę. Co więcej, każda wycieczka może zostać wybrana przez co najwyżej jedną grupę. Pracownicy biura podróży poprosili Cię o pomoc. Chcą oni zorganizować jak najwięcej wycieczek. Twoim zadaniem jest przyporządkowanie grup do wycieczek w taki sposób, aby można było zorganizować największą możliwą liczbę wycieczek.

Zadanie

Napisz program, który:

• wczyta opis grup i wycieczek ze standardowego wejścia,
• przyporządkuje grupy do wycieczek w taki sposób, aby liczba organizowanych wycieczek była największa,
• wypisze wynik na standardowe wyjście.

Wejście

Pierwszy wiersz standardowego wejścia zawiera dwie liczby całkowite oraz oddzielone pojedynczym odstępem, , ; jest liczbą grup, jest liczbą wycieczek. Grupy są ponumerowane od do , a wycieczki od do .

Kolejne wierszy zawiera wielkości poszczególnych grup. Wiersz -szy zawiera liczbę całkowitą - wielkość -tej grupy, .

Kolejne wierszy zawiera opisy wycieczek, jedna wycieczka w wierszu. Wiersz -szy zawiera dwie liczby całkowite i , oddzielone pojedyńczym odstępem: jest minimalną, a maksymalną liczebnością grupy, która może pojechać na tę wycieczkę, .

Wyjście

Pierwszy wiersz wyjścia powinien zawierać jedną liczbę całkowitą - maksymalną liczbę wycieczek, które mogą zostać zorganizowane. Kolejne wierszy powinno zawierać opisy przyporządkowań grup do wycieczek. Każdy z tych wierszy powinien zawierać parę liczb całkowitych oddzielonych pojedynczym odstępem: numer grupy oraz numer wycieczki. Może istnieć wiele poprawnych rozwiązań, a Twój program ma wypisać dowolne z nich.

Przykład

Dla danych wejściowych:

5 4
54
6
9
42
15
6 6
20 50
2 8
7 20

poprawną odpowiedzią jest:

3
2 1
3 4
4 2

Autor zadania: Krzysztof Sikora.