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, mỗi 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~ 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ề để thiết bị bay khác tiếp tục. Mỗi thiết bị chỉ bay đúng ~1~ 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 mà không sử dụng quá ~M~ thiết bị bay.

Input

Vào từ file văn bản DRONE.INP gồm ~3~ dòng:

• Dòng ~1~: hai số nguyên dương ~N~, ~M~ với giới hạn ~1 \leq M \leq N \leq 10^4~.
• Dòng ~2~: ~N~ số nguyên ~A_1, A_2, \ldots, A_N~ với giới hạn ~1 \leq A_i \leq 10^6~.
• Dòng ~3~: ~N~ số nguyên ~B_1, B_2, \ldots, B_N~ với ~B_i \in \{0,1\}~.

Output

Ghi ra file văn bản DRONE.OUT:

• Ghi giá trị ~K~ nhỏ nhất tìm được. 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~.

Scoring

• Subtask ~1~: ~M = N~
• Subtask ~2~: ~1 \leq M, N \leq 100~ và ~B_i = 1~
• Subtask ~3~: Không ràng buộc gì thêm

Example input 1

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

Example output 1

5

Note 1

• Mỗi thiết bị bay sẽ giao hàng cho ~1~ nhà.

Example input 2

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

Example output 2

7

Note 2

• Có thể chia thành ~3~ lượt giao liên tiếp: nhà ~1~-~2~, nhà ~3~-~4~, nhà ~5~-~7~.

Example input 3

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

Example output 3

-1

Note 3

• Có ~4~ nhà cần hàng cứu trợ mà chỉ có ~3~ thiết bị bay.