Đề bài: Có một dãy n ngôi nhà, nhà thứ i có số tiền là a[i]. Có một người muốn lấy trộm tiền từ các ngôi nhà trên. Biết mỗi lần vào được ngôi nhà, tên trộm sẽ lấy hết số tiền trong nhà đó. Tuy nhiên nếu lấy tiền từ hai ngôi nhà kề nhau, thì tên trộm sẽ bị bắt. Hãy viết chương trình với tiếp cận quy hoạch động để tính số tiền lớn nhất mà tên trộm có thể lấy được từ các ngôi nhà trên mà không bị bắt.

Input:

- Dòng đầu tiên nhập vào số nguyên dương n.

- Dòng thứ hai nhập vào n số nguyên dương là số tiền của từng ngôi nhà, mỗi số nguyên dương cách nhau bởi một khoảng trắng.

Output:

- Số tiền lớn nhất mà tên trộm có thể lấy được.

Ví dụ:

Giải thích:

- Tên trộm lần lượt đi vào nhà thứ 1 (a[0]), 4 (a[3]) và 6 (a[5]) nên tổng số tiền có được là 3 + 10 + 8 = 21.

Lưu ý: Có thể có nhiều cách đi khác thoả bài toán như tên trộm có thể đi vào lần lượt các nhà thứ 1, 3, 5, 7 với tổng số tiền có được là 3 + 5 + 7 + 6 = 21.