당신은 친구들과 함께 스키를 타러 스키장에 왔다.

스키장에는 일정 고도마다 중간 지점이 설치되어 있다. 중간 지점은 총 N개 있으며,
고도가 감소하는 순서대로 1번부터 N번까지 번호가 매겨져 있다.

즉 가장 높은 지점이 1번 지점, 가장 낮은 지점이 N번 지점이다.

현재 당신은 S번 지점에 친구들과 함께 있다.

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

스키장에는 M개의 코스가 있다.

각 코스는 a_i번 지점에서 b_i번 지점 방향으로 이어지며, 코스에 진입하면 t_i분 동안 스키를 탈 수 있다.

코스는 항상 고도가 감소하는 방향으로 이어진다. 즉, a_i < b_i를 만족한다.

또한, 각 코스에는 스키 리프트가 있다. 스키 리프트는 코스와는 반대 방향으로, 고도가 증가하는 방향으로 이어진다.

즉, 스키 리프트를 타면 b_i번 지점에서 a_i번 지점으로 이동할 수 있다. 스키 리프트는 최대 K번 탑승할 수 있다.

당신은 스키 코스와 리프트만을 사용해서 T번 지점까지 가되, 스키를 타는 시간을 최대화하려고 한다.

리프트를 타는 시간은 스키를 타는 시간에 포함되지 않는다.

코스의 정보가 주어질 때, 최대 몇 분 동안 스키를 탈 수 있을지 구하여라.

스키장 timer 1s memory 1024MB

스키장 1s 1024MB