Matrix Number Selection Game

You are given an \( n \times m \) matrix in which each element \( a_{i,j} \) is a non-negative integer. The game is played in \( m \) turns. At each turn, from every row you must remove exactly one element. However, in each row you are only allowed to take the element at the beginning (leftmost) or the end (rightmost) of that row.

Let the current turn be the \( i\text{-th} \) turn (where \( i \) starts from 1). The score obtained from a row at the \( i\text{-th} \) turn is defined as:

[ \text{score} = a \times 2^{i} ]

where \( a \) is the value of the element removed from that row. The total score of the game is the sum of the scores obtained from each row over all \( m \) turns. Your task is to determine the maximum total score possible by optimally choosing which element to remove from each row at every turn.

Note: Since the multiplier \( 2^{i} \) increases with each turn, you should plan to remove smaller numbers in the earlier turns, reserving larger numbers for later turns if possible. In each row, the removals are restricted by the rule that you can only remove the first or last element remaining.

inputFormat

The first line contains two integers \( n \) and \( m \) indicating the number of rows and columns of the matrix respectively. The following \( n \) lines each contain \( m \) non-negative integers, representing the matrix row by row.

outputFormat

Output a single integer representing the maximum total score that can be obtained by playing the game optimally.

sample

1 1
5

10