Світова подорож#3293
Kita_masa планує подорож навколо світу. У цьому світі є країн, і в країні є M_i міст. Kita_masa хоче відвідати кожне місто рівно один раз і повернутися назад до початкового міста.
У цьому світі люди можуть подорожувати лише літаком. Існує два види авіаліній: внутрішні та міжнародні. Оскільки міжнародні аеропорти вимагають спеціальних споруд, таких як митниця та паспортний контроль, лише кілька міст у кожній країні мають міжнародні аеропорти.
Вам надано список усіх авіамаршрутів у цьому світі та ціни на кожен маршрут. Тепер настав час розрахувати найдешевший маршрут для світової подорожі Kita_masa!
Перший рядок містить два цілі числа, які представляють кількість країн та кількість авіамаршрутів відповідно. Другий рядок містить цілих чисел, де -те число представляє кількість міст M_i у країні . Третій рядок також містить цілих чисел, де -те число представляє кількість міжнародних аеропортів F_i у країні . Кожен з наступних рядків містить п'ять цілих чисел: [Країна 1] [Місто 1] [Країна 2] [Місто 2] [Ціна]. Це означає, що існує двосторонній авіамаршрут між [Місто 1] у [Країна 1] та [Місто 2] у [Країна 2], і його ціна становить [Ціна].
Зверніть увагу, що міста в кожній країні пронумеровані з 1, і лише міста, номер яких менший або дорівнює F_i, мають міжнародні аеропорти. Тобто, якщо існує авіамаршрут між містом n_1 у країні c_1 та містом n_2 у країні c_2, то повинно бути n_1 \leq F_{c_1} та n_2 \leq F_{c_2}. Ви можете припустити, що немає авіамаршруту, який відправляється з одного міста і повертається до того ж міста, і що в цьому світі існує не більше одного авіамаршруту для кожної пари міст.
Наступні обмеження діють для кожного набору даних:
1 \leq N \leq 15
1 \leq M_i \leq 15
1 \leq F_i \leq 4
\text{sum}(F_i) \leq 15
1 \leq \text{Ціна} \leq 10{,}000
Виведіть одне ціле число, яке представляє мінімальну ціну для здійснення світової подорожі.
Якщо така подорож неможлива, виведіть -1.
Приклад 1