题目描述

原题来自：Southwestern Europe 2002，题面可参考 POJ 1201。

给定 \(n\) 个闭区间 \([a_i,b_i]\) 和 \(n\) 个整数 \(c_i\)。你需要构造一个整数集合 \(Z\)，使得对于任意 \(i\in [1,n]\)，\(Z\) 中满足 \(a_i\le x\le b_i\) 的整数 \(x\) 不少于 \(c_i\) 个，求这样的整数集合 \(Z\) 最少包含多少个数。

简而言之就是，从 \(0\sim 5\times 10^4\) 中选出尽量少的整数，使每个区间 \([a_i,b_i]\) 内都有至少 \(c_i\) 个数被选出。

输入格式

第一行一个整数 \(n\)，表示区间个数；

以下 \(n\) 行每行描述这些区间，第 \(i+1\) 行三个整数 \(a_i,b_i,c_i\)，由空格隔开。

输出格式

一行，输出满足要求的序列最少整数个数。

样例数据

输入样例

5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1

输出样例

6

限制与提示

对于全部数据，\(1\le n\le 5\times 10^4,0\le a_i\le b_i\le 5\times 10^4,1\le c_i\le b_i-a_i+1\)。