Description

　　有一个整数序列，我们不知道她的长度是多少（即序列中整数的个数），但我们知道在某些区间中至少有多少个整数，用区间 [ai,bi,ci]来描述它，[ai，bi，ci]表示在该序列中处于[ai，bi]这个区间的整数至少有ci个。现在给出若干个这样的区间，请你求出满足条件的最短序列长度是多少。如果不存在则输出 -1。

Format

Input

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

Output

文件输出只有一个整数表示满足要求序列长度的最小值。

Sample 1

Input

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

Output

6

Limitation

1s, 128MiB for each test case.