Soccer Tournament

Interview

Time limit1sMemory limit1024 MB

Summary

Select 11 players, exactly one goalkeeper and at least one each of striker, midfielder, and defender, to maximize the sum of their assigned preference scores.

Level: Medium5 of 10
Topics: Dynamic programming, Greedy
Solved: No attempts yet

Problem

Seollal is here, and Dohun's army unit is holding a soccer tournament. As the team's coach, Dohun must select $11$ players to join the team.

Each selected player must be registered at one of four positions: striker, midfielder, defender, or goalkeeper. Each position must have at least one player. However, exactly one goalkeeper must be selected.

Each applicant submitted preference scores $a_i$ , $b_i$ , $c_i$ , and $d_i$ for the striker, midfielder, defender, and goalkeeper positions. The team's satisfaction is the sum of the preference scores for the positions each player is assigned to. Using this information, Dohun wants to select players that satisfy the team rules and maximize the team's satisfaction. Find the maximum team satisfaction when exactly $11$ players are selected.

Input

The first line contains the number of soldiers $N$ .

The next $N$ lines are given such that line $i+1$ contains the striker, midfielder, defender, and goalkeeper preference scores $a_i$ , $b_i$ , $c_i$ , and $d_i$ of soldier $i$ , separated by spaces.

Output

Print the maximum team satisfaction when players are selected according to the team rules.

Constraints

$11 \le N \le 200\,000$
$1 \le a_i \le 10^8$
$1 \le b_i \le 10^8$
$1 \le c_i \le 10^8$
$1 \le d_i \le 10^8$
All input values are integers.

Examples1

Example 1

Input

Expected output