22358번 - 스키장

문제

당신은 친구들과 함께 스키를 타러 스키장에 왔다. 스키장에는 일정 고도마다 중간 지점이 설치되어 있다. 중간 지점은 총 $N$개 있으며, 고도가 감소하는 순서대로 1번부터 $N$번까지 번호가 매겨져 있다. 즉 가장 높은 지점이 1번 지점, 가장 낮은 지점이 $N$번 지점이다.

현재 당신은 $S$번 지점에 친구들과 함께 있다. 당신의 친구들은 각자 자유롭게 스키를 탄 이후, 끝나면 $T$번 지점에 모이기로 약속했다.

스키장에는 $M$개의 코스가 있다. 각 코스는 $a_i$번 지점에서 $b_i$번 지점 방향으로 이어지며, 코스에 진입하면 $t_i$시간 동안 스키를 탈 수 있다. 코스는 항상 고도가 감소하는 방향으로 이어진다. 즉, $a_i < b_i$를 만족한다.

또한, 각 코스에는 스키 리프트가 있다. 스키 리프트는 코스와는 반대 방향으로, 고도가 증가하는 방향으로 이어진다. 즉, 스키 리프트를 타면 $b_i$번 지점에서 $a_i$번 지점으로 이동할 수 있다. 스키 리프트는 최대 $K$번 탑승할 수 있다.

당신은 스키 코스와 리프트만을 사용해서 $T$번 지점까지 가되, 스키를 타는 시간을 최대화하려고 한다. 리프트를 타는 시간은 스키를 타는 시간에 포함되지 않는다. 코스의 정보가 주어질 때, 최대 몇 시간 동안 스키를 탈 수 있을지 구하여라.

입력

첫 번째 줄에 다섯 개의 정수 $N, M, K, S, T$ (1ドル \le N, M \le 10^5,ドル 0ドル \le K \le 10,ドル 1ドル \le S, T \le N$) 가 주어진다.

이후 $M$ 개의 줄에 각 코스의 정보가 세 개의 정수 $a_i, b_i, t_i$ (1ドル \le a_i < b_i \le N,ドル 1ドル \le t_i \le 10^9$) 로 주어진다.

서로 다른 두 지점을 잇는 코스는 최대 하나이다.

출력

최대 몇 시간 동안 스키를 탈 수 있는지 하나의 정수로 출력하라.

만약 어떻게 코스와 리프트를 선택해도 $T$번 지점으로 이동할 수 없다면 -1을 대신 출력하라.

제한

힌트