İkiyönlü Örtük#9724

İkiyönlü Örtük

1 saniyə

128 meqabayt

Çox çətin

İkiyönlü qrafda zirvələr $A$ və $B$ kimi iki kəsişməyən çoxluğa bölünüb, hər bir kənar $A$ -dakı bir zirvəni $B$ -dəki bir zirvə ilə birləşdirir. Tutma $M$ — ümumi zirvəsi olmayan kənarların çoxluğudur. Bir tutmanın $M$ zirvələr çoxluğunu $V$ örtməsi deyilir, əgər $V$ -də hər bir zirvə $M$ -dən ən azı bir kənarın ucu olarsa.

Qrafda hər bir zirvəyə müsbət tam ədəd olan bir çəki verilmişdir. Zirvələr çoxluğunun çəkisi onun tərkibindəki zirvələrin çəkilərinin cəmi kimi təyin olunur.

Bütöv bir eşik $t$ verilib. Çəkilərinin cəmi ən azı $t$ olan və ən azı bir tutma $M$ ilə örtülən fərqli zirvələr çoxluqlarının sayını müəyyən edin.

Giriş

Birinci sətirdə iki tam ədəd $n$ və $m$ ( $1 \leq n, m \leq 20$ 1 \le n, m \le 20) verilmişdir — $A$ və $B$ çoxluqlarındakı zirvələrin sayı müvafiq olaraq. $A$ çoxluğundaki zirvələri $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n, və $B$ çoxluğundaki zirvələri $b_{1}, b_{2}, \dots, b_{m}$ b_1, b_2, \ldots, b_m kimi ifadə edək.

Sonraki $n$ sətir qrafın kənarlarını təsvir edən $m$ simvolu ehtiva edir. Əgər $a_{i}$ a_i ilə $b_{j}$ b_j arasında kənar varsa, $i$ -ci sətirdə $j$ -ci simvol " $1$ " olur və əks halda " $0$ " olur.

Növbəti sətir $n$ tam ədəd $v_{1}, v_{2}, \dots, v_{n}$ v_1, v_2, \ldots, v_n ( $1 \leq v_{k} \leq 1 0^{7}$ 1 \le v_k \le 10^7) ehtiva edir — $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n zirvələrinin çəkiləri.

Sonra $m$ tam ədəd $w_{1}, w_{2}, \dots, w_{m}$ w_1, w_2, \ldots, w_m olan bir sətir gəlir ( $1 \leq w_{k} \leq 1 0^{7}$ 1 \le w_k \le 10^7) — $b_{1}, b_{2}, \dots, b_{m}$ b_1, b_2, \ldots, b_m zirvələrinin çəkiləri.

Sonuncu sətir isə bir tam ədəd olan $t$ -i ehtiva edir ( $1 \leq t \leq 4 \cdot 1 0^{8}$ 1 \le t \le 4 \cdot 10^8) — çəki eşiyi.

Çıxış

Çəkilərinin cəmi ən azı $t$ olan və ən azı bir tutma $M$ ilə örtülən zirvələr çoxluqlarının sayını çıxarın.

Nümunələr

Göstərilən nümunədə $a_{1}, a_{2}, b_{2}, b_{3}$ {a_1, a_2, b_2, b_3} altçoxluğu $(a_{1}, b_{2}), (a_{2}, b_{3})$ {(a_1, b_2), (a_2, b_3)} tutması ilə örtülür və çəkisi $21$ -dir.

Altçoxluqlar $a_{3}, b_{2}, b_{3}$ {a_3, b_2, b_3} və $a_{2}, a_{3}, b_{2}, b_{3}$ {a_2, a_3, b_2, b_3} də $(a_{2}, b_{3}), (a_{3}, b_{2})$ {(a_2, b_3), (a_3, b_2)} tutması ilə örtülür və onların çəkisi müvafiq olaraq $21$ və $23$ -dir.

Qalan bütün digər çoxluqlar ya çəkisinin cəmi $21$ -dən azdır, ya da heç bir tutma ilə örtülmür.

Məsələn, $a_{2}, a_{3}, b_{1}, b_{3}$ {a_2, a_3, b_1, b_3} altçoxluğu çəkisi $26$ -dır, lakin heç bir tutma ilə örtülmür və buna görə də sayda nəzərə alınmır.

Nümunə 2

Nümunə 1