Độ khó: Trung bình (2/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Sắn rất yêu thích việc mua sắm những đồ chơi khoa học viễn tưởng hiếm và đắt. Anh ta giữ chúng theo một dãy theo thứ tự ngày mua và để trong một cái tủ. Vì vậy, Mì sẽ không bao giờ lấy được đồ chơi của anh ta. Nhưng vì một lần không may mắn, Sắn đã thua Mì trong một vụ cá cược toán học. Và Mì đã yêu cầu Sắn chia sẻ đồ chơi. Bởi vì Sắn không muốn mất nhiều tiền nên anh ta đã quyết định dựa trên một chiến lược để giảm thiểu sự mất mát xuống thấp nhất. Chiến lược đó như sau:

• Đồ chơi được giữ theo thứ tự từ ~1..n~.
• Sắn bắt đầu chọn từ đồ chơi đầu tiên ở trong tủ, sẽ lấy ~x~ đồ chơi liên tiếp.
• Mì sau đó sẽ chọn đúng ~x~ đồ chơi tiếp theo còn lại (chú ý là Mì sẽ chọn số đồ chơi bằng với Sắn, trừ khi số đồ chơi còn lại nhỏ hơn ~x~).
• Việc này sẽ tiếp tục cho đến khi không còn lại đồ chơi nào nữa.

Bạn được cho một dãy của đồ chơi với giá của chúng. Hãy giúp Sắn lấy được đồ chơi với số tiền lớn nhất có thể. Sắn chỉ có thể chọn ~1~, ~2~ hay ~3~ đồ chơi (~x~ có giá trị ~1~, ~2~ hay ~3~).

Dữ liệu vào

• Dòng đầu tiên là ~T~, số lượng testcase ~(1 \le T \le 10)~.
• Mỗi testcase chứa ~N~ ở dòng đầu tiên ~(1 \le N \le 10^5)~. Dòng thứ 2 là ~N~ số nguyên là giá tiền của các đồ chơi ~(1 \le v_i \le 10^9)~.

Kết quả

• In ra 1 số nguyên trên một dòng cho mỗi test case là tổng số tiền lớn nhất của các đồ chơi mà Sắn chọn.

Sample Input 1

2
4
5 4 3 2
6
10 8 7 11 15 20

Sample Output 1

12
53

Nguồn: VinhDinhCoder.