High Score

Time limit2sMemory limit512 MB

Summary

Given counts of Cog, Tablet, Compass, and Wildcard tokens, assign each Wildcard to one type to maximize a^2+b^2+c^2+7*min(a,b,c).

Level: Medium5 of 10
Topics: Greedy, Math, Brute force
Solved: No attempts yet

Problem

Mårten and Simon enjoy the board game Seven Wonders and have just finished a match. It is time to tally the scores.

One way to score in Seven Wonders is Science. During the game, each player collects Science tokens of three types: Cog, Tablet, and Compass. A player with $a$ Cogs, $b$ Tablets, and $c$ Compasses scores $a^2 + b^2 + c^2 + 7 \times \min(a, b, c)$ points.

Wildcard Science tokens complicate the count. Each Wildcard Science token a player holds may be counted as any one of the three ordinary types. For instance, a player with 2 Cogs, 1 Tablet, 2 Compasses, and 1 Wildcard Science token can end up with $(3, 1, 2)$ , $(2, 2, 2)$ , or $(2, 1, 3)$ Cogs, Tablets, and Compasses. The possible scores are $3^2 + 1^2 + 2^2 + 7 \times 1 = 21$ , $2^2 + 2^2 + 2^2 + 7 \times 2 = 26$ , and $2^2 + 1^2 + 3^2 + 7 \times 1 = 21$ , so the maximum score for this player is 26.

Given the number of tokens each player holds, compute the maximum score each player can reach by assigning the Wildcard Science tokens optimally.

Input

The first line contains an integer $n$ ( $3 \le n \le 7$ ), the number of players in the game.

Each of the next $n$ lines contains four integers $a$ , $b$ , $c$ , $d$ ( $0 \le a, b, c, d \le 10^9$ ): the number of Cog, Tablet, Compass, and Wildcard Science tokens of one player.

Output

For each player, in input order, print the maximum score that player can get, one per line.

Examples2

Example 1
Input
```
3
2 1 2 1
3 2 1 0
1 3 0 1
```
Expected output
```
26
21
18
```
Example 2
Input
```
3
0 0 0 0
0 0 0 1
0 0 0 3
```
Expected output
```
0
1
10
```