8788: BZOJ4788：[CERC2016]Bipartite Blanket

在二分图中，所有点被划分成了两个不相交的集合A和B，每条边都恰好连接着某个A和某个B。一个匹配是一个边集 ，满足没有任何两条边有相同的端点。我们称一个匹配M覆盖了点集V当且仅当V中的每个点都是M中至少一条边的端 点。给定一个二分图，每个点有一个正整数权值。定义一个点集的权值为其中所有点的权值之和。给定一个参数t ，请统计有多少点集V，满足V的权值不小于t，且V被至少一个匹配M覆盖。

输入格式

第一行包含两个正整数n,m(1<=n,m<=20)，分别表示A集合的点数和B集合的点数。 接下来n行，每行m个01字符，其中第i行第j列为1表示A_i和B_j之间有一条边。 接下来一行包含n个正整数v_1,v_2,...,v_n(1<=v_i<=10^7)，分别表示A中每个点的权值。 接下来一行包含m个正整数w_1,w_2,...,w_m(1<=w_i<=10^7)，分别表示B中每个点的权值。 最后一行包含一个正整数t(1<=t<=4*10^8)，表示参数t。

输出格式

输出一行一个整数，即满足条件的点集个数。

样例输入

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

样例输出

3
HINT
3个集合分别为{a1,a2,b2,b3}、{a3,b2,b3}、{a2,a3,b2,b3}。

提示

没有写明提示

题目来源

没有写明来源