시장조성하기

Hudson River Trading(HRT)은 뛰어난 수학, 기술적 역량을 활용하여 거래 전략을 설계하는 퀀트 트레이딩 회사이다. HRT는 엔지니어와 연구자들이 한 팀을 이뤄 어려운 문제를 해결하며, 글로벌 금융 시장에서 매일 수백만 주의 주식을 거래한다.

HRT의 신입 알고리즘 개발자는 새로 설계한 거래 전략을 따르는 시장조성(market-making) 엔진을 개발한 뒤, 그 엔진의 안정성을 평가하고자 한다. 시장조성 엔진은 주식을 보유하지 않은 가상의 계좌를 이용하여 거래를 시작하며, $N$개의 연속된 매매 시점(틱)에 아래와 같은 전략을 따라 거래한다.

• $i$번째 매매 시점에 엔진은 $a_i$ 이상 $b_i$ 이하의 정수 하나를 선택한다. 선택한 정수가 양수라면 그만큼 주식을 매수하고, 음수라면 선택한 정수의 절댓값만큼 주식을 매도하고, $0$이라면 주식을 매매하지 않는다. 이 때 보유한 주식이 부족해도 매도가 가능하며, 이 경우 보유 주식의 수는 음수가 된다.
• $i$번째 매매 직후 보유 주식이 $0$주라면, 해당 전략이 포지션 노출을 최소화하여 위험성을 완화하고 시장 안정성에 기여했다고 평가하여 시장조성 엔진의 안정성이 $x_i$만큼 증가한다.
• 수수료 또는 슬리피지 등 다른 요소는 모두 무시한다.

총 $N$번의 매매를 모두 마쳤을 때, 신규 개발한 시장조성 엔진이 달성할 수 있는 안정성의 최댓값을 구해보자.

첫째 줄에는 주식을 매매한 횟수 $N$이 주어진다. ($1 \leq N \leq 1\,000\,000$)

다음 $N$개의 줄에 걸쳐, 그 중 $i$번째 줄에 $i$번째 매매에 대한 정보를 의미하는 세 정수 $a_i, b_i, x_i$가 공백으로 구분되어 주어진다. ($-10^9 \leq a_i \leq b_i \leq 10^9$; $1 \leq x_i \leq 10^9$)

총 $N$번의 매매를 모두 마쳤을 때, 신규 개발한 시장조성 엔진이 달성할 수 있는 안정성의 최댓값을 출력한다.