あなたは友達と一緒にスキーをするためにスキー場にやってきた。スキー場には、一定の高度ごとに中間地点が設置されている。中間地点は全部で $N$ 個あり、高度が減少する順に 1 番から $N$ 番まで番号が付けられている。すなわち、最も高い地点が 1 番地点、最も低い地点が $N$ 番地点である。

現在、あなたは $S$ 番地点に友達と一緒にいる。あなたの友達はそれぞれ自由にスキーを楽しんだ後、終わったら $T$ 番地点に集まることを約束した。

スキー場には $M$ 個의 コースがある。各コースは $a_i$ 番地点から $b_i$ 番地点の方向へと繋がっており、コースに入ると $t_i$ 時間の間スキーを滑ることができる。コースは常に高度が減少する方向へと繋がっている。すなわち、$a_i < b_i$ を満たす。

また、各コースにはスキーリフトがある。スキーリフトはコースとは逆方向、すなわち高度が増加する方向へと繋がっている。つまり、スキーリフトに乗ると $b_i$ 番地点から $a_i$ 番地点へと移動することができる。スキーリフトは最大 $K$ 回まで搭乗することができる。

あなたはスキーコースとリフトだけを使用して $T$ 番地点まで行くが、スキーを滑る時間を最大化したい。リフトに乗っている時間は、スキーを滑る時間には含まれない。コースの情報が与えられたとき、最大で何時間スキーを滑ることができるかを求めよ。

入力

最初の行に 5 つの整数 $N, M, K, S, T$ ($1 \le N, M \le 10^5$, $0 \le K \le 10$, $1 \le S, T \le N$) が与えられる。

その後 $M$ 行にわたって、各コースの情報が 3 つの整数 $a_i, b_i, t_i$ ($1 \le a_i < b_i \le N$, $1 \le t_i \le 10^9$) で与えられる。

異なる 2 つの地点を結ぶコースは最大 1 つである。

出力

最大で何時間スキーを滑ることができるかを 1 つの整数で出力せよ。

もしどのようにコースとリフトを選択しても $T$ 番地点に移動できない場合は、代わりに -1 を出力せよ。

入出力例

入力 1

3 2 1 1 3
1 2 10
2 3 5

出力 1

25

入力 2

3 3 1 1 3
1 2 10
2 3 5
1 3 1

出力 2

30

入力 3

3 2 1 3 1
1 2 10
2 3 5

出力 3

-1

入力 4

3 2 2 3 1
1 2 10
2 3 5

出力 4

0