An chiến thắng trong một trò chơi trên truyền hình. Ban tổ chức không phát thưởng ngay mà tổ chức phát thưởng bằng một trò chơi. Ban tổ chức bày ra một dãy gồm N phần thưởng, phần thưởng thứ i có giá trị ai và yêu cầu An: “Hãy chọn 3 phần thưởng có tổng giá trị lớn nhất sao cho không được chọn hai phần thưởng liên tiếp nhau”.
Yêu cầu: Cho n và dãy a1, a2, ..., an. Em hãy viết chương trình giúp An chọn 3 phần thưởng có giá trị lớn nhất thỏa mãn yêu cầu trên?
INPUT
OUTPUT một số duy nhất là tổng giá trị lớn nhất 3 phần thưởng chọn được.
INPUT |
OUTPUT |
8 2 4 5 3 5 9 4 2 |
16 |