Magical Dungeon

入力
1. 勇者アーサーの最大HP
2. ダンジョンのマップ（有向グラフ）
   - 部屋に番号が振ってあって、何番と何番の部屋が通路で繋がってるかの情報が与えられる
   - 通路は全部一方通行
   - すべての通路には整数 w が振ってある
      - w<0 の通路を通ると、その分だけ毒でダメージを受ける（0になったらGAME OVERです）
      - w>0 の通路を通ると、その分だけ聖なる魔法の力でHPが回復する（ただし最大HPまでしか回復しません）
   - 入り口の部屋の番号
   - ボスのいる部屋の番号

勇者アーサーは最初、HP満タンで入り口の部屋にいます。
ボスのいる部屋に入ると強制戦闘開始です。

できるだけ残りHPを高く保った状態でボスの部屋に辿り着く歩き方を考えて下さい。

入出力

入力は

部屋の個数 通路の個数
通路1の始まる部屋 通路1の終わる部屋 w1
...
通路Mの始まる部屋 通路Mの終わる部屋 wM
入り口 ボス 最大HP

みたいな形式で。
部屋数は100以下。通路数は10000以下。最大HPは1000000以下と仮定してよい。
出力は、一番HP高く辿り着けるときのそのHPを出して下さい。

Sample Input

7 8
0 2 3
2 3 -20
3 4 3
4 1 -5
1 5 1
5 4 5
1 3 2
3 6 -2
0 6 30

7 8
0 2 3
2 3 -20
3 4 3
4 1 -5
1 5 1
5 4 5
1 3 2
3 6 -2
0 6 20

4 4
0 1 -10
1 2 -50
2 1 51
1 3 1
0 3 20

11 14
0 1 -49
1 2 1
2 3 40
3 1 -40
1 4 -9
4 5 40
5 1 -30
1 6 -19
6 7 40
7 1 -20
1 8 -30
8 9 40
9 1 -9
1 10 1
0 10 50

3 4
0 1 -49
1 2 10
2 0 50
2 1 10
0 1 50

Output for the Sample Input

25
GAME OVER
11
31
1