Рус Uzb Eng

C10D. Biznes markaz
Ограничение по времени: 2 cекунды
Ограничение по памяти: 64 мегабайт

International Cyber Police Corporation (ICPC) markaziy ofis qilish va ma’lum hududni ijaraga olish va bundan daromad olish uchun yangi megabaland biznes-markaz qurdi. Bunda bir necha qavat bor, va bu shunday noqulaylik tug’diradiki, ya’ni har bir qavatga m-avtomobil lifti uchun alohida tugmalar o’rnatish kerak bo’ladi. Buning o’rniga m-avtomobil liftiga ikkita tugma o’rnatilgan. Bir tugma i-nchi avtomobil tugmasini ui qavat tepaga olib chiqsa, boshqa tugma di qavat pastga olib tushadi. Biznes markaz shunday balandki, biz uni balandligini bu muammo uchun chegaralamaymiz.(Siz hech qachon yuqori qavatga yetib kela olmaysiz), lekin siz birinchi qavatga ham tusha olmaysiz. Barcha qavatlar boshi noldan boshlangan butun sonlar bilan nomerlangan bo’lib, nol birinchi qavat hisoblanadi.
Siz biznes-markazning birinchi qavatidan boshlaysiz. Siz chiqish uchun bitta m-avtomobil liftini tanlashingiz kerak. Bundan keyin siz boshqa avtomobil liftini ishga solishingiz mumkin emas. Aniq bir n-vaqtda avtomobil liftlarini tugmasini bosganda, yerdan baland turgan eng quyi qavat qaysinisi bo’ladi?

Входные данные:
Birinchi qator n va m (1 ≤ n ≤ 1 000 000, 1 ≤ m ≤ 2 000) butun sonlarni o’z ichiga oladi.Mos ravishda tugmalar bosilish sonini va avtomobil liftlari sonini bildiradi. Quyidagi m - chiziqlari avtomobil liftlari sonini bildiradi. Har bir chiziq ikkita butun ui va di (1 ≤ ui, di ≤ 1 000) sonlardan tashkil topgan.

Выходные данные:
Aniq n-vaqtda m lift tugmasiga bosilgandagi yerdan yuqori quyi qavatdagi yagona musbat butun sonni yozing.

Пример ввода Пример вывода
10 3
15 12
15 4
7 12
1 1
239 687
1 1
1000 996
7 2
285 913
255 812
13




239


1000


718
Область: Kombinatorika
Источник задачи: Informatika va axborot texnologiyalari fanidan Respublika fan olimpiadasi 2 - tur, TATU, Toshkent, 2014 yil 12 may

Отправить решение на проверку

Design by TUIT © 2012-2017 TUIT Online Judge. All rights reserved.