004 - 怨なの子

問題1

あるところにほものさんがいました。ほものさんは"おんなのこ"が嫌いです。ほものさんは"おんなのこ"が怖いです。ある日、美男子れんさんのおうちに行くことになりました。ほものさんはとてもウキウキしています。ただ、ほものさんは恐怖におびえていました。なぜなら、ほものさんのおうちかられんさんのおうちに行くまでに数々の"おんなのこ"がいることです。"おんなのこ"になるべく会いたくありません。おばかちゃんなほものさんに"おんなのこ"に会う人数が最小のルートを教えてあげたいです。

まず、ホモーノ国には複数の都市が存在し、都市の間に道が存在します。都市ごとに今いる"おんなのこ"の人数が分かっています。ある都市に行ったら、その都市にいる"おんなのこ"全員に会うことが法律で決められています。そして、ほものさんに会った"おんなのこ"は死んじゃうらしいです。なので、ある都市に行くと、その都市の"おんなのこ"は0人になります。"おんなのこ"が再び出現することはないものとします。

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

また、ほものさんは何個か"おんなのこ撃退器"をもっています。これをどこかの都市に使うことで、今都市にいる"おんなのこ"の人数を半分に減らすことができます。半分に減らした結果、小数になってしまった場合は切り捨てすることになっています。ひとつの都市にひとつのおんなのこ撃退器しか使うことはできません。もっているおんなのこ撃退器をすべて使う必要はありません。

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

これらの条件を加えた上で、都市の数n、道の本数の合計m、各道の距離d、ほものさんの脚力k、おんなのこ撃退器の数zが与えられたときの会う"おんなのこ"の人数の最小を求めるプログラムを作成してください。

入力

n m
k z
g1
:
gi
:
gn-2
a1 b1 d1
   :    
ai bi di
   :
am bm dm

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

出力

ほものさんが会う"おんなのこ"の人数の最小を出力せよ。
どんなルートでも出発地から目的地にたどり着かない場合は、1行で"Dead Homono"を出力してください。

制約

すべての入出力ケースについて以下を満たす。
都市の数nは2以上100以下、道の本数mは1以上300以下、脚力kは1以上10000以下、おんなのこ撃退器の数zは0以上n-2以下、各都市の"おんなのこ"の人数gは0以上100以下、道の距離dは1以上10000以下とする。
出発地および目的地はどのようなテストケースでもそれぞれ0番目,n-1番目とする。

入出力例

入力例1

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

出力例1

3

入力例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