Of course you have heard the famous task about Hanoi Towers, but did you know that there is a special factory producing the rings for this wonderful game? Once upon a time, the ruler of the ancient Egypt ordered the workers of Hanoi Factory to create as high tower as possible. They were not ready to serve such a strange order so they had to create this new tower using already produced rings.

There are n rings in factory's stock. The i-th ring has inner radius a_{i}, outer radius b_{i} and height h_{i}. The goal is to select some subset of rings and arrange them such that the following conditions are satisfied:  Outer radiuses form a non-increasing sequence, i.e. one can put the j-th ring on the i-th ring only if b_{j} ≤ b_{i}.  Rings should not fall one into the the other. That means one can place ring j on the ring i only if b_{j} > a_{i}.  The total height of all rings used should be maximum possible. 


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of rings in factory's stock.

The i-th of the next n lines contains three integers a_{i}, b_{i} and h_{i} (1 ≤ a_{i}, b_{i}, h_{i} ≤ 10^9, b_{i} > a_{i}) — inner radius, outer radius and the height of the i-th ring respectively.


-----Output-----

Print one integer — the maximum height of the tower that can be obtained.


-----Examples-----
Input
3
1 5 1
2 6 2
3 7 3

Output
6

Input
4
1 2 1
1 3 3
4 6 2
5 7 1

Output
4



-----Note-----

In the first sample, the optimal solution is to take all the rings and put them on each other in order 3, 2, 1.

In the second sample, one can put the ring 3 on the ring 4 and get the tower of height 3, or put the ring 1 on the ring 2 and get the tower of height 4.

Difficulty: interview

Starter code:

Solutions:
from operator import attrgetter, itemgetter
n = int(input());
arr = [[int(x) for x in input().split(' ')] for y in range(n)];
arr = sorted(arr, key=itemgetter(1,0,2), reverse=True);
dp = [0 for x in range(n)];
s = [];
for i in range(n):
	while (s != [] and arr[s[-1]][0] >= arr[i][1]):
		s.pop();
	if (s != []):
		dp[i] = dp[s[-1]];
	dp[i] += arr[i][2];
	s.append(i);
print(max(dp));

#!/usr/bin/env python3
def ri():
    return list(map(int, input().split()))

n = int(input())

r = []
T = []
maxt = -1
for i in range(n):
    r.append(list(ri()))

r.sort(key=lambda e: (e[1], e[0]))

T.append([r[0][2], r[0][1]])
for i in range(1, n):
    tmp = r[i][2]
    l = len(T)
    for j in range(l):
        if r[i][0] >= T[-1][1]:
            T.append([tmp, r[i][1]])
            break
        else:
            tmp = max(T[-1][0]+r[i][2], tmp)
            T.pop()
    else:
        T.append([tmp, r[i][1]])


print(max(T)[0])




import operator
n = int(input()) 
arr=[]
for i in range(n):
    arr.append([int(element) for element in input().split()])
arr = sorted(arr, key=operator.itemgetter(1,0,2), reverse= True) 
heigh = [0 for i in range(n)] 
seq = [] 
for i in range(n):
    while len(seq) > 0 and arr[seq[-1]][0] >= arr[i][1] :
        seq.pop()
    if len(seq) > 0 :
        heigh[i] = heigh[seq[-1]] 
    heigh[i] += arr[i][2] 
    seq.append(i)
print(max(heigh))


from bisect import *
from sys import *
p = list(map(int, stdin.read().split()))
t = [(p[i + 1], p[i], p[i + 2]) for i in range(1, len(p), 3)]
t.sort(reverse=True)
s = [(0, 0), (1e9, 1e16)]
for b, a, h in t:
    i = bisect(s, (b,))
    h += s[i - 1][1]
    j = bisect(s, (a,))
    while s[j][1] <= h: s.pop(j)
    s.insert(j, (a, h))
print(s[-2][1])


t = [(9e9, 0, 0)]
n = int(input())
for i in range(n):
    a, b, h = map(int, input().split())
    t.append((b, a, h))
t.sort(reverse=True)
s, p = [0], [0] * (n + 1)
for i in range(1, n + 1):
    while t[s[-1]][1] >= t[i][0]: s.pop()
    p[i] = p[s[-1]] + t[i][2]
    s.append(i)
print(max(p))

aux = [(9e9, 0, 0)]
n = int(input())
 
for i in range(n):
    a, b, h = map(int, input().split())
    aux.append((b, a, h)) #sort padrao eh pelo item 0 da tupla
 
aux.sort(reverse=True)
 
s, p = [0], [0] *(n + 1)
 
for i in range(1, n + 1):
    while aux[s[-1]][1] >= aux[i][0]:
        s.pop()
        
    p[i] = p[s[-1]] + aux[i][2]
    s.append(i)
 
print(max(p))

aux = [(9e9, 0, 0)]
n = int(input())
 
for i in range(n):
    a, b, h = map(int, input().split())
    aux.append((b, a, h)) #sort padrao eh pelo item 0 da tupla
 
aux.sort(reverse=True)
 
s, p = [0], [0] *(n + 1)
 
for i in range(1, n + 1):
    while aux[s[-1]][1] >= aux[i][0]:
        s.pop()
        
    p[i] = p[s[-1]] + aux[i][2]
    s.append(i)
print(max(p))

n = int(input())
d = []
for i in range(n):
    a, b, h = map(int, input().split())
    d.append((b, a, h))
    
d.sort()


ht = d[len(d) - 1][2]

ans = ht

s = []
s.append(d[len(d) - 1])


for i in range(n - 2, -1, -1):
    while s and d[i][0] <= s[len(s) - 1][1]:
        ht -= s.pop()[2]
    s.append(d[i])
    ht += d[i][2]
    if ans < ht:
        ans = ht
        
print(ans)

n = int(input())
d = []
for i in range(n):
    a, b, h = map(int, input().split())
    d.append((b, a, h))
    
d.sort()
 
 
ht = d[len(d) - 1][2]
 
ans = ht
 
s = []
s.append(d[len(d) - 1])
 
 
for i in range(n - 2, -1, -1):
    while s and d[i][0] <= s[len(s) - 1][1]:
        ht -= s.pop()[2]
    s.append(d[i])
    ht += d[i][2]
    if ans < ht:
        ans = ht
        
print(ans)

n = int(input())
d = []
for i in range(n):
    a, b, h = map(int, input().split())
    d.append((b, a, h))
d.sort()
ht = d[len(d) - 1][2]
ans = ht
s = [d[len(d) - 1]]

for i in range(n - 2, -1, -1):
    while s and d[i][0] <= s[len(s) - 1][1]:
        ht -= s.pop()[2]
    s.append(d[i])
    ht += d[i][2]
    if ans < ht:
        ans = ht
print(ans)