Đất nước Alpha
Đề bài
Mô tả
Ở đất nước Alpha có hòn đảo được đánh số từ đến . Các hòn đảo được nối với nhau bằng những cây cầu một chiều: từ đảo chỉ có thể đi sang đảo . Mỗi khi đến một hòn đảo , bạn sẽ được thưởng hoặc bị phạt đô la: dương là số tiền bạn nhận được, âm nghĩa là bạn phải nộp phạt đô la (số tiền hiện có của bạn được phép âm).
Một nhà ảo thuật cho Tuấn hai lần sử dụng phép thuật: một lần để dịch chuyển tới một hòn đảo bất kỳ (dùng lần đầu tiên để đến đất nước Alpha), sau đó Tuấn đi lần lượt sang các đảo kế tiếp, và một lần để trở về nhà vào bất kỳ lúc nào. Tuy nhiên, Tuấn phải gửi lại cho nhà ảo thuật một số tiền bằng số tiền lớn nhất mà anh nhận được ở một hòn đảo đã đi qua.
Nói cách khác, Tuấn chọn hai chỉ số , đi qua các đảo và số tiền kiếm được là
Tuấn sử dụng phép thuật một cách tối ưu để kiếm được nhiều tiền nhất. Hãy in ra số tiền lớn nhất mà Tuấn có thể kiếm được.
Dữ liệu vào
- Dòng đầu tiên chứa một số nguyên (): số hòn đảo ở đất nước Alpha.
- Dòng thứ hai chứa số nguyên (): số tiền được thưởng hoặc bị phạt ở đảo .
Dữ liệu ra
In ra một số nguyên duy nhất là số tiền lớn nhất mà Tuấn có thể kiếm được.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 6 -5 7 3 -2 |
4 | Tuấn dịch chuyển tới đảo , đi qua các đảo rồi về nhà ở đảo . Anh nhận được đô la và gửi lại nhà ảo thuật đô la, nên kiếm được đô la. |
| 8 -1 5 -4 3 4 6 -10 4 |
8 | Tuấn dịch chuyển tới đảo và về nhà ở đảo : nhận đô la, gửi lại đô la, kiếm được đô la. |
Bình luận