Bipartite Blanket#9724

Bipartite Blanket

1 second

128 megabytes

Very hard

In a bipartite graph, the nodes are divided into two disjoint sets $A$ and $B$ such that every edge connects a node from $A$ to a node from $B$ . A matching $M$ is a set of edges where no two edges share a common node. We say that a matching $M$ blankets a set of nodes $V$ if every node in $V$ is an endpoint of at least one edge in $M$ .

Each node in the bipartite graph is assigned a weight — a positive integer. The weight of a set of nodes is defined as the sum of the weights of its individual nodes.

Given an integer threshold $t$ , determine the number of distinct node sets $V$ such that the total weight of $V$ is at least $t$ and $V$ is blanketed by at least one matching $M$ .

Input

The first line contains two integers $n$ and $m$ ( $1 \leq n, m \leq 20$ 1 \le n, m \le 20) — the number of nodes in sets $A$ and $B$ , respectively. Let the nodes of $A$ be denoted as $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n and the nodes of $B$ as $b_{1}, b_{2}, \dots, b_{m}$ b_1, b_2, \ldots, b_m.

The next $n$ lines each contain $m$ characters describing the edges of the graph. The $j$ -th character of the $i$ -th line is " $1$ " if there is an edge between $a_{i}$ a_i and $b_{j}$ b_j, and " $0$ " otherwise.

The following line contains $n$ integers $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) — the weights of the nodes $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n.

The next line contains $m$ integers $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) — the weights of the nodes $b_{1}, b_{2}, \dots, b_{m}$ b_1, b_2, \ldots, b_m.

The final line contains a single integer $t$ ( $1 \leq t \leq 4 \cdot 1 0^{8}$ 1 \le t \le 4 \cdot 10^8) — the weight threshold.

Output

Print the number of node sets whose total weight is at least $t$ and that are blanketed by at least one matching $M$ .

Examples

In the example, the subset ${a_{1}, a_{2}, b_{2}, b_{3}}$ \{a_1, a_2, b_2, b_3\} is blanketed by the matching ${(a_{1}, b_{2}), (a_{2}, b_{3})}$ \{(a_1, b_2), (a_2, b_3)\} and has a weight of $21$ .

The subsets ${a_{3}, b_{2}, b_{3}}$ \{a_3, b_2, b_3\} and ${a_{2}, a_{3}, b_{2}, b_{3}}$ \{a_2, a_3, b_2, b_3\} are both blanketed by the matching ${(a_{2}, b_{3}), (a_{3}, b_{2})}$ \{(a_2, b_3), (a_3, b_2)\}, with weights of $21$ and $23$ , respectively.

All other subsets either have a total weight less than $21$ or are not blanketed by any matching.

For instance, the subset ${a_{2}, a_{3}, b_{1}, b_{3}}$ \{a_2, a_3, b_1, b_3\} has a total weight of $26$ but is not blanketed by any matching, so it is not included in the count.

Example 2

Example 1