盖房子

Time Limit: 1000MS

Memory Limit: 65535KB

Description

手机上的都市摩天楼的游戏大家想必都玩过,当年曾经让snow和xiaoyoulei课上课下玩了很多天,一直想找到个最优的建筑方案,于是想到了用程序去解决。

为了让题目更简单,我们简化了游戏,游戏规则如下:

地图是一个4*4的矩形,每格最多摆一个房子

格子相邻指有条边是公共的

有3种房子,蓝房子,红房子,绿房子

每种房子有个固定的价值

蓝房子随便摆,红房子只能摆在有蓝房子相邻的格子上,绿房子只能摆在有蓝房子和红房子相邻的格子上,该格子上原来的房子可以被拆掉。

如果知道了每种房子的价值,snow想知道价值最大是多少。

Input

第一行是Case数

对于每个case

3个整数,vb,vr,vg,代表蓝房子,红房子,绿房子的价值。0< vb,vr,vg <1000

Output

返回最大的价值

Sample Input

2
1 1 1
1 2 1

Sample Output

16
31

Hint

None

Source

沈宇亮

提交代码