Under construction

Still being built. Things may change

⚾

Time limit1sMemory limit512 MB

Summary
Given each of 9 players' predetermined results over N innings, choose a batting order with player 1 batting 4th to maximize total runs scored.
Level

Medium5 of 10

Topics
Brute force, Simulation, Backtracking, Implementation
Solved
No attempts yet

Problem

⚾ is a game played by two teams of 9 players each, taking turns on offense and defense. One inning consists of an offense and a defense, and the game runs for a total of N innings. When 3 outs occur in an inning, the inning ends and the two teams switch between offense and defense.

Before the game starts, each team must decide its batting order (the order in which batters come to the plate), and the order cannot be changed during the game. If the 9th batter has batted and 3 outs have not occurred, the inning does not end and the 1st batter comes to the plate again. The batting order must be maintained even when the inning changes. For example, if the 6th batter was the last batter in the 2nd inning, the 3rd inning starts with the 7th batter at the plate.

On offense, the batter at the plate hits the ball thrown by the pitcher. When a player on the offensive team passes first, second, and third base and reaches home, the team scores 1 point. A batter who does not reach home may remain on one of first, second, or third base. A player on a base is called a runner. There are no runners at the start of an inning.

The possible outcomes when a batter hits the ball are a single, a double, a triple, a home run, or an out. When each occurs, the following happens.

  • Single: the batter and all runners advance one base.
  • Double: the batter and all runners advance two bases.
  • Triple: the batter and all runners advance three bases.
  • Home run: the batter and all runners advance to home.
  • Out: no runner advances, and the offensive team's out count increases by one.

The manager of a baseball team, Ainta, is trying to decide the batting order. Ainta's team has 9 players, numbered 1 through 9. Ainta has already decided that player 1, his favorite player, will be the 4th batter. Now he must decide the batting order for all the other players. Ainta knows in advance what result each player will get in each inning. Find the batting order that scores the most points, and compute the score for that order.

Input

The first line gives the number of innings N (2 ≤ N ≤ 50). From the second line, N lines give the results each player gets in each inning, in order from inning 1 to inning N. The results for an inning are 9 integers separated by spaces. The integer for each result means the following.

  • Single: 1
  • Double: 2
  • Triple: 3
  • Home run: 4
  • Out: 0

In each inning, at least one batter records an out.

Output

Print the maximum number of points Ainta's team can score.

Examples5

  1. Example 1

    Input
    2
4 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0
    Expected output
    1

  2. Example 2

    Input
    2
4 0 0 0 1 1 1 0 0
0 0 0 0 0 0 0 0 0
    Expected output
    4

  3. Example 3

    Input
    2
0 4 4 4 4 4 4 4 4
0 4 4 4 4 4 4 4 4
    Expected output
    43

  4. Example 4

    Input
    2
4 3 2 1 0 4 3 2 1
1 2 3 4 1 2 3 4 0
    Expected output
    46

  5. Example 5

    Input
    9
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
    Expected output
    216