题目描述

小可可喜欢花，小薰也喜欢花，两个人结伴来到一片花海中。\(N\) 朵巨大的花排一圈。这些奇异的花有着奇异的香味，乘着这花香，小可可和小薰可以从一朵花到达另一朵花。因为每朵花可能有不同的色彩，不同的花瓣数，所以从每朵花能到达的花，需要的时间也有可能不一样。但是小可可和小薰知道，从第 \(i\) 朵花能且只能到第 \(i+1\) 朵花，第 \(N\) 朵花能且只能到第 \(1\) 朵花，并他们爬上一朵花和从一朵花下来都需要时间。

小可可和小薰想在这里尽量长时间地停留，但是两人不可以在地上和花上停留，并且只能到每朵花一次。也就是说当他们一来到这里就必须选择一朵花爬上去，而从花上下来之后就必须离开这个地方，他们只能上一次和下一次。

请计算出他们能停留（停留的时间当然包括上、下花的时间和在花上爬行的时间）的最长时间最多是多少。

格式

输入格式

第一行有且只有一个正整数 \(N\)，表示花数。

接下来的 \(N\) 行，每行三个正整数\(A_i, B_i, C_i\)，用单个空格隔开，表示爬上第 \(i\) 朵花需要时间 \(A_i\)，从第 \(i\) 朵花上下来需 \(B_i\) 时间，到达下一朵花需 \(C_i\) 时间。

输出格式

输出一行，为这个最长时间最长是多少。

样例1

样例输入1

4
3 1 1
1 4 1
1 1 3
1 2 2

样例输出1

11

样例2

样例输入2

4
4 5 1
1 1 1
1 1 1
1 1 1

样例输出2

9

样例1解释

从\(3\)号花爬上去，时间为\(1\)；从 \(3\) 号花爬到 \(4\) 号花，时间为 \(3\)；从 \(4\) 号花爬到 \(1\) 号花，时间为 \(2\)；再从 \(1\) 号花爬到 \(2\) 号花，时间为 \(1\)；最后从 \(2\) 号花下来，时间为 \(4\)；故停留时间总和为\(1+3+2+1+4=11\) 。

样例2解释

从 \(1\) 号花爬上去再从 \(1\) 号花爬下来，停留时间为 \(4+5=9\)。

限制

\(50\%\)的数据：\(N \le 2000\)；

\(100\%\)的数据：\(1 \le N \le 10^6，0 \le A_i，B_i，C_i \le 10^9\)。