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: HARD
Tags: Sorting

Greedy algorithms

Complete search

Dynamic programming

Data structures
Skill types: Sorting

Greedy algorithms

Complete search

Dynamic programming

Data structures

Starter code:

Solutions:
aux = [(9000000000.0, 0, 0)]
n = int(input())
for i in range(n):
	(a, b, h) = map(int, input().split())
	aux.append((b, a, h))
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))


from sys import stdin
n = int(input())
(x, ans, sum) = ([[0] * 3 for i in range(n)], 0, 0)
d = []
for i in range(n):
	(x[i][1], x[i][0], x[i][2]) = map(int, stdin.readline().split())
x.sort()
for i in range(n - 1, -1, -1):
	while len(d) > 0 and d[len(d) - 1][1] >= x[i][0]:
		sum -= d[len(d) - 1][2]
		d.pop()
	d.append(x[i])
	sum += x[i][2]
	ans = max(ans, sum)
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)


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 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))


import os, sys
from io import BytesIO, IOBase
INF = float('inf')

def update(tree, pos, value, si):
	pos += si - 1
	tree[pos] = value
	pos >>= 1
	while pos:
		tree[pos] = min(tree[pos << 1], tree[pos << 1 | 1])
		pos >>= 1

def query(tree, mini, si, pos):
	if pos >= si:
		return pos - si
	if tree[pos << 1] > mini:
		return query(tree, mini, si, pos << 1 | 1)
	return query(tree, mini, si, pos << 1)

def main():
	n = int(input())
	si = 1 << n.bit_length() - (not n & n - 1)
	(a, b, h) = ([], [], [])
	for _ in range(n):
		(u1, v1, w1) = map(int, input().split())
		a.append(u1)
		b.append(v1)
		h.append(w1)
	rr = sorted(sorted(range(n), key=lambda yy: a[yy]), key=lambda xx: b[xx])
	tree = [INF] * (si << 1)
	dp = [0] * n
	for ind in range(n - 1, -1, -1):
		i = rr[ind]
		if tree[1] >= b[i]:
			dp[ind] = h[i]
		else:
			dp[ind] = h[i] + dp[query(tree, b[i] - 1, si, 1)]
		update(tree, ind + 1, a[i], si)
	print(max(dp))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


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), (1000000000.0, 1e+16)]
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])


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
	return int(input())

def rl():
	return list(map(int, input().split()))

class segmentTree:

	def __init__(self, n):
		self.n = n
		self.tree = [0] * (2 * self.n)

	def update(self, p, value):
		self.tree[self.n + p] = value
		p = p + self.n
		while p > 1:
			self.tree[p >> 1] = max(self.tree[p], self.tree[p ^ 1])
			p >>= 1

	def min(self, l, r):
		res = 0
		l += self.n
		r += self.n
		while l < r:
			if l & 1:
				res = max(res, self.tree[l])
				l += 1
			if r & 1:
				r -= 1
				res = max(res, self.tree[r])
			l >>= 1
			r >>= 1
		return res

def solve():
	n = ri()
	disks = []
	A = set()
	for i in range(n):
		(a, b, h) = rl()
		disks.append([b, a, h])
		A.add(a)
	disks.sort(reverse=True)
	AS = sorted(list(A))
	xref = {a: i for (i, a) in enumerate(AS)}

	def bi(b):
		return bisect.bisect_left(AS, b)
	T = segmentTree(n)
	for (b, a, h) in disks:
		prev = T.min(0, bi(b))
		local = h + prev
		T.update(xref[a], local)
	print(T.min(0, n))
mode = 's'
if mode == 'T':
	t = ri()
	for i in range(t):
		solve()
else:
	solve()


def ri():
	return 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])


from collections import defaultdict as dd
from collections import deque
import bisect
import heapq
import sys
input = sys.stdin.readline

def ri():
	return int(input())

def rl():
	return list(map(int, input().split()))

class segmentTree:

	def __init__(self, n):
		self.n = n
		self.tree = [0] * (2 * self.n)

	def update(self, p, value):
		self.tree[self.n + p] = value
		p = p + self.n
		while p > 1:
			self.tree[p >> 1] = max(self.tree[p], self.tree[p ^ 1])
			p >>= 1

	def min(self, l, r):
		res = 0
		l += self.n
		r += self.n
		while l < r:
			if l & 1:
				res = max(res, self.tree[l])
				l += 1
			if r & 1:
				r -= 1
				res = max(res, self.tree[r])
			l >>= 1
			r >>= 1
		return res

def solve():
	n = ri()
	disks = []
	A = set()
	for i in range(n):
		(a, b, h) = rl()
		disks.append([b, a, h])
		A.add(a)
	disks.sort(reverse=True)
	AS = sorted(list(A))
	xref = {a: i for (i, a) in enumerate(AS)}

	def bi(b):
		return bisect.bisect_left(AS, b)
	T = segmentTree(n)
	for (b, a, h) in disks:
		prev = T.min(0, bi(b))
		local = h + prev
		T.update(xref[a], local)
	print(T.min(0, n))
mode = 's'
if mode == 'T':
	t = ri()
	for i in range(t):
		solve()
else:
	solve()


import sys
n = int(sys.stdin.readline())
valores = [sys.stdin.readline().strip().split(' ') for _ in range(n)]
tmp = [0] * n
stack = []
valores.sort(key=lambda x: (int(x[1]), int(x[0])), reverse=True)
for i in range(n):
	while len(stack) > 0 and int(valores[stack[-1]][0]) >= int(valores[i][1]):
		stack.pop()
	if len(stack) > 0:
		tmp[i] = tmp[stack[-1]] + int(valores[i][2])
	else:
		tmp[i] += int(valores[i][2])
	stack.append(i)
sys.stdout.write(str(max(tmp)) + '\n')


import os, sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	(a, b, h) = ([], [], [])
	for _ in range(n):
		(u1, v1, w1) = map(int, input().split())
		a.append(u1)
		b.append(v1)
		h.append(w1)
	rr = sorted(sorted(range(n), key=lambda yy: a[yy]), key=lambda xx: b[xx])
	(dp, st) = ([0] * n, [n] * n)
	for ind in range(n - 1, -1, -1):
		(i, y) = (rr[ind], ind + 1)
		while y != n and a[i] <= a[rr[y]]:
			y = st[y]
		st[ind] = y
	for ind in range(n - 1, -1, -1):
		(i, y) = (rr[ind], ind + 1)
		while y != n and b[i] <= a[rr[y]]:
			y = st[y]
		dp[ind] = h[i] + (0 if y == n else dp[y])
	print(max(dp))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()