Problem C
Commuting To Work

Tom has a flexible work schedule, so he leaves for work at a different time every day, depending on when he is needed, commuting by car. However, he realises that the amount of time he takes to get to work differs every day, causing him to be late sometimes. He deduced the cause of this: traffic lights!

Formally, Tom lives in a city with $N$ junctions numbered $1$ to $N$, where his house is located at junction $1$ and his office at junction $N$. There are also $M$ bidirectional roads connecting pairs of junctions, where the $i$-th road takes $w_i$ seconds to drive through. It is guaranteed that we can get from any junction to any other junction using the roads.

At each junction $2, 3, \dots , N - 1$, there is a traffic light. All traffic lights operate with the same period of $T$ seconds, and in particular, the traffic light at junction $i$ becomes red at the $t_i$-th second of each period, and stays red for $l_i$ seconds. More specifically, the traffic light at junction $i$ is red during the interval $[t_i + kT, t_i + kT + l_i - 1]$ for each integer $k$ (note that $k$ can be negative), and green at all other times. Tom may only leave a junction when the traffic light is green, but there is no restriction to when he may reach a junction.

Let $f(t)$ be the minimum number of seconds Tom needs to get to work, if he leaves his house at the $t$-th second. Since Tom is non-justifiably optimistic, he wants to find out the minimum value of $f(t)$ across all integers $t$.

Input

The first line of input contains three integers $N, M, T$ $(2 \leq N \leq 1000, N - 1 \leq M \leq 2000, 2 \leq T \leq 10^9)$, the number of junctions and the number of roads respectively.

The next $M$ lines each contain three integers $a_i, b_i, w_i$ $(1 \leq a_i, b_i \leq N, a_i \neq b_i, 1 \leq w_i \leq 10^9)$. It is guaranteed that each pair of junctions is connected by at most one road, and it is possible to travel between every pair of junctions using these roads.

Finally, this is followed by $N - 2$ lines, where the $i$-th of them contains two integers $t_i, l_i$ $(0 \leq t_i \leq T - 1, 1 \leq l_i \leq T - 1)$ which show how the traffic light at junction $i + 1$ operates.

Output

Output one integer in a single line: the maximum possible of $f(t)$ across all integers $t$.

Sample 1 Explanation

The minimum value is $f(0) = 9$. The optimal route if Tom leaves at time $0$ is:

1. Travel from $1 \to 2$, taking $1$ second and reaching at time $1$.

2. Travel from $2 \to 3$, taking $1$ second and reaching at time $2$. Wait until time $8$ for the light to turn green.

3. Travel from $3 \to 5$, taking $1$ second and reaching at time $9$. The total time taken is $9 - 0 = 9$ seconds.

It can be shown that $f(0)$ achieves the maximum value. On the other hand, for example’s sake, $f(1) = 13$ achieves the largest possible value with the following optimal route:

1. Travel from $1 \to 4$, taking $5$ seconds and reaching at time $6$. Wait until time $7$ for the light to turn green.

2. Travel from $4 \to 5$, taking $7$ seconds and reaching at time $14$. The total time taken is $14 - 1 = 13$ seconds.

Another possible route if Tom leaves at time $1$ (that isn’t optimal) is:

1. Travel from $1 \to 2$, taking $1$ second and reaching at time $2$. Wait until time $10$ for the light to turn green.

2. Travel from $2 \to 3$, taking $1$ second and reaching at time $11$. Wait until time $18$ for the light to turn green.

3. Travel from $3 \to 5$, taking $1$ second and reaching at time $19$. The total time taken is $19 - 1 = 18$ seconds.

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

9