Problem H: Hogemon Get

Problem

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

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

がっちょ君は最初、町1にいて、町NにR分以内で移動しなければならない。つまり、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)に訪れることで入手することができるボールの個数d_iが空白区切りで与えられる。
3行目からM+2行目に道j(j=1,2,...,M)の情報a_j,b_j,c_jが空白区切りで与えられる。j番目の道は町a_jと町b_jの間をc_j分で移動できることを表す。

Constraints

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

Output

町1から町NへR分以内に移動するまでに入手することができる最大のボールの個数を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

※経過時間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

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