Let \(L\) be the maximum “coordinate” \((=2 \times 10^5)\). Additionally, let \(g_x\) (\(0 \leq x \leq L\)) be \(\sum |B_i-x| - \sum |A_i-x|\). Our objective is to change \(A\) so that \(g_x \geq 0\) for every \(x\).

First, assume we start by making \(A_i=0\). We can now do the following:

• Increment \(A_i\) by \(1\). The cost of this action is \(C_i \times (2 \times (cur-org) +1)\), where \(org\) is the original value of \(A_i\) given as input, and \(cur\) is the current value of \(A_i\).

Let \(D_{i,x}\) be the cost of incrementing \(A_i\) when \(A_i=x\).

When an element \(A_i\) changes from \(x\) to \(x+1\), \(g_0,g_1,\cdots,g_x\) decrease by \(1\) and \(g_{x+1},\cdots,g_L\) increase by \(1\). Here, we can rephrase the problem into the following:

• Make every element in \(g\) at least \(0\) by repeating the following operation, with the minimum possible total cost.
• Operation: Choose \(i\) and \(x\). You can choose the same pair \((i,x)\) only once. Then, pay the cost of \(D_{i,x}\), decrease \(g_0,g_1,\cdots,g_x\) by \(1\) and increase \(g_{x+1},\cdots,g_L\) by \(1\).

Originally, we are restricted to choose \((i,x-1)\) before choosing \((i,x)\). However, from the value of the cost and the way \(g_x\) changes, we can see that ignoring that restriction does not change the answer.

Let us solve the problem above. First, the total number of operations will be \(\sum B_i\). Let \(f(x)\) be the number of times \((i,x)\) is chosen for some \(i\). Using \(f(x)\), we can rephrase the objective of making all of \(g_x\) non-negative. By noting that the total number of operations is fixed, we can rephrase the objective into the following, using some integer sequence \(E_x\):

• For every \(x\), \(\sum_{p=x}^L f(p) \leq E_x\).

This leads to a solution that works in polynomial time. Specifically, we let \(S\) be a multiset of integers and do the following operations in descending order of \(x\):

• For every \(i\), add \(D_{i,x}\) to \(S\).
• Among the elements in \(S\), keep the smallest \(E_x\) and delete the rest.

It is too slow to do these operations naively, so let us maintain \(S\) as follows:

• We keep an integer \(t\) and an integer array \(offset\), where:
• \(S\) contains no elements greater than or equal to \(t\), and
• \(S\) contains \(offset[v]+getcnt(v,x)\) instances of \(v\) for a value \(v\) less than \(t\), where \(getcnt(v,x)\) is the number of pairs \((i,p)\) satisfying \(D_{i,p}=v\).

Then, in the change \(x+1 \rightarrow x\), we should do the following operations:

• Let \(E'_x=E_x-E_{x+1}\).
• Let \(V\) be the number of indices \(i\) satisfying \(D_{i,x}<t\).
• If \(V>E'_x\), decrease \(t\) one by one to look for the position where the size of \(S\) is exactly \(E_x\).
• If \(V<E'_x\), increase \(t\) one by one to look for the position where the size of \(S\) is exactly \(E_x\).

Let us evaluate the time complexity of this algorithm. The bottleneck is the part where we change \(t\).

First, let us consider the amount of time we need each time we increase or decrease \(t\) by one. It turns out that we can do it in \(O(K)\) time, where \(K=max(C_i)\). For example, computing \(getcnt\) once takes \(O(K)\) time. (In precomputation, we should classify the elements according to the value of \(C_i\) and find the prefix sums.) We can also do the other operations in \(O(K)\) time.

Finally, we will show that the total number of times \(t\) increases or decreases is \(O(LK)\).

Let \(F_x\) be the \((E'_x)\)-th smallest number among \(D_{1,x}, D_{2,x}, \cdots, D_{N,x}\). Let us consider \(E'_x\) first. We can see that this is the number of indices \(i\) such that \(x<B_i\). Particularly, we have \(E'_x \leq N\) and \(E'_x \leq E_{x-1}\). Then, let us show that \(\sum_{x=L}^1 |F_x-F_{x-1}|\) is \(O(LK)\). In the first place, the value of \(F_x\) is \(O(LK)\), so we just need to show that the total decrease of \(F_x\) is at most \(O(LK)\). Let \(F'_{x-1}\) be the \((E'_x)\)-th smallest number among \(D_{1,x-1},D_{2,x-1},\cdots,D_{N,x-1}\). Now, by focusing on the definition of \(D_{i,x}\), we obtain \(F_x-K \leq F'_{x-1} \leq F_{x-1}\). Thus, the total decrease of \(F_x\) is at most \(O(LK)\).

Lastly, let \(dist=|F_x-t|\). We can see that \(dist\) decreases by \(1\) each time we increase or decrease \(t\) by \(1\). Furthermore, since the total increase plus the total decrease of \(F_x\) is \(O(LK)\), the total increase of \(dist\) is also \(O(LK)\), completing the proof.

Therefore, the time complexity of the algorithm is \(O(N+LK^2)\).