#397. 园艺

园艺

说明


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

徐老师将所有的  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