Przyjechałeś ze znajomymi do ośrodka narciarskiego, aby pojeździć na nartach. W ośrodku tym na różnych wysokościach znajdują się stacje pośrednie. Istnieje łącznie $N$ stacji pośrednich, ponumerowanych od 1 do $N$ w kolejności malejącej wysokości. Oznacza to, że najwyżej położona stacja ma numer 1, a najniżej położona stacja ma numer $N$.

Obecnie znajdujesz się wraz ze znajomymi na stacji $S$. Umówiliście się, że po swobodnej jeździe na nartach spotkacie się na stacji $T$.

W ośrodku znajduje się $M$ tras zjazdowych. Każda trasa prowadzi ze stacji $a_i$ do stacji $b_i$, a zjazd nią trwa przez czas $t_i$. Trasy zawsze prowadzą w dół (w kierunku malejącej wysokości), czyli spełniony jest warunek $a_i < b_i$.

Dodatkowo, na każdej trasie znajduje się wyciąg narciarski. Wyciąg prowadzi w kierunku przeciwnym do trasy zjazdowej, czyli w stronę rosnącej wysokości. Oznacza to, że korzystając z wyciągu, można przemieścić się ze stacji $b_i$ do stacji $a_i$. Z wyciągów można skorzystać łącznie co najwyżej $K$ razy.

Chcesz dotrzeć do stacji $T$, korzystając wyłącznie z tras zjazdowych i wyciągów, tak aby maksymalnie wydłużyć łączny czas jazdy na nartach. Czas spędzony na wyciągach nie wlicza się do czasu jazdy na nartach. Mając dane informacje o trasach, wyznacz maksymalny czas, przez jaki możesz jeździć na nartach.

Wejście

W pierwszym wierszu podanych jest pięć liczb całkowitych $N, M, K, S, T$ ($1 \le N, M \le 10^5$, $0 \le K \le 10$, $1 \le S, T \le N$).

W kolejnych $M$ wierszach znajdują się informacje o trasach. Każdy z nich zawiera trzy liczby całkowite $a_i, b_i, t_i$ ($1 \le a_i < b_i \le N$, $1 \le t_i \le 10^9$).

Między dowolnymi dwiema stacjami istnieje co najwyżej jedna trasa.

Wyjście

Wypisz jedną liczbę całkowitą — maksymalny czas, przez jaki możesz jeździć na nartach.

Jeśli niezależnie od wyboru tras i wyciągów nie jest możliwe dotarcie do stacji $T$, wypisz -1.

Przykład

Wejście 1

3 2 1 1 3
1 2 10
2 3 5

Wyjście 1

25

Wejście 2

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

Wyjście 2

30

Wejście 3

3 2 1 3 1
1 2 10
2 3 5

Wyjście 3

-1

Wejście 4

3 2 2 3 1
1 2 10
2 3 5

Wyjście 4

0