Олимпиадная задача по информатике ПОМОГИТЕ!

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



Квест состоит из четырёх комнат: «Древняя Греция», «Римская империя», «Вавилония» и «Ассирия». Команда выполняет каждый этап в отдельной комнате, причём вход и выход находятся в «Древней Греции». Из каждой комнаты можно перейти в любую другую, но за проход нужно заплатить игровыми монетами (считайте, что за испытания команда зарабатывает достаточно монет на любой переход).



Стоимость переходов между комнатами указана в таблице.

Какое минимальное количество монет команда может потратить на переходы, чтобы пройти все этапы? Помните, что вход и выход из игры находятся в комнате «Древняя Греция», начать и закончить маршрут нужно именно там.