6297번 - Intervals 다국어

문제

You are given n closed, integer intervals [a_i, b_i] and n integers c₁, ..., c_n.

Write a program that:

• reads the number of intervals, their end points and integers c₁, ..., c_n from the standard input,
• computes the minimal size of a set Z of integers which has at least ci common elements with interval [a_i, b_i], for each i=1,2,...,n,
• writes the answer to the standard output.

입력

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 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.

출력

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.

제한

힌트