Purple Mountain (Zijin Shan) is one of the most famous mountain in Nanjing and its ropeway, the Purple Mountain Ropeway, used to be the longest chairlift in China. Tourists can take the ropeway from the foot of the mountain and go all the way up to the top in less than ten minutes.
The old Purple Mountain Ropeway. Photo by MiNe. Licensed under CC BY 2.0.
In order to build a ropeway, aside from the stations at the foot and the top of the mountain, we also need to build supporting towers along the way. The engineers have built the stations at $$$0$$$ and $$$(n + 1)$$$ unit of distance from the entrance of the ropeway and have investigated the cost to build a supporting tower at $$$1, 2, \cdots, n$$$ unit of distance, which are $$$a_1, a_2, \cdots, a_n$$$ respectively.
Due to some of the considerations on engineering, supporting towers must be built at some position. Also, to ensure the safety of the ropeway, the distance between neighboring supporting towers or stations must be less than or equal to $$$k$$$. That is, let $$$b_0, b_1, b_2, \cdots, b_m, b_{m + 1}$$$ be the final positions to build two stations and $$$m$$$ supporting towers, where $$$0 \le m \le n$$$ and $$$0 = b_0 \lt b_1 \lt b_2 \lt \cdots \lt b_m \lt b_{m + 1} = n + 1$$$, we have $$$b_i - b_{i - 1} \le k$$$ for all $$$1 \le i \le m + 1$$$.
In the meantime, to make plans more flexible, the engineers will temporarily change the cost sequence for $$$q$$$ times. The $$$i$$$-th change can be described as $$$(p_i, v_i)$$$, which means changing the value of $$$a_{p_i}$$$ to $$$v_i$$$ temporarily.
For each change, please calculate the minimum total cost to build supporting towers such that all requirements above can be satisfied.
Please note again that all changes are temporary and independent from each other. That is, after calculating the answer for a change, this change will be reverted and the cost sequence will be reverted back to its original state.
There are multiple test cases. The first line of the input contain an integer $$$T$$$ indicating the number of test cases. For each test case:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 5 \times 10^5$$$, $$$1 \le k \le \min(n + 1, 3 \times 10^3)$$$) indicating the number of candidate positions to build supporting towers and the maximum distance between neighboring supporting towers or stations.
The second line contains $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) where $$$a_i$$$ indicates the cost to build a supporting tower at $$$i$$$ unit of distance.
The third line contains a binary string $$$s_1s_2\cdots s_n$$$ of length $$$n$$$ ($$$s_i \in \{\text{'0'}, \text{'1'}\}$$$). If $$$s_i = \text{'1'}$$$ you must build a supporting tower at $$$i$$$ unit of distance. If $$$s_i = \text{'0'}$$$ you can decide whether to build a supporting tower at $$$i$$$ unit of distance.
The fourth line contains an integer $$$q$$$ ($$$1 \le q \le 3 \times 10^3$$$) indicating the number of changes.
For the following $$$q$$$ lines, the $$$i$$$-th line contains two integers $$$p_i$$$ and $$$v_i$$$ ($$$1 \le p_i \le n$$$, $$$1 \le v_i \le 10^9$$$) indicating the $$$i$$$-th change.
It's guaranteed that the sum of $$$n$$$ of all test cases will not exceed $$$2 \times 10^6$$$. It's also guaranteed that neither the sum of $$$k$$$ nor the sum of $$$q$$$ of all test cases will exceed $$$10^4$$$.
For each change output one line containing one integer indicating the minimum total cost to build supporting towers after temporarily applying the change.
310 35 10 7 100 4 3 12 5 100 1000100001022 36 155 61 1 1 1 10000013 1005 61 1 1 1 10010013 100
206 214 0 100
For the first sample test case:
- By applying the first change, the cost sequence is now $$$\{5, 3, 7, 100, 4, 3, 12, 5, 100, 1\}$$$. We should build supporting towers at $$$2$$$, $$$4$$$, $$$6$$$ and $$$9$$$ unit of distance to minimize the total cost.
- By applying the second change the cost sequence is now $$$\{5, 10, 7, 100, 4, 15, 12, 5, 100, 1\}$$$. We should build supporting towers at $$$1$$$, $$$4$$$, $$$5$$$, $$$8$$$ and $$$9$$$ unit of distance to minimize the total cost.
For the second sample test case, no supporting towers are needed.
For the third sample test case we have to build a supporting tower at $$$3$$$ unit of distance, so the cost is just $$$a_3$$$.
