Problem Description

Today is the eagerly awaited "first time picking flowers together" anniversary for Kitamu and his girlfriend. He was supposed to present her with $K$ flowers today. However, he has been overwhelmed by the numerous anniversaries and forgot to buy the flowers. Therefore, he decided to buy flowers on his way to school.

The city where Kitamu lives has $N$ stations, each labeled with numbers from $1$ to $N$. The railway he uses has $M$ lines, where the $i$-th line connects two stations $A_i$ and $B_i$ with a fare of $C_i$ yen, allowing bidirectional travel. At station $j$, one can buy as many sets of $X_j$ flowers for $Y_j$ yen as desired. He lives near station $1$ and his school is near station $N$.

What is the minimum total cost of transportation and flower expenses after he buys at least $K$ flowers for his commute?

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ K $ $ A_1 $ $ B_1 $ $ C_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $\vdots$ $ A_M $ $ B_M $ $ C_M $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $\vdots$ $ X_N $ $ Y_N $

Output Format

Output the minimum total cost of transportation and flower expenses after Kitamu buys at least $K$ flowers for his commute in one line. If it is impossible to buy $K$ flowers or reach the school, output -1.

Sample Input and Output

Sample Input #1

4 3 10
1 2 100
2 3 100
3 4 100
3 10
5 20
10 1000
1 8

Sample Output #1

338

Sample Input #2

4 4 3
1 2 50
2 3 50
3 4 100
3 1 100
2 500
2 200
2 500
2 500

Sample Output #2

600

Sample Input #3

2 1 1
1 2 1
0 1
0 1

Sample Output #3

-1

Sample Input #4

10 16 10
6 10 3
3 1 4
2 3 9
8 8 8
10 4 10
6 5 9
2 3 1
7 4 3
8 2 2
6 10 9
8 6 10
8 3 4
7 8 2
6 4 6
8 7 9
9 6 7
5 10
4 3
7 7
1 8
3 8
5 1
6 3
1 7
2 8
7 8

Sample Output #4

22

Notes/Hints

Constraints

• All inputs are integers.
• $2 \leq N \leq 1000$
• $1 \leq M \leq 2000$
• $1 \leq K \leq 1000$
• $1 \leq A_i, B_i \leq N$ $(1 \leq i \leq M)$
• $1 \leq C_i \leq 10^9$ $(1 \leq i \leq M)$
• $0 \leq X_j \leq K$ $(1 \leq j \leq N)$
• $1 \leq Y_j \leq 10^9$ $(1 \leq j \leq N)$

Correction on 2019/05/01 21:32: Some constraints had mistakes where $N$ was $M$ and $M$ was $N$, which have been corrected.

Explanation

Explanation

Sample Explanation 1

Move from station $1$ to station $4$ via station $2$ and station $3$. The total transportation cost is $300$ yen. Buy $3$ sets at station $1$ and $1$ set at station $4$, making the total flower cost $38$ yen.

Sample Explanation 2

Note that it's okay to buy more than $K$ flowers.

见题面 Input 部分

见题面 Output 部分