Освітній архів Чемпіона
На квадратній галявині, утвореній LxL, на квадратних ділянках зі стороною 1 метр були сховані яйця. Деякі яйця цінніші за інші. Кролики знаходяться на ділянках, розташованих на краю лугу, і беруть участь у конкурсі «Мій кошик дорожчий». Спочатку на одній ділянці не кілька кролів. Вони носять футболки з чіткими номерами від 1 до N. Оскільки кролики мають багато тренувань, вони суворо дотримуються наступних правил:
1) всі кролики починають одночасно шукати яйця, починаючи з ділянки, на якій вони перебувають;
2) початкові напрямки руху кроликів (представлені на малюнку 1) такі: ті, що на північній стороні, рухаються на південь, ті, що на західній стороні, рухаються на схід, ті, що на південній стороні, і ті, що на півночі східна сторона на захід;
3) У кожному сюжеті кролик залишається одну хвилину, протягом цього часу він здійснює пошук і врешті-решт збирає яйце та сіль на ділянці, вказані напрямком руху;
4) збір яйця визначає зміну напрямку руху;
5) зміна напрямку руху відбувається наступним чином: якщо кролик приходить з Півночі, то він піде на Захід, якщо прийде з Півдня, то піде на Схід, якщо прийде зі Сходу, то піде на Північ, а якщо прийде із Заходу, то піде на південь. Приклад руху показано на малюнку 2 для кролика, який залишає ділянку (1,4);
6) якщо два або більше кроликів досягають одного і того ж яйця одночасно, його вибирає той, хто має найменше число на сорочці.
Конкурс закінчується, коли на луках більше не буде кроликів.
Напишіть програму, яка відображає загальну кількість зібраних Зайчиками яєць, найціннішу кошик (її вартість), а також тривалість (у хвилинах) змагання.
Файл введення яєць .in містить у першому рядку два натуральних числа, L і P, розділені пробілом, L представляє кількість рядків і стовпців таблиці, що використовуються для подання ділянки, а P - кількість яєць на луках.
На кожному з наступних Р рядків є 3 натуральних числа, розділені пробілом, що представляє координати ділянки (i, j), на якій знаходиться яйце (1), та його значення (v).
На наступному рядку - число N кроликів, а на кожному з наступних N рядків є пари натуральних чисел, що представляють координати ділянок, на яких кролики спочатку знаходяться, у порядку чисел на сорочці.
Вихідний файл egg .out буде містити
у першому рядку 3 натуральних числа, розділені пробілом, числа, що представляють загальну кількість яєць, зібраних N Кроликами, найцінніший кошик (його вартість), а також тривалість (у хвилинах) змагання.
2
Кролик виходить з лугу, якщо він виходить за межі матриці.
Одночасно на одній ділянці може бути кілька кроликів, крім першої хвилини.
Другий кролик перебуває на луках 6 хвилин, збирає 2 яйця загальною вартістю 11 і йде за маршрутом (3,5) - (3,4) - (3,3) - (2,3) - (2,4) - (2.5) ->