[BeijingWc2008]雷涛的小猫

雷涛同学在宿舍里养了一只因受伤而被救助的小猫。小猫恢复健康后变得十分活泼可爱，但有一天，雷涛发现小猫跑到了阳台上，正对着窗外的柿子树发呆。

雷涛所在的宿舍楼前有 $N$ 棵柿子树，每棵树的高度均为 $H$。冬天来临后，树叶渐渐落尽，只剩下许多柿子。小猫非常喜欢吃柿子，于是决定利用敏捷的跳跃能力到树上去吃柿子。

小猫可以从宿舍阳台跳到任意一棵柿子树的树顶。之后，她可以沿着当前所在的树向下跳跃 $1$ 个单位的距离。她还可以在树之间跳跃：每次都能从当前所在的树跳到另外任意一棵树，但在跳跃过程中高度会下降 $\Delta$ 个单位。

在任意时刻，只要小猫所在的位置有柿子，她就可以将其吃掉。整个行动会一直持续到小猫落到地面为止。

请计算小猫从阳台出发后最多能吃到多少个柿子。

输入格式

第一行包含三个整数 $N$、$H$ 和 $\Delta$。

接下来 $N$ 行，每行首先包含一个整数 $N_i$，表示第 $i$ 棵树上柿子的数量；随后包含 $N_i$ 个整数 $T_{i,j}$，表示第 $i$ 棵树高度为 $T_{i,j}$ 的位置上有一个柿子。

输出格式

输出一个整数，表示小猫最多能吃到的柿子数量。

样例输入

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

样例输出

8

数据范围

• $1\le N,H\le 2000$；
• $0\le N_i\le 5000$；
• $1\le \Delta\le N$；
• $1\le T_{i,j}\le H$；
• 输入文件大小不超过 $40960\text{ KB}$。

来源与许可

本题为 BeijingWc 2008 试题「雷涛的小猫」，题面与测试数据整理自 BZOJ 1270。

样例 1

输入

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

输出

8