Hogemon Get

Time Limit : 3 sec, Memory Limit : 262144 KB

Problem H: Hogemon Get

Problem

がっちょ君は人気のゲームHogemon Getに熱中している。がっちょ君が住んでいる会津国はそれぞれ1からNの番号がついているN個の町からなる。また、会津国にはM本の道があり、すべての道は異なる2つの町を結んでいる。がっちょ君は道を双方向に移動することができるが、道以外を通って、ある町から別の町に行くことはできない。

Hogemon Getでは、町iでボールをdi個入手することができる。ただし、ある町で再びボールを入手するためには、最後にその町でボールを入手してから15分以上経過している必要がある。なお、がっちょ君は町1、町Nを含むすべての町を何度でも訪れることができる。

がっちょ君は最初、町1にいて、町NR分以内で移動しなければならない。つまり、R分後に町Nにいる必要がある。がっちょ君は移動の際に、最大でいくつのボールを入手することができるだろうか。

Input

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

N M R
d1 d2 ... dN
a1 b1 c1
a2 b2 c2
...
aM bM cM

入力はすべて整数である。
1行目に町の個数N,道の本数M,制限時間Rが空白区切りで与えられる。
2行目に町i(i=1,2,...,N)に訪れることで入手することができるボールの個数diが空白区切りで与えられる。
3行目からM+2行目に道j(j=1,2,...,M)の情報aj,bj,cjが空白区切りで与えられる。j番目の道は町ajと町bjの間をcj分で移動できることを表す。

Constraints

  • 3 ≤ N ≤ 30
  • N-1 ≤ M ≤ min(N×(N-1)/2, 300)
  • 10 ≤ R ≤ 1000
  • 0 ≤ di ≤ 10
  • d1 = dN = 0
  • 1 ≤ aj < bjN
  • 5 ≤ cj ≤ 100
  • 町1から町NへはR分以内で移動できることが保証されている
  • ある2つの町の組に対して2本以上の道があることはない

Output

町1から町NR分以内に移動するまでに入手することができる最大のボールの個数を1行で出力せよ。

Sample Input 1

5 4 40
0 1 1 1 0
1 2 5
2 3 5
3 4 5
4 5 5

Sample Output 1

6
図1

経過時間(分)町の番号ボールの数(個)
010
521
1032
1543
2033
2524
3035
3546
4056

※経過時間20分の町3では最後に町3でボールを入手してから15分経過していないのでボールを入手することができない。

Sample Input 2

4 3 100
0 3 1 0
1 2 5
2 3 30
3 4 5

Sample Output 2

16
図2

経過時間(分)町の番号ボールの数(個)
010
523
2026
3529
50212
65215
95316
100416

Sample Input 3

5 4 50
0 1 1 10 0
1 2 10
2 3 10
2 4 10
4 5 10

Sample Output 3

22

Source: Aizu Competitive Programming Camp 2016 Day2 , Japan, 2016-09-18