问题描述

有一个序列，题目用n个整数组合 [ai,bi,ci]来描述它，[ai，bi，ci]表示在该序列中处于[ai，bi]这个区间的整数至少有ci个。如果存在这样的序列，请求出满足题目要求的最短的序列长度是多少。如果不存在则输出 -1。

输入

第一行包括一个整数n，表示区间个数，以下n行每行描述这些区间，第i+1行三个整数ai，bi，ci，由空格隔开，其中n<=20,0<=ai<=bi<=50000 而且 1<=ci<=bi-ai+1。

输出

一行，输出满足要求的序列的长度的最小值。

输入样例intervals.in

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

输出样例intervals.out

6