Intervals

Intervals

Description

给定n 个闭区间(形如[Ai,Bi],Ai,Bi都为整数)和n个整数Ci(1<=i<=n)。你需要构造一个整数集合Z,使得对于任意i∈[1,n],Z中满足ai<=x<=bi的整数x不少于Ci个,求这样的整数集合Z最少包含多少个数。

Format

Input

第一行包括一个整数n(1<=n<=50000),表示区间数。以下的n行依次描述区间。
第i+1行三个整数 Ai,Bi,Ci,由空格隔开,其中0<=Ai<=Bi<=50 000;而且1<=Ci<=Bi-Ai+1。

Output

输出仅一行,包括一个整数,表示集合中最少的公共元素的个数。

Sample 1

Input

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

Output

6

Limitation

1s, 64MiB for each test case.

Source

Poj1201,TYVJ1415