You are traversing a nuclear wasteland, trying to make it back to your hideout. You are currently located at location 1, whereas your hideout is at location ~n~. However, certain locations are covered in nuclear waste, and you would like to stay as far away as possible from this nuclear waste. This locations are connected by paths with a particular distance. The danger of a route is the closest you ever get to a nuclear waste location.

Because of the dangerous nature of the environment, you can only traverse paths in one direction, (however, you consider them going both directions for the purposes of distance from a nuclear waste location.)

In addition, you can also gain a certain amount of food by traversing a path. Traversing the path another time with again yeild that same amount of food!

What is the minimum danger of a route to your hideout. In addition, what is maximum amount of food you can pick up along the way for that minimum amount of danger.

Input

The first line contains the integers ~n, m~ and ~w~, the number of locations, number of paths, and number of waste locations respectively. The second line contains ~w~ integers, listing all of the locations which contain a nuclear waste site. The following ~m~ lines contain integers ~a, b, c, d~ indicating a directed path from node ~a~ to node ~b~ with distance ~c~ and food ~d~. The nodes are numbers ~1~ through ~n~.

It is guaranteed that there exists path from location 1 to the hideout.

Output

A line containing the smallest danger, and the maximum amount of food. If an infinite amount of food is possible, then write -1 instead.

Constraints

• ~1 \le a,b \le n \le 200~
• ~1 \le c, d \le 10^9~
• ~1 \le m \le 500~

Example 1

Input

3 3 1
2
1 2 3 10
2 3 4 10
1 3 1 1

3 1

Example 2

Input

10 20 2
5 7 
1 2 10 0
2 3 10 0
3 4 7 0
4 5 4 0
5 6 10 0
6 7 3 0
7 8 8 0
8 9 10 0
9 10 9 9
10 1 8 0
5 9 2 0
8 7 1 2
7 7 2 0
1 1 1 0
9 10 1 6
8 5 1 0
9 4 3 0
10 6 3 2
2 1 1 0
3 10 3 7

Output

3 7

Example 3

Input

10 20 1
6 
1 2 4 0
2 3 4 6
3 4 8 0
4 5 4 0
5 6 3 0
6 7 5 0
7 8 8 0
8 9 1 0
9 10 10 0
10 1 2 7
9 4 3 0
10 3 3 0
8 7 3 0
5 5 1 0
6 3 2 0
2 2 3 9
5 9 3 10
4 10 3 0
8 2 1 0
2 7 2 9

Output

5 -1