最初にスコア \(\sum A\) を獲得したうえで， \(i\to i+2\) に跳ぶときスコア \(A_{i+1}\) を失うものとして考えます．このとき失うスコアの集合は以下の条件を満たしていればよいです．

• \(A_1,A_N\) を選んではならない．
• \(i(1\le i<N)\) に対し， \(A_i\) と \(A_{i+1}\) をともに選んではならない．

このことは簡単に証明できます．いま， \(f(l,r,x,y,k)\) を以下のように定義します．

• \(A_l,A_{l+1}\dots,A_r\) の中から上記の条件を満たすように失うスコアを \(k\) 個選ぶときの総和の最小値．ただし， \(x=1\) のとき \(A_l\) を， \(y=1\) のとき \(A_r\) を選んではならない．

このとき答えは \(\sum A-f(1,N,1,1,K)\) と表されます．

\(l=r\) の場合は簡単に計算できます． \(l<r\) のとき \(m=\lfloor(l+r)/2\rfloor\) とすると， \(A_l,A_{l+1},\dots,A_m\) および \(A_{m+1},A_{m+2},\dots,A_r\) を選んだあと， \(A_m,A_{m+1}\) に関する隣接条件より，「\(A_m\) を選ばない」「\(A_{m+1}\) を選ばない」のいずれかを満たしていればよいことがわかります．よって， \(f(l,r,x,y,k)\) は \(f(l,m,x,z,i)\) と \(f(m+1,r,1-z,y,k-i)\) によって求められます．

\(f\) は \(k\) に関して凸であることが示せるので， \(f(l,r,*,*,*)\) をまとめて min-plus convolution を使って求めることができます．

計算量は \(O(N\log N)\) です．