Biznes Mərkəzi
Beynəlxalq Kibercinayətkarlıq Polisi Korporasiyası (ICPC) yeni bir mega-hündür biznes mərkəzi inşa edib. Bu mərkəzdə qərargahlarını yerləşdirmək və əlavə gəlir əldə etmək üçün bəzi sahələri icarəyə vermək istəyirlər. Mərkəzin o qədər çox mərtəbəsi var ki, hər bir m liftində hər mərtəbə üçün ayrıca düymə yerləşdirmək mümkün deyil. Bunun əvəzinə, hər bir lift yalnız iki düymə ilə təchiz olunub. i-ci liftin bir düyməsi onu u_i mərtəbə yuxarı, digəri isə d_i mərtəbə aşağı hərəkət etdirir. Mərkəzin hündürlüyü o qədərdir ki, bu problem üçün onun hündürlüyünü nəzərə almaya bilərsiniz (ən üst mərtəbəyə heç vaxt çatmayacaqsınız), lakin yeraltı mərtəbəyə gedə bilməzsiniz. Bütün mərtəbələr sıfırdan başlayaraq tam ədədlərlə nömrələnir, sıfır yeraltı mərtəbədir.
Siz biznes mərkəzinin yeraltı mərtəbəsində başlayırsınız. m liftindən birini seçməlisiniz və seçiminizdən sonra liftləri dəyişə bilməzsiniz. Liftin düymələrini dəqiq n dəfə basdıqdan sonra yeraltı mərtəbədən yuxarıda olan ən aşağı mərtəbə hansıdır?
Giriş verilənləri
Giriş faylının ilk sətri iki tam ədəd n və m (1 <= n <= 1 000 000, 1 <= m <= 2000) – düymə basmalarının sayı və seçmək üçün liftlərin sayı. Sonrakı m sətir liftləri təsvir edir. Hər sətir iki tam ədəd u_i və d_i (1 <= u_i, d_i <= 1 000) ehtiva edir.
Çıxış verilənləri
Çıxış faylına bir müsbət tam ədəd yazın – m liftlərdən birinin düymələrini dəqiq n dəfə basdıqdan sonra yeraltı mərtəbədən yuxarıda çatmaq mümkün olan ən aşağı mərtəbənin nömrəsi.