財宝の山が N 個あり、それぞれの山は 1 から N までで番号づけられている。i 番目の山には価値 p_i のお宝が眠っており、このお宝はその山に訪れた時点で得ることができる。一度お宝を得るとその山からはお宝がなくなってしまうので、お宝はそれぞれ一度しか得ることはできない。
異なる山に移動するには必ず道を利用しなければならない。山と山の間には合計 N-1 本の道があり、i 番目の道は山 u_i と v_i を双方向に結んでいる。もしもどの道も問題なく通行可能であると仮定すると、任意の 2 つの山について相互に行き来可能であることが分かっている。
どの道も長らく誰も通行しておらず修復しないと渡れないため、i 番目の道について最初に渡る際には c_i 円を支払って工事し、通行可能にする必要がある。一度工事した道であればそれ以上お金を支払うことなく通行が可能である。
トレジャーハンターであるあなたは、道の工事費用の予算を W 円持っている。あなたの目的は、はじめに降り立つ山を任意に 1 つ決め、合計 W 円以下で道を工事して異なる山に移動することで、得られるお宝の価値の合計を最大化することである。あなたは最大でどれだけの価値を得られるだろうか？
なお、お宝を途中で換金することはできないため、お宝を工事費用として使用することはできないことに注意せよ。
入力は以下の形式で与えられる。
N W
p_1 p_2 ... p_N
u_1 v_1 c_1
:
u_{N-1} v_{N-1} c_{N-1}
得られるお宝の価値の合計の最大値を 1 行に出力せよ。末尾の改行を忘れないこと。
3 10 6 8 2 1 2 3 2 3 8
14
3 15 10 10 12 1 2 6 1 3 4
32
5 1 4 8 8 2 10 1 2 3 2 4 5 2 5 2 1 3 7
10