该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

这几天徐老师对培养盆栽很感兴趣，于是他想搭建一个温室来满足他的研究欲望。

徐老师将所有的  n  株盆栽都放在新建的温室里，所以所有盆栽都处于完全相同的环境中。

每一株盆栽都有一个最佳生长温度区间   [l,r]  ，在这个范围的温度下生长会生长得最好，但是不一定会提供最佳的研究价值（徐老师认为研究发育不良的盆栽也是很有研究价值的）。

徐老师进行了若干次试验，发现若第  i  株盆栽的生长温度适宜，可以提供  ai  的研究价值；若生长温度超过了适宜温度的上限，能提供  bi  的研究价值；若生长温度低于适宜温度的下限，则能提供  ci  的研究价值。

现在通过试验，徐老师已经得知了每一株盆栽的适宜生长温度范围，也知道了它们的  a, b, c  的值。你需要根据这些信息，给温室选定一个温度（这个温度可以是任意实数），使得徐老师能获得的研究价值最大。
</p>

输入格式

第一行输入一个整数  n(1 <= n <= 10^4)  ，表示盆栽数量。

接下来  n  行，每行五个整数  1<=li, ri, ai, bi, ci<=10^4 ，其中  (li <= ri) ，意义如上所述。

输出格式

样例

5
5 8 16 20 12
10 16 3 13 13
8 11 13 1 11
7 9 6 17 5
2 11 20 8 5

83