005 - れんさん退治

問題1

あるところにほものさんがいました。ほものさんは美男子れんさんを堕とそうとしています。ほものさんはれんさんを退治するためにほものさんの家かられんさんの家までの途中で仲間となる"ほも"を集めなければなりません。ほものさんが集められる"ほも"の最大の人数をおばかちゃんであるほものさんに教えてあげたい。

まず、ホモー国には複数の都市が存在し、都市の間に道が存在します。都市ごとに今いる"ほも"の人数が分かっています。ある都市に行ったら、その都市にいる"ほも"を全員仲間にします。全員集めるため、都市の人数は0人になり、その都市に再び"ほも"が現れることはありません。

ほものさんはより多くの"ほも"を集めるため、すべての都市をまわりたい。しかし、ほものさんは運動神経が情弱らしく、歩くたびに脚力が減少していくらしいです。なので、道の距離が1だった場合、ほものさんの脚力は1減少します。脚力がゼロになった時点でほものさんは永遠の眠りについてしまいます。なので、目的地に脚力0で着くことは避けたいです

また、ほものさんは何個か"ほも増殖器"をもっています。これをどこかの都市に使うことで、今都市にいる"ほも"の人数を2倍に増やすことができます。もっているほも増殖器をすべて使う必要はありません。

注意事項として、都市は0~n-1番目の番号がついていて、出発地は必ず0番目の都市であり、目的地は必ずn-1番目の都市とします。入力での都市の数nのなかに出発地および目的地も含まれます。そして出発地および目的地に"ほも"はいないとします。道は双方向で移動できるものとする。

これらの条件を加えた上で、都市の数n、都市にいる人数m、各道の距離d、ほものさんの脚力k、ほも増殖器の数zが与えられたときの集められるほもの人数の最大を求めるプログラムを作成してください。

入力

n m
k z
h1
:
hi
:
hn-2
a1 b1 d1
   :    
ai bi di
   :
am bm dm

1行目に2つの整数n,mが半角空白区切りで与えられる。
n : 都市の数 m : 都市間の道の本数の合計
2行目に2つの整数k,zが半角空白区切りで与えられる。
k : ほものさんの脚力 z : ほも増殖器の数
3行目からn行目には整数hが半角空白区切りで与えられる。
(1番目からn-2番目までn-2回入力する)
h : 都市にいる"ほも"の人数
n+3行目からm+n+2行目には3つの整数a,b,dが半角空白区切りで与えられる。
a,b : 道の両端の点 d : 道の距離

出力

ほものさんが集められる"ほも"の人数の最大を出力せよ。

どんなルートでも出発地から目的地にたどり着かない場合は、1行で"Dead Homono"を出力してください。

制約

すべての入出力ケースについて以下を満たす。

都市の数nは2以上100以下、道の本数mは1以上500以下、脚力kは1以上10000以下、ほも増殖器の数zは0以上n-2以下、各都市の"ほも"の人数hは0以上100以下、道の距離dは1以上10000以下とする。

出発地および目的地はどのようなテストケースでもそれぞれ0番目,n-1番目とする。

入出力例

入力例1

5 6
8 1
3
4
1
0 1 2
0 2 3
1 2 6
1 3 2
2 4 5
3 4 3

出力例1

7

入力例2

7 9
10 1
3
2
2
4
3
0 1 1
0 2 2
1 3 4
2 3 6
2 4 5
3 4 2
4 5 1
4 6 5
5 6 7

出力例2

Dead Homono

入力例3

2 1
10000 0
0 1 9999

出力例3

0