Drone

Sau khi cơn lũ đi qua, có \(N\) ngôi nhà đánh số từ \(1\) đến \(N\) cần được cứu trợ. Ngôi nhà thứ \(i\) cần \(A_i\) gói hàng cứu trợ.
Chính quyền xã huy động được tối đa \(M\) thiết bị bay không người lái, các thiết bị bay có cùng một tải trọng.

Tuy nhiên do điều kiện địa hình nên có một số ngôi nhà mà thiết bị bay không thể tiếp cận.
Khả năng tiếp cận ngôi nhà thứ \(i\) được cho bởi \(B_i\):

• \(B_i = 1\) nếu thiết bị bay có thể tiếp cận ngôi nhà đó,
• \(B_i = 0\) nếu không thể tiếp cận.

Mỗi thiết bị bay chở tối đa \(K\) gói hàng, và sẽ giao hàng cho một dãy các ngôi nhà liên tiếp theo thứ tự tăng dần chỉ số.
Nếu trong quá trình bay gặp một ngôi nhà không thể tiếp cận (\(B_i=0\)) thì thiết bị bay phải quay trở về ngay lập tức, để thiết bị bay khác tiếp tục (từ các ngôi nhà phía sau).
Mỗi thiết bị bay chỉ bay đúng một lần.

Yêu cầu: Hãy xác định giá trị \(K\) nhỏ nhất sao cho có thể giao đủ hàng cho tất cả các ngôi nhà có thể tiếp cận (\(B_i=1\)) mà không sử dụng quá \(M\) thiết bị bay.
Trong trường hợp không đủ thiết bị bay hoặc tất cả các ngôi nhà đều không thể tiếp cận thì ghi \(-1\).

Input

• Dòng đầu chứa hai số nguyên dương \(N, M\) \((1 \le M \le N \le 10^4)\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \ldots, A_N\) \((1 \le A_i \le 10^6)\).
• Dòng thứ ba chứa \(N\) số nguyên \(B_1, B_2, \ldots, B_N\) \((B_i \in \{0,1\})\).

Output

In ra một số nguyên duy nhất là \(K\) nhỏ nhất tìm được. Nếu không có lời giải thì in ra \(-1\).

Scoring

• Subtask 1: (\(20\%\) số điểm) \(M = N\).
• Subtask 2: (\(30\%\) số điểm) \(1 \le M, N \le 100\) và \(B_i = 1\) với mọi \(i\).
• Subtask 3: (\(50\%\) số điểm) Không có ràng buộc bổ sung.

Sample Input 1

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

Sample Output 1

5

Sample Input 2

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

Sample Output 2

7

Sample Input 3

7 3
3 4 2 5 1 3 2
1 0 1 0 1 0 1

Sample Output 3

-1