Renkli Kısıtlar

Giriş

İlk satırda üç tam sayı $n$, $m$ ve $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) — düğüm, kenar ve renk sayısı verilir.

İkinci satırda uzunluğu $n$ olan ikili $a$ dizgisi verilir; burada a_i, $i$ düğümünün başlangıç bitidir.

Üçüncü satırda $n$ tam sayı w_1,w_2,\ldots,w_n (0 \leq w_i \leq 10^9) — bitleri değiştirme maliyetleri verilir.

Sonraki $m$ satırın her birinde dört tam sayı $u$, $v$, $b$ ve $c$ (1 \leq u,v \leq n, b \in \{0,1\}, 1 \leq c \leq k) verilir. Bu, $u$ ve $v$ düğümleri arasında x_u \oplus x_v=b kısıtını getiren $c$ renkli bir kenarı tanımlar.

Çizgede paralel kenarlar ve ilmekler bulunabilir. Bazı renkler kenarlar arasında hiç geçmeyebilir.

Çıktı

$k$ tam sayı yazdırın.

$c$ konumundaki sayı, $c$ renkli tüm kenarlar silindikten sonraki minimum maliyet olmalıdır; kalan kısıtların tümü sağlanamıyorsa $-1$ yazdırın.

Örnekler

Not

Birinci örnekte, $1$, $2$ ve $3$ renkli kenarlar silindikten sonra son bitler sırasıyla 100, 110 ve 000 seçilebilir. Minimum maliyetler sırasıyla 5+2=7, $5$ ve $2$'dir.

İkinci örnekte, $1$ renginin silinmesiyle birbirinin aynısı olan iki x_1=x_2 kısıtı kalır. Birinci düğümün bitini $4$ maliyetle değiştirmek yeterlidir. $2$ renginin veya çizgede bulunmayan $3$ renginin silinmesiyle x_1 \oplus x_1=1 gerektiren bir ilmek kalır ki bunu sağlamak mümkün değildir.

Üçüncü örnekte hiç kenar yoktur. Her renk için tüm başlangıç bitleri değiştirilmeden bırakılabilir, bu yüzden her iki cevap da $0$'dır.

Puanlama

1. $20$ puan — k=1.

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

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

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

5. $80$ puan — her kenar için b=0.

6. $100$ puan — her düğüm için w_i=0.

7. $120$ puan — ek kısıt yoktur.