题目描述

在二分图中，所有点被划分成了两个不相交的集合 $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$。

输出格式

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

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

3

数据规模与约定

对于 $100\%$ 的数据，$1\leq n,m\leq 20$，$1\leq v_i,w_i\leq 10^7$，$1\leq t\leq 4\times 10^8$。