008 - 試食

問題

YDKスーパーにはN個の試食コーナーと、それを繋ぐM本の道があります。
各道は双方向に移動可能であり、任意の試食コーナー同士をつなぐルートは必ず一つ以上存在します。
各試食コーナーでは試食をすることができ、i番目の試食コーナーで試食すると満腹度がm_i上がり、幸福度がh_i上がります。
また、スーパーに入った直後は試食コーナー1に着き、スーパーから帰るときも試食コーナー1から帰る必要があります。

YTAくんは3200円のイヤホン(ゴミ)を買ってしまったため、現在お金がありません。
そこで試食コーナーでお腹を満たすことにしました。

試食コーナーでは、連続で試食を行うことができません。
しかし、別の場所に一度移動すれば(たとえそこで試食をしなくても)もう一度戻ってきたときに再び試食をすることができることに気が付きました。

YTAくんはそれを利用してできるだけ幸福になろうと思いました。
しかし、YTAくんの満腹限界度Lを超えてしまったとき、YTAくんは動けなくなってしまいます。
満腹限界度を超えないように食事をした際、YTAくんが最大でどれだけ幸福になれるかを求めてください。

入力

入力は1+N+M行からなる。
1行目には、試食コーナーの数N(2≦N≦100)、道の数M(問題文の制約を満たすような数)、およびYTAの満腹限界度L(2≦L≦10000)が与えられる。
その後N行にわたり、試食コーナーiの満腹度m_i(1≦m≦100)、および幸福度h_i(1≦h≦100)が与えられる
続くM行には道の情報a_i,b_i(1≦a,b≦N,a≠b)が与えられ、試食コーナーa_iとb_iを結ぶ道が存在することを表す。
任意の試食コーナー同士を直接結ぶ道は2つ以上与えられない。

出力

YTAの幸福度の最大値を1行で出力せよ

入出力例

入力例

5 6 21
2 1
7 5
5 4
4 5
3 3
1 2
2 3
3 4
1 3
2 5
4 2

出力例

25