Минимакс cütləşmə
Verilmiş tam ikiqat qrafda, hər bir hissə N zirvədən ibarətdir. Hər zirvəyə bir çəki - tam ədəd təyin olunub. Kənarın çəkisi isə, onun birləşdirdiyi zirvələrin çəkilərinin hasilinə bərabərdir.
Qrafda uyğunluq, bir-biri ilə ortaq zirvəsi olmayan kənarların çoxluğuna deyilir. Əgər uyğunluq qrafın bütün zirvələrini əhatə edirsə, yəni qrafın hər zirvəsi uyğunluğun hansısa kənarına təsadüf edirsə, bu uyğunluq mükəmməl adlanır.
Sizin vəzifəniz mükəmməl minimaks uyğunluğu tapmaqdır. Yəni uyğunluğun kənarlarının çəkilərindən ən böyüyü mümkün olan ən kiçik olmalıdır.
Giriş verilənləri
Giriş faylının birinci sətirində tam ədəd N (1 ≤ N ≤ 10^5) verilib. İkinci sətirdə - modulca 10^9-dan böyük olmayan N tam ədəd verilib. Buradakı i-ci ədəd qrafın birinci hissəsinin i-ci zirvəsinin çəkisini göstərir. Üçüncü sətirdə isə eyni qaydada ikinci hissənin zirvələrinin çəkiləri təqdim olunub. Hər bir hissənin zirvələri 1-dən N-ə qədər nömrələnib.
Çıxış verilənləri
Çıxış faylının birinci sətirində bir tam ədəd - mükəmməl minimaks uyğunluğun çəkisi, yəni onun kənarlarının çəkilərindən ən böyüyü. İkinci sətirdə isə bu uyğunluğun təsviri - N tam ədəd, burada i-ci ədəd birinci hissənin i-ci zirvəsi ilə uyğunluq kənarı ilə birləşdirilmiş ikinci hissənin zirvəsinin nömrəsini göstərir.