Biznes Mərkəzi#522
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. O qədər çox mərtəbə var ki, hər bir liftində hər mərtəbə üçün ayrı 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. -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ə enmək mümkün deyil. 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. liftindən birini seçməlisiniz və seçiminizdən sonra liftləri dəyişə bilməzsiniz. Liftin düymələrini dəqiq dəfə basdıqdan sonra yeraltı mərtəbədən yuxarıda olan ən aşağı mərtəbə hansıdır?
Giriş faylının ilk sətri iki tam ədəd və (1 \le n \le 1\ 000\ 000, 1 \le m \le 2000) — düymə basmalarının sayı və seçmək üçün liftlərin sayı. Sonrakı sətir liftləri təsvir edir. Hər sətir iki tam ədəd u_i və d_i (1 \le u_i, d_i \le 1\ 000) ehtiva edir.
Çıxış faylına bir müsbət tam ədəd yazın — liftlərdən birinin düymələrini dəqiq 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.
Nümunə 1