1. Таксомотор

Максимальна оцінка: 105 балів
Обмеження на час: 1 сек.
Обмеження на пам’ять: 32 MБ
Вхідний файл: tax.in
Вихідний файл: tax.out
Програма: tax.*

У мiстi таксомотори розвозять пасажирiв певними маршрутами протягом доби. З останньої зупинки маршруту таксомотор «їде в парк» (а не на першу зупинку). Всi зупинки занумеровано натуральними числами в межах вiд 1 до деякого натурального n.

Завдання
Створiть програму, яка визначить:

• час припинення подорожi й найменшу вартiсть подорожi для найшвидшого маршруту;

• найменший час припинення подорожi й вартiсть подорожi для найдешевшого маршруту.

Вхідні дані
Перший рядок файлу мiстить у вказаному порядку такі натуральнi числа:
n — кiлькiсть зупинок, що не перевищує 250;
m — кiлькiсть маршрутiв;
t — кiлькiсть хвилин вiд початку доби, коли пасажир починає свiй рух;
a — номер зупинки, з якої вiн починає свiй рух;
b — номер зупинки, на яку вiн хоче потрапити.

Для j в межах вiд 1 до m включно ( j + 1)-ий рядок мiстить трiйки чисел. У кожнiй такiй трiйцi:

• перше (натуральне) число — номер зупинки;

• друге (натуральне) число — час прибуття у хвилинах вiд початку доби на вказану зупинку таксомотора, що їде j-тим машрутом. Вважається, що на кожнiй зупинцi кожний автобус стоїть рiвно хвилину, пiд час якої можна сiсти на нього або зiйти з нього;

• третє (невiд'ємне цiле) число — вартiсть проїзду вiд попередньої зупинки (0 для першої зупинки кожного маршруту, додатне для всiх наступних зупинок).

Загальна кiлькiсть ланок всiх маршрутiв не перевищує 7800.

Вихідні дані
Перший рядок файлу має містити у вказаному порядку час припинення подорожi й найменшу вартiсть подорожi для найшвидшого маршруту.
Другий рядок файлу має містити у вказаному порядку найменший час припинення подорожi й вартiсть подорожi для найдешевшого маршруту.
Для правильної відповіді усі ці числа менші за 65432.

Приклад

2. Гра «Ряд фішок»

Максимальна оцінка: 40 балів
Обмеження на час: 0,15 сек.
Обмеження на пам’ять: 4 MБ
Вхідний файл: game.in
Вихідний файл: game.out
Програма: game.*

Скiнченну кiлькiсть фiшок розташовано в ряд i занумеровано послiдовними натуральними числами, починаючи з 1. Два гравцi по черзi забирають довiльнi одну або двi фiшки, розташованi поруч (номери яких вiдрiзняються на 1). Переможцем вважають того, хто примусить суперника зробити останнiй хiд.

Завдання
Створiть програму, яка для довiльної позицiї гри визначає всi виграшнi ходи — такi ходи, що ґарантують виграш (за умови правильного продовження гри зi свого боку) незалежно вiд ходiв суперника.

Вхідні дані
Файл мiстить номери наявних фiшок, якi меншi за 21.

Вихідні дані
Перший i другий рядки файлу мають мiстити (у довільному) порядку номери фiшок, забравши якi відповідно по однiй або разом з наступною по двi гравець робить виграшний хiд з позицiї, заданої вхiдними даними. Якщо таких ходiв немає, то вiдповiдний рядок game.out порожнiй. Зайвими пропусками при перевірці буде знехтувано.

Приклади