← 返回题目列表

AtCoder · dp_c

C. 假期

中文机器翻译题面 查看原题

分数: 100 点

问题陈述

太郎的暑假明天开始,他决定现在就开始计划。

假期包括 N 天。 对于每个 i (1 \leq i \leq N),太郎将选择以下活动之一并在 i第一天:

  • A:在海里游泳。增益 a_i 点幸福。
  • B:到山里捉虫子。增益 b_i 点幸福。
  • C:在家做作业。增益 c_i 点幸福。

由于太郎很容易感到无聊,他无法连续两天或以上进行相同的活动。

找出太郎获得的最大可能的幸福总分。

约束

  • 输入中的所有值都是整数。
  • 1 \leq N \leq 10^5
  • 1 \leq a_i, b_i, c_i \leq 10^4

输入

输入由标准输入按以下格式给出:

N
a_1 b_1 c_1
a_2 b_2 c_2
:
a_N b_N c_N

输出

打印太郎获得的最大可能的幸福总分。


示例输入 1

3
10 40 70
20 50 80
30 60 90

示例输出 1

210

如果太郎按照C、B、C的顺序进行活动,他将获得 70 + 50 + 90 = 210 点幸福。


示例输入 2

1
100 10 1

示例输出 2

100

示例输入 3

7
6 7 8
8 8 3
2 5 2
7 8 6
4 6 8
2 3 4
7 5 1

示例输出 3

46

太郎应该按照C、A、B、A、C、B、A的顺序进行活动。