#AT3. Vacation

Vacation

[C] Vacation(dp_c)

来源: AtCoder Educational DP Contest - Problem C 原题时限:2 秒 / 内存:1024 MB

题目描述

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

假期共有 NN 天。对于每个 ii(1≤i≤N1 \le i \le N),太郎会在第 ii 天从下面的活动中选择一项来做:

  • A:去海里游泳,获得 aia_i 点幸福值。
  • B:去山里抓虫子,获得 bib_i 点幸福值。
  • C:在家做作业,获得 cic_i 点幸福值。

由于太郎很容易厌倦,他不能连续两天或更多天做同一项活动。

求太郎能获得的最大幸福值总和。

输入格式

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

N
a_1 b_1 c_1
a_2 b_2 c_2
:
a_N b_N c_N

输出格式

输出太郎能获得的最大幸福值总和。

数据范围

  • 输入中的所有值均为整数。
  • 1≤N≤1051 \le N \le 10^5
  • 1≤ai,bi,ci≤1041 \le a_i, b_i, c_i \le 10^4

样例 1

输入:

3
10 40 70
20 50 80
30 60 90

输出:

210

样例 2

输入:

1
100 10 1

输出:

100

样例 3

输入:

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

输出:

46