2745.D - 打砖块

## 题目描述

有$N$个砖块排成一排，计算鸭通过敲击的形式破坏$M$块砖块，他可以从任意一点开始不断破坏两侧相邻的砖块。

除此以外，每个砖块下方还有诸多任务，每个任务需要花费不同的时间来完成，同时，为节约时间，计算鸭在每个砖块下仅能停留TT秒。砖块之间移动的时间忽略不计。

当然计算鸭完成每个任务会带来不同的$\texttt{KPI}$，并且，当相邻的砖块已经被破坏时，其$\texttt{KPI}$会增加。

例如，假设计算鸭在某块砖块下收获$k$点$\texttt{KPI}$，但该砖块一侧（按照破坏顺序的规则，显然只有一侧可能被破坏）收获$\texttt{KPI}$为$k_1$，那么这块砖块的$\texttt{KPI}$变为$k+k_1$。而当某块砖块一侧有$n$块砖块被破坏，其实际收获的$\texttt{KPI}$为$k+k_1+k_2+...+k_n$。

一段砖块得到的$\texttt{KPI}$为这一段砖块中每一个砖块得到的$\texttt{KPI}$之和。

显然，最终的$\texttt{KPI}$还和破坏顺序有关。

现在，计算鸭想知道他能得到的$\texttt{KPI}$最大是多少。

## 输入格式

输入的第一行给出三个整数$N,M,T$，含义见题目描述。

接下来输入$N$行，每行首先有正整数$K$表示该块砖块下方的存在的任务数量，接下来$2K$个正整数，依次是第$1$个任务完成后的$\texttt{KPI}v_i$，第$1$个任务完成的用时$t_i$。 第$2$个任务完成后的获得的$\texttt{KPI}$和完成用时......直到第$K$个任务。

对于$20\%$的数据，满足$K=1$

对于另外$20\%2$的数据，满足$M=1$

对于额外$20\%$的数据，满足$M\le3,K\le5$

对于$100\%$的数据，满足：

$0<K\le30$,

$0<T\le200$,

$0<M<30$,

$0<N<10000$，

$0<v_i,t_i\le50$

保证答案在$long \ long \ int$范围内。

## 输出格式

输出一个正整数，表示计算鸭能够得到的最大$\texttt{KPI}$

## 输入
```in1
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
```

## 输出
```out1
52
```

## 提示