Konkurs programistyczny

Limit pamięci: 32 MB

Bartuś i jego koledzy startują w Drużynowym Konkursie Programistycznym. Każda drużyna składa się z zawodników i ma do dyspozycji komputerów. Zawody trwają minut i w tym czasie zawodnicy mają do rozwiązania zadań programistycznych. Dodatkowo, drużynom przyznawane są punkty karne - za rozwiązanie zadania po upływie minut od początku konkursu drużyna otrzymuje punktów karnych. Wygrywa ta drużyna, która rozwiąże największą liczbę zadań, a w przypadku remisu ta, która ma najmniej punktów karnych.

W dniu zawodów Bartuś szybko przegląda treści zadań i rozdziela je między kolegów. Zna on dobrze swoją drużynę i potrafi bezbłędnie ocenić, kto jest w stanie zrobić które zadanie. Każdemu zawodnikowi rozwiązanie zadania, które umie on zrobić, zajmuje dokładnie minut pracy przy komputerze.

Drużynie Bartusia nie poszło zbyt dobrze na tegorocznej edycji Konkursu. Zastanawia się on, jaki wpływ na ten przykry fakt miały jego decyzje dotyczące przydziału zadań. Poprosił Cię, abyś napisał program, który na podstawie danych, jakie posiadał Bartuś na początku konkursu, obliczy maksymalny możliwy wynik drużyny Bartusia, a także przydział zadań członkom drużyny, który umożliwi osiągnięcie tego wyniku.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się pięć liczb całkowitych , , , i (, ), pooddzielanych pojedynczymi odstępami i oznaczających odpowiednio: liczbę zawodników, liczbę zadań, czas rozwiązywania zadania przez zawodnika, czas trwania zawodów i liczbę par zawodnik-zadanie (podanych dalej na wejściu). Każdy z kolejnych wierszy zawiera dwie liczby całkowite i (, ), oddzielone pojedynczym odstępem, oznaczające, że zawodnik jest w stanie rozwiązać zadanie . Każda taka para może pojawić się na wejściu co najwyżej raz.

W testach wartych łącznie 30% punktów zachodzi dodatkowy warunek .

Wyjście

W pierwszym wierszu standardowego wyjścia należy wypisać najlepszy możliwy wynik drużyny Bartusia w postaci dwóch liczb całkowitych oddzielonych pojedynczym odstępem: liczby rozwiązanych zadań i liczby punktów karnych. W kolejnych wierszach należy wypisać przykładowy przydział zadań: w każdym wierszu mają znaleźć się trzy liczby całkowite , i (, , ), pooddzielane pojedynczymi odstępami i oznaczające, że zawodnik powinien zacząć rozwiązywać zadanie w chwili (konkurs rozpoczyna się w chwili ). Nie należy nikomu przydzielać zadań, których dana osoba nie potrafi rozwiązać. Jeśli istnieje więcej niż jedna poprawna odpowiedź, Twój program powinien wypisać dowolną z nich.

Przykład

Dla danych wejściowych:

2 4 3 15 4
1 1
2 3
1 4
1 3

poprawną odpowiedzią jest:

3 12
1 4 0
2 3 0
1 1 3

Autor zadania: Tomasz Idziaszek.