13946번 - Bipartite Blanket 다국어

문제

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₁, a₂, . . . , a_n and the nodes of B with b₁, b₂, . . . , 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₁, v₂, . . . , v_n (1 ≤ v_k ≤ 10 000 000) — the weights of the nodes a₁, a₂, . . . a_n. The following line contains m integers w₁, w₂, . . . , w_m (1 ≤ w_k ≤ 10 000 000) — the weights of the nodes b₁, b₂, . . . 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.

제한

힌트

In the first example above, subset {a₁, a₂, b₂, b₃} is blanketed by matching {(a₁, b₂),(a₂, b₃)} and has weight 21. Subsets {a₃, b₂, b₃} and {a₂, a₃, b₂, b₃} are both blanketed by matching {(a₂, b₃),(a₃, b₂)}, 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₂, a₃, b₁, b₃} has weight 26, but is not blanketed by any matching, so it’s not included in the count.