25566번 - 김밥

김밥은 소금과 참기름으로 맛을 낸 밥에 속재료를 얹어 김으로 말아서 한입 크기로 썰어 낸 음식이다. 김밥은 포장 방식이 간편하고 휴대가 용이하며 특별한 도구 없이 손으로 집어 먹을 수 있기 때문에 바쁜 아침 출근길에 간편하게 먹기 좋으며 나들이용 도시락으로 인기 있는 음식이다. 기본적인 줄김밥에는 속재료로 달걀, 햄, 당근, 단무지, 맛살, 오이, 우엉, 어묵 등이 들어가지만 그 이외의 특별한 재료가 포함될 경우 그 재료의 이름을 따서 김밥의 이름을 붙인다. 이렇게 파생되어 분류되는 김밥의 종류 중 흔히 시중에서 판매되는 김밥에는 참치김밥, 치즈김밥, 소고기김밥, 김치김밥, 멸치김밥, 콩나물김밥 등이 있다. 다소 이국적인 재료인 아보카도, 파인애플, 아스파라거스, 망고 등을 넣은 김밥도 존재하는데 요리 연구가들은 이런 식으로 최근에 국내에 소개된 다양한 식재료를 김밥에 접목시키는 시도를 하고 있다.

(출처: 위키백과)

[그림 1] 김밥을 말기 위해 김 위에 식재료를 얹은 모습

당신은 세계 최고의 김밥 장인입니다. 당신 앞에 수직선상의 구간으로 나타낼 수 있는 $N$개의 식재료가 놓여 있고, 오늘도 당신은 김밥을 말아야 합니다. 세계 최고 타이틀을 가진 당신을 검증하기 위한 미션이 주어졌는데, 그것은 바로 식재료의 좌우 위치를 바꾸지 않으면서 가장 맛있는 김밥 한 줄을 마는 것입니다.

김밥을 말기 위해서는 [그림 1]과 같이 김 위에 다른 식재료가 모두 얹힌 형태가 되어야 합니다. 즉, 수직선상에서 김이 김밥을 구성하는 다른 모든 식재료를 포함해야 합니다. 원래 김밥은 김으로 말아야 하지만 지금은 가장 맛있는 김밥을 만드는 것이 중요하기 때문에 어떠한 식재료로 말아도 상관없습니다. 다시 말해서, 김밥을 말기 위해서는 수직선상에서 당신이 고른 식재료 중 어떤 식재료가 당신이 고른 다른 모든 식재료를 포함해야 합니다. 수직선상에서 식재료 $S$가 식재료 $T$를 포함한다는 것은 $S$의 구간이 $[l_S, r_S]$이고, $T$의 구간이 $[l_T, r_T]$일 때 $l_S\leq l_T, r_T\leq r_S\,$라는 것입니다.

또한 식재료 하나로 구성된 김밥을 마는 것도 가능합니다. 김밥의 맛은 김밥에 속한 각 식재료의 맛을 모두 더한 값이며, 김밥의 맛이 클수록 맛있는 김밥입니다. 가장 맛있는 김밥을 말아 당신이 세계 최고의 김밥 장인임을 증명해주세요!

첫째 줄에 식재료의 개수 $N$이 주어집니다. $\left(1\leq N\leq 1\,000\,000\right)$

둘째 줄부터 $N$개의 줄에 걸쳐 $i$번째 줄에는 $i$번째 식재료의 구간과 맛을 나타내는 정수 $l_i, r_i, v_i$가 공백을 사이에 두고 차례로 주어집니다. 수직선상에서 식재료의 구간이 $[l_i, r_i]$이고, 맛이 $v_i$임을 의미합니다. $(-10^9\leq l_i\leq r_i\leq 10^9;$ $1\leq v_i\leq 10^9)$

당신이 말 수 있는 가장 맛있는 김밥의 맛을 출력하세요.

김밥은 믿음직스러워요. 재료를 한눈에 볼 수 있어 예상 밖의 식감이나 맛에 놀랄 일이 없습니다.