Để chuẩn bị cho cuộc thi Marathon, bò Bessie tham gia luyện tập trên một đường chạy trong vòng phút . Với mỗi phút, Bessie có thể chạy hoặc nghỉ, nhưng cô không thể thực hiện cả hai tùy chọn này trong cùng một phút.
Yếu tố quyết định đến kết quả chạy của Bessie là thể lực của cô, được xác định lúc ban đầu bằng . Tại phút thứ , nếu Bessie quyết định chạy, cô sẽ chạy được mét , nhưng đồng thời sẽ làm giảm thể lực của cô xuống . Bessie không được phép để thể lực của cô xuống dưới . Nếu cô chọn nghỉ trong phút đó, thể lực của cô sẽ tăng lên , nhưng không bao giờ giá trị này vượt quá . Một khi Bessie bắt đầu nghỉ, cô chỉ có thể tiếp tục chạy khi thể lực của cô trở lại như lúc ban đầu, tức là .
Kết thúc đường chạy, Bessie cần đảm bảo thể lực của cô vẫn là . Xác định quãng đường tối đa Bessie có thể chạy nếu áp dụng chiến thuật tối ưu.
Dữ liệu vào:
Dòng đầu chứa hai số nguyên và ;
dòng tiếp theo, dòng thứ chứa số nguyên .
Dữ liệu ra:
Một dòng duy nhất là độ dài quãng đường lớn nhất có thể chạy được.
Ví dụ:
Dữ liệu vào:
5 2
5
3
4
2
10
Dữ liệu ra:
9
Giải thích:
Bessie sẽ chạy ở phút , nghỉ ở phút , chạy tiếp ở phút , nghỉ ở phút và và độ dài chạy được là .
