Một công ty công nghệ cần xử lý lần lượt ~n~ tác vụ theo thứ tự đã cho. Tác vụ thứ ~i~ yêu cầu ít nhất ~a_i~ GB bộ nhớ trong (RAM) và ~b_i~ GB dung lượng lưu trữ (Disk).

Các tác vụ phải được chia thành đúng ~k~ lô gồm các tác vụ liên tiếp. Mỗi lô được xử lý trên một máy chủ có cấu hình cố định là ~(x,y)~, trong đó ~x~ là dung lượng bộ nhớ trong và ~y~ là dung lượng lưu trữ. Máy chủ có thể xử lý tác vụ thứ ~i~ nếu ~a_i \le x~ và ~b_i \le y~.

Chi phí thuê một máy chủ cấu hình ~(x,y)~ để xử lý một lô là ~x+y~, không phụ thuộc vào số lượng tác vụ trong lô. Sau khi hoàn thành lô, máy chủ được trả lại; nếu cần sử dụng cùng cấu hình cho một lô khác, công ty phải thuê lại từ đầu.

Yêu cầu: Hãy chia ~n~ tác vụ thành đúng ~k~ lô liên tiếp và lựa chọn cấu hình máy chủ cho từng lô sao cho tất cả các tác vụ đều được xử lý, đồng thời tổng chi phí thuê là nhỏ nhất.

Input

• Dòng 1 chứa hai số nguyên dương ~n,k~ (~n \le 10^5~, ~k \le \min(n,100)~, ~n \cdot k \le 10^6~) cho biết số tác vụ và số lô;

• Dòng 2 chứa ~n~ số nguyên dương ~a_1,a_2,\dots,a_n~ (~a_i \le 10^9~);

• Dòng 3 chứa ~n~ số nguyên dương ~b_1,b_2,\dots,b_n~ (~b_i \le 10^9~).

Output

• Một số nguyên duy nhất là chi phí thuê nhỏ nhất tìm được.

Scoring

Sample Input 1

6 3
4 4 2 3 1 1
2 1 3 3 7 6

Sample Output 1

20

Sample Input 2

6 3
8 3 3 1 7 6
3 9 6 9 7 7

Sample Output 2

37

Sample Input 3

4 2
1 4 5 1
1 1 1 1

Sample Output 3

8

Notes

Trong ví dụ thứ nhất, chia ~6~ tác vụ thành ~3~ lô liên tiếp là ~[1,2]~, ~[3,4]~, ~[5,6]~. Chi phí thuê nhỏ nhất bằng ~(4+2)+(3+3)+(1+7)=20~.

Trong ví dụ thứ hai, hia ~6~ tác vụ thành ~3~ lô liên tiếp là ~[1]~, ~[2,3,4]~, ~[5,6]~. Chi phí thuê nhỏ nhất bằng ~(8+3)+(3+9)+(7+7)=37~.

Trong ví dụ thứ ba, có ~2~ cách chia ~4~ tác vụ thành ~2~ lô đạt chi phí thuê nhỏ nhất là ~8~.

• Cách 1: ~[1]~, ~[2,3,4]~
• Cách 2: ~[1,2,3]~, ~[4]~