EduBrick

B. Станки с ёмкостью

2000 мс · 256 МБ · всё или ничего

Есть nn работ и mm станков. Каждая работа может быть выполнена на некоторых станках, а станок номер jj успевает за смену выполнить не больше cjc_j работ.

Нужно узнать, какое наибольшее число работ можно выполнить за смену.

Формат ввода

В первой строке nn и mm (1≤n,m≤10001 \le n, m \le 1000). Во второй строке mm чисел cjc_j (1≤cj≤1001 \le c_j \le 100) — ёмкости станков.

В следующих nn строках описаны работы: сначала kik_i — число подходящих станков, затем kik_i их номеров. Сумма всех kik_i не превосходит 2⋅1042 \cdot 10^4.

Формат вывода

Выведите наибольшее число работ, которые можно выполнить за смену.

Примеры

ввод
3 2
2 1
1 1
2 1 2
1 1
вывод
3
ввод
1 1
1
0
вывод
0
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.