도시 개발

$20yy$년 모스크바에는 새로운 건설을 할 공간이 부족해졌다. 정부는 새로운 수입원을 찾고 있으며, 도시 경계 안의 철도 선로를 모두 지하 터널로 바꾼다고 발표했다. 비게 된 공간은 개발에 쓰인다.

재개발은 길이가 $k$ 미터인 옥탸브리스카야 철도 선로 구간에서 시작한다. 빈 공간에는 많은 관광객이 몰리겠지만, 터널에 가해지는 압력은 균형을 이뤄야 한다. 새 구역은 커피 가게나 아이스크림 트럭처럼 가장 중요한 사업체만 사용할 수 있다.

선로는 1부터 $k$까지 번호가 붙은 $k$개의 같은 길이 구간으로 나뉜다. 새 땅을 쓰려는 회사는 $n$개다. $i$번째 회사는 $l_i$부터 $r_i$까지의 모든 구간을 사용하려 하며, 건물의 압력을 나타내는 정수 $p_i$를 제출했다. 각 신청은 통째로 수락하거나 거절해야 하며, 일부만 수락할 수는 없다.

시장은 모든 구간이 최소 한 회사에 의해 사용되기를 바란다. 또한 어느 구간에서든 최대 압력을 최소로 줄이고자 한다. 같은 구간을 여러 수락된 신청이 덮으면, 그 구간의 총 압력은 각 건물 압력의 합이다.

모든 구간이 최소 하나의 수락된 신청에 덮이도록 신청의 집합을 고르되, 모든 구간의 최대 압력이 가능한 한 작아지게 하라.

첫 줄에 신청의 수 $n$과 구간의 수 $k$가 주어진다 ($1 \le n \le 100\,000$, $1 \le k \le 10^9$).

다음 $n$개의 줄에는 각각 정수 $l_i$, $r_i$, $p_i$가 주어진다 ($1 \le l_i \le r_i \le 10^9$, $1 \le p_i \le 10^9$). 이는 $i$번째 신청의 가장 왼쪽 구간, 가장 오른쪽 구간, 압력이다.

조건을 만족하는 신청의 집합에서 모든 구간의 최대 압력이 가질 수 있는 최솟값을 한 줄에 출력한다. 조건을 만족하는 신청의 집합이 없으면 $-1$을 출력한다.

첫 번째 예제에서 최적의 방법은 처음 두 신청을 수락하는 것이다. 이때 최대 압력은 세 번째 구간에서 나타나며 값은 3이다.

두 번째 예제에서는 세 번째 구간을 사용하려는 회사가 없으므로 조건을 만족할 수 없다.

세 번째 예제에서는 모든 신청을 수락하는 것이 최적해 중 하나다. 최대 압력은 네 번째 구간에서 나타나며 값은 8이다. 수락하는 신청의 개수를 최소화하거나 최대화할 필요는 없다.

네 번째 예제에서는 첫 번째 신청과 네 번째 신청을 수락하는 것이 최적해다. 이때 모든 구간의 압력은 1이다.