Description

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.

Input Format

• 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 Format

Output a single integer, the minimum total cost.

3 2
1 2
2 3 2
1 1 0
10 20 30

4

Hint

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