이분 바리케이드

이분 그래프에서 정점은 서로소인 두 집합 $A$와 $B$로 나눌 수 있으며, 모든 간선은 $A$의 정점과 $B$의 정점을 잇습니다. 매칭 $M$은 두 간선이 정점을 공유하지 않는 간선들의 집합입니다. 매칭 $M$이 정점 집합 $V$를 바리케이드한다는 것은 $V$의 모든 정점이 $M$에 속한 간선 중 하나의 끝점이라는 뜻입니다.

각 정점에는 정수 가중치가 주어집니다. 정점 집합의 가중치는 그 집합에 속한 정점들의 가중치 합입니다.

정수 $t$가 주어졌을 때, 가중치가 $t$ 이상이면서 적어도 하나의 매칭으로 바리케이드되는 정점 집합 $V$의 개수를 구하세요.

첫 줄에 자연수 $n$과 $m$ ($1 \le n, m \le 20$)이 주어집니다. 각각 집합 $A$와 $B$의 정점 수입니다. 정점은 $a_1, \dots, a_n$과 $b_1, \dots, b_m$으로 표시합니다.

다음 $n$개 줄에는 각각 $m$개의 문자가 주어집니다. $i$번째 줄의 $j$번째 문자가 '1'이면 $a_i$와 $b_j$를 잇는 간선이 있고, '0'이면 없습니다.

다음 줄에는 $a_1, \dots, a_n$의 가중치 $v_1, \dots, v_n$ ($1 \le v_k \le 10000000$)이 주어집니다.

다음 줄에는 $b_1, \dots, b_m$의 가중치 $w_1, \dots, w_m$ ($1 \le w_k \le 10000000$)이 주어집니다.

마지막 줄에는 자연수 $t$ ($1 \le t \le 400000000$)가 주어집니다.

가중치가 $t$ 이상이면서 적어도 하나의 매칭으로 바리케이드되는 정점 집합의 개수를 출력하세요.

첫 번째 예시에 대한 설명입니다. 집합 $\{a_1, a_2, b_2, b_3\}$은 매칭 $\{(a_1, b_2), (a_2, b_3)\}$으로 바리케이드되며, 가중치는 21입니다. 집합 $\{a_3, b_2, b_3\}$과 $\{a_2, a_3, b_2, b_3\}$은 매칭 $\{(a_2, b_3), (a_3, b_2)\}$으로 바리케이드되며, 가중치는 각각 21과 23입니다. 나머지 정점 집합은 가중치가 21보다 작거나 어떤 매칭으로도 바리케이드되지 않습니다. 예를 들어 집합 $\{a_2, a_3, b_1, b_3\}$의 가중치는 26이지만, 이를 바리케이드하는 매칭은 존재하지 않습니다.