Asia-Pacific Informatics Olympiad 2009

Problem 3: The Great ATM Robbery

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 →, 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

The first line of input contains 2 integers N (N ≤ 500000) and M (M ≤ 500000), where N is the number of intersections and M is the number of roads. This is following by M lines, each with two integers in the range 1, 2, …, N, giving the starting and ending intersection for one of the roads. This is followed by N lines, each containing a single non-negative integer not exceeding 4000, giving the amount of cash available at the ATMs at the N intersections. The following line contains two integers S and P, where S is the starting intersection (the city centre) and P is the number of pubs. This is followed by a line with P integers listing the intersections that contain pubs. It is guaranteed that a solution is always possible.

Output

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.

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

Note on grading

In 50% of the inputs, M and N will not exceed 3000.

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 3.00s
Memory Limit: 64M
Added: Jul 22, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Can I get my error message why I get SIGSEGV? Thanks

I'm not sure what you're asking for. A SIGSEGV is a SIGSEGV. We don't pass your program through anything like memcheck.

hmm... APIO #3 only 20 points? Is this supposed to be relatively simple once you get it or something?

All problems are "relatively simple" for Hanson. I'd provide some feedback if I could, but I haven't done the contest yet.

Hehe, true, true. :)

Hmm.. this is one of those problems that relies on a certain type of algorithm (if you know it, it makes the problem almost trivial). Otherwise, it's really really hard to solve (for full points, anyway). If you'd like to know the type of algorithm, I can tell you :P

I really would like to know and learn the type of algorithm, but let me try it for a while first. :) Struggling is a nice way of learning the value of something.

This question is totally worth 30 points because a similar question like [url]http://wcipeg.com/problem/ccc07s2p6[/url] is worth 30 points...