eolymp
bolt
Try our new interface for solving problems
Məsələlər

Ən böyük axın B

Ən böyük axın B

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Mənbə və mənsəb ikipaylı qrafı verilir. Hər bir pay n təpə ehtiva edir. Mənbədən sol paya ötürücülük qabiliyyəti a[i] olan til aparılır, sağ payın hər bir təpəsindən mənsəbə ötürücülük qabiliyyəti b[i] olan til aparılır. Həmçinin sol və sağ pay təpələri arasında axının bu və ya digər istiqamətdə ola biləcəyi sonsuz ötürücülük qabiliyyəti olan til vardır. Mənbədən mənsəbə ən böyük axının qiymətini təyin edin.

Giriş verilənləri

İlk sətirdə hər bir paydakı təpələrin sayını və paylar arasındakı tillərin sayını ifadə edən nk (1n10^4, 0k10^5) ədədləri verilir. İkinci sətirdə mənbədən sol payın hər bir təpəsinə olan tillərin ötürücülük qabiliyyətlərini ifadə edən a[i] (1a[i]10^4) ədədləri verilir. Üçüncü sətirdə sağ payın hər bir təpəsindən mənsəbə olan tillərin ötürücülük qabiliyyətlərini ifadə edən b[i] (1b[i]10^4) ədədləri verilir. Növbəti k sətrin hər birində tilin olduğunu və sol payın u təpələri və sağ payın v təpələrini ifadə edən iki uv (1u, vn) ədədləri verilir.

Çıxış verilənləri

Ən böyük axının qiymətini verin.

Nümunə

Giriş verilənləri #1
3 4
3 2 1
5 4 4
1 1
1 2
2 3
3 3
Çıxış verilənləri #1
6
Mənbə III International Summer School Programming in Sevastopol 2012