狗卡

题目信息

时间限制: 1s

空间限制: 256M

输入文件: dog.in

输出文件: dog.out

题目描述

zzy 的农场里有一只小狗叫小卡。大家都喜欢叫他狗卡。
狗卡开发了一款 蒸蒸日上 的游戏，它会出很多武将并诱导人们氪金购买。
游戏 蒸蒸日上，但是狗卡已经出完了所有三国时期的人物，于是它想出了一个办法，将武将升级并当作一个新武将卖出！
比如赵云这个武将，狗卡可以设计 界赵云、群赵云、sp赵云、神赵云、族赵云、武赵云，并继续吸引人们氪金……
狗卡想要知道他最多能吸引多少人氪金，并寻求你的帮助。

游戏中有 $n$ 个武将，一开始并不会吸引人氪金，我们认为每个武将一开始都是 $0$ 级。

每个武将可以升级若干次，每升级一次，这个武将会每天会多吸引 $1$ 个人氪金。也就是说如果一个武将被升级过 $x$ 次，那么这个武将就会每天吸引 $x$ 个人氪金。

需要注意的是，一个人物必须按顺序升级，因为如果你先设计出神武将售卖，就没有人想买界武将了。

设计武将升级需要一定时间，第 $i$ 个武将升第 $j$ 次级需要 $a_{i,j}$ 天，狗卡同时只能设计一个武将。在一个武将从 $x$ 级升到 $x+1$ 级期间它仍然会每天吸引 $x$ 个人氪金。

它想知道当第 $m$ 天后游戏倒闭时最多能吸引多少人氪金。

由于狗卡正在蒸蒸日上，所以游戏会存在很长时间，保证 $m \ge 10^{10}$

输入格式

第一行两个整数 $n,m$。

接下来 $n$ 行，每行第一个整数 $k_i$ ，代表这个武将可以升级的次数，接下来 $k_i$ 个整数，第 $j$ 个整数是 $a_{i,j}$。

输出格式

一行一个整数，代表狗卡能吸引多少人氪金。

样例

样例输入 #1

2 10000000000
2 2 1
2 1 2

样例输出 #1

39999999986

样例输入 #2

5 10000000000
2 5 4
2 4 4
2 3 3
2 2 1
2 1 5

样例输出 #1

99999999861

数据范围与提示

本题采用捆绑测试

对于 $100\%$ 的数据，满足：$1\le n\le 6\times10^5$，$\sum{k_i}\le1.2\times10^6$，$10^{10}\le m\le10^{11}$，$k_i\ge2$，$0\le a_{i,j}\le5\times10^3$

特殊性质 A: $\forall 1\le i\le n,2\le j\le k_i,a_{i,j}\ge a_{i,j-1}$

特殊性质 B: $\forall 1\le i\le n,2\le j\le k_i,a_{i,j}\le a_{i,j-1}$

特殊性质 C: $\forall 1\le i\le n,k_i=2$