chooseGifts

Hải vừa được trúng thưởng cực lớn trong một trò chơi. Ban tổ chức đã chuẩn bị sẵn cho Hải n món quà có giá trị lần lượt là a0, a1, ..., an-1.

Ban tổ chức cho phép Hải chọn quà theo luật như sau:

• Mỗi lượt chỉ được chọn 1 món quà.
• Nếu lượt này đã chọn món quà thứ k thì lượt sau chỉ được chọn các phần quà từ k+1 đến n-1.
• Ở lượt chọn quà lẻ (lượt 1, lượt 3,…) thì Hải được chọn bất kỳ phần quà giá trị tùy ý.
• Ở lượt chọn quà chẵn (lượt 2, lượt 4,..) thì Hải bắt buộc phải chọn phần quà có cùng giá trị với phần quà ngay trước đó mà Hải đã chọn.

Hãy tìm và in ra tổng giá trị lớn nhất của các phần quà mà Hải có thể chọn.

Ví dụ:

• Với a = [2,3,2], thì chooseGifts(a) = 4.
  Giải thích:
  • Lượt 1 Hải chọn phần quà có giá trị a[0]=2, lượt 2 Hải chọn phần quà có giá trị a[2] = 2.
• Với a = [10,6,7,6,1], thì chooseGifts(a) = 13.

Đầu vào/Đầu ra:

• [Thời gian chạy] 0.5s với C++, 3s với Java, C#, 4s với Python, Js, Go
• [Đầu vào] Arrays a
  0 ≤ a.size ≤ 104
0 ≤ a[i] ≤ 103
• [Đầu ra] Integer
  Tổng giá trị lớn nhất của các phần quà mà Hải có thể chọn.