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

Problem

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

Output

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.

Sample Input

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

6