買うすべての商品の集合を固定し、その番号を昇順に \(B_1, B_2, \ldots, B_K\) とします。このとき、これら \(K\) 個の商品を買う順番をうまく決めることで、これらをすべて買う合計費用を最小でいくらにできるかを考えます。

商品 \(B_i\) を買うとき、すでに \(B_1, B_2, \ldots, B_{i-1}\) の中から \(x\) 個の商品を買っていたとすると、 その時点で商品 \(B_i\) は「現在売れ残っている商品のうち番号が \(B_i-x\) 番目に小さい商品」であるので、商品 \(B_i\) の購入費用は \(A_{B_i} + C_{B_i-x}\) 円です。 \(x\) としては \(0\) 以上 \(i-1\) 以下の整数があり得るので、商品 \(B_i\) を買う費用は

\[A_{B_i} + \mathrm{cost}(B_i, i-1) \tag{1}\]

以上です（ただし、\(\mathrm{cost}(i, j) \coloneqq \min\lbrace C_{i-j}, \ldots, C_{i-2}, C_{i-1}, C_{i}\rbrace\) ）。

よって、商品 \(B_1, B_2, \ldots, B_K\) をすべて買う費用の下界として

\[\sum_{i = 1}^K (A_{B_i} + \mathrm{cost}(B_i, i-1)) \tag{2}\]

が得られます。実は、この下界は達成可能です。 実際、「現時点での購入費用がその下界 (1) を達成している商品」の中で番号が最大のものを買うという行動を繰り返すことで達成できます。

したがって本問題は、買う商品の集合 \(B_1, B_2, \ldots, B_K\) を高橋君が欲しい商品をすべて含むように選ぶときの、式 (2) の値を最小化する問題に帰着できます。

そこで、\(i = 1, 2, \ldots, N\) の順に、「商品 \(i\) を買うかどうか」を決定していくことにします。 このとき、商品 \(i\) を買うことにするたび、商品 \(1, 2, \ldots, i-1\) のうち買うことにした商品の個数を \(j\) として、\(A_i + \mathrm{cost}(i, j)\) 円の費用が追加で発生することが確定します。 これを踏まえて、動的計画法で解きます。具体的には、

\(\mathrm{dp}[i][j] = \) （商品 \(i\) までは買うかどうかをすでに決定しており、そのうち買うことにした商品の個数が \(j\) であるときの、それまでに確定した合計費用としてあり得る最小値）

とおき、各 \(i, j\) について、

• 商品 \((i+1)\) を買う場合に対応して、\(\mathrm{dp}[i+1][j+1] \leftarrow \min\lbrace \mathrm{dp}[i+1][j+1], \mathrm{dp}[i][j] + A_{i+1} + \mathrm{cost}(i+1, j) \rbrace\)
• 商品 \((i+1)\) を買わない場合に対応して、\(\mathrm{dp}[i+1][j] \leftarrow \min\lbrace \mathrm{dp}[i+1][j], \mathrm{dp}[i][j] \rbrace\)

という遷移を行います。ただし、商品 \((i+1)\) が欲しい商品である場合は、必ず買わなければならないため後者の遷移は行いません。

\(\mathrm{cost}(i, j) = \min\lbrace \mathrm{cost}(i, j-1), C_{i-j} \rbrace\) の関係を使って、必要な \(\mathrm{cost}(\cdot, \cdot)\) の値全体を \(O(N^2)\) 時間で前計算しておくことで、本問題全体を \(O(N^2)\) 時間で解くことができます。