While switching buildings, he loses height $\boldsymbol{I}$ while jumping.

The second restriction is explained below with an example.

Assume $I=2$. Now Superman is in the 2^{nd} building 5^{th} floor ($B=2$, $F=5$). If he wants to switch to the fifth building ($B=5$), he will lose height ($I=2$), which means he will be at floor 3 at building 5 ($B=5$, $F=3$). He can jump freely from the current floor to the floor below on the same building . That is, suppose if he is at $(B=5,F=4)$, he can go to $(B=5,F=3)$ without any restrictions. He cannot skip a floor while jumping in the same building. He can go to the floor below the current floor of the same building or use his jumping power, switch building, and lose height $\boldsymbol{I}$.

Given the information about the occupied floors in each of the $N$ buildings, help Superman to determine the maximum number of people he can save in one single drop from the top to the bottom floor with the given restrictions.

Input Format

Input starts with three values:  the number of buildings $N$, the height of the buildings $\mbox{H}$, and the height Superman will lose when he switches buildings $\boldsymbol{I}$.

These are followed by $N$ lines. Each $i^{\mbox{th}}$ line starts with a non negative integer $\mbox{u}$ indicating how many people are in the $i^{\mbox{th}}$ building. Each of the following $\mbox{u}$ integers indicates that a person is at height $u_i$ in the $i^{\mbox{th}}$ buiding. Each of the following $\mbox{u}$ integers are given and repetitions are allowed which means there can be more than one person in a floor.

$\boldsymbol{i}$ indicates building number and $j$ indicates floor number. Building number will not be given; since $N$ lines follow the first line, you can assume that the $i^{\mbox{th}}$ line indicates the $i^{\mbox{th}}$ building's specifications.

Constraints 

$1\leq H,N\leq1900$ 

$1\leq I\leq450$ 

$0\leq u\leq1900$ (for each $\boldsymbol{i}$, which means the maximum number of people in a particular building will not exceed $\textbf{1900}$) 

$1\leq u_{ij}\leq H$

Output Format

Output the maximum number of people Superman can save.

Sample Input
4 15 2 
5 1 1 1 4 10
8 9 5 7 7 3 9 8 8
5 9 5 6 4 3
0   

Sample Output
12

Explanation

Input starts with $N=4$, $H=15$, $I=2$ .

$N$ lines follow. Each line describes building $\boldsymbol{i}$.

Each line begins with $\mbox{u}$, which denotes the number of persons in a particular building, followed by floor number, where each person resides. Floor number can repeat as any number of people can reside on a particular floor.  

I've attached a figure here to explain the sample test case.  

You can verify the first building's specifications with the figure. 

$u=5$ (Total number of persons in the first building), followed by 1 1 1 4 10(Floor numbers). 

$1\mbox{st}$ floor = 3 persons.

$4th$ floor = 1 person.

$10th$ floor = 1 person. 

Similarly, the specifications for the other three buildings follow. 

The connected line shows the path which Superman can use to save the maximum number of people. In this case, that number is $12$.

You can also note in the figure that when he switches from Building 2 to Building 3, he loses height $\boldsymbol{I}$ ($I=2$). Similarly, when he switches from Building 3 to Building 1 ,the same height loss happens as mentioned in the problem statement.

Difficulty: MEDIUM_HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
(n, h, drop) = map(int, input().split())
a = [[0] * (h + 1) for _ in range(n)]
for i in range(n):
	tmp = list(map(int, input().split()))[1:]
	for j in tmp:
		a[i][j] += 1
dp = [[0] * (h + 1) for _ in range(n)]
opt = [0] * (h + 1)
for i in range(1, h + 1):
	for j in range(n):
		dp[j][i] = dp[j][i - 1] + a[j][i]
		if i >= drop:
			dp[j][i] = max(dp[j][i], opt[i - drop] + a[j][i])
		opt[i] = max(opt[i], dp[j][i])
print(opt[h])


import sys

def solve(B, I):
	R = [[0 for _ in f] for f in B]
	for h in range(len(B)):
		if h < I:
			m = 0
		else:
			m = max(R[h - I])
		for b in range(len(B[h])):
			R[h][b] = max(R[h - 1][b], m) + B[h][b]
	return max(R[-1])
(N, H, I) = (int(_) for _ in input().split())
B = [[0 for _ in range(N)] for _ in range(H)]
for b in range(N):
	U = tuple((int(_) for _ in input().split()))
	for u in U[1:]:
		B[u - 1][b] += 1
print(B, file=sys.stderr)
print(solve(B, I))


from collections import defaultdict

def solve(buildings, n, height, jump):
	can_save_prev = [0] * n
	best_per_height = [0]
	for h in range(1, height + 1):
		can_save_now = 0
		if jump >= h:
			can_save_other_building = 0
		else:
			can_save_other_building = best_per_height[-jump]
		for (i, b) in enumerate(buildings):
			prev = max(can_save_prev[i], can_save_other_building)
			can_save_prev[i] = prev + b[h]
			can_save_now = max(can_save_prev[i], can_save_now)
		best_per_height.append(can_save_now)
	return best_per_height[-1]
(n, h, i) = [int(s) for s in input().split()]
buildings = []
for _ in range(n):
	(_, *floors) = [int(s) for s in input().split()]
	b = defaultdict(int)
	for f in floors:
		b[f] += 1
	buildings.append(b)
print(solve(buildings, n, h, i))


def main():
	(bldgs, hite, hiteloss) = readints()
	floors = [[0] * bldgs for _ in range(hite)]
	for bnum in range(bldgs):
		(npeeps, *peeps) = readints()
		assert npeeps == len(peeps)
		for peep in peeps:
			floors[peep - 1][bnum] += 1
	best = []
	prevfloorbest = [0] * bldgs
	for floor in range(hite):
		if floor < hiteloss:
			floorbest = [here + down for (here, down) in zip(floors[floor], prevfloorbest)]
		else:
			jumpgain = best[floor - hiteloss]
			floorbest = [here + max(down, jumpgain) for (here, down) in zip(floors[floor], prevfloorbest)]
		prevfloorbest = floorbest
		best.append(max(floorbest))
	print(best[-1])

def readints():
	return [int(fld) for fld in input().split()]
main()


def maxSaved(people, B, H, I):
	P = [people[0]]
	for h in range(1, I):
		P.append([P[h - 1][b] + people[h][b] for b in range(B)])
	for h in range(I, H):
		maxjump = max(P[h - I])
		P.append([people[h][b] + max(maxjump, P[h - 1][b]) for b in range(B)])
	return max(P[-1])
(B, H, I) = map(int, input().split())
H += 1
people = [[0] * B for h in range(H)]
for building in range(B):
	person_floor = map(int, input().split())
	next(person_floor)
	for floor in person_floor:
		people[floor][building] += 1
print(maxSaved(people, B, H, I))


from copy import deepcopy
(N, H, I) = (int(x) for x in input().split())
buildings = []
for i in range(N):
	p = [int(x) for x in input().split()]
	building = [0] * H
	for item in p[1:]:
		building[item - 1] += 1
	buildings.append(building)
building_sums = deepcopy(buildings)
for i in reversed(range(H - I, H - 1)):
	for building in building_sums:
		building[i] += building[i + 1]
for i in reversed(range(H - I)):
	max_i_up = 0
	for (index, building) in enumerate(building_sums):
		current_i_up = building[i + I]
		if current_i_up > max_i_up:
			max_i_up = current_i_up
	for (target_index, target_building) in enumerate(buildings):
		target_sum = building_sums[target_index][i + 1] + target_building[i]
		max_other_sum = max_i_up + target_building[i]
		if target_sum > max_other_sum:
			max_sum = target_sum
		else:
			max_sum = max_other_sum
		building_sums[target_index][i] = max_sum
final_sums = []
for L in building_sums:
	final_sums.append(L[0])
print(max(final_sums))


(n, h, i) = input().split()
n = int(n)
h = int(h)
i = int(i)
b = [[0 for j in range(0, h)] for j in range(0, n)]
for k in range(0, n):
	l = input().split()
	for m in range(0, int(l[0])):
		b[k][int(l[m + 1]) - 1] += 1
for level in range(0, h):
	if level > 0:
		twoprev = 0
		if level >= i:
			for j in range(0, n):
				if b[j][level - i] > twoprev:
					twoprev = b[j][level - i]
		for j in range(0, n):
			if level >= i and b[j][level - 1] < twoprev:
				b[j][level] += twoprev
			else:
				b[j][level] += b[j][level - 1]
absmax = 0
for j in range(0, n):
	if absmax < b[j][h - 1]:
		absmax = b[j][h - 1]
print(absmax)


(num_buildings, height, jump) = [int(c) for c in input().split()]
M = [[0 for i in range(num_buildings)] for k in range(height + 1)]
M_dp = [[0 for i in range(num_buildings)] for k in range(height + 1)]
dp = [0 for i in range(height + 1)]
for i in range(num_buildings):
	A = [int(c) for c in input().split()]
	n = A[0]
	floor_numbers = A[1:]
	for floor in floor_numbers:
		M[floor][i] += 1
dp[1] = max(M[1])
for h in range(1, jump + 1):
	M_dp[h] = [M[h][i] + M_dp[h - 1][i] for i in range(num_buildings)]
	dp[h] = max(M_dp[h])
for h in range(jump + 1, height + 1):
	M_dp[h] = [max(M[h][i] + M_dp[h - 1][i], M[h][i] + dp[h - jump]) for i in range(num_buildings)]
	dp[h] = max(M_dp[h])
print(dp[height])


(n, h, i) = [int(i) for i in input().split()]
buildings = list()
for b in range(n):
	(pop, *floors) = list(map(int, input().split()))
	cur_building = [0] * h
	for f in floors:
		cur_building[f - 1] += 1
	buildings.append(cur_building)
count_of_humans_on_floor = list()
for floor in range(h):
	c_h_f = list()
	for b in buildings:
		c_h_f.append(b[floor])
	count_of_humans_on_floor.append(c_h_f)
saved = list()
max_saved_on_floor = list()
saved.append(count_of_humans_on_floor[0])
max_saved_on_floor.append(max(saved[0]))
for floor in range(1, min(i, h)):
	new_saved = count_of_humans_on_floor[floor].copy()
	for b in range(n):
		new_saved[b] += saved[floor - 1][b]
	max_saved_on_floor.append(max(new_saved))
	saved.append(new_saved)
for floor in range(i, h):
	new_saved = count_of_humans_on_floor[floor].copy()
	for b1 in range(n):
		new_saved[b1] += max(saved[floor - 1][b1], max_saved_on_floor[floor - i])
	max_saved_on_floor.append(max(new_saved))
	saved.append(new_saved)
max_saved = max(saved[-1])
print(max_saved)


(N, H, I) = [int(i) for i in input().split()]
buildings = [[0 for j in range(N)] for i in range(H)]
for _ in range(N):
	for item in [int(i) for i in input().split()][1:]:
		buildings[item - 1][_] += 1
for i in range(1, I):
	for j in range(N):
		buildings[i][j] = buildings[i][j] + buildings[i - 1][j]
for i in range(I, H):
	add2 = max(buildings[i - I])
	for j in range(N):
		val = buildings[i][j]
		buildings[i][j] = max(val + buildings[i - 1][j], val + add2)
print(max(buildings[-1]))


(N, H, I) = [int(x) for x in input().split()]
a = [[0] * N for _ in range(H + 1)]
for n in range(N):
	people = [int(x) for x in input().split()]
	for h in people[1:]:
		a[h][n] += 1
maxa = [(0, 1)]
DP = [[0] * N for _ in range(H + 1)]
for h in range(1, H + 1):
	for n in range(N):
		if h - I > 0 and DP[h - 1][n] < maxa[h - I][0]:
			DP[h][n] = a[h][n] + DP[h - I][maxa[h - I][1]]
		else:
			DP[h][n] = a[h][n] + DP[h - 1][n]
	maxa.append(max(((m, i) for (i, m) in enumerate(DP[h]))))
print(max(DP[-1]))


(n, h, i) = input().split()
n = int(n)
h = int(h)
i = int(i)
b = [[0 for j in range(0, h)] for j in range(0, n)]
for k in range(0, n):
	l = input().split()
	for m in range(0, int(l[0])):
		b[k][int(l[m + 1]) - 1] += 1
for level in range(0, h):
	if level > 0:
		twoprev = 0
		if level >= i:
			for j in range(0, n):
				if b[j][level - i] > twoprev:
					twoprev = b[j][level - i]
		for j in range(0, n):
			if level >= i and b[j][level - 1] < twoprev:
				b[j][level] += twoprev
			else:
				b[j][level] += b[j][level - 1]
absmax = 0
for j in range(0, n):
	if absmax < b[j][h - 1]:
		absmax = b[j][h - 1]
print(absmax)


def get_max_from_top(max_saved, level, building):
	if level + 1 < len(max_saved):
		return max_saved[level + 1][building]
	else:
		return 0

def get_max_from_level(max_saved, level, step):
	if level + step < len(max_saved):
		return max(max_saved[level + step])
	else:
		return 0

def find_max_saves(people_locations, step):
	levels = len(people_locations)
	buildings = len(people_locations[0])
	max_saved = [[0 for j in range(buildings)] for i in range(levels)]
	for level in reversed(range(levels)):
		side = get_max_from_level(max_saved, level, step)
		for building in range(buildings):
			current = people_locations[level][building]
			top = get_max_from_top(max_saved, level, building)
			max_saved[level][building] = current + max(top, side)
	return max(max_saved[0])
(n, h, i) = (int(x) for x in input().split())
people = [[0 for j in range(n)] for i in range(h)]
for building in range(n):
	(_, *floors) = [int(x) for x in input().split()]
	for floor in floors:
		people[floor - 1][building] = people[floor - 1][building] + 1
print(find_max_saves(people, i))


def main():
	(N, H, I) = map(int, input().split())
	people = [[0 for i in range(H + 1)] for j in range(N)]
	dp = [[0 for i in range(H + 1)] for j in range(N)]
	for i in range(N):
		(u, *temp) = input().split()
		for j in temp:
			people[i][int(j)] += 1

	def iterative():
		maximum = []
		for h in range(H + 1):
			m = -1
			for b in range(N):
				if h - I >= 0:
					dp[b][h] = max(maximum[h - I], dp[b][h - 1])
				elif h - 1 >= 0:
					dp[b][h] = dp[b][h - 1]
				else:
					dp[b][h] = 0
				dp[b][h] += people[b][h]
				m = max(m, dp[b][h])
			maximum.append(m)
		return maximum[-1]
	print(iterative())
main()


(N, H, I) = [int(i) for i in input().split()]
buildings = [[0 for j in range(N)] for i in range(H)]
for _ in range(N):
	for item in [int(i) for i in input().split()][1:]:
		buildings[item - 1][_] += 1
for i in range(1, I):
	for j in range(N):
		buildings[i][j] = buildings[i][j] + buildings[i - 1][j]
for i in range(I, H):
	add2 = max(buildings[i - I])
	for j in range(N):
		val = buildings[i][j]
		buildings[i][j] = max(val + buildings[i - 1][j], val + add2)
print(max(buildings[-1]))


(N, H, I) = [int(x) for x in input().split()]
occupants = [[0] * (H + 1) for _ in range(N)]
for building in range(N):
	[_, *floors] = [int(x) for x in input().split()]
	for floor in floors:
		occupants[building][floor] += 1
max_rescued = occupants
for floor in range(1, H + 1):
	prev_floor = floor - I
	if prev_floor > 0:
		best_with_jump = max((max_rescued[b][prev_floor] for b in range(N)))
	else:
		best_with_jump = 0
	for building in range(N):
		max_rescued[building][floor] += max(best_with_jump, max_rescued[building][floor - 1])
print(max((max_rescued[b][H] for b in range(N))))


(N, H, I) = map(int, input().rstrip().split())
U = {}
for i in range(N):
	U[i] = {}
	for f in list(map(int, input().rstrip().split()))[1:]:
		U[i][f] = U[i].get(f, 0) + 1
dp = [[0] * (H + 1) for _ in range(N)]
dpmax = [0] * (H + 1)
for i in range(N):
	dp[i][H] = U[i].get(H, 0)
	if dp[i][H] >= dpmax[H]:
		dpmax[H] = dp[i][H]
for h in range(H - 1, 0, -1):
	for i in range(N):
		dp[i][h] = max(dp[i][h + 1], dpmax[h + I] if h + I <= H else 0) + U[i].get(h, 0)
		if dp[i][h] >= dpmax[h]:
			dpmax[h] = dp[i][h]
print(max((dp[i][1] for i in range(N))))


(n, h, d) = list(map(int, input().split()))
B = [[0 for _ in range(h + 1)] for _ in range(n)]
T = [[0 for _ in range(h + 1)] for _ in range(n)]
M = [0 for _ in range(h + 1)]
for i in range(n):
	(p, *lis) = list(map(int, input().split()))
	for x in lis:
		B[i][x] += 1
m = 0
for i in range(1, h + 1):
	down = 0 if i - d <= 0 else i - d
	m = 0
	for j in range(n):
		T[j][i] = max(M[down], T[j][i - 1]) + B[j][i]
		m = max(m, T[j][i])
	M[i] = m
print(m)


(N, H, I) = map(int, input().split())
a = [[0] * (H + I + 1) for _ in range(N)]
for p in range(N):
	for q in list(map(int, input().split()))[1:]:
		a[p][q] += 1
for h in range(H, 0, -1):
	m = max((a[p][h + I] for p in range(N)))
	for p in range(N):
		a[p][h] += max(a[p][h + 1], m)
print(max((a[p][1] for p in range(N))))


def get_maximum(result, building_data, n, h, current_pos, loss, max_floor):
	(x, y) = (current_pos[0], current_pos[1])
	a = building_data[x][y]
	b = 0
	c = 0
	if y - 1 >= 0:
		b = result[x][y - 1]
	if y - loss >= 0:
		c = max_floor[y - loss]
	if b > c:
		(b, c) = (c, b)
	a = a + c
	return a
(n, h, loss) = [int(i) for i in input().split()]
building_data = []
for _ in range(n):
	building = [0 for i in range(h)]
	for (index, person) in enumerate(input().split()):
		if index == 0:
			continue
		person = int(person)
		building[person - 1] = building[person - 1] + 1
	building_data.append(building)
result = [[0 for i in range(h)] for j in range(n)]
max_floor = [0 for i in range(h)]
maximum = -1
for i in range(h):
	current_height_max = -1
	for j in range(n):
		if i == 0:
			result[j][i] = building_data[j][i]
		else:
			result[j][i] = get_maximum(result, building_data, n, h, (j, i), loss, max_floor)
		if result[j][i] > maximum:
			maximum = result[j][i]
		if result[j][i] > current_height_max:
			current_height_max = result[j][i]
	max_floor[i] = current_height_max
print(maximum)


from collections import Counter
(n, h, l) = map(int, input().split())
b = []
saved = dict()
for i in range(n):
	line = list(map(int, input().split()))
	b.append(Counter(line[1:]))
for floor in range(h, 0, -1):
	beforejump = 0
	prev = [0 for _ in range(n)]
	if floor + l <= h:
		beforejump = max(saved[floor + l])
	if floor + 1 <= h:
		prev = saved[floor + 1]
	saved[floor] = [b[building][floor] + max(prev[building], beforejump) for building in range(n)]
	if floor + l <= h:
		saved.pop(floor + l)
print(max(saved[1]))


import sys
(n, h, i) = input().strip().split(' ')
(n, h, i) = [int(n), int(h), int(i)]
buildings = []
for build in range(n):
	people = [int(f_temp) for f_temp in input().strip().split()][1:]
	people_indexed = [0 for i in range(h)]
	for p in people:
		people_indexed[p - 1] += 1
	buildings.append(people_indexed)
max_people = [[0 for building in range(n)] for floor in range(h)]
floor_maxes = [0 for floor in range(h)]
for f in range(0, h):
	floor_num = h - f
	for b_ind in range(0, n):
		curr_p = buildings[b_ind][floor_num - 1]
		if floor_num < h:
			curr_up = max_people[floor_num][b_ind]
		else:
			curr_up = 0
		if floor_num < h - i + 1:
			other_up = floor_maxes[floor_num - 1 + i]
		else:
			other_up = 0
		max_people[floor_num - 1][b_ind] = curr_p + max(other_up, curr_up)
	floor_maxes[floor_num - 1] = max(max_people[floor_num - 1])
print(max(max_people[0]))


(N, H, I) = list(map(int, input().split()))
people = [[0] * N for h in range(H)]
for n in range(N):
	uu = map(int, input().split())
	u = next(uu)
	for h in uu:
		people[h - 1][n] += 1
maxpeople = [0] * H
curpeople = [0] * N
for h in range(H - 1, -1, -1):
	for n in range(N):
		if H - 1 - h >= I:
			curpeople[n] = max(curpeople[n], maxpeople[h + I]) + people[h][n]
		else:
			curpeople[n] = curpeople[n] + people[h][n]
	maxpeople[h] = max(curpeople)
print(maxpeople[0])


str = input().split()
n = int(str[0])
h = int(str[1])
ii = int(str[2])
b = [[0] * n for i in range(h)]
dp = [[0] * (n + 1) for i in range(h)]
for i in range(n):
	str = input().split()
	for j in range(1, len(str)):
		b[h - int(str[j])][i] += 1
for i in range(n):
	dp[0][i] = b[0][i]
	dp[0][n] = max(dp[0][n], dp[0][i])
for i in range(0, h - 1):
	for j in range(0, n):
		dp[i + 1][j] = dp[i][j] + b[i + 1][j]
		if i + 1 - ii >= 0:
			dp[i + 1][j] = max(dp[i + 1][j], dp[i + 1 - ii][n] + b[i + 1][j])
		dp[i + 1][n] = max(dp[i + 1][n], dp[i + 1][j])
print(dp[h - 1][n])


import logging
import sys
from collections import Counter
nivel_log = logging.ERROR

def imprime_edificios_parados(edificios):
	cadena = ''
	for idx_piso in range(len(edificios[0]) - 1, 0, -1):
		cadena += '\t'.join([str(edif[idx_piso]) for edif in edificios]) + '\n'
	return cadena

def supermono_mierda_core(edificios, brinco_deficit):
	max_edificios = 0
	salvados_dp = [[0] * len(edificios[0]) for _ in range(len(edificios))]
	primer_piso_dp = len(edificios[0]) - 1
	max_por_piso = [0] * (len(edificios[0]) + 1)
	for (idx, _) in enumerate(edificios):
		salvados_dp[idx][primer_piso_dp] = edificios[idx][primer_piso_dp]
	piso_invalidos = 1
	while piso_invalidos < brinco_deficit:
		for (idx, _) in enumerate(edificios):
			salvados_dp[idx][primer_piso_dp - piso_invalidos] += salvados_dp[idx][primer_piso_dp - piso_invalidos + 1] + edificios[idx][primer_piso_dp - piso_invalidos]
		piso_invalidos += 1
	primer_piso_dp -= piso_invalidos
	for idx_piso in range(len(edificios[0]) - 1, primer_piso_dp, -1):
		max_por_piso[idx_piso] = max([edificio[idx_piso] for edificio in edificios])
	for idx_piso in range(primer_piso_dp, 0, -1):
		for (idx_edificio, edificio) in enumerate(edificios):
			salvados_dp[idx_edificio][idx_piso] = max(salvados_dp[idx_edificio][idx_piso + 1], max_por_piso[idx_piso + brinco_deficit])
			salvados_dp[idx_edificio][idx_piso] += edificio[idx_piso]
		max_por_piso[idx_piso] = max([salvados[idx_piso] for salvados in salvados_dp])
	max_edificios = max([salvados[1] for salvados in salvados_dp])
	return max_edificios

def supermono_mierda_main():
	lineas = list(sys.stdin)
	edificios = []
	(num_edificios, altura, brinco_deficit) = [int(caca) for caca in lineas[0].strip().split(' ')]
	edificios = [[0] * (altura + 1) for _ in range(num_edificios)]
	for (idx_edificio, linea) in enumerate(lineas[1:]):
		personas = Counter(filter(lambda x: x, map(lambda mierda: int(mierda), linea.strip().split(' ')[1:])))
		for idx_piso in personas:
			edificios[idx_edificio][idx_piso] = personas[idx_piso]
	caca = supermono_mierda_core(edificios, brinco_deficit)
	print(caca)
FORMAT = '[%(filename)s:%(lineno)s - %(funcName)20s() ] %(message)s'
logging.basicConfig(level=nivel_log, format=FORMAT)
supermono_mierda_main()


(N, H, I) = map(int, input().split())
people = [[0] * N for i in range(H)]
for buil in range(N):
	nums = list(map(int, input().split()))
	assert nums[0] == len(nums) - 1
	for floor in nums[1:]:
		people[floor - 1][buil] += 1
saved = [[0] * N for i in range(H + I)]
for f in range(H - 1, -1, -1):
	temp = max(saved[f + I])
	for b in range(N):
		saved[f][b] = people[f][b] + max(saved[f + 1][b], temp)
print(max(saved[0]))


from collections import defaultdict
(n, h, i) = list(map(int, input().strip().split(' ')))
ludzie = []
for bud in range(n):
	inf = list(map(int, input().strip().split(' ')))
	ludzie.append(defaultdict(int))
	for pietro in inf[1:]:
		ludzie[bud][pietro] += 1
best = []
for bud in range(n + 1):
	best.append(defaultdict(int))
if i >= h:
	for floor in range(1, h + 1):
		for bud in range(n):
			best[bud][floor] = best[bud][floor - 1] + ludzie[bud][floor]
else:
	for floor in range(1, i + 1):
		for bud in range(n):
			best[bud][floor] = best[bud][floor - 1] + ludzie[bud][floor]
	for floor in range(i + 1, h + 1):
		bestSkok = 0
		for bud in range(n):
			bestSkok = max(bestSkok, best[bud][floor - i])
		for bud in range(n):
			best[bud][floor] = max(best[bud][floor - 1], bestSkok) + ludzie[bud][floor]
bestWynik = 0
for bud in range(n):
	bestWynik = max(bestWynik, best[bud][h])
print(bestWynik)


def superman_dp(ARR, I):
	dp = [[]] * len(ARR)
	max_l = [0] * len(ARR[0])
	for i in range(len(ARR)):
		dp[i] = [0] * len(ARR[0])
	for j in range(len(ARR[0])):
		if j == 0:
			for i in range(len(ARR)):
				dp[i][j] = ARR[i][j]
		elif j < I:
			for i in range(len(ARR)):
				dp[i][j] = dp[i][j - 1] + ARR[i][j]
		else:
			for i in range(len(ARR)):
				dp[i][j] = max(max_l[j - I], dp[i][j - 1]) + ARR[i][j]
		for i in range(len(ARR)):
			if dp[i][j] > max_l[j]:
				max_l[j] = dp[i][j]
	m = 0
	for i in range(len(ARR)):
		if dp[i][-1] > m:
			m = dp[i][-1]
	return m
(N, H, I) = list(map(int, input().strip().split(' ')))
ARR = [[]] * N
for i in range(N):
	ARR[i] = [0] * H
for i in range(N):
	arr = list(map(int, input().strip().split(' ')))
	for j in arr[1:]:
		ARR[i][j - 1] += 1
print(superman_dp(ARR, I))


import sys

def solve(B, I):
	R = [[0 for _ in f] for f in B]
	for h in range(len(B)):
		if h < I:
			m = 0
		else:
			m = max(R[h - I])
		for b in range(len(B[h])):
			R[h][b] = max(R[h - 1][b], m) + B[h][b]
	return max(R[-1])
(N, H, I) = (int(_) for _ in input().split())
B = [[0 for _ in range(N)] for _ in range(H)]
for b in range(N):
	U = tuple((int(_) for _ in input().split()))
	for u in U[1:]:
		B[u - 1][b] += 1
print(B, file=sys.stderr)
print(solve(B, I))


arr = list(map(int, input().split()))
N = arr[0]
H = arr[1]
I = arr[2]
if I > H:
	I = H
M = [[0 for x in range(H + 1)] for y in range(N)]
for i in range(N):
	arr = list(map(int, input().split()))
	arr.pop(0)
	for j in arr:
		M[i][j] += 1
saved = [[0 for x in range(H + 1)] for y in range(N)]
maxa = [0 for x in range(H + 1)]
for j in range(1, I + 1):
	for i in range(N):
		saved[i][j] = M[i][j] + saved[i][j - 1]
	maxa[j] = max([row[j] for row in saved])
for j in range(I + 1, H + 1):
	for i in range(N):
		saved[i][j] = M[i][j] + max(saved[i][j - 1], maxa[j - I])
	maxa[j] = max([row[j] for row in saved])
print(maxa[H])


(n, h, i) = [int(i) for i in input().split()]
buildings = list()
for b in range(n):
	(pop, *floors) = list(map(int, input().split()))
	cur_building = [0] * h
	for f in floors:
		cur_building[f - 1] += 1
	buildings.append(cur_building)
count_of_humans_on_floor = list()
for floor in range(h):
	c_h_f = list()
	for b in buildings:
		c_h_f.append(b[floor])
	count_of_humans_on_floor.append(c_h_f)
saved = list()
max_saved_on_floor = list()
saved.append(count_of_humans_on_floor[0])
max_saved_on_floor.append(max(saved[0]))
for floor in range(1, min(i, h)):
	new_saved = count_of_humans_on_floor[floor].copy()
	for b in range(n):
		new_saved[b] += saved[floor - 1][b]
	max_saved_on_floor.append(max(new_saved))
	saved.append(new_saved)
for floor in range(i, h):
	new_saved = count_of_humans_on_floor[floor].copy()
	for b1 in range(n):
		new_saved[b1] += max(saved[floor - 1][b1], max_saved_on_floor[floor - i])
	max_saved_on_floor.append(max(new_saved))
	saved.append(new_saved)
max_saved = max(saved[-1])
print(max_saved)


import sys

def solve(B, I):
	R = [[0 for _ in f] for f in B]
	for h in range(len(B)):
		if h < I:
			m = 0
		else:
			m = max(R[h - I])
		for b in range(len(B[h])):
			R[h][b] = max(R[h - 1][b], m) + B[h][b]
	return max(R[-1])
(N, H, I) = (int(_) for _ in input().split())
B = [[0 for _ in range(N)] for _ in range(H)]
for b in range(N):
	U = tuple((int(_) for _ in input().split()))
	for u in U[1:]:
		B[u - 1][b] += 1
print(solve(B, I))


import sys

def solve(B, I):
	R = [[0 for _ in f] for f in B]
	for h in range(len(B)):
		if h < I:
			m = 0
		else:
			m = max(R[h - I])
		for b in range(len(B[h])):
			R[h][b] = max(R[h - 1][b], m) + B[h][b]
	return max(R[-1])
(N, H, I) = (int(x) for x in input().split())
B = [[0 for _ in range(N)] for _ in range(H)]
for b in range(N):
	U = tuple((int(_) for _ in input().split()))
	for u in U[1:]:
		B[u - 1][b] += 1
print(B, file=sys.stderr)
print(solve(B, I))


(n, h, i) = input().split()
n = int(n)
h = int(h)
i = int(i)
b = [[0 for j in range(0, h)] for j in range(0, n)]
for k in range(0, n):
	l = input().split()
	for m in range(0, int(l[0])):
		b[k][int(l[m + 1]) - 1] += 1
for level in range(0, h):
	if level > 0:
		twoprev = 0
		if level >= i:
			for j in range(0, n):
				if b[j][level - i] > twoprev:
					twoprev = b[j][level - i]
		for j in range(0, n):
			if level >= i and b[j][level - 1] < twoprev:
				b[j][level] += twoprev
			else:
				b[j][level] += b[j][level - 1]
absmax = 0
for j in range(0, n):
	if absmax < b[j][h - 1]:
		absmax = b[j][h - 1]
print(absmax)


(n, h, i) = input().split()
n = int(n)
h = int(h)
i = int(i)
b = [[0 for j in range(0, h)] for j in range(0, n)]
for k in range(0, n):
	l = input().split()
	for m in range(0, int(l[0])):
		b[k][int(l[m + 1]) - 1] += 1
for level in range(0, h):
	if level > 0:
		twoprev = 0
		if level >= i:
			for j in range(0, n):
				if b[j][level - i] > twoprev:
					twoprev = b[j][level - i]
		for j in range(0, n):
			if level >= i and b[j][level - 1] < twoprev:
				b[j][level] += twoprev
			else:
				b[j][level] += b[j][level - 1]
absmax = 0
for j in range(0, n):
	if absmax < b[j][h - 1]:
		absmax = b[j][h - 1]
print(absmax)


entrada1 = input().split()
edificios = entrada1[0]
pisos = entrada1[1]
salto = entrada1[2]
pisosV = [[0] * (int(pisos) + 1) for _ in range(int(edificios))]
for i in range(int(edificios)):
	aux = list(map(int, input().split()))[1:]
	for j in aux:
		pisosV[i][j] += 1
personasE = [[0] * (int(pisos) + 1) for _ in range(int(edificios))]
personasS = [0] * (int(pisos) + 1)
for i in range(1, int(pisos) + 1):
	for j in range(int(edificios)):
		personasE[j][i] = personasE[j][i - 1] + pisosV[j][i]
		if i >= int(salto):
			personasE[j][i] = max(personasE[j][i], personasS[i - int(salto)] + pisosV[j][i])
		personasS[i] = max(personasS[i], personasE[j][i])
print(personasS[int(pisos)])


import sys

def solve(B, I):
	R = [[0 for _ in f] for f in B]
	for h in range(len(B)):
		if h < I:
			m = 0
		else:
			m = max(R[h - I])
		for b in range(len(B[h])):
			R[h][b] = max(R[h - 1][b], m) + B[h][b]
	return max(R[-1])
(N, H, I) = (int(_) for _ in input().split())
B = [[0 for _ in range(N)] for _ in range(H)]
for b in range(N):
	U = tuple((int(_) for _ in input().split()))
	for u in U[1:]:
		B[u - 1][b] += 1
print(B, file=sys.stderr)
print(solve(B, I))


(n, h, drop) = map(int, input().split())
a = [[0] * (h + 1) for _ in range(n)]
for i in range(n):
	tmp = list(map(int, input().split()))[1:]
	for j in tmp:
		a[i][j] += 1
dp = [[0] * (h + 1) for _ in range(n)]
opt = [0] * (h + 1)
for i in range(1, h + 1):
	for j in range(n):
		dp[j][i] = dp[j][i - 1] + a[j][i]
		if i >= drop:
			dp[j][i] = max(dp[j][i], opt[i - drop] + a[j][i])
		opt[i] = max(opt[i], dp[j][i])
print(opt[h])


entrada1 = input().split()
edificios = entrada1[0]
pisos = entrada1[1]
salto = entrada1[2]
pisosV = [[0] * (int(pisos) + 1) for _ in range(int(edificios))]
for i in range(int(edificios)):
	aux = list(map(int, input().split()))[1:]
	for j in aux:
		pisosV[i][j] += 1
personasE = [[0] * (int(pisos) + 1) for _ in range(int(edificios))]
personasS = [0] * (int(pisos) + 1)
for i in range(1, int(pisos) + 1):
	for j in range(int(edificios)):
		personasE[j][i] = personasE[j][i - 1] + pisosV[j][i]
		if i >= int(salto):
			personasE[j][i] = max(personasE[j][i], personasS[i - int(salto)] + pisosV[j][i])
		personasS[i] = max(personasS[i], personasE[j][i])
print(personasS[int(pisos)])


(n, h, i) = map(int, input().split())
a = [[0] * (h + 1) for _ in range(n)]
for j in range(n):
	tmp = list(map(int, input().split()))[1:]
	for k in tmp:
		a[j][k] += 1
dp = [[0] * (h + 1) for _ in range(n)]
opt = [0] * (h + 1)
for j in range(1, h + 1):
	for k in range(n):
		dp[k][j] = dp[k][j - 1] + a[k][j]
		if j >= i:
			dp[k][j] = max(dp[k][j], opt[j - i] + a[k][j])
		opt[j] = max(opt[j], dp[k][j])
print(opt[h])


(n, h, drop) = map(int, input().split())
a = [[0] * (h + 1) for _ in range(n)]
for i in range(n):
	tmp = list(map(int, input().split()))[1:]
	for j in tmp:
		a[i][j] += 1
dp = [[0] * (h + 1) for _ in range(n)]
opt = [0] * (h + 1)
for i in range(1, h + 1):
	for j in range(n):
		dp[j][i] = dp[j][i - 1] + a[j][i]
		if i >= drop:
			dp[j][i] = max(dp[j][i], opt[i - drop] + a[j][i])
		opt[i] = max(opt[i], dp[j][i])
print(opt[h])


(n, h, drop) = map(int, input().split())
a = [[0] * (h + 1) for _ in range(n)]
for i in range(n):
	tmp = list(map(int, input().split()))[1:]
	for j in tmp:
		a[i][j] += 1
dp = [[0] * (h + 1) for _ in range(n)]
opt = [0] * (h + 1)
for i in range(1, h + 1):
	for j in range(n):
		dp[j][i] = dp[j][i - 1] + a[j][i]
		if i >= drop:
			dp[j][i] = max(dp[j][i], opt[i - drop] + a[j][i])
		opt[i] = max(opt[i], dp[j][i])
print(opt[h])


(num_buildings, height, jump) = [int(c) for c in input().split()]
M = [[0 for i in range(num_buildings)] for k in range(height + 1)]
M_dp = [[0 for i in range(num_buildings)] for k in range(height + 1)]
dp = [0 for i in range(height + 1)]
for i in range(num_buildings):
	A = [int(c) for c in input().split()]
	n = A[0]
	floor_numbers = A[1:]
	for floor in floor_numbers:
		M[floor][i] += 1
dp[1] = max(M[1])
for h in range(1, jump + 1):
	M_dp[h] = [M[h][i] + M_dp[h - 1][i] for i in range(num_buildings)]
	dp[h] = max(M_dp[h])
for h in range(jump + 1, height + 1):
	M_dp[h] = [max(M[h][i] + M_dp[h - 1][i], M[h][i] + dp[h - jump]) for i in range(num_buildings)]
	dp[h] = max(M_dp[h])
print(dp[height])


(n, h, drop) = map(int, input().split())
a = [[0] * (h + 1) for _ in range(n)]
for i in range(n):
	tmp = list(map(int, input().split()))[1:]
	for j in tmp:
		a[i][j] += 1
saved = [[0] * (h + 1) for _ in range(n)]
optativa = [0] * (h + 1)
for i in range(1, h + 1):
	for j in range(n):
		saved[j][i] = saved[j][i - 1] + a[j][i]
		if i >= drop:
			saved[j][i] = max(saved[j][i], optativa[i - drop] + a[j][i])
		optativa[i] = max(optativa[i], saved[j][i])
print(optativa[h])


(n, h, drop) = map(int, input().split())
a = [[0] * (h + 1) for _ in range(n)]
for i in range(n):
	tmp = list(map(int, input().split()))[1:]
	for j in tmp:
		a[i][j] += 1
dp = [[0] * (h + 1) for _ in range(n)]
opt = [0] * (h + 1)
for i in range(1, h + 1):
	for j in range(n):
		dp[j][i] = dp[j][i - 1] + a[j][i]
		if i >= drop:
			dp[j][i] = max(dp[j][i], opt[i - drop] + a[j][i])
		opt[i] = max(opt[i], dp[j][i])
print(opt[h])


import sys

def solve(B, I):
	R = [[0 for _ in f] for f in B]
	for h in range(len(B)):
		if h < I:
			m = 0
		else:
			m = max(R[h - I])
		for b in range(len(B[h])):
			R[h][b] = max(R[h - 1][b], m) + B[h][b]
	return max(R[-1])
(N, H, I) = (int(_) for _ in input().split())
B = [[0 for _ in range(N)] for _ in range(H)]
for b in range(N):
	U = tuple((int(_) for _ in input().split()))
	for u in U[1:]:
		B[u - 1][b] += 1
print(B, file=sys.stderr)
print(solve(B, I))


(num_buildings, height, jump) = [int(c) for c in input().split()]
M = [[0 for i in range(num_buildings)] for k in range(height + 1)]
M_dp = [[0 for i in range(num_buildings)] for k in range(height + 1)]
dp = [0 for i in range(height + 1)]
for i in range(num_buildings):
	A = [int(c) for c in input().split()]
	n = A[0]
	floor_numbers = A[1:]
	for floor in floor_numbers:
		M[floor][i] += 1
dp[1] = max(M[1])
for h in range(1, jump + 1):
	M_dp[h] = [M[h][i] + M_dp[h - 1][i] for i in range(num_buildings)]
	dp[h] = max(M_dp[h])
for h in range(jump + 1, height + 1):
	M_dp[h] = [max(M[h][i] + M_dp[h - 1][i], M[h][i] + dp[h - jump]) for i in range(num_buildings)]
	dp[h] = max(M_dp[h])
print(dp[height])


def superman(n, h, jump, arr):
	dp = [[0] * h for _ in range(n)]
	ma = [0] * h
	for i in range(n):
		dp[i][0] = arr[i][0]
		ma[0] = max(ma[0], dp[i][0])
	for j in range(1, h):
		for i in range(n):
			dp[i][j] = dp[i][j - 1] + arr[i][j]
			if j >= jump:
				dp[i][j] = max(dp[i][j], ma[j - jump] + arr[i][j])
			ma[j] = max(ma[j], dp[i][j])
	return ma[h - 1]
(n, h, jump) = list(map(int, input().split()))
arr = [[0] * h for _ in range(n)]
for i in range(n):
	p = list(map(int, input().split()))
	for l in p[1:]:
		arr[i][l - 1] += 1
r = superman(n, h, jump, arr)
print(r)


(n, h, k) = list(map(int, input().split()))
pb = [[0] * (h + 1) for i in range(n)]
for i in range(n):
	temp = list(map(int, input().split()))[1:]
	for j in temp:
		pb[i][j] += 1
save_a = [[0] * (h + 1) for i in range(n)]
if n == 1:
	print(sum(pb[0]))
	exit()
for i in range(1, h + 1):
	m1 = 0
	if i >= k:
		(m1, m2) = sorted([save_a[j][i - k] for j in range(n)], reverse=True)[0:2]
	for j in range(n):
		mx = m1
		if i >= k and save_a[j][i - 2] == m1 and (m1 != m2):
			mx = m2
		save_a[j][i] = pb[j][i] + max(mx, save_a[j][i - 1])
print(max([save_a[i][-1] for i in range(n)]))


(n, h, drop) = map(int, input().split())
a = [[0] * (h + 1) for _ in range(n)]
for i in range(n):
	tmp = list(map(int, input().split()))[1:]
	for j in tmp:
		a[i][j] += 1
dp = [[0] * (h + 1) for _ in range(n)]
opt = [0] * (h + 1)
for i in range(1, h + 1):
	for j in range(n):
		dp[j][i] = dp[j][i - 1] + a[j][i]
		if i >= drop:
			dp[j][i] = max(dp[j][i], opt[i - drop] + a[j][i])
		opt[i] = max(opt[i], dp[j][i])
print(opt[h])


def main(N, H, I):
	people = [[0] * N for _ in range(H + 1)]
	for n in range(N):
		a = [int(x) for x in input().split()]
		for h in a[1:]:
			people[h][n] += 1
	apartments = [(0, 1)]
	S = [[0] * N for _ in range(H + 1)]
	for h in range(1, H + 1):
		for n in range(N):
			if h - I > 0 and S[h - 1][n] < apartments[h - I][0]:
				S[h][n] = people[h][n] + S[h - I][apartments[h - I][1]]
			else:
				S[h][n] = people[h][n] + S[h - 1][n]
		apartments.append(max(((m, i) for (i, m) in enumerate(S[h]))))
	print(max(S[-1]))
(N, H, I) = [int(x) for x in input().split()]
main(N, H, I)


(N, H, I) = map(int, input().split())
l = [[0 for i in range(H + 1)] for j in range(N)]
x = [0] * (H + 1)
m = 0
for i in range(N):
	l1 = list(map(int, input().split()))
	for j in range(1, len(l1)):
		l[i][l1[j]] = l[i][l1[j]] + 1
dp = [[0 for i in range(N)] for j in range(H + 1)]
for j in range(1, H + 1):
	for i in range(N):
		if j > I:
			dp[j][i] = max(dp[j - 1][i] + l[i][j], x[j - I] + l[i][j])
		else:
			dp[j][i] = dp[j - 1][i] + l[i][j]
		if x[j] < dp[j][i]:
			x[j] = dp[j][i]
print(x[H])


(n, h, drop) = map(int, input().split())
a = [[0] * (h + 1) for _ in range(n)]
for i in range(n):
	tmp = list(map(int, input().split()))[1:]
	for j in tmp:
		a[i][j] += 1
dp = [[0] * (h + 1) for _ in range(n)]
opt = [0] * (h + 1)
for i in range(1, h + 1):
	for j in range(n):
		dp[j][i] = dp[j][i - 1] + a[j][i]
		if i >= drop:
			dp[j][i] = max(dp[j][i], opt[i - drop] + a[j][i])
		opt[i] = max(opt[i], dp[j][i])
print(opt[h])


s = input().split()
n = int(s[0])
h = int(s[1])
i = int(s[2])
bs = [[0 for j in range(n)] for k in range(h)]
mm = [0 for j in range(n)]
ju = [0 for j in range(i)]
for i in range(n):
	s = input().split()
	s = list(map(int, s))
	for j in range(s[0]):
		bs[h - s[j + 1]][i] += 1
ct = [0 for j in range(n)]
for j in range(h):
	for k in range(n):
		ct[k] = max(mm[k], ju[0]) + bs[j][k]
	ju = ju[1:] + [max(ct)]
	mm = ct.copy()
print(max(ju))


tmp = input().rstrip().split()
n = int(tmp[0])
h = int(tmp[1])
i = int(tmp[2])
persons = [[0 for j in range(h)] for k in range(n)]
for j in range(n):
	tmp = input().rstrip().split()
	for k in range(1, len(tmp)):
		floor = int(tmp[k]) - 1
		persons[j][floor] += 1
dp = [[0 for j in range(h)] for k in range(n)]
maxFloor = [0 for j in range(h)]
currMax = 0
for j in range(n):
	dp[j][0] = persons[j][0]
	if dp[j][0] > currMax:
		currMax = dp[j][0]
maxFloor[0] = currMax
for j in range(1, h):
	currMax = 0
	for k in range(n):
		curr = persons[k][j] + dp[k][j - 1]
		if j - i >= 0:
			tmp = persons[k][j] + maxFloor[j - i]
			if tmp > curr:
				curr = tmp
		dp[k][j] = curr
		if curr > currMax:
			currMax = curr
	maxFloor[j] = currMax
print(maxFloor[h - 1])


(n, f, I) = map(int, input().split())
l = []
m = [0] * f
for i in range(f):
	l.append([0] * n)
for i in range(n):
	ar = list(map(int, input().split()))
	u = ar[0]
	for j in range(1, u + 1):
		l[ar[j] - 1][i] += 1
m[0] = max(l[0])
for i in range(1, len(l)):
	for j in range(n):
		if i < I:
			l[i][j] += l[i - 1][j]
		else:
			l[i][j] = max(l[i][j] + l[i - 1][j], l[i][j] + m[i - I])
	m[i] = max(l[i])
print(m[-1])


(n, f, jp) = list(map(int, input().split()))
lst = []
for i in range(1901):
	ls = []
	for j in range(1901):
		ls.append(0)
	lst.append(ls)
for i in range(n):
	ls = list(map(int, input().split()))
	x = ls.pop(0)
	for j in range(x):
		lst[ls[j] - 1][i] += 1
m = []
for i in range(1901):
	m.append(0)
for i in range(f):
	for j in range(n):
		if i > jp - 1:
			lst[i][j] += max(lst[i - 1][j], m[i - jp])
		else:
			lst[i][j] += lst[i - 1][j]
		if m[i] < lst[i][j]:
			m[i] = lst[i][j]
print(m[f - 1])


import sys

def solve(B, I):
	R = [[0 for _ in f] for f in B]
	for h in range(len(B)):
		if h < I:
			m = 0
		else:
			m = max(R[h - I])
		for b in range(len(B[h])):
			R[h][b] = max(R[h - 1][b], m) + B[h][b]
	return max(R[-1])
(N, H, I) = (int(_) for _ in input().split())
B = [[0 for _ in range(N)] for _ in range(H)]
for b in range(N):
	U = tuple((int(_) for _ in input().split()))
	for u in U[1:]:
		B[u - 1][b] += 1
print(B, file=sys.stderr)
print(solve(B, I))


def solve(n, h, i, u):
	arr = [[0] * (h + 1) for _ in range(n)]
	for x in range(n):
		for y in u[x][1:]:
			arr[x][y] += 1
	dp = [[0] * (h + 1) for _ in range(n)]
	opt = [0] * (h + 1)
	for x in range(1, h + 1):
		for y in range(n):
			dp[y][x] = dp[y][x - 1] + arr[y][x]
			if x >= i:
				dp[y][x] = max(dp[y][x], opt[x - i] + arr[y][x])
			opt[x] = max(opt[x], dp[y][x])
	return opt[h]
(n, h, i) = map(int, input().strip().split())
u = []
for _ in range(n):
	u.append(list(map(int, input().strip().split())))
print(solve(n, h, i, u))


(n, h, drop) = map(int, input().split())
a = [[0] * (h + 1) for _ in range(n)]
for i in range(n):
	tmp = list(map(int, input().split()))[1:]
	for j in tmp:
		a[i][j] += 1
dp = [[0] * (h + 1) for _ in range(n)]
opt = [0] * (h + 1)
for i in range(1, h + 1):
	for j in range(n):
		dp[j][i] = dp[j][i - 1] + a[j][i]
		if i >= drop:
			dp[j][i] = max(dp[j][i], opt[i - drop] + a[j][i])
		opt[i] = max(opt[i], dp[j][i])
print(opt[h])


(n, h, drop) = map(int, input().split())
a = [[0] * (h + 1) for _ in range(n)]
for i in range(n):
	tmp = list(map(int, input().split()))[1:]
	for j in tmp:
		a[i][j] += 1
dp = [[0] * (h + 1) for _ in range(n)]
opt = [0] * (h + 1)
for i in range(1, h + 1):
	for j in range(n):
		dp[j][i] = dp[j][i - 1] + a[j][i]
		if i >= drop:
			dp[j][i] = max(dp[j][i], opt[i - drop] + a[j][i])
		opt[i] = max(opt[i], dp[j][i])
print(opt[h])


(n, h, hl) = map(int, input().split())
cnt = f = [[0 for _ in range(1901)] for _ in range(1900)]
g = [0 for _ in range(1901)]
for ctr in range(n):
	lis = list(map(int, input().split()))
	for j in range(1, len(lis)):
		cnt[ctr][lis[j]] += 1
for ctr in range(n):
	f[ctr][h] = cnt[ctr][h]
	if f[ctr][h] > g[h]:
		g[h] = f[ctr][h]
for j in range(h - 1, -1, -1):
	for i in range(n):
		tmp = 0
		if j + hl <= h:
			if g[j + hl] > tmp:
				tmp = g[j + hl]
		if f[i][j + 1] > tmp:
			tmp = f[i][j + 1]
		f[i][j] = tmp + cnt[i][j]
		if f[i][j] > g[j]:
			g[j] = f[i][j]
ans = 0
for ctr in range(n):
	ans = max(ans, f[ctr][0])
print(ans)


(n, h, hl) = map(int, input().split())
cnt = f = [[0 for _ in range(1901)] for _ in range(1900)]
g = [0 for _ in range(1901)]
for ctr in range(n):
	lis = list(map(int, input().split()))
	for j in range(1, len(lis)):
		cnt[ctr][lis[j]] += 1
for ctr in range(n):
	f[ctr][h] = cnt[ctr][h]
	if f[ctr][h] > g[h]:
		g[h] = f[ctr][h]
for j in range(h - 1, -1, -1):
	for i in range(n):
		tmp = 0
		if j + hl <= h:
			if g[j + hl] > tmp:
				tmp = g[j + hl]
		if f[i][j + 1] > tmp:
			tmp = f[i][j + 1]
		f[i][j] = tmp + cnt[i][j]
		if f[i][j] > g[j]:
			g[j] = f[i][j]
ans = 0
for ctr in range(n):
	ans = max(ans, f[ctr][0])
print(ans)


(n, h, hl) = map(int, input().split())
cnt = f = [[0 for _ in range(1901)] for _ in range(1900)]
g = [0 for _ in range(1901)]
for ctr in range(n):
	lis = list(map(int, input().split()))
	for j in range(1, len(lis)):
		cnt[ctr][lis[j]] += 1
for ctr in range(n):
	f[ctr][h] = cnt[ctr][h]
	if f[ctr][h] > g[h]:
		g[h] = f[ctr][h]
for j in range(h - 1, -1, -1):
	for i in range(n):
		tmp = 0
		if j + hl <= h:
			if g[j + hl] > tmp:
				tmp = g[j + hl]
		if f[i][j + 1] > tmp:
			tmp = f[i][j + 1]
		f[i][j] = tmp + cnt[i][j]
		if f[i][j] > g[j]:
			g[j] = f[i][j]
ans = 0
for ctr in range(n):
	ans = max(ans, f[ctr][0])
print(ans)


(n, h, hl) = map(int, input().split())
cnt = f = [[0 for _ in range(1901)] for _ in range(1900)]
g = [0 for _ in range(1901)]
for ctr in range(n):
	lis = list(map(int, input().split()))
	for j in range(1, len(lis)):
		cnt[ctr][lis[j]] += 1
for ctr in range(n):
	f[ctr][h] = cnt[ctr][h]
	if f[ctr][h] > g[h]:
		g[h] = f[ctr][h]
for j in range(h - 1, -1, -1):
	for i in range(n):
		tmp = 0
		if j + hl <= h:
			if g[j + hl] > tmp:
				tmp = g[j + hl]
		if f[i][j + 1] > tmp:
			tmp = f[i][j + 1]
		f[i][j] = tmp + cnt[i][j]
		if f[i][j] > g[j]:
			g[j] = f[i][j]
ans = 0
for ctr in range(n):
	ans = max(ans, f[ctr][0])
print(ans)


(n, h, hl) = map(int, input().split())
cnt = f = [[0 for _ in range(1901)] for _ in range(1900)]
g = [0 for _ in range(1901)]
for ctr in range(n):
	lis = list(map(int, input().split()))
	for j in range(1, len(lis)):
		cnt[ctr][lis[j]] += 1
for ctr in range(n):
	f[ctr][h] = cnt[ctr][h]
	if f[ctr][h] > g[h]:
		g[h] = f[ctr][h]
for j in range(h - 1, -1, -1):
	for i in range(n):
		tmp = 0
		if j + hl <= h:
			if g[j + hl] > tmp:
				tmp = g[j + hl]
		if f[i][j + 1] > tmp:
			tmp = f[i][j + 1]
		f[i][j] = tmp + cnt[i][j]
		if f[i][j] > g[j]:
			g[j] = f[i][j]
ans = 0
for ctr in range(n):
	ans = max(ans, f[ctr][0])
print(ans)


(n, h, drop) = map(int, input().split())
a = [[0] * (h + 1) for _ in range(n)]
for i in range(n):
	tmp = list(map(int, input().split()))[1:]
	for j in tmp:
		a[i][j] += 1
dp = [[0] * (h + 1) for _ in range(n)]
opt = [0] * (h + 1)
for i in range(1, h + 1):
	for j in range(n):
		dp[j][i] = dp[j][i - 1] + a[j][i]
		if i >= drop:
			dp[j][i] = max(dp[j][i], opt[i - drop] + a[j][i])
		opt[i] = max(opt[i], dp[j][i])
print(opt[h])


(n, h, hl) = map(int, input().split())
cnt = f = [[0 for _ in range(1901)] for _ in range(1900)]
g = [0 for _ in range(1901)]
for ctr in range(n):
	lis = list(map(int, input().split()))
	for j in range(1, len(lis)):
		cnt[ctr][lis[j]] += 1
for ctr in range(n):
	f[ctr][h] = cnt[ctr][h]
	if f[ctr][h] > g[h]:
		g[h] = f[ctr][h]
for j in range(h - 1, -1, -1):
	for i in range(n):
		tmp = 0
		if j + hl <= h:
			if g[j + hl] > tmp:
				tmp = g[j + hl]
		if f[i][j + 1] > tmp:
			tmp = f[i][j + 1]
		f[i][j] = tmp + cnt[i][j]
		if f[i][j] > g[j]:
			g[j] = f[i][j]
ans = 0
for ctr in range(n):
	ans = max(ans, f[ctr][0])
print(ans)


(n, h, hl) = map(int, input().split())
cnt = f = [[0 for _ in range(1901)] for _ in range(1900)]
g = [0 for _ in range(1901)]
for ctr in range(n):
	lis = list(map(int, input().split()))
	for j in range(1, len(lis)):
		cnt[ctr][lis[j]] += 1
for ctr in range(n):
	f[ctr][h] = cnt[ctr][h]
	if f[ctr][h] > g[h]:
		g[h] = f[ctr][h]
for j in range(h - 1, -1, -1):
	for i in range(n):
		tmp = 0
		if j + hl <= h:
			if g[j + hl] > tmp:
				tmp = g[j + hl]
		if f[i][j + 1] > tmp:
			tmp = f[i][j + 1]
		f[i][j] = tmp + cnt[i][j]
		if f[i][j] > g[j]:
			g[j] = f[i][j]
ans = 0
for ctr in range(n):
	ans = max(ans, f[ctr][0])
print(ans)


(n, h, hl) = map(int, input().split())
cnt = f = [[0 for _ in range(1901)] for _ in range(1900)]
g = [0 for _ in range(1901)]
for ctr in range(n):
	lis = list(map(int, input().split()))
	for j in range(1, len(lis)):
		cnt[ctr][lis[j]] += 1
for ctr in range(n):
	f[ctr][h] = cnt[ctr][h]
	if f[ctr][h] > g[h]:
		g[h] = f[ctr][h]
for j in range(h - 1, -1, -1):
	for i in range(n):
		tmp = 0
		if j + hl <= h:
			if g[j + hl] > tmp:
				tmp = g[j + hl]
		if f[i][j + 1] > tmp:
			tmp = f[i][j + 1]
		f[i][j] = tmp + cnt[i][j]
		if f[i][j] > g[j]:
			g[j] = f[i][j]
ans = 0
for ctr in range(n):
	ans = max(ans, f[ctr][0])
print(ans)


(n, h, hl) = map(int, input().split())
cnt = f = [[0 for _ in range(1901)] for _ in range(1900)]
g = [0 for _ in range(1901)]
for ctr in range(n):
	lis = list(map(int, input().split()))
	for j in range(1, len(lis)):
		cnt[ctr][lis[j]] += 1
for ctr in range(n):
	f[ctr][h] = cnt[ctr][h]
	if f[ctr][h] > g[h]:
		g[h] = f[ctr][h]
for j in range(h - 1, -1, -1):
	for i in range(n):
		tmp = 0
		if j + hl <= h:
			if g[j + hl] > tmp:
				tmp = g[j + hl]
		if f[i][j + 1] > tmp:
			tmp = f[i][j + 1]
		f[i][j] = tmp + cnt[i][j]
		if f[i][j] > g[j]:
			g[j] = f[i][j]
ans = 0
for ctr in range(n):
	ans = max(ans, f[ctr][0])
print(ans)


(n, h, hl) = map(int, input().split())
cnt = f = [[0 for _ in range(1901)] for _ in range(1900)]
g = [0 for _ in range(1901)]
for ctr in range(n):
	lis = list(map(int, input().split()))
	for j in range(1, len(lis)):
		cnt[ctr][lis[j]] += 1
for ctr in range(n):
	f[ctr][h] = cnt[ctr][h]
	if f[ctr][h] > g[h]:
		g[h] = f[ctr][h]
for j in range(h - 1, -1, -1):
	for i in range(n):
		tmp = 0
		if j + hl <= h:
			if g[j + hl] > tmp:
				tmp = g[j + hl]
		if f[i][j + 1] > tmp:
			tmp = f[i][j + 1]
		f[i][j] = tmp + cnt[i][j]
		if f[i][j] > g[j]:
			g[j] = f[i][j]
ans = 0
for ctr in range(n):
	ans = max(ans, f[ctr][0])
print(ans)


(n, h, hl) = map(int, input().split())
cnt = f = [[0 for _ in range(1901)] for _ in range(1900)]
g = [0 for _ in range(1901)]
for ctr in range(n):
	lis = list(map(int, input().split()))
	for j in range(1, len(lis)):
		cnt[ctr][lis[j]] += 1
for ctr in range(n):
	f[ctr][h] = cnt[ctr][h]
	if f[ctr][h] > g[h]:
		g[h] = f[ctr][h]
for j in range(h - 1, -1, -1):
	for i in range(n):
		tmp = 0
		if j + hl <= h:
			if g[j + hl] > tmp:
				tmp = g[j + hl]
		if f[i][j + 1] > tmp:
			tmp = f[i][j + 1]
		f[i][j] = tmp + cnt[i][j]
		if f[i][j] > g[j]:
			g[j] = f[i][j]
ans = 0
for ctr in range(n):
	ans = max(ans, f[ctr][0])
print(ans)


(n, h, drop) = map(int, input().split())
a = [[0] * (h + 1) for _ in range(n)]
for i in range(n):
	tmp = list(map(int, input().split()))[1:]
	for j in tmp:
		a[i][j] += 1
dp = [[0] * (h + 1) for _ in range(n)]
opt = [0] * (h + 1)
for i in range(1, h + 1):
	for j in range(n):
		dp[j][i] = dp[j][i - 1] + a[j][i]
		if i >= drop:
			dp[j][i] = max(dp[j][i], opt[i - drop] + a[j][i])
		opt[i] = max(opt[i], dp[j][i])
print(opt[h])


(n, h, drop) = map(int, input().split())
a = [[0] * (h + 1) for _ in range(n)]
for i in range(n):
	tmp = list(map(int, input().split()))[1:]
	for j in tmp:
		a[i][j] += 1
dp = [[0] * (h + 1) for _ in range(n)]
opt = [0] * (h + 1)
for i in range(1, h + 1):
	for j in range(n):
		dp[j][i] = dp[j][i - 1] + a[j][i]
		if i >= drop:
			dp[j][i] = max(dp[j][i], opt[i - drop] + a[j][i])
		opt[i] = max(opt[i], dp[j][i])
print(opt[h])


(n, h, hl) = map(int, input().split())
cnt = f = [[0 for _ in range(1901)] for _ in range(1900)]
g = [0 for _ in range(1901)]
for ctr in range(n):
	lis = list(map(int, input().split()))
	for j in range(1, len(lis)):
		cnt[ctr][lis[j]] += 1
for ctr in range(n):
	f[ctr][h] = cnt[ctr][h]
	if f[ctr][h] > g[h]:
		g[h] = f[ctr][h]
for j in range(h - 1, -1, -1):
	for i in range(n):
		tmp = 0
		if j + hl <= h:
			if g[j + hl] > tmp:
				tmp = g[j + hl]
		if f[i][j + 1] > tmp:
			tmp = f[i][j + 1]
		f[i][j] = tmp + cnt[i][j]
		if f[i][j] > g[j]:
			g[j] = f[i][j]
ans = 0
for ctr in range(n):
	ans = max(ans, f[ctr][0])
print(ans)


(n, h, hl) = map(int, input().split())
cnt = f = [[0 for _ in range(1901)] for _ in range(1900)]
g = [0 for _ in range(1901)]
for ctr in range(n):
	lis = list(map(int, input().split()))
	for j in range(1, len(lis)):
		cnt[ctr][lis[j]] += 1
for ctr in range(n):
	f[ctr][h] = cnt[ctr][h]
	if f[ctr][h] > g[h]:
		g[h] = f[ctr][h]
for j in range(h - 1, -1, -1):
	for i in range(n):
		tmp = 0
		if j + hl <= h:
			if g[j + hl] > tmp:
				tmp = g[j + hl]
		if f[i][j + 1] > tmp:
			tmp = f[i][j + 1]
		f[i][j] = tmp + cnt[i][j]
		if f[i][j] > g[j]:
			g[j] = f[i][j]
ans = 0
for ctr in range(n):
	ans = max(ans, f[ctr][0])
print(ans)


(n, h, hl) = map(int, input().split())
cnt = f = [[0 for _ in range(1901)] for _ in range(1900)]
g = [0 for _ in range(1901)]
for ctr in range(n):
	lis = list(map(int, input().split()))
	for j in range(1, len(lis)):
		cnt[ctr][lis[j]] += 1
for ctr in range(n):
	f[ctr][h] = cnt[ctr][h]
	if f[ctr][h] > g[h]:
		g[h] = f[ctr][h]
for j in range(h - 1, -1, -1):
	for i in range(n):
		tmp = 0
		if j + hl <= h:
			if g[j + hl] > tmp:
				tmp = g[j + hl]
		if f[i][j + 1] > tmp:
			tmp = f[i][j + 1]
		f[i][j] = tmp + cnt[i][j]
		if f[i][j] > g[j]:
			g[j] = f[i][j]
ans = 0
for ctr in range(n):
	ans = max(ans, f[ctr][0])
print(ans)


(n, h, hl) = map(int, input().split())
cnt = f = [[0 for _ in range(1901)] for _ in range(1900)]
g = [0 for _ in range(1901)]
for ctr in range(n):
	lis = list(map(int, input().split()))
	for j in range(1, len(lis)):
		cnt[ctr][lis[j]] += 1
for ctr in range(n):
	f[ctr][h] = cnt[ctr][h]
	if f[ctr][h] > g[h]:
		g[h] = f[ctr][h]
for j in range(h - 1, -1, -1):
	for i in range(n):
		tmp = 0
		if j + hl <= h:
			if g[j + hl] > tmp:
				tmp = g[j + hl]
		if f[i][j + 1] > tmp:
			tmp = f[i][j + 1]
		f[i][j] = tmp + cnt[i][j]
		if f[i][j] > g[j]:
			g[j] = f[i][j]
ans = 0
for ctr in range(n):
	ans = max(ans, f[ctr][0])
print(ans)


(n, h, hl) = map(int, input().split())
cnt = f = [[0 for _ in range(1901)] for _ in range(1900)]
g = [0 for _ in range(1901)]
for ctr in range(n):
	lis = list(map(int, input().split()))
	for j in range(1, len(lis)):
		cnt[ctr][lis[j]] += 1
for ctr in range(n):
	f[ctr][h] = cnt[ctr][h]
	if f[ctr][h] > g[h]:
		g[h] = f[ctr][h]
for j in range(h - 1, -1, -1):
	for i in range(n):
		tmp = 0
		if j + hl <= h:
			if g[j + hl] > tmp:
				tmp = g[j + hl]
		if f[i][j + 1] > tmp:
			tmp = f[i][j + 1]
		f[i][j] = tmp + cnt[i][j]
		if f[i][j] > g[j]:
			g[j] = f[i][j]
ans = 0
for ctr in range(n):
	ans = max(ans, f[ctr][0])
print(ans)


(n, h, drop) = map(int, input().split())
a = [[0] * (h + 1) for _ in range(n)]
for i in range(n):
	tmp = list(map(int, input().split()))[1:]
	for j in tmp:
		a[i][j] += 1
dp = [[0] * (h + 1) for _ in range(n)]
opt = [0] * (h + 1)
for i in range(1, h + 1):
	for j in range(n):
		dp[j][i] = dp[j][i - 1] + a[j][i]
		if i >= drop:
			dp[j][i] = max(dp[j][i], opt[i - drop] + a[j][i])
		opt[i] = max(opt[i], dp[j][i])
print(opt[h])


import collections
(n, h, ii) = map(int, input().split())
dp = [[0] * h for _ in range(n)]
for i in range(n):
	x = list(map(int, input().split()))
	for j in x[1:]:
		dp[i][j - 1] += 1
last = collections.deque()
for j in range(h):
	x = last.popleft() if j >= ii else 0
	for i in range(n):
		dp[i][j] += max(0 if j == 0 else dp[i][j - 1], x)
	last.append(max((k[j] for k in dp)))
print(max((k[-1] for k in dp)))


(n, h, hl) = map(int, input().split())
cnt = f = [[0 for _ in range(1901)] for _ in range(1900)]
g = [0 for _ in range(1901)]
for ctr in range(n):
	lis = list(map(int, input().split()))
	for j in range(1, len(lis)):
		cnt[ctr][lis[j]] += 1
for ctr in range(n):
	f[ctr][h] = cnt[ctr][h]
	if f[ctr][h] > g[h]:
		g[h] = f[ctr][h]
for j in range(h - 1, -1, -1):
	for i in range(n):
		tmp = 0
		if j + hl <= h:
			if g[j + hl] > tmp:
				tmp = g[j + hl]
		if f[i][j + 1] > tmp:
			tmp = f[i][j + 1]
		f[i][j] = tmp + cnt[i][j]
		if f[i][j] > g[j]:
			g[j] = f[i][j]
ans = 0
for ctr in range(n):
	ans = max(ans, f[ctr][0])
print(ans)


(n, h, hl) = map(int, input().split())
cnt = f = [[0 for _ in range(1901)] for _ in range(1900)]
g = [0 for _ in range(1901)]
for ctr in range(n):
	lis = list(map(int, input().split()))
	for j in range(1, len(lis)):
		cnt[ctr][lis[j]] += 1
for ctr in range(n):
	f[ctr][h] = cnt[ctr][h]
	if f[ctr][h] > g[h]:
		g[h] = f[ctr][h]
for j in range(h - 1, -1, -1):
	for i in range(n):
		tmp = 0
		if j + hl <= h:
			if g[j + hl] > tmp:
				tmp = g[j + hl]
		if f[i][j + 1] > tmp:
			tmp = f[i][j + 1]
		f[i][j] = tmp + cnt[i][j]
		if f[i][j] > g[j]:
			g[j] = f[i][j]
ans = 0
for ctr in range(n):
	ans = max(ans, f[ctr][0])
print(ans)


import collections
(n, h, ii) = map(int, input().split())
dp = [[0] * h for _ in range(n)]
for i in range(n):
	x = list(map(int, input().split()))
	for j in x[1:]:
		dp[i][j - 1] += 1
last = collections.deque()
for j in range(h):
	x = last.popleft() if j >= ii else 0
	for i in range(n):
		dp[i][j] += max(0 if j == 0 else dp[i][j - 1], x)
	last.append(max((k[j] for k in dp)))
print(max((k[-1] for k in dp)))


(n, h, drop) = map(int, input().split())
a = [[0] * (h + 1) for _ in range(n)]
for i in range(n):
	tmp = list(map(int, input().split()))[1:]
	for j in tmp:
		a[i][j] += 1
dp = [[0] * (h + 1) for _ in range(n)]
opt = [0] * (h + 1)
for i in range(1, h + 1):
	for j in range(n):
		dp[j][i] = dp[j][i - 1] + a[j][i]
		if i >= drop:
			dp[j][i] = max(dp[j][i], opt[i - drop] + a[j][i])
		opt[i] = max(opt[i], dp[j][i])
print(opt[h])


import collections
(n, h, ii) = map(int, input().split())
dp = [[0] * h for _ in range(n)]
for i in range(n):
	x = list(map(int, input().split()))
	for j in x[1:]:
		dp[i][j - 1] += 1
last = collections.deque()
for j in range(h):
	x = last.popleft() if j >= ii else 0
	for i in range(n):
		dp[i][j] += max(0 if j == 0 else dp[i][j - 1], x)
	last.append(max((k[j] for k in dp)))
print(max((k[-1] for k in dp)))


(n, h, hl) = map(int, input().split())
cnt = f = [[0 for _ in range(1901)] for _ in range(1900)]
g = [0 for _ in range(1901)]
for ctr in range(n):
	lis = list(map(int, input().split()))
	for j in range(1, len(lis)):
		cnt[ctr][lis[j]] += 1
for ctr in range(n):
	f[ctr][h] = cnt[ctr][h]
	if f[ctr][h] > g[h]:
		g[h] = f[ctr][h]
for j in range(h - 1, -1, -1):
	for i in range(n):
		tmp = 0
		if j + hl <= h:
			if g[j + hl] > tmp:
				tmp = g[j + hl]
		if f[i][j + 1] > tmp:
			tmp = f[i][j + 1]
		f[i][j] = tmp + cnt[i][j]
		if f[i][j] > g[j]:
			g[j] = f[i][j]
ans = 0
for ctr in range(n):
	ans = max(ans, f[ctr][0])
print(ans)


(n, h, drop) = map(int, input().split())
a = [[0] * (h + 1) for _ in range(n)]
for i in range(n):
	tmp = list(map(int, input().split()))[1:]
	for j in tmp:
		a[i][j] += 1
dp = [[0] * (h + 1) for _ in range(n)]
opt = [0] * (h + 1)
for i in range(1, h + 1):
	for j in range(n):
		dp[j][i] = dp[j][i - 1] + a[j][i]
		if i >= drop:
			dp[j][i] = max(dp[j][i], opt[i - drop] + a[j][i])
		opt[i] = max(opt[i], dp[j][i])
print(opt[h])


import collections
(n, h, ii) = map(int, input().split())
dp = [[0] * h for _ in range(n)]
for i in range(n):
	x = list(map(int, input().split()))
	for j in x[1:]:
		dp[i][j - 1] += 1
last = collections.deque()
for j in range(h):
	x = last.popleft() if j >= ii else 0
	for i in range(n):
		dp[i][j] += max(0 if j == 0 else dp[i][j - 1], x)
	last.append(max((k[j] for k in dp)))
print(max((k[-1] for k in dp)))


(n, h, hl) = map(int, input().split())
cnt = f = [[0 for _ in range(1901)] for _ in range(1900)]
g = [0 for _ in range(1901)]
for ctr in range(n):
	lis = list(map(int, input().split()))
	for j in range(1, len(lis)):
		cnt[ctr][lis[j]] += 1
for ctr in range(n):
	f[ctr][h] = cnt[ctr][h]
	if f[ctr][h] > g[h]:
		g[h] = f[ctr][h]
for j in range(h - 1, -1, -1):
	for i in range(n):
		tmp = 0
		if j + hl <= h:
			if g[j + hl] > tmp:
				tmp = g[j + hl]
		if f[i][j + 1] > tmp:
			tmp = f[i][j + 1]
		f[i][j] = tmp + cnt[i][j]
		if f[i][j] > g[j]:
			g[j] = f[i][j]
ans = 0
for ctr in range(n):
	ans = max(ans, f[ctr][0])
print(ans)


import collections
(n, h, ii) = map(int, input().split())
dp = [[0] * h for _ in range(n)]
for i in range(n):
	x = list(map(int, input().split()))
	for j in x[1:]:
		dp[i][j - 1] += 1
last = collections.deque()
for j in range(h):
	x = last.popleft() if j >= ii else 0
	for i in range(n):
		dp[i][j] += max(0 if j == 0 else dp[i][j - 1], x)
	last.append(max((k[j] for k in dp)))
print(max((k[-1] for k in dp)))


(n, h, hl) = map(int, input().split())
cnt = f = [[0 for _ in range(1901)] for _ in range(1900)]
g = [0 for _ in range(1901)]
for ctr in range(n):
	lis = list(map(int, input().split()))
	for j in range(1, len(lis)):
		cnt[ctr][lis[j]] += 1
for ctr in range(n):
	f[ctr][h] = cnt[ctr][h]
	if f[ctr][h] > g[h]:
		g[h] = f[ctr][h]
for j in range(h - 1, -1, -1):
	for i in range(n):
		tmp = 0
		if j + hl <= h:
			if g[j + hl] > tmp:
				tmp = g[j + hl]
		if f[i][j + 1] > tmp:
			tmp = f[i][j + 1]
		f[i][j] = tmp + cnt[i][j]
		if f[i][j] > g[j]:
			g[j] = f[i][j]
ans = 0
for ctr in range(n):
	ans = max(ans, f[ctr][0])
print(ans)


(n, h, hl) = map(int, input().split())
cnt = f = [[0 for _ in range(1901)] for _ in range(1900)]
g = [0 for _ in range(1901)]
for ctr in range(n):
	lis = list(map(int, input().split()))
	for j in range(1, len(lis)):
		cnt[ctr][lis[j]] += 1
for ctr in range(n):
	f[ctr][h] = cnt[ctr][h]
	if f[ctr][h] > g[h]:
		g[h] = f[ctr][h]
for j in range(h - 1, -1, -1):
	for i in range(n):
		tmp = 0
		if j + hl <= h:
			if g[j + hl] > tmp:
				tmp = g[j + hl]
		if f[i][j + 1] > tmp:
			tmp = f[i][j + 1]
		f[i][j] = tmp + cnt[i][j]
		if f[i][j] > g[j]:
			g[j] = f[i][j]
ans = 0
for ctr in range(n):
	ans = max(ans, f[ctr][0])
print(ans)


(n, h, drop) = map(int, input().split())
a = [[0] * (h + 1) for _ in range(n)]
for i in range(n):
	tmp = list(map(int, input().split()))[1:]
	for j in tmp:
		a[i][j] += 1
dp = [[0] * (h + 1) for _ in range(n)]
opt = [0] * (h + 1)
for i in range(1, h + 1):
	for j in range(n):
		dp[j][i] = dp[j][i - 1] + a[j][i]
		if i >= drop:
			dp[j][i] = max(dp[j][i], opt[i - drop] + a[j][i])
		opt[i] = max(opt[i], dp[j][i])
print(opt[h])


(n, h, hl) = map(int, input().split())
cnt = f = [[0 for _ in range(1901)] for _ in range(1900)]
g = [0 for _ in range(1901)]
for ctr in range(n):
	lis = list(map(int, input().split()))
	for j in range(1, len(lis)):
		cnt[ctr][lis[j]] += 1
for ctr in range(n):
	f[ctr][h] = cnt[ctr][h]
	if f[ctr][h] > g[h]:
		g[h] = f[ctr][h]
for j in range(h - 1, -1, -1):
	for i in range(n):
		tmp = 0
		if j + hl <= h:
			if g[j + hl] > tmp:
				tmp = g[j + hl]
		if f[i][j + 1] > tmp:
			tmp = f[i][j + 1]
		f[i][j] = tmp + cnt[i][j]
		if f[i][j] > g[j]:
			g[j] = f[i][j]
ans = 0
for ctr in range(n):
	ans = max(ans, f[ctr][0])
print(ans)