В столовой ИТМО стоит 2 PlayStation. Начинается борьба за PlayStation, но студенты ИТМО — приличные люди, поэтому они соблюдают правила очереди. Каждый раз, когда студент или пара друзей решают поиграть на одной из консолей, они создают заявку в ИСУ (электронная система университета), становясь частью очереди на использование PlayStation. Заявка содержит следующую информацию:
- имя студента (или пары студентов);
- время прихода (целое, номер минуты);
- длительность игры первого игрока (минуты);
- длительность игры второго игрока (минуты).
(Если один закончил раньше, второй продолжает играть один; консоль освобождается, когда закончит последний.)
Правила очереди:
- Когда PlayStation освобождается, система ИСУ автоматически выбирает следующую заявку из очереди ожидания, и доступ к PlayStation получают создатели этой заявки.
- Выбирается заявка с минимальным временем прихода (пришла раньше).
- Если время прихода одинаково, выбирается та, что раньше во входных данных.
- Если в момент освобождения никто не ждёт, консоль простаивает до следующего прихода.
- Если одновременно свободны несколько PlayStation, заявки распределяются по консолям в порядке их номеров (1, 2, …).
В один день в столовой ИТМО было подано 8 заявок на использование PlayStation. Отсчёт времени начинается с 0 в момент запуска электронной системы для создания заявок и идёт в минутах; первая заявка пришла спустя 1 минуту после запуска. Время ожидания заявки — это период, прошедший с момента подачи заявки, но до того, как её инициаторы начали играть на PlayStation. Общее время ожидания — это сумма времени ожидания всех заявок.
Вам дана таблица заявок студентов:
| Кто | Время прихода (мин) | Время игры первого игрока (мин) | Время игры второго игрока (мин) |
|---|
| Антон | 2 | 4 | — |
| Коля+Миша | 1 | 3 | 6 |
| Маша | 3 | 2 | — |
| Гриша | 2 | 5 | — |
| Ильяс | 1 | 2 | — |
| Света+Саша | 3 | 4 | 1 |
| Андрей | 2 | 1 | — |
| Богдан | 1 | 4 | — |
Вам нужно вывести два числа через пробел:
- Общее время ожидания всех заявок.
- Номер минуты, когда освободилась последняя PlayStation, после завершения последней заявки.
Пример записи ответа: «12 34».