Республиканская олимпиада по информатике, 2015 год, 10-11 класс

Задача B. Кафе

Сегодня в кафе Нового Университета (НУ) пришли $N$ студентов. Каждый из них хочет выпить чашку кофе и съесть одно пирожное (никто из них не согласен только на кофе либо только на пирожное — в этом случае студент уходит). В кафе подают $M$ видов кофе и $K$ видов пирожных. Для каждого из видов кофе или пирожного известно, сколько чашек или порций этого вида имеется в наличии.

Кроме того, у каждого студента есть свои вкусовые предпочтения. Для каждого студента известно, какие виды кофе и пирожных он любит. Никто из студентов не согласен есть или пить то, что ему не нравится.

Хозяин кафе задумался: какое максимальное количество студентов он сможет обслужить? А вы можете посчитать это число?

Входные данные:

Первая строка входных данных содержит целые числа $N$, $M$, $K$ ($1 \le N, M, K \le 500$).
Во второй строке записано $M$ целых чисел через пробел $C_1,C_2,\dots,C_M$ ($1 \le C_i \le 500$) — количество чашек кофе каждого вида, имеющихся в наличии.
В третьей строке записано $K$ целых чисел через пробел $P_1,P_2,\dots,P_K$ ($1 \le P_i \le 500$) — количество порций пирожных каждого вида, имеющихся в наличии.
В следующих $N$ строках дана информация о том, какие виды кофе любит каждый студент. $i$-я строка ($1 \le i \le N$) содержит число $X_i$, за которым следуют различные числа $A_1,A_2,\dots,A_{X_i}$ — виды кофе, которые любит $i$-й студент.
Следующие $N$ строк задают информацию о том, какие виды пирожных любит каждый студент. $i$-я строка ($1 \le i \le N$) содержит число $Y_i$, за которым следуют различные числа $B_1,B_2,\dots,B_{Y_i}$ — виды пирожных, которые любит $i$-й студент.

Выходные данные:

Выведите единственное число — ответ на задачу.

Примеры:

1.Вход:

2 3 1 
5 1 3 
2
3 1 2 3 
1 2
1 1
1 1

Ответ:

2

Оценивание:

Данная задача содержит 3 подзадачи:
$1 \le N, M, K \le 5$. Сумма всех $X_i$ и $Y_i$ ($1 \le i \le N$) вместе не превосходит $10$. Оценивается в $21$ балл.
$1 \le N, M, K \le 20$. Сумма всех $X_i$ и $Y_i$ ($1 \le i \le N$) вместе не превосходит $15$. Оценивается в $33$ балла.
$1 \le N, M, K \le 500$. Сумма всех $X_i$ и $Y_i$ ($1 \le i \le N$) вместе не превосходит $2000$. Оценивается в $46$ баллов.
Каждая следующая подзадача оценивается только при прохождении всех предыдущих. ( Адилет Жаксыбай )