Có ~n~ điểm dân cư nằm trên một con đường thẳng, theo thứ tự từ trái sang phải. Điểm thứ ~i~ có tọa độ ~x_i~ và nhu cầu phục vụ ~w_i~. Cần chia dãy điểm dân cư thành đúng ~K~ nhóm liên tiếp, mỗi nhóm không rỗng. Trong mỗi nhóm phải đặt đúng một trạm tại tọa độ của một điểm dân cư thuộc nhóm đó. Nếu chọn điểm ~j~ làm vị trí đặt trạm thì ngoài chi phí phục vụ, còn phải trả thêm một khoản chi phí mở trạm cố định là ~c_j~.

Nếu điểm ~i~ được phục vụ bởi trạm đặt tại điểm ~j~, chi phí là ~w_i \cdot |x_i-x_j|~.

Yêu cầu: Hãy tìm tổng chi phí nhỏ nhất.

Input

• Dòng đầu chứa hai số nguyên ~n, K~.

• Dòng thứ hai chứa ~n~ số nguyên tăng nghiêm ngặt ~x_1, x_2, \dots, x_n~.

• Dòng thứ ba chứa ~n~ số nguyên ~w_1, w_2, \dots, w_n~.

• Dòng thứ tư chứa ~n~ số nguyên ~c_1, c_2, \dots, c_n~.

Output

• Một số nguyên là tổng chi phí nhỏ nhất.

Scoring

• ~1 \le K \le \min(30,n)~, ~1 \le n \le 20000~, ~0 \le x_1 < x_2 < \dots < x_n \le 10^5~, ~1 \le w_i \le 10000~, ~0 \le c_i \le 10^9~.

Sample Input 1

4 2
1 4 7 9
2 1 3 2
5 1 4 2

Sample Output 1

15

Notes

• Một phương án tối ưu là chia sau điểm thứ ~2~.

• Nhóm ~[1,2]~ đặt trạm tại điểm ~2~, có chi phí phục vụ ~6~ và chi phí mở trạm là ~1~, tổng là ~7~. Nhóm ~[3,4]~ đặt trạm tại điểm ~4~, có chi phí phục vụ ~6~ và chi phí mở trạm là ~2~, tổng là ~8~. Tổng chi phí là ~15~.