P2605 [ZJOI2010] Base Station Placement

There are $N$ villages located on a straight line. For village $i$ ($i > 1$), the distance to village $1$ is $D_i$. You need to build at most $K$ communication base stations in these villages. The cost to build a base station at village $i$ is $C_i$. If there is a base station within a distance no more than $S_i$ from village $i$, then village $i$ is considered covered. If village $i$ is not covered, you must compensate it at a cost of $W_i$. Choose the locations of the base stations to minimize the total cost.

- The first line contains two integers $N, K$, as described above. - The second line contains $N-1$ integers, $D_2, D_3, \cdots, D_N$, which are in ascending order. - The third line contains $N$ integers, $C_1, C_2, \cdots, C_N$. - The fourth line contains $N$ integers, $S_1, S_2, \cdots, S_N$. - The fifth line contains $N$ integers, $W_1, W_2, \cdots, W_N$.

Output a single integer, the minimum total cost.

Constraints: - For $30\%$ of the testdata, $N \leq 500$. - For $100\%$ of the testdata, $K \leq N$, $K \leq 100$, $N \leq 2 \times 10^4$, $D_i \leq 10^9$, $C_i \leq 10^4$, $S_i \leq 10^9$, $W_i \leq 10^4$. Translated by ChatGPT 5