Trong kỳ thi học sinh giỏi môn Tin học, em là người đạt giải đặc biệt. Ban tổ chức cho phép em chọn các phần thưởng cho mình. Các phần thưởng xếp thành một dãy được đánh số từ 1 đến N (0 ≤ N ≤ 10000), phần thưởng thứ i có giá trị là ai (1 ≤ ai ≤ 100). Em được phép chọn các phần thưởng cho mình theo nguyên tắc không chọn 3 phần thưởng liên tiếp nhau trong dãy. Em hãy lập chương trình chọn ra các phần thưởng sao cho tổng giá trị của các phần thưởng nhận được là lớn nhất.
Dữ liệu: Cho trong file PTHUONG.INP gồm các dòng:
- Dòng đầu tiên là số phần thưởng N.
- Dòng tiếp theo ghi N số ai (1 ≤ i ≤ N).
Kết quả: Ghi ra file PTHUONG.OUT gồm ba dòng:
- Dòng đầu ghi tổng giá trị lớn nhất của các phần thưởng đã chọn và số lượng các phần tử được chọn đó.
- Dòng tiếp theo ghi vị trí của các phần thưởng đã chọn theo thứ tự trong dãy.
- Dòng cuối cùng ghi giá trị của các phần thưởng đã chọn theo thứ tự trong dãy.
Ví dụ:
PTHUONG.INP | PTHUONG.OUT |
7 6 9 1 3 5 10 4 |
32 5 1 2 4 6 7 6 9 3 10 4 |