In a *bipartite graph*, nodes are partitioned into two disjoint sets $A$ and $B$ such that every edge connects a node from $A$ with 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$. We are given a bipartite graph where each node is assigned a *weight* — a positive integer. Weight of a set of nodes is simply the sum of the weights of the individual nodes. Given an integer threshold $t$, find the number of different sets of nodes $V$ such that the weight of $V$ is at least $t$ and $V$ is blanketed by at least one matching $M$.

The first line contains two integers $n$ and $m (1 ≤ n, m ≤ 20)$ — the number of nodes in $A$ and $B$ respectively. Let us denote the nodes of $A$ with $a_1, a_2, ..., a_n$ and the nodes of $B$ with $b_1, b_2, ..., b_m$.

The following $n$ lines contain m characters each that describe the edges of the graph. The $j$-th character in the $i$-th line is “1” if there is an edge between $a_i$ and $b_j$ and “0” otherwise.

The following line contains $n$ integers $v_1, v_2, ..., v_n(1 ≤ v_k ≤ 10 000 000)$ — the weights of the nodes $a_1, a_2, ..., a_n$. The following line contains $m$ integers $w_1, w_2, ..., w_m (1 ≤ w_k ≤ 10 000 000)$ — the weights of the nodes $b_1, b_2, ..., b_m$.

The following line contains an integer $t (1 ≤ t ≤ 400 000 000)$ — the weight threshold.

Output the number of sets of nodes whose weight is at least $t$ and are blanketed by at least one matching $M$.

3 3
010
111
010
1 2 3
8 5 13
21 · \n
   \n
   \n
   \n
 · · \n
 · ·  \n
  \n

3 \n

In the example above, subset ${ a_1, a_2 , b_2, b_3 }$ is blanketed by matching ${( a_1, b_2) , (a_2, b_3 )}$ and has weight $21$. Subsets ${ a_3 , b_2 , b_3 }$ and ${ a_2 , a_3 , b_2 , b_3 }$ are both blanketed by matching ${( a_2 , b_3 ) , ( a_3 , b_2 )}$ , and have weights $21$ and $23$ respectively. All the other subsets either weigh less than $21$ or are not blanketed by any matching. For example, subset ${ a_2 , a_3 , b_1 , b_3 }$ has weight $26$, but is not blanketed by any matching, so it’s not included in the count.