#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