Một thiết bị bay Drone có nhiệm vụ bay qua các điểm 1, 2, . . . , N được phân bố đều trên 1 đường thẳng, điểm i có tọa độ i. Mỗi điểm i vừa có hàng hóa cần lấy với lượng hàng là c[i] và vừa là trạm để nạp năng lượng với lượng năng lượng a[i]. Khi Drone dừng tại trạm i thì nó sẽ lấy được lượng hàng là c[i] và nạp đúng mức năng lượng a[i] bất kể là đang còn thừa năng lượng hay không. Tiếp theo nó có thể bay tiếp tối đa đến trạm i + a[i] (nó có thể dừng tiếp theo ở trạm nào đó trong số các trạm i + 1, i + 2, . . . i + a[i]). Do đặc tính kỹ thuật, Drone chỉ có thể dừng tối đa K trạm. Hãy tính toán cách đi cho Drone xuất phát từ điểm 1 sao cho nó đến được điểm cuối N và lấy được nhiều hàng hóa nhất.

Dữ liệu vào

• Dòng 1: chứa N và K (1 ≤ N ≤ 3000, 1 ≤ K ≤ 100)

• Dòng 2: N số nguyên dương c[1], c[2], . . . , c[N] (Giá trị các số từ 1 đến 20)

• Dòng 2: N số nguyên dương a[1], a[2], . . . , a[N] (Giá trị các số từ 1 đến 50)

Kết quả

Ghi ra tổng lượng hàng lớn nhất mà Drone lấy được hoặc ghi giá trị -1 nếu không có cách đi thỏa mãn yêu cầu đặt ra.

Sample Input

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

Sample Output

8