Suppose that you are going to play a hopscotch game. In the hopscotch game, the land consists of "N" rows and 4 columns where the score is written on each space. As you are moving down the rows one by one, stepping on the spaces, you should only touch 1 space among the 4 spaces in the row. However, in this hopscotch game, there is a special rule that the spaces on the same column cannot be touched consecutively.

For example, assume that the land is given as follows.

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |

After touching the fourth space (5) in the first row, you cannot touch the fourth space (8) in the second row.

Write a function "solution" to return the maximum score that you can win after moving to the last row. In the above example, by touching the fourth space at row 1 (5), second space at row 2 (7) and first space at row 3 (4), you can get the maximum score of 16. Hence, return 16.

  • The number of rows "N" : natural number less than 100,000.
  • The number of columns is 4 and the land is given in a 2-dimensional array.
  • Score : natural number less than 100.
land answer
[[1,2,3,5],[5,6,7,8],[4,3,2,1]] 16

Example #1
It is the same as the example in the problem statement.

Result Stop
Result of [Run] or [Submit] will be displayed here