二次元 dp 応用 Objective-C編（paizaランク S 相当）

N 個のマスが横一列にならんでいます。
左から i 番目のマスをマス i とします。
あるマス i から右向きに 1 マス移動するとマス i+1 に、左向きに 1 マス移動するとマス i-1 に移動します。

あなたは最初マス 1 から右向きに移動を開始します。
あなたは以下の 2 種類の操作を、任意の順番で任意の回数だけ行うことができます。
ただし、すべての操作を終えた後、すべてのマスで必ず 1 度ポイントを取得していなければなりません。

操作 1 : いまの進行方向に 1 マス移動する。ただし、マスの外 (マス 0, マス N+1) にでるような操作を行うことはできない。
操作 2 : 進行方向が右向きのときのみこの操作を行える。いまいるマス i で一度もポイントを獲得していなければ、A_i ポイントを獲得する。その後、進行方向を左向きにする。
操作 3 : 進行方向が左向きのときのみこの操作を行える。いまいるマス i で一度もポイントを獲得していなければ、B_i ポイントを獲得する。その後、進行方向を右向きにする。
操作 4 : 進行方向が右向きのときのみこの操作を行える。いまいるマス i で一度もポイントを獲得していなければ、C_i ポイントを獲得する。進行方向の変更はない。
操作 5 : 進行方向が左向きのときのみこの操作を行える。いまいるマス i で一度もポイントを獲得していなければ、D_i ポイントを獲得する。進行方向の変更はない。

すべての操作後、得られるポイントの総和の最大値を求めてください。

入力例 1 では、例えば以下のように行動できます。
・最初進行方向は右でマス 1 にいる。操作 4 を行う。2 ポイント獲得する。
・操作 1 を 3 回行い、マス 4 に移動する。
・操作 2 を行う。7 ポイント獲得し、進行方向を左向きに変更する。
・操作 1 を 1 回行い、マス 3 に移動する。
・操作 5 を行う。10 ポイント獲得する。
・操作 1 を 1 回行い、マス 2 に移動する。
・操作 3 を行う。8 ポイント獲得し、進行方向を右向きに変更する。
このように行動したとき、獲得したポイントの総和は 27 です。
28 ポイント以上獲得できる行動方法は存在しないため、27 を出力します。