問題
gousuperは動画を見るためにサブスクに入りました。
ですが、見たいものがなく、やけくそでN個のサブスクに入りまくりました。
その結果、1年間に払う金額がわからなくなりました。
サブスクの契約は$S_i$年から$T_i$年までの間で年間$P_i$円です。
($S_i$年と$T_i$年の分も含み、$T_i$年-$S_i$年+1年間分です。)
gousuperが1年間で最大何円払う必要があるかを求めてください。
入力
入力は以下の形式で標準入力から与えられる。
$N$ $S_1$ $T_1$ $P_1$ ⋮ $S_N$ $T_N$ $P_N$
出力
gousuperが1年間で最大何円払う必要があるか求めよ。
出力の最後に改行を入れること。
制約
全ての入出力ケースについて以下を満たす。
- $1≤N≤2×10^5$
- $0≤S_i＜T_i≤2×10^5$
- $1≤P_i≤10^9$
- 入力はすべて整数
入出力例
入力例1
4 1 3 5 2 4 4 3 10 6 2 4 1
出力例1
16
入力例2
6 0 200000 999999998 2 20 1 20 200 1 200 2000 1 2000 20000 1 20000 200000 1
出力例2
1000000000