[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。

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

3