eolymp
bolt
Try our new interface for solving problems
Məsələlər

World Trip

World Trip

Zaman məhdudiyyəti 5 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Kita_masa is planning a trip around the world. This world has N countries and the country i has M_i cities. Kita_masa wants to visit every city exactly once, and return back to the starting city.

In this world, people can travel only by airplane. There are two kinds of airlines: domestic and international lines. Since international airports require special facilities such as customs and passport control, only a few cities in each country have international airports.

You are given a list of all flight routes in this world and prices for each route. Now it's time to calculate the cheapest route for Kita_masa's world trip!

Giriş verilənləri

N

K

N

i

M_i

i

N

i

F_i

i

K

The first line contains two integers and , which represent the number of countries and the number of flight routes, respectively. The second line contains integers, and the -th integer represents the number of cities in the country . The third line contains integers too, and the -th integer represents the number of international airports in the country . Each of the following lines contains five integers [Country 1] [City 1] [Country 2] [City 2] [Price]. This means that, there is a bi-directional flight route between the [City 1] in [Country 1] and the [City 2] in [Country 2], and its price is [Price].

F_i

c_1

n_1

c_2

n_2

n_1≠n_2

c_1≤F_n1

c_2≤F_n2

Note that cities in each country are numbered from 1, and the cities whose city number is smaller or equal to have international airports. That is, if there is a flight route between the city in the country and the city in the country with , it must be and . You can assume that there's no flight route which departs from one city and flies back to the same city, and that at most one flight route exists in this world for each pair of cities.

The following constraints hold for each dataset:

  • 1 ≤ N ≤ 15

  • 1 ≤ M_i ≤ 15

  • 1 ≤ F_i ≤ 4

  • sum(F_i) ≤ 15

  • 1 ≤ Price ≤ 10,000

Çıxış verilənləri

Print a line that contains a single integer representing the minimum price to make a world trip.

If such a trip is impossible, print -1 instead.

Nümunə

Giriş verilənləri #1
4 6
1 1 1 1
1 1 1 1
1 1 2 1 1
1 1 3 1 2
1 1 4 1 1
2 1 3 1 1
2 1 4 1 2
3 1 4 1 1
Çıxış verilənləri #1
4
Mənbə Japan Alumni Group Winter Contest 2012