题号：NC54756
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
从前有一位聚聚zn带着挂件wnm游历中国的各个宝地,只要通过了宝地守护神的考验,就能获得丰厚的金钱奖励和无穷无尽的小姐姐，每次zn聚聚都凭借强悍的实力和过硬的心里素质带着挂件wnm通过考验，但这一次却让zn聚聚犯了难。
宝地守护神的考验是这样的:现在有`n`块能量宝石，每块宝石都蕴含着能量,能量是由一个二元组构成`)
`,而这些宝石是可以融合的，并且在融合的过程中会释放出大量的能量(只有相邻的宝石可以融合)。融合规则是：存在两个相邻的宝石`%E5%92%8C(a_2%2Cb_2))
`,如果融合这两个宝石,宝石就会变成`)
`并释放出`
`的能量,现在要找到融合成一块宝石并且产生能量最大的方案。
宝地守护神的考验是这样的:现在有`n`块能量宝石，每块宝石都蕴含着能量,能量是由一个二元组构成`
这个问题对于zn聚来说当然轻松解决，但是宝地守护神却要两个人都解决这个问题才能得到奖励,并且守护神对wnm增加了考验的难度，wnm需要从n个宝石里选择一段连续的区间进行增幅，增幅是让宝石的能量乘上k倍，即`(x,y)`会变成`(kx,ky)`，缺少了pjb聚聚的帮助，zn陷入了麻烦，好在wnm可以作弊,他找到了聪明的你，你能帮助他们得到金钱和小姐姐吗?
输入描述:
第一行有2个整数``
接下来有n行 每一行有两个整数``
输出描述:
输出一个整数表示所能产生的最大能量。
备注:
n块宝石最后要融合成1块。