BOI’ 2005 RHODES Island – HELLAS 
3-8 September 2005
Bulgaria
Задача 2. Заявки

Разглеждаме набор от обекти с еднакви размери, кутия, в която могат да се поместят К обекта и последователност от N заявки към обектите. На всяка заявка към даден обект е съпоставено в съответствие време, което определя до кога обектът е валиден. Цената на заявка към обект, който се намира в кутията и все още е валиден, е нула. Ако заявеният обект не се намира в кутията, той трябва да бъде поместен, като цената за това е една единица. Цената на обновяването на времето за валидност на все още валиден обект е нула. Цената на обновяването на времето за валидност на обект с изтекла валидност е една единица. 
Поместването в запълнена кутия на нов обект или обновяването на обект, чиято валидност е изтекла, изисква прилагането на алгоритъм за заместване, за определяне на обект измежду намиращите се в момента в кутията, който да бъде изваден, за да може да се помести новият. В самото начало кутията е празна. 
Вашата задача е да разработите алгоритъм за заместване, чрез който зададените заявки ще се изпълнят с обща минимална цена.

Бележка: Всички заявки са известни от самото начало.

Вход
Входните данни се четат от файл “requests.in”.  Първият ред на файла съдържа цяло число K, задаващо капацитета на кутията (6≤K≤ 100). Вторият ред съдържа цяло число N – брой на заявките (61≤N ≤1000). Всеки от следващите N реда съдържа двойка цели числа P и Q. P е заявеният обект, а Q е времето, до което обектът е валиден (абсолютно време) (обектът е валиден до зададения момент включително). След всяка заявка абсолютното време се увеличава с една единица. Първата заявка се появява във време 1.

Изход
Програмата трябва да изведе във файл “requests.out” единствен ред, съдържащ едно цяло число – определената минимална цена за изпълнение на заявките.

Пример
requests.in 
3
6
1 2
2 4
2 4
3 5
3 9
2 9	requests.out 
4	

Формат: Във всеки от файловете числата в един ред са разделени с единичен интервал. Всички редове завършват с край на ред.

Време за изпълнение: 1 секунда.