二次元 dp 応用 1 D(Beta)編（paizaランク A 相当）

N 個のマスが横 1 列に並べられています。
各マスの表と裏には数字が書かれており、左から i 番目のマスの表には整数 A_i、裏には整数 B_i が書かれています。
いまからあなたは各時刻 t = 1, 2, ... N + K - 1 に以下のいずれかの操作を選び、行動します。

・操作 1：右に 1 マス進む。
・操作 2：いまいるマスを裏返す。

ただし、時刻 N + K - 1 までに、操作 1 は N-1 回だけ、操作 2 は K 回だけ行う必要があります。
同じマスで複数回操作 2 を行ってもよいです。
時刻 t = 0.5, 1.5, 2.5, ... , N + K - 1 + 0.5 では、いまいるマスの表に書かれている整数だけポイントが加算されます。
最初時刻 t = 0 にあなたはマス 1 にいます。
適切に行動したとき、時刻 N + K までに得られるポイントの合計の最大値を求めてください。

入力例 1 では、例えば以下のように行動できます。
・時刻 t = 0.5 では、マス 1 におり表の数字は 1 であるため 1 ポイント獲得する。
・時刻 t = 1 では、操作 1 を選びマス 2 に移動する。
・時刻 t = 1.5 では、マス 2 におり表の数字は 2 であるため 2 ポイント獲得する。
・時刻 t = 2 では、操作 2 を選びマス 2 を裏返す。この操作により、マス 2 の表に書かれた数字は 5、裏に書かれた数字は 2 になる。
・時刻 t = 2.5 では、マス 2 におり表の数字は 5 であるため 5 ポイント獲得する。
・時刻 t = 3 では、操作 1 を選びます 3 に移動する。
・時刻 t = 3.5 では、マス 3 におり表の数字は 3 であるため 3 ポイント獲得する。
・時刻 t = 4 では、操作 2 を選びマス 3 を裏返す。この操作により、マス 3 の表に書かれた数字は 4、裏に書かれた数字は 3 になる。
・時刻 t = 4.5 では、マス 3 におり表の数字は 4 であるため 4 ポイント獲得する。
この行動では操作 1 を 2 回、操作 2 を 2 回行っており、時刻 5 までに 15 ポイント獲得することができました。
どのように行動しても時刻 5 までに 16 ポイント以上獲得することはできないので、15 を出力します。