Bipartitna Barikada

U bipartitnom grafu, čvorovi se mogu podijeliti u dva disjunktna skupa $A$ i $B$ tako da svaki brid povezuje čvor iz skupa $A$ s čvorom iz skupa $B$. Sparivanje $M$ je skup bridova gdje nijedna dva brida ne dijele zajednički čvor. Kažemo da sparivanje $M$ barikadira skup čvorova $V$ ako je svaki čvor iz $V$ krajnja točka barem jednog brida iz $M$.

Zadan je bipartitan graf u kojem je svakom čvoru pridružena cjelobrojna težina. Pritom, težinu skupa čvorova definiramo kao sumu težina čvorova toga skupa.

Za dani cijeli broj $t$, potrebno je pronaći broj skupova $V$ takvih da je njihova težina barem $t$ te da je skup $V$ barikadiran barem jednim sparivanjem $M$.

U prvom su retku prirodni brojevi $n$ i $m$ ($1 ≤ n, m ≤ 20$) koji redom predstavljaju broj čvorova u skupovima $A$ i $B$. Označit ćemo čvorove u skupu $A$ s $a_1, a_2, \dots , a_n$, a čvorove u skupu $B$ s $b_1, b_2, \dots , b_m$.

Svaki od idućih $n$ redaka sastoji se od $m$ znakova koji opisuju bridove bipartitnog grafa. Preciznije, $j$-ti znak u $i$-tom retku je '1' ako postoji brid koji spaja čvorove $a_i$ i $b_j$, odnosno '0' tako to nije slučaj.

U idućem je retku $n$ prirodnih brojeva $v_1, v_2, \dots , v_n$ ($1 ≤ v_k ≤ 10\, 000\, 000$) koji redom predstavljaju težine čvorova $a_1, a_2, \dots , a_n$.

U idućem je retku $m$ prirodnih brojeva $w_1, w_2, \dots , w_m$ ($1 ≤ w_k ≤ 10\, 000\, 000$) koji redom predstavljaju težine čvorova $b_1, b_2, \dots , b_m$.

U posljednjem je retku prirodan broj $t$ ($1 ≤ t ≤ 400\, 000\, 000$) iz teksta zadatka.

Ispišite broj skupova čvorova težine barem $t$ koji su barikadirani barem jednim sparivanjem.

Pojašnjenje prvog probnog primjera:

Skup $\{a_1, a_2, b_2, b_3\}$ je barikadiran sparivanjem $\{(a_1, b_2),(a_2, b_3)\}$ i ima težinu $21$. Skupovi $\{a_3, b_2, b_3\}$ i $\{a_2, a_3, b_2, b_3\}$ barikadirani su sparivanjem $\{(a_2, b_3),(a_3, b_2)\}$, te redom imaju težine $21$ i $23$. Preostali skupovi čvorova ili imaju težinu manju od $21$ ili nisu barikadirani niti jednim sparivanjem. Primjerice, skup $\{a_2, a_3, b_1, b_3\}$ ima težinu $26$, međutim ne postoji sparivanje koje ga barikadira.