Подкиньте идею решения задачи

[adidas_pro]

Задача 2.
Направо пойдешь – коня потеряешь
В некотором царстве, в некотором государстве жил в град-столице царевич. И полюбилась ему царевна из соседнего царства. Поставила она ему такую задачу. Буду я ждать тебя в одном из городов царства на расстоянии n переходов из города в город, а путь ко мне из столицы таков – из каждого города выходят только три дороги, в каждом городе есть для меня подарок определенной стоимости. Если сумеешь найти такой путь, что общая стоимость подарков наибольшая – то и меня найдешь.
Задание.
Составить программу нахождения пути для царевича.
Входные данные.
Файл input.txt в первой строке содержит общее число городов m, включая столицу; во второй строке – целое число (стоимость подарка в столице); в третьей строке - три целых числа (стоимости подарков в тех городах, в которые можно попасть из столицы, т.е. из первого уровня); в следующей строке – пять целых чисел (описывают города, в которые можно попасть из второго уровня) и т.д.
Выходные данные и обязательные условия.
Файл output.txt содержит целое число – суммарную стоимость подарков.
Ограничения. Число городов m < 25; время выполнения менее 10 сек.

Подкиньте идею решения

[adidas_pro]

up! up! up! up!

[Ybn2]

По моему здесь или теория графов, нахождение наибольшего пути к точке,(в качестве длины выбирается стоимость подарка) или теория игр если нужно найти за меньшее число прохождения по городам наибольшую суммарную стоимость подарков (по моему этого нет в задании). Если ошибаюсь подправьте, мне самому интересно!

[Ybn2]

А по чему в 4-й строке "пять целых чисел (описывают города, в которые можно попасть из второго уровня)"? Не как не пойму.