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