Rəngli məhdudiyyətlər

Giriş

Birinci sətirdə üç tam ədəd $n$, $m$ və $k$ (1 \leq n \leq 2 \cdot 10^5, 0 \leq m \leq 2 \cdot 10^5, 1 \leq k \leq 2 \cdot 10^5) — təpələrin, tillərin və rənglərin sayı verilir.

İkinci sətirdə uzunluğu $n$ olan ikilik $a$ sətri verilir. Burada a_i, $i$ təpəsinin başlanğıc bitidir.

Üçüncü sətirdə $n$ tam ədəd w_1,w_2,\ldots,w_n (0 \leq w_i \leq 10^9) — bitləri dəyişməyin xərcləri verilir.

Növbəti $m$ sətrin hər birində dörd tam ədəd $u$, $v$, $b$ və $c$ (1 \leq u,v \leq n, b \in \{0,1\}, 1 \leq c \leq k) verilir. Bu, $u$ və $v$ təpələri arasında x_u \oplus x_v=b şərtini qoyan $c$ rəngli til olduğunu bildirir.

Qrafda paralel tillər və ilgəklər ola bilər. Bəzi rənglər heç bir tildə istifadə olunmaya bilər.

Çıxış

$k$ tam ədəd çap edin.

$c$ mövqeyindəki ədəd $c$ rəngli bütün tillər silindikdən sonra minimum xərcə bərabər olmalıdır. Qalan bütün şərtləri ödəmək mümkün deyilsə, $-1$ çap edin.

Nümunələr

Qeyd

Birinci nümunədə $1$, $2$ və $3$ rəngli tillər silindikdən sonra son bitləri uyğun olaraq 100, 110 və 000 seçmək olar. Minimum xərclər uyğun olaraq 5+2=7, $5$ və $2$-dir.

İkinci nümunədə $1$ rəngi silindikdən sonra iki eyni x_1=x_2 şərti qalır. Birinci təpənin bitini $4$ xərclə dəyişmək kifayətdir. $2$ rəngi və ya qrafda olmayan $3$ rəngi silindikdə x_1 \oplus x_1=1 şərtini qoyan ilgək qalır. Bu şərti ödəmək mümkün deyil.

Üçüncü nümunədə til yoxdur. Hər rəng üçün bütün başlanğıc bitlərini dəyişmədən saxlamaq olar, buna görə hər iki cavab $0$-dır.

Bal hesablama

1. $20$ bal — k=1.

2. $40$ bal — n \leq 16, m \leq 30, k \leq 10.

3. $60$ bal — n,m,k \leq 2000.

4. $80$ bal — k \leq 20.

5. $80$ bal — bütün tillər üçün b=0.

6. $100$ bal — bütün təpələr üçün w_i=0.

7. $120$ bal — əlavə məhdudiyyət yoxdur.