问题 26777 --Get the Points

26777: Get the Points

时间限制: 20 Sec  内存限制: 128 MB
提交: 5  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

Fat Brother and Maze are fans of amusement parks. They always go there on the weekend and play different kind of games. This weekend they found a challenging one, a target shooting game. There are N targets place along a straight line from left to right with number from 1 to n. For the ith target, Fat Brother can get three possible points when he shoots this target: ai, if there are no neighbor targets chosen; bi, if one neighbor targets chosen; ci, if both neighbor targets chosen.

Now Fat Brother wants to know how to choose the targets to make the points he get be as much as possible. You can assume that Fat Brother is good at shooting when he is playing together with Maze, he can shoot any target as he wish.

Note that Fat Brother can choose arbitrarily number of targets to shoot.

输入

The first line of the date is an integer T (1 <= T <= 100), which is the number of the text cases.

Then T cases follow, each contains an integer N (1 <= N <= 100000) which descript above.

Then N lines follow, each with three integer ai, bi and ci (0 <= ai, bi, ci <= 100) which descript above.

输出

For each case, output the case number first, then output the maximum number of points Fat Brother can gets.

See the sample input and output for more details.

 

样例输入

3
1
3 0 0
1
1 2 3
2
1 2 3
1 2 3

样例输出

Case 1: 3
Case 2: 1
Case 3: 4

来源

 

[提交][状态]