Задание 26 ЕГЭ по информатике

Группа авантюристов хочет добраться до максимально возможно отдаленной от экватора зоны Земли, для чего им предстоит пересечь множество других зон в качестве перевалочных пунктов. При посещении очередной зоны авантюристы затрачивают некоторую сумму денежных единиц на организацию перевала, эта сумма может варьироваться в зависимости от отправной и конечной зоны. Начинает свой путь группа в зоне №1, а изначальные затраты средств равны нулю.

Известно, что чем больше номер зоны, тем дальше она расположена от экватора. Из каждой зоны можно попасть только в зоны с большим номером. Имеется $N$ записей, каждая из которых содержит информацию о какой-то зоне: номер текущей зоны, номер переходной зоны, до которой можно добраться отсюда и сумма средств для посещения переходной зоны. Каждая зона может быть представлена в нескольких вариантах с разными переходными пунктами и ценами за переход. Некоторые записи также могут содержать информацию о недостижимых зонах (в которые невозможно попасть, начав движение из зоны №1).

Определите номер максимальной зоны, которой могут достигнуть авантюристы, если их бюджет составляет $K$ денежных единиц, а также максимальный возможный остаток средств при этих условиях.

Входные данные

В первой строке входного файла находится два натуральных числа: $N$ $(N ≤ 100 000)$ – количество записей о зонах и $K$ $(K ≤ 1 000 000)$ - бюджет, которым располагает группа. В каждой из следующих $N$ строк находятся по три числа: номер текущей зоны, номер переходной зоны (в которую можно передвинуться из текущей) и сумма средств, необходимая для перехода. Каждое из чисел натуральное, не превосходящее $1 000 000$.

Запишите в ответе два числа: номер максимальной зоны, которой могут достигнуть авантюристы, если их бюджет составляет $K$денежных единиц, а также максимальный возможный остаток средств при этих условиях.

Типовой пример организации данных во входном файле

8 100

1 4 20

2 4 30

1 3 10

3 4 5

4 5 5

1 2 10

3 5 20

2 5 50

При таких исходных данных можно достигнуть максимум зоны №5 несколькими способами.

Оптимальным вариантом движения будет переход из зоны №1 в зону №3 за 10 ед., затем из зоны №3 в зону №4 за 5 ед. и в конце из зоны №4 в зону №5 за 5 ед. Остаток бюджета при этом составит 80 ед. Ответ: 5 80.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/21588_26.txt