Мирлин Теренс тщетно пытался спасти Рика и Валлону от агентов Трантора. Переодевшись патрульным, он разыскивал их по всему Верхнему городу, однако никак не мог напасть на их след. Встреча произошла уже недалеко и космопорта, но тут завязалась перестрелка между Теренсом и агентом, а Рик и Валлона, не узнав Мирлина, сбежали, и уже летели на космическом корабле до Сарка. Теренс понимал, что не может лететь вслед за ними на корабле — его тут же узнают. Однако у многих зажиточных граждан Верхнего города были космические яхты, путешествие на которой вызвало бы намного меньше подозрений. Конечно, Теренс к этим гражданам не относился и ключей от яхты не имел, но форма патрульного, оружие и полумрак ночных улиц помогли их раздобыть.

Теренс все еще должен был оставаться незамеченным, и потому ему стоило избегать встречи с патрульными. Квартал рядом с портом состоит из $$$n$$$ перекрестков, соединенных $$$m$$$ дорожками с односторонним движением, для каждой дорожки известно, за какое время ее можно преодолеть. Посреди ночи по кварталу ходили всего двое патрульных, которые сейчас находятся на перекрестках $$$s_1$$$ и $$$s_2$$$. По рации, отобранной у патрульного, Теренс узнал, что они должны обойти $$$k$$$ перекрестков $$$p_1, p_2, ... p_k$$$ в заданном порядке (один перекресток может встречаться в этом списке несколько раз). Обходить они будут по одному, то есть на каждом из заданных перекрестков может побывать один из патрульных. Они действуют следующим образом: сначала какой-либо из патрульных доходит до перекрестка $$$p_1$$$ и сообщает об этом напарнику. После этого какой-либо патрульный начинает свое движение до перекрестка $$$p_2$$$. Так происходит, пока патрульные не осмотрят перекресток $$$p_k$$$, после чего их смена заканчивается. Если в какой-то момент патрульным необходимо проверить перекресток $$$i$$$, и какой-то из патрульных как раз находится на этом перекрестке, они переходят к проверке следующего перекрестка. При необходимости патрульные могут находиться на одном перекрестке. Патрульные хотят как можно быстрее закончить свою работу, а потому выбирают пути и разделяют между собой перекрестки таким образом, чтобы обход занял минимальное время.

Мирлин Теренс решил, что проще всего проникнуть в порт во время смены патрульных. Поэтому он спрашивает вас: сколько времени патрульные будут совершать обход, если они выбирают свои пути оптимально?