Home Web Board ProblemSet Standing Status Statistics
1.该OJ由于交换空间受限,暂不不支持万能头文件:bits/stdc++.h!!! 2.该OJ如果是长整型的话,C的输入输出请使用%lld!!!
Problem I: Intervals

Problem I: Intervals

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 41  Solved: 12
[Submit][Status][Web Board]

Description

Chengdu Neusoft University, founded and organized by Neusoft Holdings, is one of the full-time undergraduate institutions approved by the Ministry of Education. CNU runs its education programs with a main focus on engineering and a minor in management and arts. Besides, CNU is also the State Cultivation Base of IT Talents, China Torch Program Chengdu Digital Entertainment Industry (Talent Training) Park and China Digital Media Industry (Talent Training) Park.
CNU is located in the World Cultural Heritage—scenic spot of Dujiangyan and Qingcheng Mountain, Chengdu, and covers an area of nearly 400 thousand square meters with a floor area of 190 thousand square meters. Currently, more than 10,000 students are studying in our university. With the perfect combination of science and technology, nature and culture, the campus in the style of western Sichuan garden provides a good learning environment for students at home and abroad.
In order to give the most advanced modern IT education for students, CNU integrated educational resources of Neusoft Corporation, nationwide-distributed Neusoft Parks with the cooperative business partners at home and abroad and adopted an internationalized teaching mode. Besides, CNU has already built academic exchange and cooperation and started educational programs with numerous famous colleges in United States, Britain and Japan, etc. Now CNU also has established educational cooperation with notable multinational IT Corporations such as IBM, SUN, SKILLSOFT, BEA, SAP, HP, Cisco, Toshiba and Panasonic, etc.

You are given n closed, integer intervals [ai, bi] and n integers c1, ..., cn. 
Write a program that: 
reads the number of intervals, their end points and integers c1, ..., cn from the standard input, 
computes the minimal size of a set Z of integers which has at least ci common elements with interval [ai, bi], for each i=1,2,...,n, 

writes the answer to the standard output. 

Input

The first line of the input contains an integer n (1 <= n <= 50000) -- the number of intervals. The following n lines describe the intervals. The (i+1)-th line of the input contains three integers ai, bi and ci separated by single spaces and such that 0 <= ai <= bi <= 50000 and 1 <= ci <= bi - ai+1.

Output

The output contains exactly one integer equal to the minimal size of set Z sharing at least ci elements with interval [ai, bi], for each i=1,2,...,n.

Sample Input

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

Sample Output

6

HINT

[Submit][Status][Web Board]