Consider the following sequence \(B=(b_1,\ldots,b_N)\) corresponding to the result of the operations:

• \(b_i=0\) if \(a_i\) is removed if \(b_i=0\), and \(b_i=1\) otherwise, for \(i=1,2,\ldots,N\)

The sum of \(A\) is \(x\) if and only if \(\sum a_ib_i\) equals \(x\). Thus, it is sufficient to find the minimum number of operations to obtain such \(B\).

The minimum number of operations required to obtain a \(B\) is equal to the number of maximal segments consisting of consecutive \(0\)s. For example, \(B=(1,0,0,1,0,1,1,0,0,0)\), the maximal segments consisting of consecutive \(0\)s are \(B[2,3], B[5,5]\), and \(B[8,10]\), so the minimum number of operations required is \(3\). (\(B[x,y]\) denotes \(b_x,\ldots,b_y\).)
Moreover, the number of maximal segments consisting of consecutive \(0\)s is equal to the number of \(i\)’s satisfying one of the following conditions:

• \(i=1\) and \(b_i=0\);
• \(i \geq 2\) and \(b_{i-1}=1, b_i=0\).

Therefore, the answer can be found by a Dynamic Programming (DP) where \(\mathrm{dp}[i][j][k]\) is “the minimum number of operations required to make \(a_1b_1 + a_2 b_2 + \ldots + a_i b_i = j\) and \(b_i=k\).” The time complexity is \(\mathrm{O}(NM)\).

By letting \(b_0=1\), the case division above can be avoided.