In the event of technical difficulties with Szkopuł, please contact us via email at szkopul@fri.edu.pl.
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
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.
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 .
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.
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.