防御法阵
题号：NC229312
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

牛牛悄悄溜进了敌人的阵地，准备破坏敌人的城墙和防御法阵，破坏防御法阵可以给牛牛带来经验值。
敌人的城墙分为  块，这些城墙排成一排，不成环。牛牛可以破坏  块城墙，他可以从任意一点开始不断破坏两侧相邻的城墙。
每块城墙下方刻有诸多防御法阵。每个法阵需要耗费不同的时间来破坏。同时，为了防止对手发现，牛牛在每块城墙下仅能停留  秒。经过的时间忽略不计。
破坏每个法阵会带来不同的经验值。并且，当相邻的城墙已经被破坏时，经验值会增加。
举例来讲，假设牛牛在某块城墙收获  点经验值，但该城墙一侧（按照破坏顺序的规则，显然只有一侧可能被破坏）收获经验值为，
那么这块城墙的经验数变为 。而当某块城墙一侧有n块城墙被破坏，其实际收获的经验值为 
一段城墙得到的经验值为这一段城墙中每一段得到的经验值之和。
显然，最终的经验值还和破坏顺序有关。
现在，牛牛想知道他能得到的经验值最大是多少。

Note:上述的k_1,k_2,...,k_n是指城墙左侧（或右侧）连续n个城墙被破坏时获得的经验值。

输入描述:

第一行三个整数 ，含义见题目描述。
接下来  行，每行首先有正整数  表示该块城墙下方的法阵数量，接下来  个正整数，依次是第  个法阵破坏后的经验值 ，第  法阵破坏的用时 。
第  个法阵破坏后的经验值和破坏用时，直到第  个法阵。

输出描述:

一个正整数，表示牛牛能够得到的最大经验值。
示例1

输入

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

输出

复制 
52

说明

城墙共5段，每段在5秒内破坏，不计相邻城墙的破坏效果加成的情况下，依次能收到最多9,3,9,5,6点经验值。破坏3段，此时选择先破坏中间的城墙获得9点经验值，再依次获得5,6点经验值，最终能够造成最大52点经验值。计算过程如下9+(9+5)+[(9+9+5)+6]=52
示例2

输入

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

输出

复制 
223

备注:

对于  的数据，满足 
对于另外  的数据，满足 
对于额外 的数据，满足 
对于  的数据，满足

保证答案在long long int范围内