1211. 【CCF2017第四期NOI教师培训】吃苹果

1211. 【CCF2017第四期NOI教师培训】吃苹果

暂无测试数据。

题目描述

连小朋友都知道,呆毛王 Saber 喜欢吃苹果。

现在Saber有三箱苹果。
第一个箱子里有 n1n_1 个苹果,第二箱有 n2n_2 个,第三箱有 n3n_3 个。
Saber是个吃货,但也是个爱美的女生。

三箱苹果这样看起来更好看:

(1) 第一点就是每个箱子都不能空。

(2) 第二点就是苹果数量应该是递增的。
也就是说,
第一个箱子的苹果数少于第二个箱子,
第二箱的苹果少于第三箱。

(3) Saber今天有些饱,
所以想通过吃尽量少的苹果同时满足以上两个要求而使箱子看上去更美。
请你输出 Saber 吃掉的最少的苹果数量。

如果她无法完成心愿就输出 -1 吧。

输入

第一行,一个正整数 nGnG,表示数据的组数,nG5nG \leq 5
接下来 nGnG 行,
每行三个正整数,依次代表 n1n_1n2n_2n3n_3
其中 1n1,n2,n330001 \leq n_1,n_2,n_3 \leq 3000

输出

nGnG 行,每行一个整数,即题目要求的答案。

样例 1

输入

1
15 40 22

输出

19

样例 2

输入

2
1 3 1
1 1234 30000

输出

-1
0

数据范围限制

1n1,n2,n330001 \leq n_1,n_2,n_3 \leq 3000

信息

ID
1210
难度
(无)
分类
(无)
标签
(无)
递交数
0
已通过
0
通过率
?
上传者