INTERVAL - Intervals

no tags 

You are given n closed integer intervals [ai, bi] and n integers c1, ..., cn.

Task

Write a program that:

  • reads the number of intervals, their endpoints 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 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 ai, bi and ci separated by single spaces and such that 0 < = ai < = bi <= 50000 and 1 < = ci < = bi -ai +1.

Output

For each test case 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.

Example

Sample input:
1
5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1

Sample output:
6
Warning: enormous Input/Output data, be careful with certain languages

hide comments
Hussain Kara Fallah: 2014-04-15 08:47:33

see QUEST5 before solving this :D

giorgi: 2013-11-05 20:24:30

<deleted>

Last edit: 2013-11-08 12:00:30
J: 2010-12-29 16:23:47

Maybe it needs lot of optimization. Mine gives TLE.

Moshiur Rahman: 2009-06-15 09:11:42


Explanation of the sample input:
A possible minimal set you can construct is: 3 6 7 8 9 10

Last edit: 2009-06-15 10:23:22
Gautam Verma: 2009-04-11 06:43:48

Better if the test case has been explained.


Added by:adrian
Date:2004-07-07
Time limit:1.604s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:ACM Central European Programming Contest, Warsaw 2002