Một thị trấn được mô tả bởi ~N~ ngọn đồi xếp thành một hàng. Ngọn đồi thứ ~i~ có độ cao ~h_i~. Khoảng thời gian để đi từ ngọn đồi ~i~ đến ngọn đồi ~i+1~ là ~t_i~ phút. Một ngọn đồi ~i~ có thể nhìn thấy một ngọn đồi ~j~ nếu không có ngọn đồi ~k~ nằm giữa sao cho ~h_k \ge h_i~.

Chính quyền dự định đặt ~K~ trạm cứu hỏa tại một số ngọn đồi. Mỗi trạm cứu hỏa có thể bảo vệ tất cả các ngọn đồi mà nó có thể nhìn thấy. Thời gian để lính cứu hỏa đến một ngọn đồi nhất định là tổng thời gian di chuyển từ trạm cứu hỏa gần nhất đến ngọn đồi đó. Nếu một trạm cứu hỏa được đặt tại ngọn đồi ~i~, thì thời gian di chuyển đến nó là ~s_i = 0~.

Hãy tìm cách đặt ~K~ trạm cứu hỏa sao cho thời gian di chuyển cứu hỏa lớn nhất ~max(s_1, s_2, ..., s_N)~ là nhỏ nhất. Nếu không thể đặt trạm theo cách hợp lệ, hãy in ra ~-1~.

Input

• Dòng 1: Chứa hai số nguyên ~N~ và ~K~ (~1 \le K \le N \le 500000~) — số lượng ngọn đồi và số trạm cứu hỏa.
• Dòng 2: Chứa ~N~ số nguyên ~h_1, h_2, ..., h_N~ (~1 \le h_i \le 10^9~) — độ cao của các ngọn đồi.
• Dòng 3: Chứa ~N-1~ số nguyên ~t_1, t_2, ..., t_{N-1}~ (~1 \le t_i \le 10^9~) — thời gian di chuyển giữa các ngọn đồi liên tiếp.

Output

• Nếu không thể đặt trạm hợp lệ, in ra ~-1~. Nếu có thể, in ra số nguyên ~S~ — thời gian phản hồi lớn nhất tối thiểu.

Sample Input 1

8 3
4 4 3 4 3 2 5 4
3 5 4 7 5 9 5

Sample Output 1

7

Giải thích ví dụ 1

Các trạm được đặt tại các ngọn đồi ~2, 5, 7~.

• Ngọn đồi ~2~ bảo vệ ~1, 2, 3~.
• Ngọn đồi ~5~ bảo vệ ~4, 5, 6~.
• Ngọn đồi ~7~ bảo vệ ~7, 8~. Thời gian phản hồi lớn nhất là ~7~ (từ đồi ~5~ đến đồi ~4~).

Sample Input 2

8 1
2 4 2 4 1 2 4 1
1 1 1 1 1 1 1

Sample Output 2

-1

Subtasks