eolymp
Задачи

Телепорты

Телепорты

Вы участвуете в соревновании по пересечению Египта с запада на восток по прямолинейному отрезку. Вначале вы располагаетесь в западном конце отрезка. По правилам соревнования вы должны двигаться только по отрезку и только на восток.

prb279

На отрезке есть n телепортов. Телепорт задается двумя точками на отрезке. Всякий раз, когда вы достигаете одной из этих точек, телепорт немедленно телепортирует вас в другую точку (следует заметить, что в зависимости от того, какой точки вы достигли, телепорт может отправить вас как на восток, так и на запад от вашего текущего положения). После телепортирования вы должны продолжать двигаться на восток вдоль отрезка. Вы не можете избежать точек телепортов, которые находятся на вашем пути. Нет двух точек телепортов с одинаковой позицией. Все точки телепортов находятся строго между началом и концом отрезка.

Каждый раз, когда вы телепортируетесь, вы получаете один балл. Цель cоревнования – получить как можно больше баллов. Чтобы максимизировать баллы, которые вы получаете, вам разрешено добавить на отрезке не более m новых телепортов перед началом вашего путешествия. При использовании новых телепортов вы также получаете баллы.

Вы можете поставить точки новых телепортов везде, где хотите (даже в нецелых позициях), но так, чтобы они не занимали позиции, уже занятые другими точками телепортов, то есть, позиции всех точек, принадлежащих всем телепортам, должны быть различными. Точки новых телепортов также должны лежать строго между началом и концом отрезка.

Следует заметить, что гарантируется, что вне зависимости от способа добавления телепортов, всегда можно достичь конца отрезка.

Напишите программу, которая по заданным позициям точек для n телепортов и количеству m новых телепортов, которые вы можете добавить, вычисляет максимальное количество баллов, которые можно получить в итоге.

Входные данные

Первая строка содержит количество телепортов n (1n106), изначально имеющихся на отрезке.

Вторая строка содержит максимальное количество m (1m106) новых телепортов, которые можно добавить.

Каждая из последующих n строк описывает один телепорт, при этом i-ая из этих строк описывает i-ый телепорт. Каждая строка состоит из двух целых чисел wi и ei (1wi, ei2*106), разделенных пробелом. Эти числа представляют собой расстояния от начала отрезка до западной и восточной точки телепорта соответственно.

Никакие две точки заданных телепортов не расположены в одной позиции. Отрезок, по которому вам нужно будет передвигаться, начинается с позиции 0 и заканчивается в позиции 2 000 001.

Выходные данные

Вывести одно целое число – максимальное количество баллов, которые можно заработать.

Лимит времени 3 секунды
Лимит использования памяти 64 MiB
Входные данные #1
3
1
10 11
1 4
2 3
Выходные данные #1
6
Источник 2008 IOI