INTERVAL  Intervals
You are given n closed integer intervals [a_{i}, b_{i}] and n integers c_{1}, ..., c_{n}.
Task
Write a program that:
 reads the number of intervals, their endpoints and integers c_{1}, ..., c_{n} from the standard input,
 computes the minimal size of a set Z of integers which has at least c_{i} common elements with interval [a_{i}, b_{i}], for each i = 1, 2, ..., n,
 writes the answer to the standard output.
Input
The input begins with the integer t, the number of test cases. Then t test cases follow.
For each test case the first line of the input contains an integer n (1 <= n <= 50000)  the number of intervals. The following n lines describe the intervals. Line (i+1) of the input contains three integers a_{i}, b_{i} and c_{i} separated by single spaces and such that 0 < = a_{i} < = b_{i} <= 50000 and 1 < = c_{i} < = b_{i} a_{i} +1.
Output
For each test case the output contains exactly one integer equal to the minimal size of set Z sharing at least c_{i} elements with interval [a_{i}, b_{i}], for each i= 1, 2, ..., n.
Example
Sample input: 1 5 3 7 3 8 10 3 6 8 1 1 3 1 10 11 1 Sample output: 6Warning: enormous Input/Output data, be careful with certain languages
hide comments
Hussain Kara Fallah:
20140415 08:47:33
see QUEST5 before solving this :D 

giorgi:
20131105 20:24:30
<deleted> Last edit: 20131108 12:00:30 

J:
20101229 16:23:47
Maybe it needs lot of optimization. Mine gives TLE. 

Moshiur Rahman:
20090615 09:11:42


Gautam Verma:
20090411 06:43:48
Better if the test case has been explained. 
Added by:  adrian 
Date:  20040707 
Time limit:  1.604s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  ACM Central European Programming Contest, Warsaw 2002 