Ən böyük axın B
Ən böyük axın B
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 ai
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 bi
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 n və k (1 ≤ n ≤ 104
, 0 ≤ k ≤ 105
) ə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 ai
(1 ≤ ai
≤ 104
) ə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 bi
(1 ≤ bi
≤ 104
) ə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 u və v (1 ≤ u, v ≤ n) ədədləri verilir.
Çıxış verilənləri
Ən böyük axının qiymətini verin.
3 4 3 2 1 5 4 4 1 1 1 2 2 3 3 3
6