P1107 [BJWC2008] Lei Tao's Kitten

原最大整数参见 P1012

Lei Tao is very compassionate. In his dormitory, he keeps a kitten that was rescued after being injured (of course, this violates the student dormitory management regulations). Under his care, the kitten quickly recovered and became even more lively and adorable. But one day, after class, Lei Tao returned to his room and found that the kitten was missing! After searching for a while, he discovered that she was lying on the balcony, staring blankly at the persimmon tree outside the window. There are many persimmon trees on the campus of Peking University, and there are $N$ of them right in front of Lei Tao’s dorm building. All these $N$ persimmon trees have the same height $H$. As the cold of winter gradually spreads over the land, the leaves on the trees fall off, leaving only the golden persimmons, which look very tempting. It just so happens that Lei Tao’s kitten loves to eat persimmons. Seeing the persimmons on the trees outside the window, she became very eager, and decided to use her agile jumping ability to jump onto the trees to eat persimmons. The kitten can jump from the dormitory balcony to the top of any tree outside. After that, each time she can jump downward along the current tree by 1 unit of distance. Of course, her abilities are not limited to this—she can also jump between trees. Each time she can jump from the current tree to any other one, and in this process her height decreases by `Delta` units. At any moment, if there is a persimmon at her current position, she can eat it. The entire "persimmon-eating operation" continues until the kitten reaches the ground. The figure shows an example with $N=3, H=10, Delta=2$. Following the route shown in the figure, the kitten can eat at most 8 persimmons. 

The first line contains three integers separated by spaces, representing $N, H, Delta$. The next $N$ lines each begin with an integer $N_i$, representing the number of persimmons on the $i$-th tree. Then follow $N_i$ integers, where each integer $T_{i,j}$ indicates that there is a persimmon at height $T_{i,j}$ on the $i$-th tree.

Output a single integer: the maximum number of persimmons the kitten can eat.

Constraints and Notes For all testdata, $1 \leq N, H \leq 2000$, $0 \leq N_i \leq 5000$, $1 \leq Delta \leq H, 1 \leq T_{i,j} \leq H$. The input file size is no more than 40 MB. Pay attention to I/O efficiency. Source: Excalibur, 2008. Translated by ChatGPT 5