操作の結果に対応する数列として次のような数列 \(B=(b_1,\ldots,b_N)\) を考えます。

• \(i=1,2,\ldots,N\) に対し、最終的に \(a_i\) が削除されるならば \(b_i=0\) 、そうでなければ \(b_i=1\)

\(A\) の総和が \(x\) に等しいという事は、\(\sum a_ib_i\) が \(x\) に等しいということです。よって、この条件を満たす \(B\) に対する必要な操作の回数の最小値が求められれば良いです。

ある \(B\) に対する必要な操作回数の最小値は、\(0\) が連続する極大な区間の個数に等しいです。たとえば \(B=(1,0,0,1,0,1,1,0,0,0)\) の場合、\(0\) が連続する極大な区間は \(B[2,3], B[5,5],B[8,10]\) の \(3\) 個なので必要な操作回数の最小値は \(3\) です。(\(B[x,y]\) は \(b_x,\ldots,b_y\) を表します)
また、\(0\) が連続する極大な区間の個数は、以下の条件のうち一方を満たす \(i\) の個数に等しいです。

• \(i=1\) かつ \(b_i=0\)
• \(i \geq 2\) かつ \(b_{i-1}=1, b_i=0\)

以上から、\(\mathrm{dp}[i][j][k]\) を「\(a_1b_1 + a_2 b_2 + \ldots + a_i b_i = j\) かつ \(b_i=k\) の時の操作回数の最小値」とする動的計画法を行うことで答えを求められます。時間計算量は \(\mathrm{O}(NM)\) です。

なお、\(b_0=1\) とすることで上記の場合分けを避けることが出来ます。