Harmonious Islands

5

2 votes
Shortest Path Algorithms, Algorithms, Graphs
Problem

Imagine a planet with two beautiful islands. Each island is decorated with several cities, and they are connected by a network of bidirectional roads. The cost of traveling through each road is provided. Both the islands have equal number of cities and roads.

You are given two arrays, and , where represents the beauty index associated with the cities on Island , and  represents the beauty index associated with the cities on Island .

To journey from a city on Island  to a city on Island , there exists special unidirectional flights. However, specific conditions must be met:

  • must be a multiple of , indicating a compatible connection between the cities. (i.e. a unidirectional flight exists between city  to city if and only if is a multiple of )
  • The cost of the flight is determined by multiplying the beauty indexes of city and city (i.e. ), ensuring a harmonious transition between the islands.

Your task is to calculate the minimum cost required to travel from city on Island to city on Island . If it is not possible to travel from city to city based on the given conditions, you should output , indicating an incompatible connection.

Input format

  • First line contains an integer , the number of test cases.
  • The first line of each test case contains 2 integers ,  seperated by a space representing the number of cities and roads respectively.
  • The next line contains integers space-seperated by a space representing the array
  • The next line contains integers space-seperated by a space representing the array
  • The next  lines of each test case contains 3 space-seperated integers , representing a bidirectional road from city  of island to city  of island and it requires a cost  to travel through that road.
  • The next  lines of each test case contains 3 space-seperated integers , representing a bidirectional road from city  of island to city  of island and it requires a cost  to travel through that road.
  • The next line of each test case contains 2 space-seperated integers ,  which are described in the problem statement.
  • It is guaranteed that there are no self loops or multiple edges in the graphs.

Output format

For each testcase, output an integer, the minimum cost required to travel from city  in  island to city  in  island. Or print if it's an incompatible connection in a new line.

Constraints

  • Also it's guaranteed that the sum of  ,  over all test cases doesn't exceed 

 

Sample Input
3
5 7
1 2 3 4 5
10 9 8 7 6
1 2 1
1 3 3
1 4 10
1 5 5
2 5 4
2 4 2
3 4 3
1 5 1
2 4 2
2 5 1
3 1 3
3 2 4
3 4 5
3 5 1
4 5
3 2
1 1 1
1 1 1
1 2 1
2 3 1
1 3 1
2 1 1
2 3
4 2
1 1 1 1
1 1 1 1
1 2 1
1 4 1
1 2 1
1 4 1
3 4
Sample Output
9
2
-1
Time Limit: 1.5
Memory Limit: 256
Source Limit:
Explanation
  • For test case : one possible path to go from city 4 of island 1 to city 5 of island 2 is as follows -: 
    • Go from city 4 of island 1 to city 2 of island 1 by incurring a cost of 2
    • Then go from city 2 of island 1 to city 1 of island 1 by incurring a cost of 1
    • Then take a flight and go from city 1 of 1st island to city 5 of 2nd island incurring a cost of = = 6 (here 5 is a multiple of 1, so the flight exists)
    • Total cost is 2+1+6 = 9, and it can be proved that this is the minimum cost required to go from city 4 of island 1 to city 5 of island 2
  • For test case : one possible path to go from city 2 of island 1 to city 3 of island 2 is as follows -: 
    • Go from city 2 of island 1 to city 3 of island 1 by incurring a cost of 1
    • Then take a flight from city 3 of 1st island to city 3 of 2nd island incurring a cost of  = = 1 (here 3 is a multiple of 3, so the flight exists)
    • Total cost is 1 + 1 = 2, and it can be proved that this is the minimum cost required to go from city 2 of island 1 to city 3 of island 2
  • For test case : it can be proved that no path exists from city 3 in island 1 to city 4 in island 2
Editor Image

?