Description

In a bipartite graph, all vertices are split into two disjoint sets $A$ and $B$, and every edge connects some vertex in $A$ to some vertex in $B$. A matching is a set of edges such that no two edges share an endpoint. We say a matching $M$ covers a vertex set $V$ if and only if every vertex in $V$ is an endpoint of at least one edge in $M$.

Given a bipartite graph where each vertex has a positive integer weight, define the weight of a vertex set as the sum of the weights of its vertices.

Given a parameter $t$, count how many vertex sets $V$ satisfy that the weight of $V$ is at least $t$, and $V$ is covered by at least one matching $M$.

Input Format

The first line contains two positive integers $n, m$, denoting the number of vertices in set $A$ and set $B$, respectively.

The next $n$ lines each contain $m$ binary characters '0' or '1'. In the $i$-th row and the $j$-th column, a $1$ indicates there is an edge between $A_i$ and $B_j$.

The next line contains $n$ positive integers $v_1, v_2, \cdots, v_n$, denoting the weight of each vertex in $A$.

The next line contains $m$ positive integers $w_1, w_2, \cdots, w_m$, denoting the weight of each vertex in $B$.

The last line contains a positive integer $t$, representing the parameter $t$.

Output Format

Output a single integer on one line, the number of vertex sets that satisfy the condition.

3 3
010
111
010
1 2 3
8 5 13
21

3

3 2
01
11
10
1 2 3
4 5
8

13

Hint

$1 \leq n, m \leq 20$, $1 \leq v_i, w_i \leq 10^7$, $1 \leq t \leq 4 \times 10^8$.

Translated by ChatGPT 5