Problem Description
Long long ago , there is a person named ShaDan. He likes walking around the streets very much. He walks around the street until the sky is black every day. When he go back home , his mother always very angry with him. “what are you doing , it’ s so late now” his mother always asked him loudly. ShaDan always answer “I’m watching the scenery around the street”.
One day, when ShaDan was walking around the street, he thought how can I visit all the streets and cost minimum time. So that, he can go back home earlier and his mother will not blame him. The streets ShaDan visited is very strange. They are all one-way streets. All the cars on a street is drived along in one direction. But ShaDan can walk around the street in two directions. For example , if the street is from city i to city j , cars can only be drived on the street from the city I to city j. But ShaDan can walk around the street from the city i to city j and also can walk around the street form the city j to city i . In addition , ShaDan have a Super-capacity. Every move , he can choose a city i , and it doesn’t cost time. When he is in a city I,he have two ways to visit the streets.
The first one :he is in the city i , and he can walk around all the streets that from the city i ( for example i= 2 , he can walk 2->5, 2->3 , 2 - >6 ,if there exists a street ), it will costs he Wi to visit all the streets from city i.
The second one : he is in the city i, and he can walk around all the streets to city I ( for example i= 2 , he can walk 5->2, 4->2 , 3 - >2 ,if there exists a street ), it will costs he Pi to visit all the streets to city i.
Although ShaDan have a Super-capiacity , but his IQ is very low.
He is unable to deal with the problem . So he asked his best friends RPRUSH to help him to calculate the minimum time to visit all the streets.
Input
Input contains multiple test cases. Each test case contains an integer N (1 <= N < = 300 , the number of city) and M (1 <= m <= 20000, the number of streets )in a line first line , the second line contain n integers( from W1 to Wn ). The third line contain n integers (from P1 to Pn). Then followed M line, each line contain two integers a and b , means there is a street from city a to city b.
If there are two or more streets from city a to b , it is also legal. The input ends with a line that has two non-positive numbers.
Output
For each input case ,output a line containing a single number, which is the minimum time it need to visit all the streets.
Sample Input
3 3
1 2 4
4 1 3
1 2
2 3
3 1
0 0
Sample Output
7
