Taro quyết định lên kế hoạch cho kỳ nghỉ kéo dài ngày. Trong mỗi ngày (), anh ấy có thể chọn một trong các hoạt động sau:
- A: Bơi ở biển. Anh ấy nhận được điểm hạnh phúc.
- B: Bắt bọ trên núi. Anh ấy nhận được điểm hạnh phúc.
- C: Làm bài tập về nhà. Anh ấy nhận được điểm hạnh phúc.
Vì Taro sẽ dễ chán, anh ấy không thể thực hiện cùng một hoạt động trong hai ngày liên tiếp.
Yêu cầu: Tìm tổng điểm hạnh phúc tối đa mà Taro có thể nhận được.
Dữ liệu:
- Dòng đầu tiên chứa số nguyên .
- dòng tiếp theo, mỗi dòng chứa ba số nguyên .
Kết quả: In ra tổng điểm hạnh phúc tối đa có thể.
Ví dụ:
Dữ liệu:
3
10 40 70
20 50 80
30 60 90
Kết quả:
Giải thích: Taro có thể chọn C vào ngày 1, B vào ngày 2, và C vào ngày 3. Tổng điểm hạnh phúc là .
Giới hạn:
