eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Таксомотор

Таксомотор

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

У м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 для найдешевшого маршруту.

Для правильної відповіді усі ці числа менші за 654321.

Приклад

Вхідні дані #1
7 4 1 7 3
3 2 0 4 35 1 2 50 1 3 70 1
5 5 0 6 15 1 4 30 1 5 45 1
7 2 0 2 5 11 6 10 1 7 20 1
7 60 0 2 70 1 6 80 1 7 90 1
Вихідні дані #1
70 12
1510 2