E - Railway Trip Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 433 点

問題文

AtCoder王国には、1 から N までの番号が付けられた N 個の都市と、都市間を結ぶ M 本の鉄道路線があります。すべての路線は双方向に運行しており、移動する向きによって運賃や所要時間は変わりません。

高橋君と青木君の 2 人は、都市 1 から都市 N へ旅行しようとしています。2 人は常に一緒に行動し、財布を 1 つにしており、所持金は 2 人合わせて K 円です。

i 番目 (1 \leq i \leq M) の路線は都市 U_i と都市 V_i を結んでおり、普通列車と特急列車の 2 種類の列車が運行されています。

2 人がこの路線を利用する際は、利用するたびに以下のいずれか一方の列車を独立に選んで 2 人で乗車します。

  • 普通列車:運賃は 1 人あたり A_i 円(2 人分で計 2A_i 円)、所要時間は S_i 分
  • 特急列車:運賃は 1 人あたり B_i 円(2 人分で計 2B_i 円)、所要時間は T_i 分

なお、A_i と B_i、S_i と T_i の大小関係に制限はなく、特急列車より普通列車の方が運賃が高い場合や、所要時間が短い場合もあります。

2 人は同じ都市や路線を何度でも通過できます。また、都市での乗り換え時間や待ち時間は無視できます。

都市 1 から都市 N まで移動するとき、2 人が支払う運賃の総額が所持金 K 円以下となる移動方法について、所要時間の総和の最小値を求めてください。

制約

  • 2 \leq N \leq 200
  • 1 \leq M \leq 500
  • 0 \leq K \leq 1000
  • 1 \leq U_i, V_i \leq N (1 \leq i \leq M)
  • U_i \neq V_i (1 \leq i \leq M)
  • 同じ都市の組を結ぶ路線が複数存在することもある。
  • 1 \leq A_i, B_i \leq 1000 (1 \leq i \leq M)
  • 1 \leq S_i, T_i \leq 10^9 (1 \leq i \leq M)
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M K
U_1 V_1 A_1 B_1 S_1 T_1
U_2 V_2 A_2 B_2 S_2 T_2
:
U_M V_M A_M B_M S_M T_M

出力

2 人が支払う運賃の総額が K 円以下で都市 1 から都市 N へ移動する際にかかる所要時間の総和の最小値を 1 行で出力してください。

ただし、運賃の総額が K 円以下で都市 N に到達する方法が存在しない場合は、代わりに -1 を出力してください。


入力例 1

3 3 20
1 2 3 5 10 5
2 3 4 6 12 6
1 3 8 12 30 8

出力例 1

16

入力例 2

4 3 15
1 2 3 5 10 4
2 3 3 6 12 5
3 4 3 4 8 3

出力例 2

-1

入力例 3

6 8 80
1 2 10 5 15 35
1 2 8 12 25 10
1 3 15 25 40 18
2 4 6 10 20 8
3 4 12 18 22 11
3 5 7 14 30 12
4 6 9 15 18 7
5 6 11 20 25 9

出力例 3

25

入力例 4

12 18 300
1 2 15 30 800000000 350000000
1 3 20 45 600000000 250000000
2 4 12 25 500000000 200000000
3 4 10 20 400000000 180000000
2 5 25 50 700000000 300000000
3 6 18 35 550000000 220000000
4 7 14 28 450000000 190000000
5 7 22 40 650000000 280000000
6 8 16 32 480000000 210000000
7 9 15 30 520000000 230000000
8 9 12 24 380000000 160000000
5 10 30 60 900000000 400000000
7 10 20 42 620000000 270000000
8 11 18 36 580000000 240000000
9 11 14 28 440000000 190000000
10 12 25 50 750000000 320000000
11 12 22 45 680000000 290000000
4 8 28 55 850000000 360000000

出力例 4

1760000000

入力例 5

2 1 2
1 2 1 2 10 5

出力例 5

10

Score : 433 pts

Problem Statement

The Kingdom of AtCoder has N cities numbered 1 to N, and M railway lines connecting cities. All lines operate bidirectionally, and the fare and travel time do not depend on the direction of travel.

Takahashi and Aoki are planning to travel from City 1 to City N. The two always travel together, share a single wallet, and have a total of K yen between them.

The i-th line (1 \leq i \leq M) connects City U_i and City V_i, and two types of trains operate on it: local trains and express trains.

Each time the two use this line, they can independently choose one of the following train types to take together:

  • Local train: Fare is A_i yen per person (a total of 2A_i yen for both), and travel time is S_i minutes.
  • Express train: Fare is B_i yen per person (a total of 2B_i yen for both), and travel time is T_i minutes.

There are no restrictions on the relative sizes of A_i and B_i, or S_i and T_i; a local train may be more expensive or faster than an express train.

They may visit the same city or pass through the same line multiple times. Also, transfer and waiting times at cities can be ignored.

Find the minimum possible total travel time to travel from City 1 to City N such that the total fare paid by the two does not exceed their funds of K yen.

Constraints

  • 2 \leq N \leq 200
  • 1 \leq M \leq 500
  • 0 \leq K \leq 1000
  • 1 \leq U_i, V_i \leq N (1 \leq i \leq M)
  • U_i \neq V_i (1 \leq i \leq M)
  • There may be multiple lines connecting the same pair of cities.
  • 1 \leq A_i, B_i \leq 1000 (1 \leq i \leq M)
  • 1 \leq S_i, T_i \leq 10^9 (1 \leq i \leq M)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M K
U_1 V_1 A_1 B_1 S_1 T_1
U_2 V_2 A_2 B_2 S_2 T_2
:
U_M V_M A_M B_M S_M T_M

Output

Print the minimum possible total travel time to travel from City 1 to City N with a total fare of at most K yen in a single line.

If it is impossible to reach City N with a total fare of at most K yen, print -1 instead.


Sample Input 1

3 3 20
1 2 3 5 10 5
2 3 4 6 12 6
1 3 8 12 30 8

Sample Output 1

16

Sample Input 2

4 3 15
1 2 3 5 10 4
2 3 3 6 12 5
3 4 3 4 8 3

Sample Output 2

-1

Sample Input 3

6 8 80
1 2 10 5 15 35
1 2 8 12 25 10
1 3 15 25 40 18
2 4 6 10 20 8
3 4 12 18 22 11
3 5 7 14 30 12
4 6 9 15 18 7
5 6 11 20 25 9

Sample Output 3

25

Sample Input 4

12 18 300
1 2 15 30 800000000 350000000
1 3 20 45 600000000 250000000
2 4 12 25 500000000 200000000
3 4 10 20 400000000 180000000
2 5 25 50 700000000 300000000
3 6 18 35 550000000 220000000
4 7 14 28 450000000 190000000
5 7 22 40 650000000 280000000
6 8 16 32 480000000 210000000
7 9 15 30 520000000 230000000
8 9 12 24 380000000 160000000
5 10 30 60 900000000 400000000
7 10 20 42 620000000 270000000
8 11 18 36 580000000 240000000
9 11 14 28 440000000 190000000
10 12 25 50 750000000 320000000
11 12 22 45 680000000 290000000
4 8 28 55 850000000 360000000

Sample Output 4

1760000000

Sample Input 5

2 1 2
1 2 1 2 10 5

Sample Output 5

10