P1005 [NOIP 2007 上級組] 行列から数を取るゲーム
問題文
シュアイシュアイはよくクラスメートと「行列から数を取るゲーム」を遊びます。
与えられた \(n \times m\) の行列において、各要素 \(a_{i,j}\) は非負整数です。
ゲームのルールは次の通りです：
- 各ターンで各行からちょうど \(1\) つの要素を取り、合計で \(n\) 個の要素を取る。\(m\) ターンの後、行列内の全要素を取り終える；
- 各行で取る要素は、その行の先頭または末尾の要素に限られる；
- 各ターンには得点があり、それは各行の得点の合計である。各行の得点は「取った要素の値 \(\times 2^i\)」で定義される。ただし \(i\) はターン番号（\(1\) から始まる）である；
- ゲーム終了後の総得点は \(m\) ターンの得点の総和である。
シュアイシュアイは、任意の行列に対して最大得点を計算するプログラムを書いてほしいと考えています。
入力形式
入力は \(n+1\) 行からなる：
- 最初の行には、空白で区切られた \(n\) と \(m\) の \(2\) つの整数が与えられる。
- 続く \(n\) 行には、各行に \(m\) 個の非負整数が与えられ、\(n \times m\) の行列を表す。
出力形式
出力は \(1\) 行で、最大得点を表す整数を出力せよ。
入出力例 #1
説明／ヒント
【データ範囲】
- \(60\%\) のデータについては、\(1 \le n,m \le 30\) であり、答えは \(10^{16}\) を超えない。
- \(100\%\) のデータについては、\(1 \le n,m \le 80\), \(0 \le a_{i,j} \le 1000\)。
【出典】
NOIP 2007 上級組 第 \(3\) 問。