Ngủ gật


Submit solution

Points: 2 (partial)
Time limit: 1.0s
Memory limit: 488M

Author:
Problem type

Do tình hình dịch bệnh căng thẳng buộc \(T\) và bạn gái của \(T\) tham gia lớp học Thuật toán và ứng dụng bằng hình thức online. Mỗi lớp học online thường có thời lượng là \(n\) phút. Giảng viên sẽ giảng \(ai\) định lý trong suốt phút thứ \(i\). \(T\) rất thích học môn đó, tuy nhiên khi học online \(T\) có tật xấu là hay ngủ gật nên không thể tập trung được hết trong suốt buổi học. Bạn sẽ có một mảng \(t\) chứa các hành vi của \(T\), nếu mà \(T\) ngủ gật vào phút thứ \(i\) của buổi học thì \(ti\) sẽ được gán là \(0\), ngược lại thì sẽ là \(1\). Tất nhiên khi vẫn còn tỉnh táo \(T\) sẽ ghi chép đầy đủ tất cả định lý mà thầy giáo giảng, ngược lại khi ngủ gật thì \(T\) không thể ghi chép được bất kì định lý nào.

Bạn gái của \(T\) có một khả năng đặc biệt giúp cho \(T\) có thể tỉnh táo cho một khoảng \(k\) phút liên tiếp. Tuy nhiên kĩ thuật này chỉ dùng được một lần duy nhất. Bạn gái \(T\) có thể bắt đầu sử dụng nó ở đầu bất kỳ phút nào trong khoảng từ \(1\) và \(n - k + 1\). Và tất nhiên khi bạn gái \(T\) dùng khả năng đó vào một phút nào đó, thì \(T\) sẽ tỉnh táo trong \(k\) tiếp phút đó và như vậy \(T\) sẽ vẫn ghi lại đầy đủ tất cả các định lý mà giảng viên đã nói.

Nhiệm vụ của bạn là phải giúp cho người yêu \(T\) tính toán để khi người yêu \(T\) xử dụng khả năng đặc biệt đó, giúp \(T\) có thể ghi được nhiều định lý nhất có thể.

Đầu vào

  • Dòng đầu vào của đầu vào chứa hai số nguyên n và k (1 ≤ k ≤ n ≤ 10^5) - Thời gian của bài giảng trong vài phút và số phút người yêu có thể giúp T tỉnh táo.
  • Dòng thứ hai của đầu vào chứa n số nguyên a1, a2, ... a (1 ≤ ai ≤ 10^4) - Số lượng định lý mà giảng viên đã nói trong phút thứ i.
  • Dòng thứ ba của đầu vào chứa số nguyên n t1, t2, ... tn (0 ≤ ti ≤ 1) - Loại hành vi của T ở phút thứ i trong bài giảng.

Đầu ra

Đầu ra chỉ in một số nguyên. Là số lượng định lý tối đa mà T sẽ có thể ghi lại nếu người yêu chỉ sử dụng khả năng đặc biệt của mình một lần để đánh thức T dậy.

Ví dụ

Đầu vào

6 3
1 3 5 2 5 4
1 1 0 1 0 0

Đầu ra

16

Giải thích: Ban đầu T có thể tỉnh táo ở phút thứ 1 2 4 nên tổng định T đã ghi lại được là 6. Khi người yêu T đùng khả năng đặc biệt của mình vào phút thứ 3. Thì T đã có thể tỉnh táo thêm phút thứ 3 và 5 nên tổng định lý mà T đã ghi được là 6+5+5=16.


Comments

There are no comments at the moment.