Sum

• 时间限制：1.5 秒
• 内存限制：512 MiB

题目描述

有 $n$ 个序列。第 $i$ 个序列包含 $t_i$ 个非负整数 $a_{i,1},a_{i,2},\ldots,a_{i,t_i}$，并且序列中的数按不降顺序排列。

你需要恰好选择 $k$ 个数。对于每个序列，选择的数必须构成它的一个前缀：如果选择了 $a_{i,j}$，那么 $a_{i,1},\ldots,a_{i,j-1}$ 也都必须被选择。

求所选数字之和的最大值。

输入格式

第一行包含两个整数 $n,k$。

接下来 $n$ 行，第 $i$ 行先给出整数 $t_i$，随后给出 $t_i$ 个整数 $a_{i,1},\ldots,a_{i,t_i}$。

保证每个序列均按不降顺序排列。

输出格式

输出一个整数，表示恰好选择 $k$ 个数时的最大总和。

样例输入 1

3 3
2 5 10
3 1 2 3
2 1 20

样例输出 1

26

数据范围

$1\le n,k\le3000$，$1\le t_i$，$0\le a_{i,j}\le10^8$，$\sum t_i\le10^6$，且 $k\le\sum t_i$。