Start: 2023-05-02 00:00:00

May day2

End: 2023-05-02 20:30:00
Now  2025-09-14 00:14:27  类型: IOI  状态: Ended 

P1. 露西亚的训练计划
Description

露西亚准备开始时长为 n 天的训练计划。

每天的训练有三种,分为低,中,高,分别可以得到a_i, b_i, c_i 的训练效果。但是高强度训练的前一天必须是低强度的训练,否则会对机体产生不可逆转的伤害。

露西亚现在想知道,在保证机体不受损伤的情况下,这 n 天的最大训练效果。

Input

第一行一个整数 n, 如题意所示。

接下来的 n 行,每行三个整数 a_i, b_i, c_i。均如题意

Output

一行一个整数为最大训练效果

Examples

Input

3
1 2 3
4 5 6
7 8 9

Output

16
Hint

1 ≤ n ≤ 10^6

-10^5 ≤ a_i, b_i, c_i ≤ 10^5

注意:第一天可以进行高强度的训练。不一定强度越高训练效果越好


Submit

题目参数
Time Limit 1 second
Memory Limit 128 MB
Submit