問題文

\(N\) 頂点 \(M\) 辺の有向グラフがあり、 \(i\) 番目の辺は頂点 \(a_i\) から頂点 \(b_i\) へ入り込んでいます。

そして、頂点 \(i\) には重さ \(w_i\) で価値 \(v_i\) の物が1つあります。

あなたは頂点 \(1\) から頂点 \(N\) まで辺に沿って最短経路で移動します。

また、あなたはナップサックを持っています。

ある頂点にきた時、その頂点に置いてある物をナップサックに入れることができます。入れなくても構いません。

ナップサックに入れる物の個数に制限はありませんが、ナップサックに入っている物の重さの総和は常に \(W\) 以下でなければいけません。

頂点 \(N\) に辿り着いた時点でのナップサックに入っている物の価値の総和があなたのスコアになります。

スコアの最大値を求めてください。

入力

\(N\) \(M\) \(W\)

\(a_1\) \(b_1\)

\(a_2\) \(b_2\)

:

\(a_M\) \(b_M\)

\(w_1\) \(v_1\)

\(w_2\) \(v_2\)

:

\(w_N\) \(v_N\)

出力

スコアの最大値を1行目に出力して下さい。

制約

• \(1≦N≦3000\)


• \(1≦M≦5000\)


• \(1≦W≦5000\)


• \(1≦a_i, b_i≦N\)


• \(a_i≠b_i\)


• \(i≠j\) なら \((a_i, b_i)≠(a_j, b_j)\)


• \(1≦w_i≦W\)


• \(1≦v_i≦10^5\)


• 頂点 \(1\) から頂点 \(N\) まで移動できる

小課題

小課題 EASY

• \(1≦N≦10\)

小課題 Straight

• \(a_i + 1 = b_i\)

小課題 Euglena

• 追加の制約はない。