#1665. TỔNG DÃY (MAXALT)

Cho hai dãy số nguyên và đều có độ dài , được ký hiệu lần lượt là và .

Bạn cần chọn ra một dãy các phần tử từ hai dãy này sao cho:

1. Nếu một phần tử được chọn tại chỉ số thuộc dãy , thì phần tử tiếp theo được chọn (nếu có) phải ở một chỉ số và thuộc dãy .
2. Ngược lại, nếu một phần tử được chọn tại chỉ số thuộc dãy , thì phần tử tiếp theo được chọn (nếu có) phải ở một chỉ số và thuộc dãy .

Hãy tìm tổng lớn nhất của các phần tử trong dãy được chọn.

Dữ liệu:

• Dòng đầu tiên chứa một số nguyên ().
• Dòng thứ hai chứa số nguyên ().
• Dòng thứ ba chứa số nguyên ().

Kết quả:

• Một số nguyên duy nhất là tổng lớn nhất có thể đạt được.

Ví dụ:

Dữ liệu:

5
9 3 5 7 3
5 8 1 4 5

Kết quả:

29

Giải thích:

• Các phần tử được chọn lần lượt là: . Tổng là .

Dữ liệu:

3
1 2 9
10 1 1

Kết quả:

19

Giải thích:

• Chọn và . Tổng là . Ta bỏ qua chỉ số để lấy được giá trị lớn hơn ở .

Giới hạn:

• Subtask #1 (10% số điểm): .
• Subtask #2 (15% số điểm): và với mọi .
• Subtask #3 (25% số điểm): .
• Subtask #4 (50% số điểm): Không có ràng buộc bổ sung.