Problem Description

Takahashi is the captain of a battleship.
Takahashi's mission is to advance from the sea area where the naval base is located to the final destination sea area.
Takahashi will act in the following order:

1. Route Selection

• Select a route to advance. If there are no routes available to move from the current sea area to a different sea area, proceed to step 4 (withdrawal from the sea area).
• If there are multiple routes from the current sea area to different sea areas, the route is selected with equal probability due to some conspiracy.
• For example, if there are 4 routes from the naval base sea area to other sea areas, each route is selected with a 25% probability.

1. Advance
   - Move to the sea area according to the selected route.

2. Battle
   - The sea area \( i \) you advance to has enemy ships waiting, and a battle occurs.
   - When leaving the naval base, the health of the battleship led by Captain Takahashi is \( H \), and the health of the battleship decreases by \( D_i \) due to the battle.
   - If the health of the battleship drops to 0 or below, the battleship sinks.
   - If the battleship sinks, Captain Takahashi will be so disheartened that he cannot go on any more missions, so the battleship must never sink.
   - Note that no battle occurs in the sea area where the naval base is located, but a battle always occurs in the final destination sea area.

3. Withdrawal from the Sea Area or Return to Route Selection
   - Withdrawal from the sea area means returning to the sea area where the naval base is located.
   - If the remaining health of the battleship when withdrawing is \( C \), it takes \( H-C \) time for health recovery.

Each cycle of steps 1, 2, 3, 4 consumes 1 unit of time.

About Sea Areas and Routes - There are \( N \) sea areas and \( M \) routes.
- These \( M \) routes are all one-way.

Therefore, for any different sea areas \( A \) and \( B \), it is impossible to move from sea area \( A \) to sea area \( B \) and then from sea area \( B \) to sea area \( A \) using a single route.

You are the chief of staff for Captain Takahashi, and your job is to calculate the expected value of the time elapsed until Captain Takahashi survives the battle at the final destination, assuming he acts to minimize the time consumed.
If it is impossible for Captain Takahashi to complete his mission under any circumstances, output -1.
The input is given in the following format from standard input: > \( N \) \( M \) \( H \) \( f_1 \) \( t_1 \) \( f_2 \) \( t_2 \) : \( f_M \) \( t_M \) \( D_1 \) \( D_2 \) : \( D_N \)

1. The first line contains the number of sea areas \( N\ (2 \leq N \leq 100) \), the number of routes \( M\ (0 \leq M \leq N * (N - 1) / 2) \), and the health of the fleet when leaving port \( H\ (1 \leq H \leq 100) \) separated by single spaces.

• The sea area where the naval base is located is 1, and the final destination sea area is \( N \).

1. The next \( M \) lines describe the \( i \)-th route. The integer \( f_i\ (1 \leq f_i \leq N) \) representing the origin sea area and the integer \( t_i\ (1 \leq t_i \leq N) \) representing the destination sea area are given separated by spaces.
   - It is guaranteed that \( f_i < t_i \).

2. The next \( N \) lines contain the integer \( D_i\ (0 \leq D_i \leq 100) \) representing the damage taken in battle at the \( i \)-th sea area, given in one line each.
   - The value of \( D_1 \) is always 0 (the naval base sea area).

• Note that inputs where the expected value to be output is greater than \( 10^6 \) will not be given.

Output the expected value of the time elapsed until Captain Takahashi survives the battle at the final destination, assuming he acts to minimize the time consumed.
The output is accepted if the absolute or relative error is at most \( 10^{-6} \).
If it is impossible for Captain Takahashi to complete his mission under any circumstances, output -1.
The output should end with a newline.

• From the naval base at 1 to the final destination at 6, there are 2 routes.

1. 1 -> 2 -> 4 -> 6

• The probability of choosing this route is 50%.
• The damage the battleship takes on this route is \( 0+1+2+4=7 \).
• The time consumed on this route is only 3 cycles, so it is 3.

1. 1 -> 3 -> 5 -> 6
   - The probability of choosing this route is 50%.
   - The damage the battleship takes on this route is \( 0+1+3+4=8 \).
   - Since the health of the battleship when leaving port is 8, it will sink on this route.
   - To avoid sinking, Captain Takahashi will choose to withdraw from the sea area after the battle at sea area 3.
   - The time consumed on this route is 1 cycle + time for health recovery = \( 1+1=2 \).

1 -> 3 -> 5 -> 6 with 1 withdrawal and then 1 -> 2 -> 4 -> 6 - 50% probability of choosing 1 -> 3 -> 5 -> 6, using time 2 to return to the naval base.
- Then, 50% probability of choosing 1 -> 2 -> 4 -> 6, using time 3 to reach the final destination.
- That means, 25% probability of using time 5 to reach the final destination.

1 -> 3 -> 5 -> 6 with 2 withdrawals and then 1 -> 2 -> 4 -> 6 - 12.5% probability of using time 7 to reach the final destination.

1 -> 3 -> 5 -> 6 with 3 withdrawals and then 1 -> 2 -> 4 -> 6 - 6.25% probability of using time 9 to reach the final destination.

From the above, the expected value to be calculated is \( 3*0.5+5*0.25+7*0.125+...=5 \).

Input Format

None

Output Format

None

Sample Input and Output

Sample Input #1

6 6 8
1 2
1 3
2 4
3 5
4 6
5 6
0
1
1
2
3
4

Sample Output #1

5.0

Sample Input #2

3 2 5
1 2
1 3
0
5
1

Sample Output #2

-1

Sample Input #3

3 2 6
1 2
1 3
0
5
1

Sample Output #3

7

Sample Input #4

9 13 4
1 2
1 3
2 4
2 5
2 7
3 5
3 6
4 7
5 8
6 8
7 8
7 9
8 9
0
1
1
1
1
1
1
1
1

Sample Output #4

36.9999999999999

Notes/Hints

None

见题面 Input 部分

见题面 Output 部分