E - The Adventurer's Journey Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 433 点

問題文

高橋君は冒険者です。彼は N 個の町を含む大陸を旅しています。

N 個の町には 1 から N までの番号がついており、町同士を結ぶ M 本の道があります。i 番目の道は町 U_i と町 V_i を双方向に結んでおり、この道を通るには体力を W_i 消費します。

高橋君の体力の初期値は F です。高橋君は町 1 を出発し、町 N にたどり着きたいと考えています。

各町 j には宿屋があり、回復量 R_j が定められています。高橋君がある町に初めて訪れたとき、その町の宿屋によって体力が R_j だけ回復します。この回復は各町につき最初の 1 回のみ適用され、同じ町を 2 回以上訪れても 2 回目以降は回復しません。なお、体力に上限値は設けられていません（回復によっていくらでも大きくなり得ます）。

町 1 については、出発時に初めて訪れたものとして扱います。したがって、最初の移動を行う前の時点での高橋君の体力は F + R_1 です。

高橋君の移動は、以下の手順を繰り返すことで行われます。

  1. 高橋君は、現在いる町に接続する道を 1 つ選びます。ただし、その道の通行に必要な体力（コスト W_i）が現在の体力以下である道しか選ぶことができません。条件を満たす道が 1 つも存在しない場合、高橋君はそれ以上移動できません。
  2. 選んだ道を通り、体力が W_i だけ減少します。体力がちょうど 0 になっても構いません。
  3. 道の先の町に到着した直後、その町を初めて訪れた場合に限り、その町の宿屋の回復量 R_j が体力に加算されます。

高橋君は同じ道を何度でも通ることができ、同じ町を何度でも訪れることができます（ただし、宿屋の回復は前述の通り各町につき 1 回のみです）。

高橋君が町 1 から出発して町 N に到着できるすべての移動の仕方を考えたとき、町 N 到着時の体力の最大値を求めてください。ここで、町 N 到着時の体力とは、上記の手順 3 まで適用した後の体力を指します（町 N を初めて訪れた場合、町 N の宿屋の回復も適用されます）。

どのように移動しても町 N に到着できない場合は -1 を出力してください。

制約

  • 2 \leq N \leq 10
  • 1 \leq M \leq \frac{N(N-1)}{2}
  • 0 \leq F \leq 1000
  • 0 \leq R_j \leq 1000 (1 \leq j \leq N)
  • 1 \leq U_i < V_i \leq N (1 \leq i \leq M)
  • 1 \leq W_i \leq 1000 (1 \leq i \leq M)
  • 同じ町の組を結ぶ道は高々 1 本である
  • 入力はすべて整数である

入力

N M F
R_1 R_2 \ldots R_N
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
  • 1 行目には、町の数を表す N、道の数を表す M、初期体力を表す F が、スペース区切りで与えられる。
  • 2 行目には、各町の宿屋の回復量を表す R_1, R_2, \ldots, R_N が、スペース区切りで与えられる。
  • 3 行目から M 行にわたって、各道の情報が与えられる。
  • 2 + i 行目では、i 番目の道が結ぶ町 U_i, V_i と、その道を通るために消費する体力 W_i が、スペース区切りで与えられる。

出力

高橋君が町 1 から町 N に到着したときの体力の最大値を 1 行で出力してください。どのように移動しても町 N に到着することが不可能な場合は -1 を出力してください。

入力例 1

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

出力例 1

11

入力例 2

3 1 5
0 0 0
1 2 3

出力例 2

-1

入力例 3

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

出力例 3

103

入力例 4

8 10 50
10 20 30 40 50 15 25 100
1 2 30
1 3 40
1 6 35
2 3 25
3 4 20
3 8 80
4 5 15
5 8 10
6 7 20
7 8 30

出力例 4

200

入力例 5

2 1 0
1000 1000
1 2 1000

出力例 5

1000

Score : 433 pts

Problem Statement

Takahashi is an adventurer. He is traveling across a continent containing N towns.

The N towns are numbered from 1 to N, and there are M roads connecting the towns. The i-th road bidirectionally connects town U_i and town V_i, and traveling along this road costs W_i stamina.

Takahashi's initial stamina is F. He starts at town 1 and wants to reach town N.

Each town j has an inn with a recovery value R_j. When Takahashi visits a town for the first time, the inn in that town restores R_j stamina. This recovery is applied only once per town — if he visits the same town two or more times, no recovery occurs from the second visit onward. Note that there is no upper limit on stamina (it can grow arbitrarily large through recovery).

Town 1 is treated as being visited for the first time at the moment of departure. Therefore, Takahashi's stamina before making the first move is F + R_1.

Takahashi's movement is performed by repeating the following steps:

  1. Takahashi chooses one road connected to the town he is currently in. However, he can only choose a road whose traversal cost (W_i) is less than or equal to his current stamina. If no road satisfies this condition, Takahashi cannot move any further.
  2. He travels along the chosen road, and his stamina decreases by W_i. It is acceptable for his stamina to become exactly 0.
  3. Immediately after arriving at the destination town, if this is his first visit to that town, the inn's recovery value R_j is added to his stamina.

Takahashi may travel along the same road any number of times and may visit the same town any number of times (however, inn recovery is applied only once per town as described above).

Considering all possible ways Takahashi can travel from town 1 to town N, find the maximum stamina upon arrival at town N. Here, the stamina upon arrival at town N refers to the stamina after step 3 above has been applied (if town N is visited for the first time, the inn recovery at town N is also applied).

If it is impossible to reach town N regardless of how he moves, output -1.

Constraints

  • 2 \leq N \leq 10
  • 1 \leq M \leq \frac{N(N-1)}{2}
  • 0 \leq F \leq 1000
  • 0 \leq R_j \leq 1000 (1 \leq j \leq N)
  • 1 \leq U_i < V_i \leq N (1 \leq i \leq M)
  • 1 \leq W_i \leq 1000 (1 \leq i \leq M)
  • There is at most one road connecting any pair of towns
  • All input values are integers

Input

N M F
R_1 R_2 \ldots R_N
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
  • The first line contains N representing the number of towns, M representing the number of roads, and F representing the initial stamina, separated by spaces.
  • The second line contains R_1, R_2, \ldots, R_N representing the inn recovery values for each town, separated by spaces.
  • The following M lines provide information about each road.
  • The (2 + i)-th line contains the towns U_i, V_i connected by the i-th road and the stamina cost W_i for traveling along that road, separated by spaces.

Output

Output in one line the maximum stamina when Takahashi arrives at town N from town 1. If it is impossible to reach town N regardless of how he moves, output -1.

Sample Input 1

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

Sample Output 1

11

Sample Input 2

3 1 5
0 0 0
1 2 3

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

103

Sample Input 4

8 10 50
10 20 30 40 50 15 25 100
1 2 30
1 3 40
1 6 35
2 3 25
3 4 20
3 8 80
4 5 15
5 8 10
6 7 20
7 8 30

Sample Output 4

200

Sample Input 5

2 1 0
1000 1000
1 2 1000

Sample Output 5

1000