There are $N$ villages located on a straight line. The distance of the $i$-th village ($i > 1$) from the first village is $D_i$. We need to build at most $K$ communication base stations in these villages. The cost of building a base station in the $i$-th village is $C_i$. If a communication base station is built within a distance of $S_i$ from the $i$-th village, then the $i$-th village is considered covered. If the $i$-th village is not covered, we must pay them a compensation of $W_i$. The problem is to choose the locations of the base stations to minimize the total cost.

Input

The first line of the input contains two integers $N$ and $K$, as described above. The second line contains $N-1$ integers, representing $D_2, D_3, \dots, D_N$. These $N-1$ numbers are in increasing order. The third line contains $N$ integers, representing $C_1, C_2, \dots, C_N$. The fourth line contains $N$ integers, representing $S_1, S_2, \dots, S_N$. The fifth line contains $N$ integers, representing $W_1, W_2, \dots, W_N$.

Output

The output contains a single integer, representing the minimum total cost.

Constraints

• For 40% of the data, $N \le 500$.
• For 100% of the data, $K \le N$, $K \le 100$, $N \le 20,000$, $D_i \le 1,000,000,000$, $C_i \le 10,000$, $S_i \le 1,000,000,000$, $W_i \le 10,000$.

Examples

Input 1

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

Output 1

4