INTERVAL - Intervals

有 $n$ 个区间，在区间 $[a_i,b_i]$ 中至少取任意互不相同的 $c_i$ 个整数。求在满足 $n$ 个区间的情况下，至少要取多少个正整数。 ### 输入格式 **本题有多组数据**。 第一行的一个整数 $T$ 表示数据个数。 对于每组数据： 第一行包含一个整数 $n(1\leq n\leq 50000)$ 表示区间数。 以下 $n$ 行描述区间。 输入的第 $i+1$ 行包含三个整数 $a_i,b_i,c_i$，由空格分开。其中 $0\leq a_i\leq b_i\leq 50000，1\leq c_i\leq b_i-a_i+1$。 ### 输出格式 对于每组数据，输出一个对于 $n$ 个区间 $[a_i,b_i]$ 至少取 $c_i$ 个不同整数的数的总个数。 ### 样例 input： ``` 1 5 3 7 3 8 10 3 6 8 1 1 3 1 10 11 1 ``` output： ``` 6 ``` ### 样例解释 可以取 $3,4,5,8,9,10$，为符合条件且取数个数最少的一组解。

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.

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.

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.

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

6