がっちょ君は人気のゲームHogemon Getに熱中している。がっちょ君が住んでいる会津国はそれぞれ1からNの番号がついているN個の町からなる。また、会津国にはM本の道があり、すべての道は異なる2つの町を結んでいる。がっちょ君は道を双方向に移動することができるが、道以外を通って、ある町から別の町に行くことはできない。
Hogemon Getでは、町iでボールをdi個入手することができる。ただし、ある町で再びボールを入手するためには、最後にその町でボールを入手してから15分以上経過している必要がある。なお、がっちょ君は町1、町Nを含むすべての町を何度でも訪れることができる。
がっちょ君は最初、町1にいて、町NにR分以内で移動しなければならない。つまり、R分後に町Nにいる必要がある。がっちょ君は移動の際に、最大でいくつのボールを入手することができるだろうか。
入力は以下の形式で与えられる。
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分で移動できることを表す。
町1から町NへR分以内に移動するまでに入手することができる最大のボールの個数を1行で出力せよ。
5 4 40 0 1 1 1 0 1 2 5 2 3 5 3 4 5 4 5 5
6
経過時間(分) | 町の番号 | ボールの数(個) |
0 | 1 | 0 |
5 | 2 | 1 |
10 | 3 | 2 |
15 | 4 | 3 |
20 | 3 | 3 |
25 | 2 | 4 |
30 | 3 | 5 |
35 | 4 | 6 |
40 | 5 | 6 |
※経過時間20分の町3では最後に町3でボールを入手してから15分経過していないのでボールを入手することができない。
4 3 100 0 3 1 0 1 2 5 2 3 30 3 4 5
16
経過時間(分) | 町の番号 | ボールの数(個) |
0 | 1 | 0 |
5 | 2 | 3 |
20 | 2 | 6 |
35 | 2 | 9 |
50 | 2 | 12 |
65 | 2 | 15 |
95 | 3 | 16 |
100 | 4 | 16 |
5 4 50 0 1 1 10 0 1 2 10 2 3 10 2 4 10 4 5 10
22