[CERC2016] 二分毯 Bipartite Blanket
题目描述
在二分图中,所有点被划分成了两个不相交的集合 $A$ 和 $B$,每条边都恰好连接着某个 $A$ 和某个 $B$。一个匹配是一个边集,满足没有任何两条边有相同的端点。我们称一个匹配 $M$ 覆盖了点集 $V$ 当且仅当 $V$ 中的每个点都是 $M$ 中至少一条边的端点。
给定一个二分图,每个点有一个正整数权值。定义一个点集的权值为其中所有点的权值之和。
给定一个参数 $t$,请统计有多少点集 $V$,满足 $V$ 的权值不小于 $t$,且 $V$ 被至少一个匹配 $M$ 覆盖。
输入输出格式
输入格式
第一行包含两个正整数 $n,m$,分别表示 $A$ 集合的点数和 $B$ 集合的点数。
接下来 $n$ 行,每行 $m$ 个 01 字符,其中第 $i$ 行第 $j$ 列为 $1$ 表示 $A_i$ 和 $B_j$ 之间有一条边。
接下来一行包含 $n$ 个正整数 $v_1,v_2,\cdots,v_n$,分别表示 $A$ 中每个点的权值。
接下来一行包含 $m$ 个正整数 $w_1,w_2,\cdots,w_m$,分别表示 $B$ 中每个点的权值。
最后一行包含一个正整数 $t$,表示参数 $t$。
输出格式
输出一行一个整数,即满足条件的点集个数。
输入输出样例
输入样例 #1
3 3
010
111
010
1 2 3
8 5 13
21
输出样例 #1
3
说明
$1\leq n,m\leq 20$,$1\leq v_i,w_i\leq 10^7$,$1\leq t\leq 4\times 10^8$。