给定 n 个整数闭区间 [ai, bi] 和 n 个整数 c1, ..., cn。

编写一个程序：

读取区间数、它们的端点和整数 c1, ..., cn，

计算整数集 Z 的最小大小，该数集满足和区间 [ai , bi]至少有 ci 个公共元素( i = 1, 2, ..., n )

输出答案

输入

输入的第一行包含一个整数 n (1 <= n <= 50 000) - 表示整数区间数。

接下来 n 行描述n个整数区间，第 i+1 行包含三个空格隔开的整数 ai，bi和ci

数据范围：0 <= ai <= bi <= 50000 1 <= ci <= bi- ai + 1

数据处理到文件末尾。

输出