The city of Siruseri has only one way roads. Roads meet at intersections and at every intersection, mandated by law, there is an ATM of the Bank of Siruseri. Strangely, the pubs in Siruseri are also located only at intersections, though not every intersection hosts a pub. Banditji plans to carry out the largest ATM robbery in the history of Siruseri. He will start from the city centre and drive around, robbing all the ATMs that he passes by, before ending the day at one of the city's pubs to celebrate his achievement. Using his well-honed hacking skills, Banditji has precise information about the amount of cash available at every ATM. He would like you to help him determine the total amount that he can rob by starting at the city centre and ending at one of the city's pubs. He can go through the same intersection or road any number of times. However, there is no money to be picked up at an ATM after the first visit. For instance, suppose the city had 6 intersections connected by roads as indicated below:
The city centre is at intersection 1, marked by an incoming arrow, and the intersections where pubs are found are marked by a double circle. The amount
of cash available at the respective ATMs is written above each intersection.
In this case, Banditji can rob a total of 47 by following the route 1–2–4–1–2–3–5
.
Input Specification
The first line of input contains 2 integers and
, where
is the number
of intersections and
is the number of roads. This is followed by
lines,
each with two integers in the range
, giving the starting and ending
intersection for one of the roads. This is followed by
lines, each containing
a single integer, giving the amount of cash available at the ATMs at the
intersections. The following line contains two integers
and
, where
is
the starting intersection (the city centre) and
is the number of pubs. This
is followed by a line with
integers listing the intersections that contain
pubs.
Output Specification
The output should be a single integer, the maximum amount of money that Banditji can rob on his way from the city centre to any one of the pubs.
Test Data
In 50% of the inputs, . In all inputs,
. The
amount of cash available at a single ATM is always non-negative and never
exceeds
. You are guaranteed that at least one pub can be reached from
the city centre by following Siruseri's one way roads.
Sample Input
6 7
1 2
2 3
3 5
2 4
4 1
2 6
6 5
10
12
8
16
1
5
1 4
4 3 5 6
Sample Output
47
Comments