Travel

You are the Magical Merchant from Magicland! Magicland has N towns. You are currently in town 1, while your beloved princess awaits in town N, imprisoned by an evil general. Because you are a magical merchant, and not a fighter, you plan on hiring mercenaries when you reach town N to get her back.

Towns are connected by bidirectional roads, and each road has a toll that you have to pay to cross. You cannot use a road if you can't pay its toll.

As a magical merchant, you make money according to a magical formula: When you enter town i and your current gold is t, your gold changes to (t+s_i)/2 if (t+s_i) is even, and (t+s_i-1)/2 if t+s_i is odd. s_i is a magical value specific to town i.

You can use as many roads as you want to reach town N and you may pass each road as many times as you want, but you have to end up at town N. You need not use all roads nor visit all towns. You want to do this task in such a way that you maximize your gold when you reach town N. Your task is to write a program to compute this value.

Input Format

The first line of input contains three integers N - the number of cities , M - the number of roads and K - your starting gold.

Each of next M lines describes a road. In each line there are three space separated integers u_i , v_i, the two towns the road connects, and c_i the toll that is needed to use the road.

Next line contains n space separated integers s_1, s_2 , .. , s_n. It is guaranteed that you can travel from town 1 to town N using the given roads.

Output Format

Print an integer which is the maximum possible final amount of gold when you reach town N.

Sample Input

2 1 1

1 2 1

4 54

Sample Output

36

Explanation

The optimal route to follow is

1 -> 2 -> 1 -> 2 -> 1 -> 2 -> 1 -> 2

The gold you have at each point on this route is:

1

(1-1+54)/2 = 27

(27-1+4)/2 = 15

(15-1+54)/2 = 34

(34-1+4)/2 = 18

(18-1+54)/2 = 35

(35-1+4)/2 = 19

(19-1+54)/2 = 36

Initially you start with 1 gold from town 1 and on passing the road your gold reduces by one and drops to zero, but due to magic on reaching town 2, your gold changes to (0+54)/2 = 27. You similarly go back and forth four times to achieve the maximum gold of 36.

Constraints

1 <= N,M <= 100 K and c_i are non-negative numbers and will fit in a 32 bit integer.