当前没有测试数据。

【题目描述】

今晚 GodCowC 和 FoolMike 准备开黑打 AtCoder。

AtCoder 的比赛规则如下。

Contest Rules

This contest is full-feedback (solutions are judged during the contest).

When you solve a problem, you get a score assigned to it. Competitors are ranked first by total scores, then by penalties. The penalties are computed as (the time you spend to get your current score) + (5 minutes) * (the number of incorrect attempts).

翻译过来就是，每道题有一个分数，做对就得分。比赛选手的成绩首先按照得分为第一关键字，罚时为第二关键字排序。这里的罚时等于最后一次提交 AC 代码的时间 $+~5$ 分钟$~\times$ 错误提交次数。

今晚的 AtCoder，共有 $n$ 道题，GodCowC 表示自己切掉第 $i$ 道题需要花 $a_{i}$ 分钟，而蒟蒻 FoolMike 却需要花 $b_{i}$ 分钟。鉴于是开黑比赛，他们也会互相协助。有经验的老司机 GodCowC 表示自己只需要 $c_{i}$ 分钟就可以把这道题教会 FoolMike 并协助他写完代码，而萌新 FoolMike 却需要花 $d_{i}$ 分钟帮助 GodCowC 完成这道题。当然二人提交代码的时间可以忽略了。

注意：

• 一个人写一道题必须是连续的，教另一个人题用时也必须是连续的。
• 一个人教另一个人做题时，两个人都不能做其他事情了。

两人都想要 AK 这次比赛，于是他们希望罚时较多的那个人罚时最少。鉴于两人都是写过相关题目的 OIer，二人都不会有错误提交。神犇 GodCowC 当然一眼就知道最优策略是什么了，但是他想考考你。

【输入格式】

第一行一个整数 $n$，表示题目的数量。

接下来 $n$ 行，每行四个整数，分别是 $a_{i},b_{i},c_{i},d_{i}$，含义如【题目描述】。

【输出格式】

一行一个整数，表示罚时较多的那个人罚时的最小值，按分钟计算。

【样例 1】

ex_atcoder1.in

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

ex_atcoder1.ans

30

样例解释

比赛过程大致是这样的。

GodCowC 花 $9$ 分钟刚掉了第 $4$ 题，发现这是个思维题，猜出来结论就秒掉了，想教教 FoolMike。

FoolMike 依次开第 $2$ 题，第 $5$ 题，总用时也是 $9$ 分钟。

这时比赛开始 $9$ 分钟了，二人同时切完了手上的题。开黑中……

GodCowC 花 $1$ 分钟教会了 FoolMike 第 $4$ 题。

这时比赛开始 $10$ 分钟了。

接着二人又开始切题。

GodCowC 依次开了第 $2$ 题，第 $5$ 题，总用时 $10$ 分钟。

FoolMike 开了第 $1$ 题，第 $3$ 题，总用时 $9$ 分钟，已经 AK 了比赛。

这时比赛开始 $20$ 分钟了，继续开黑……

口齿不清的 FoolMike 花了 $5$ 分钟教会了 GodCowC 第 $1$ 题，又花了 $5$ 分钟教会了 GodCowC 第 $3$ 题，和 GodCowC 讲题的效率相差甚远，被 GodCowC 批判了一番。

这时比赛开始 $30$ 分钟了，二人都 AK 了比赛。罚时较多的 GodCowC 的罚时是 $30$ 分钟。

可以证明，不存在更优的策略，因此答案是 $30$。

【样例 2】

ex_atcoder2.in

9
2 14 17 4 
19 10 2 5 
6 10 19 13 
14 3 4 15 
12 18 2 17 
9 11 17 15 
5 11 20 15 
4 8 3 9 
20 7 13 19

ex_atcoder2.ans

81

【样例 3】

参见样例数据下载。

【数据范围】

**读入数据中的 $a_{i},b_{i},c_{i},d_{i}$ 都是在值域中随机生成的。**这可能对程序的效率产生影响。

数据中的数均为正整数。

测试点编号	$n$	$a_{i},b_{i},c_{i},d_{i}$
$1, 2$	$\leq 5$	$\leq 10$
$3, 4$	$ \leq 10$	$\leq 20$
$5, 6$	$\leq 16$
$7, 8$	$\leq 20$
$9, 10, 11, 12$	$\leq 50$
$13, 14$	$\leq 16$	$\leq 500$
$15, 16, 17, 18, 19, 20$	$\leq 500$

请注意常数因子对程序效率带来的影响。