兔子的兴奋度 描述

Dima有n只兔子，她把这n只兔子排成一排，编号从1到n，她给这些兔子喂食玉米。Dima发现每只兔子在吃玉米时，会有一个兴奋度，而且它的兴奋度在下列三种情况下是有所变化的：当它旁边两只兔子都饥饿时、当它旁边有一只兔子饥饿时（即有一只兔子已经吃过了）、当它旁边两只兔子都已经吃过时。现在Dima想知道她只给每只兔子喂食一次，所有兔子兴奋度之和的最大值。

输入 第一行为正整数t(≤5)，表示数据组数；每组数据中，第一行为正整数n(≤3000)，表示兔子总数，然后是三行整数ai,bi,ci，分别表示第i只兔子上述三种情况下的兴奋度，0≤ai,bi,ci≤10000。

输出 对于每组数据，输出所有兔子兴奋度之和的最大值。

输入样例 1

3 4 1 2 3 4 4 3 2 1 0 1 1 0 7 8 5 7 6 1 8 9 2 7 9 5 4 3 1 2 3 3 4 1 1 3 3 1 1 1 1 2 1 1 1 1 输出样例 1

13 44 4 提示