Lịch hoạt động nhiều ngày

Bối cảnh và bài toán

Trong n ngày, mỗi ngày có 3 loại hoạt động với điểm hài lòng khác nhau. Không được chọn cùng loại hoạt động trong hai ngày liên tiếp.

Yêu cầu

Tối đa hóa tổng điểm hài lòng.

Input

Dòng 1 n; n dòng, mỗi dòng 3 điểm.

Output

In tổng lớn nhất.

Ràng buộc

• 1 <= n <= 10^5
• 0 <= điểm <= 10^9

Chấm điểm

Ví dụ 1

Input

3
10 40 70
20 50 80
30 60 90

Output

210

Giải thích. Ví dụ nhỏ giúp kiểm tra cách mô hình hóa trạng thái và kết quả cuối; khi tự giải, cần suy luận từ ràng buộc thay vì suy đoán từ sample.

Ví dụ 2

Input

1
5 1 2

Output

5

Giải thích. Hãy đối chiếu với edge case: trạng thái đầu, trạng thái không đạt được, tie hoặc biên chỉ số tùy bài.

Gợi ý

Trước khi code, hãy viết rõ ý nghĩa của trạng thái, các trạng thái tiền nhiệm và thứ tự tính sao cho mọi dependency đã có giá trị.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from AtCoder Educational DP Contest C – Vacation. Bản FULLHOUSE DEV đã biên tập bối cảnh/format và ràng buộc khi cần để khớp scope-lock của khóa học.