Nông dân John có một đàn bò gồm con xếp thành một hàng. Con bò thứ có mức năng suất là . John muốn chọn một số con bò để tham gia cuộc thi cắt cỏ, nhưng anh ta muốn đảm bảo rằng đàn bò không bị làm việc quá sức.
Quy tắc là: John không được chọn quá con bò liên tiếp. Nghĩa là, trong bất kỳ dãy con bò liên tiếp nào, phải có ít nhất một con bò không được chọn. Hãy giúp John chọn các con bò sao cho tổng mức năng suất của các con bò được chọn là lớn nhất.
Dữ liệu:
Dòng đầu tiên chứa hai số nguyên và (, ).
Dòng sau chứa số nguyên (, i=1..N).
Kết quả:
Một số nguyên duy nhất là tổng năng suất lớn nhất có thể đạt được thỏa mãn điều kiện đề bài.
