Мировое путешествие
Kita_masa планирует отправиться в кругосветное путешествие. В этом мире существует N стран, и в каждой стране i находится M_i городов. Kita_masa хочет посетить каждый город ровно один раз и вернуться в город, с которого началось путешествие.
В этом мире путешествовать можно только на самолете. Существуют два типа авиалиний: внутренние и международные. Поскольку международные аэропорты требуют специальных условий, таких как таможня и паспортный контроль, только несколько городов в каждой стране имеют международные аэропорты.
Вам предоставлен список всех авиамаршрутов в этом мире и стоимость каждого маршрута. Теперь необходимо рассчитать самый дешевый маршрут для кругосветного путешествия Kita_masa!
Входные данные
Первая строка содержит два целых числа, обозначающих количество стран и количество авиамаршрутов соответственно. Вторая строка содержит целые числа, где -е число обозначает количество городов в стране . Третья строка также содержит целые числа, где -е число обозначает количество международных аэропортов в стране . Каждая из следующих строк содержит пять целых чисел [Страна 1] [Город 1] [Страна 2] [Город 2] [Цена]. Это означает, что существует двунаправленный авиамаршрут между [Городом 1] в [Стране 1] и [Городом 2] в [Стране 2], и его стоимость равна [Цена].
Заметьте, что города в каждой стране нумеруются с 1, и только города, номер которых меньше или равен количеству международных аэропортов, имеют международные аэропорты. То есть, если существует авиамаршрут между городом в стране и городом в стране с , то должно быть и . Вы можете предположить, что нет авиамаршрута, который отправляется из одного города и возвращается в тот же город, и что в этом мире существует не более одного авиамаршрута для каждой пары городов.
Следующие ограничения выполняются для каждого набора данных:
1 ≤ N ≤ 15
1 ≤ M_i ≤ 15
1 ≤ F_i ≤ 4
sum(F_i) ≤ 15
1 ≤ Цена ≤ 10,000
Выходные данные
Выведите одно целое число, представляющее минимальную стоимость кругосветного путешествия.
Если такое путешествие невозможно, выведите -1.