이분 그래프 덮기

이분 그래프는 정점 집합이 서로소인 두 집합 $A$와 $B$로 나뉘고, 모든 간선이 $A$의 정점 하나와 $B$의 정점 하나를 잇는 그래프다. 매칭 $M$은 어떤 두 간선도 정점을 공유하지 않는 간선 집합이다. 정점 집합 $V$에 속한 모든 정점이 $M$의 어떤 간선의 끝점이면, 매칭 $M$이 $V$를 덮는다고 하자.

각 정점에 양의 정수 가중치가 붙은 이분 그래프가 주어진다. 정점 집합의 가중치는 그 집합에 속한 정점의 가중치를 모두 더한 값이다.

정수 기준값 $t$가 주어진다. 가중치가 $t$ 이상이면서 적어도 하나의 매칭이 덮는 정점 집합 $V$가 몇 개인지 구하라. $V$는 $A \cup B$의 부분집합이며, 서로 다른 두 부분집합은 다른 것으로 센다.

첫째 줄에 $A$의 정점 개수 $n$과 $B$의 정점 개수 $m$이 공백으로 구분되어 주어진다 ($1 \le n, m \le 20$). $A$의 정점을 $a_1, a_2, \dots, a_n$, $B$의 정점을 $b_1, b_2, \dots, b_m$이라고 하자.

다음 $n$개 줄에는 간선을 나타내는 $m$개의 문자가 주어진다. $i$번째 줄의 $j$번째 문자는 $a_i$와 $b_j$ 사이에 간선이 있으면 1, 없으면 0이다.

다음 줄에 $n$개의 정수 $v_1, v_2, \dots, v_n$이 주어진다 ($1 \le v_k \le 10\,000\,000$). $v_k$는 $a_k$의 가중치다. 그다음 줄에 $m$개의 정수 $w_1, w_2, \dots, w_m$이 주어진다 ($1 \le w_k \le 10\,000\,000$). $w_k$는 $b_k$의 가중치다.

마지막 줄에 정수 $t$가 주어진다 ($1 \le t \le 400\,000\,000$).

가중치가 $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이지만 이를 덮는 매칭이 없으므로 세지 않는다.