В городе Фловиль были проведены выборы T чиновников. Сам город можно представить в виде связного неориентированного графа, состоящего из N вершин и M рёбер. Каждое ребро графа задаётся тройкой чисел: ui vi leni (ребро между вершинами ui и vi) leni - длина ребра.
Каждому чиновнику предоставляется жильё. Чиновнику с номером t предоставляется жильё в вершине графа с номером ht. В городе имеется T свободных офисов для работы чиновников. Если чиновнику с номером t предоставлен офис в вершине графа с номером wt, то ежедневно чиновнику необходимо ехать на автомобиле из вершины ht в вершину wt. Чиновник обязательно будет ехать по кратчайшему пути. Из всех возможных кратчайших путей он выбирает маршрут по следующему правилу: упорядочим номера вершин маршрута в обратном порядке (т.е. от места работы к дому) и выберем «лексикографически наименьший» путь.
Например, если существуют 2 кратчайших пути из вершины 0 в вершину 5: 0→1→2→4→5 и 0→3→5, то чиновник выберет путь 0→3→5. Т.к. в обратном порядке (от места работы к дому): 5→4→2→1→0 и 5→3→0. А «лексикографически наименьший» - это 5→3→0.
Все дороги (рёбра графа) лежащие вдоль маршрута чиновника всегда будут будут поддерживаться в хорошем состоянии.
Каждому чиновнику необходимо выбрать только один офис из имеющихся в списке так, чтобы суммарная длина дорог, находящихся в хорошем состоянии, была максимальной.
В первой строке через пробел заданы три целых числа N, M и T.
N - количество вершин графа (N≤100);
M - количество рёбер в графе (M≤1000);
T - количество чиновников (T≤8);
Далее идут M строк, описывающих рёбра графа. Каждое ребро задано в формате: ui vi leni, где leni - длина ребра (0≤ui,vi≤n), (leni≤100000).
Далее идёт строка из T целых чисел:
0≤h1,h2,…,ht,…,hT≤n - номера вершин, в которых находятся дома чиновников;
Далее идёт строка из T целых чисел:
0≤w1,w2,…,wt,…,wT≤n - номера вершин, в которых находятся офисы для будущей работы чиновников.
SUM - максимальная суммарная длина дорог, которые будут гарантированно отремонтированы.
0≤wres1,wres2,…,wrest,…,wresT≤n - номера вершин, в которых находятся офисы для будущей работы чиновников, соответствующие максимальной суммарной длине гарантированно отремонтированных дорог SUM.