Двочастковий покрив#9724

Двочастковий покрив

1 секунда

128 мегабайтів

Дуже складна

У двочастковому графі вершини розбиваються на дві непересічні множини $A$ і $B$ так, що кожне ребро з'єднує вершину з $A$ з вершиною з $B$ . Паросполучення $M$ — це множина ребер, жодні два з яких не мають спільну вершину. Кажуть, що паросполучення $M$ покриває множину вершин $V$ , якщо кожна вершина з $V$ є кінцем хоча б одного ребра з $M$ .

Кожній вершині в графі приписана вага — додатне ціле число. Вагою множини вершин називають суму ваг усіх вершин, що до неї входять.

Задано цілий поріг $t$ . Визначте кількість різних множин вершин $V$ , таких що їх сумарна вага не менше $t$ , і вони покриваються хоча б одним паросполученням $M$ .

Вхідні дані

У першому рядку дано два цілі числа $n$ і $m$ ( $1 \leq n, m \leq 20$ 1 \le n, m \le 20) — кількість вершин у множинах $A$ і $B$ відповідно. Позначимо вершини множини $A$ як $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n, а вершини множини $B$ як $b_{1}, b_{2}, \dots, b_{m}$ b_1, b_2, \ldots, b_m.

Наступні $n$ рядків містять по $m$ символів, що описують ребра графа. $j$ -й символ у $i$ -му рядку дорівнює " $1$ ", якщо між $a_{i}$ a_i та $b_{j}$ b_j є ребро, та " $0$ " в протилежному випадку.

Наступний рядок містить $n$ цілих чисел $v_{1}, v_{2}, \dots, v_{n}$ v_1, v_2, \ldots, v_n ( $1 \leq v_{k} \leq 1 0^{7}$ 1 \le v_k \le 10^7) — ваги вершин $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n.

Далі йде рядок з $m$ цілих чисел $w_{1}, w_{2}, \dots, w_{m}$ w_1, w_2, \ldots, w_m ( $1 \leq w_{k} \leq 1 0^{7}$ 1 \le w_k \le 10^7) — ваги вершин $b_{1}, b_{2}, \dots, b_{m}$ b_1, b_2, \ldots, b_m.

Останній рядок містить одне ціле число $t$ ( $1 \leq t \leq 4 \cdot 1 0^{8}$ 1 \le t \le 4 \cdot 10^8) — поріг ваги.

Вихідні дані

Виведіть кількість множин вершин, сумарна вага яких не менше $t$ і які покриваються хоча б одним паросполученням $M$ .

Приклади

У наведеному прикладі підмножина ${a_{1}, a_{2}, b_{2}, b_{3}}$ \{a_1, a_2, b_2, b_3\} покривається паросполученням ${(a_{1}, b_{2}), (a_{2}, b_{3})}$ \{(a_1, b_2), (a_2, b_3)\} і має вагу $21$ .

Підмножини ${a_{3}, b_{2}, b_{3}}$ \{a_3, b_2, b_3\} і ${a_{2}, a_{3}, b_{2}, b_{3}}$ \{a_2, a_3, b_2, b_3\} також покриваються паросполученням ${(a_{2}, b_{3}), (a_{3}, b_{2})}$ \{(a_2, b_3), (a_3, b_2)\}, і їх ваги рівні $21$ і $23$ відповідно.

Усі інші множини або мають сумарну вагу менше $21$ , або не покриваються жодним паросполученням.

Наприклад, підмножина ${a_{2}, a_{3}, b_{1}, b_{3}}$ \{a_2, a_3, b_1, b_3\} має вагу $26$ , але не покривається жодним паросполученням, тому не враховується при підрахунку.

Приклад 2

Приклад 1