Nhà Thắng có khu vườn đánh số từ đến , mỗi khu vườn trồng một trong loại quả: khu vườn thứ trồng loại quả và có quả.
Để có nguyên liệu làm bánh, mẹ Thắng giao cho cậu đi hái quả. Thắng sẽ chọn một đoạn liên tiếp các khu vườn từ đến và hái hết quả ở những khu vườn đó. Mỗi bánh cần nguyên liệu là một quả mỗi loại, vì vậy nếu Thắng lần lượt hái được quả mỗi loại, mẹ sẽ làm được bánh, số quả còn dư sẽ thưởng cho Thắng. Nói cách khác, Thắng sẽ được ăn số lượng quả là:
Hãy giúp Thắng chọn đoạn để được ăn nhiều quả nhất nhé!
Dữ liệu:
Dòng đầu tiên chứa hai số nguyên dương và () là số khu vườn và số loại quả được trồng.
Dòng thứ hai chứa số nguyên dương () là loại quả được trồng trong các khu vườn tương ứng.
Dòng cuối cùng chứa số nguyên dương () là số lượng quả được trồng trong các khu vườn tương ứng.
Kết quả:
Ghi ra một số duy nhất là số lượng quả nhiều nhất Thắng có thể được ăn.
Ví dụ:
Dữ liệu:
6 2
2 2 1 2 1 1
2 7 8 2 8 6
Kết quả:
20
Giải thích: Ta có thể chọn đoạn . Khi đó, số lượng quả Thắng hái được lần lượt là . Vì vậy số lượng quả còn lại Thắng được ăn là .
Dữ liệu:
5 1
1 1 1 1 1
8 8 10 9 1
Kết quả:
0
Giải thích: Vì chỉ có một loại quả duy nhất nên toàn bộ số quả mà Thắng hái được sẽ đem đi làm bánh, và Thắng sẽ không có quả nào để ăn.
Giới hạn:
Subtask #1 (40% số điểm): .
Subtask #2 (30% số điểm): .
Subtask #3 (30% số điểm): Không có ràng buộc bổ sung.
