#1068. Luke's Game

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: TosakaUCW

题目描述

宇宙大帝 Luke 和他的好友 鬼才 决定在星际旅行的途中来一场精彩的卡牌游戏对决。这场游戏与《七大奇迹》有几分相似,得分的方式之一是通过收集不同类型的天体卡牌来积累智慧能量。在这场宇宙卡牌游戏中,玩家可以收集三种不同的天体卡牌:恒星黑洞行星

每个玩家的得分公式为:

其中:

  • 表示恒星卡牌的数量,
  • 表示黑洞卡牌的数量,
  • 表示行星卡牌的数量。

然而,游戏还有一个特殊的通配卡牌,它可以作为三种天体卡牌中的任意一种。每个玩家可以根据他们拥有的通配卡牌,合理地分配它们来最大化自己的得分。

宇宙大帝 Luke 和 鬼才 都在努力计算最佳策略,他们想知道如何合理分配自己的通配卡牌来获得最大可能的分数。

输入格式

第一行包含一个整数 ),表示游戏中的玩家数量。

接下来的 行,每行包含四个整数 ),分别表示玩家获得的恒星卡牌、黑洞卡牌、行星卡牌和通配卡牌的数量。

输出格式

对于每个玩家,按输入顺序输出该玩家可能获得的最大分数。

样例

Input

3
1 1 4 1
5 1 4 1
1 9 1 9

Output

33
59
332