Телепорти
Ви приймаєте участь у змаганнях по перетину Єгипту з заходу на схід по прямолінійному відрізку. Спочатку ви розміщені у західному кінці відрізку. За правилами змагань ви повинні рухатись лише по відрізку і лише на схід.
На відрізку є N телепортів. Телепорт задається двома точками на відрізку. Кожен раз, коли ви досягаєте однієї з таких точек, телепорт миттєво телепортує вас в іншу точку (слід відмітити, що в залежності від того, якої точки ви досягли, телепорт може відправити вас як на схід, так і на захід від вашого поточного положення). Після телепортування ви повинні продовжувати рухатись на схід вздовж відрізка. Ви не можете уникнути точок телепортів, які знаходяться на вашому шляху. Немає двох точок телепортів з однаковою позицією. Всі точки телепортів знаходяться строго між початком і кінцем відрізку.
Кожен раз, коли ви телепортуєтесь, ви отримуєте один бал. Мета змагань – отримати якомога більше балів. Щоб максимизувати бали, які ви отримуєте, вам дозволено добавляти на відрізку не більше M нових телепортів перед початком вашої подорожі. При використанні нових телепортів ви також отримуєте бали.
Ви можете поставити точки нових телепортів скрізь, де хочете (навіть в не цілих позиціях), але так, щоб вони не займали позициї, вже зайняті іншими точками телепортів, тобто, позиції всіх точок, що належать всім телепортам, повинні бути відмінні. Точки нових телепортів також повинні лежати строго між початком та кінцем відрізку.
Слід відмітити, що гарантується, що незалежно від способу додавання телепортів, завжди можна досягнути кінця відрізку.
Завдання
Напишіть програму, яка за заданими позиціями точок для N телепортів та кількості M нових телепортів, які ви можете добавити, обчисоює максимальну кількість балів, яку можна отримати в результаті.
Обмеження
1 <= N <= 1 000 000 (N – кількість телепортів, що є спочатку на відрізку)
1 <= M <= 1 000 000 (M – максимальна кількість нових телепортів, які ви можете додати)
1 <= WX < EX <= 2 000 000 (WX та EX – відстані від початку відрізку до західної та східної точки телепорту X)
Вхідні дані
Ваша програма повинна читати зі стандартного вводу дані у настунному форматі:
• Рядок 1 містить ціле число N – кількість телепортів, що є спочатку на відрізку.
• Рядок 2 містить ціле число M – максимальну кількість нових телепортів, які можна додати.
• Кожен з наступних N рядків описує один телепорт, при цьому i-й з цих рядків описує i-й телепорт. Кожен рядок складається з двох цілих чисел W_i та E_i, відокремлених пропуском. Ці числа представляють собою відстані від початку відрізка до західної та східної точок телепорту відповідно.
Ніякі дві точки заданих телепортів не розміщені в одній позиції. Відрізок, по якому вам потрібно буде пересуватись, починається у позиції 0 і завершується у позиції 2 000 001.
Вихідні дані
Ваша програма повинна вивести у стандартний вивід єдиний рядок, що містить одне ціле число – максимальну кількість балів, які можна отримати.