Trên trang trại UCPC, có $N$ chiếc cọc được đóng thành một hàng thẳng. Những chiếc cọc này có chiều cao ngẫu nhiên nên trông không được đẹp mắt. Do đó, bạn cần điều chỉnh chiều cao của các cọc để làm cho trang trại UCPC trông đẹp mắt hơn.

Các cọc được đánh số từ $1$ đến $N$ từ trái qua phải, và chiều cao ban đầu của cọc thứ $i$ là $H_i$ cm. Ngoài ra, do chất liệu của mỗi chiếc cọc là khác nhau, lực cần thiết để kéo lên hoặc đóng xuống của mỗi cọc cũng khác nhau. Để kéo cọc thứ $i$ lên thêm $1$ cm cần một lực là $A_i$, và để đóng cọc thứ $i$ xuống thêm $1$ cm cần một lực là $B_i$.

"Độ đẹp" của trang trại UCPC được quyết định bởi chiều dài của phân đoạn liên tiếp dài nhất gồm các cọc có cùng chiều cao. Hãy tìm lực tối thiểu cần thiết để đưa độ đẹp của trang trại UCPC đạt từ $K$ trở lên.

Hình E.1: Trạng thái ban đầu của các cọc với độ đẹp bằng 1. Hình E.2: Tăng độ đẹp lên 3 bằng cách tác dụng lực.

Dữ liệu vào

Dòng đầu tiên chứa số lượng cọc $N$ và độ đẹp $K$ cần đạt được của trang trại UCPC. ($1 \le N \le 100\,000$, $1 \le K \le N$)

Dòng tiếp theo chứa chiều cao ban đầu của các cọc $H_1, H_2, \dots, H_N$, ngăn cách nhau bởi khoảng trắng. ($1 \le H_i \le 100\,000$, $1 \le i \le N$)

Dòng tiếp theo chứa lực cần thiết để kéo mỗi cọc lên $1$ cm, $A_1, A_2, \dots, A_N$, ngăn cách nhau bởi khoảng trắng. ($1 \le A_i \le 20\,000$, $1 \le i \le N$)

Dòng tiếp theo chứa lực cần thiết để đóng mỗi cọc xuống $1$ cm, $B_1, B_2, \dots, B_N$, ngăn cách nhau bởi khoảng trắng. ($1 \le B_i \le 20\,000$, $1 \le i \le N$)

Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Dữ liệu ra

In ra một số nguyên duy nhất là lực tối thiểu cần thiết để độ đẹp của trang trại UCPC đạt ít nhất là $K$.

Ví dụ

Dữ liệu vào 1

2 2
1 3
4 1
1 3

Dữ liệu ra 1

6

Dữ liệu vào 2

5 3
1 2 3 2 1
1 3 1 3 4
1 3 5 3 1

Dữ liệu ra 2

5