Thiết bị bay

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ù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\) là \(B_i\), trong đó \(B_i = 1\) nếu thiết bị bay có thể tiếp cận ngôi nhà để thả hàng, ngược lại thì \(B_i = 0\).

Một thiết bị bay chở tối đa \(K\) gói hàng sẽ giao cho dãy các ngôi nhà liên tục nhưng nếu gặp ngôi nhà không thể tiếp cận thì sẽ quay trở về, để cho thiết bị bay khác tiếp tục. Mỗi thiết bị chỉ bay đúng một lần duy nhất. Hàng cho một ngôi nhà phải do đúng một thiết bị giao trọn vẹ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 mà không sử dụng quá \(M\) thiết bị bay.

Input

Dữ liệu vào gồm \(3\) dòng:

• Dòng đầu tiên chứa \(2\) 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\}\)).

Ràng buộc:

• Subtask 1: \(M = N\).

• Subtask 2: \(1 \le M, N \le 100\), \(B_i = 1\).

• Subtask 3: Không ràng buộc gì thêm.

Output

In ra giá trị \(K\) nhỏ nhất tìm được. 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\).

Example 1

Input:

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

Output:

5

Example 2

Input:

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

Output:

7

Example 3

Input:

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

Output:

-1

Note

Ví dụ 1: mỗi thiết bị bay sẽ giao hàng cho \(1\) ngôi nhà.

Ví dụ 2: thiết bị bay \(1\) giao hàng cho nhà \(1\) và \(2\), thiết bị bay \(2\) giao hàng cho nhà \(3\) và \(4\), thiết bị bay \(3\) giao hàng cho nhà \(5\), \(6\) và \(7\).

Ví dụ 3: có \(4\) ngôi nhà cần hàng cứu trợ mà chỉ có \(3\) thiết bị bay.