You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

你暑假有$n$ 天，每一天你都可以选择做语文作业，数学作业，英语作业 或者 信息学刷题！

第$i$天，做语文作业的幸福感$a_i$, 做数学作业的幸福感$b_i$, 做英语作业的幸福感$c_i$, 做信息学刷题的幸福感$d_i$。

但是有些事情你可能感觉很恶心，所以幸福感也可以是负数。

你每一天只能选择做一件事情，且不能连续两天做相同的事情，比如你不能第$i - 1$天做语文作业了，同时第$i$天继续做语文作业。

请规划你的暑假，使你自己幸福感最大化。

Format

Input

第一行一个整数$n$ 表示暑假的天数。

接下来$n$行，每行四个整数$a_i, b_i, c_i, d_i$ 如题目描述

Output

输出一个整数表示最大幸福感。

Samples

样例输入

3
1 1 1 100
1 1 1 100
1 1 1 100

样例输出

201

样例解释

100 + 1 + 100 = 201

你可以第一题信息学刷题，第二题做数学作业，第三天信息学刷题！

Limitation

1s, 1024KiB for each test case.

$20\%$的数据，$1 \leq n \leq 8$

$50\%$的数据，$1 \leq n \leq 1000$

$100\%$的数据，$1 \leq n \leq 10^5, -10^6 \leq a_i, b_i, c_i, d_i \leq 10^6$