EduBrick
← вернуться к уроку · Жадные идеи и их ловушки

Покрыть отрезок

5000 мс · 256 МБ · всё или ничего

Дорога тянется от точки 0 до точки mm. Есть nn бригад, бригада с номером ii готова обслуживать участок [li,ri][l_i, r_i].

Выберите наименьшее число бригад так, чтобы вся дорога от 0 до mm была обслужена. Если это невозможно, выведите -1.

Формат ввода

В первой строке числа nn от 11 до 21052 \cdot 10^5 и mm от 11 до 10910^9. Во второй — 2n2n чисел: пары lil_i и rir_i подряд, 0liri1090 \le l_i \le r_i \le 10^9.

Формат вывода

Одно число.

Примеры

ввод
3 8
0 3 2 5 4 8
вывод
3

Примечание

Держите точку, до которой дорога уже обслужена. Из всех бригад, начинающих не позже неё, берите ту, что тянется дальше всех. Если такой нет — ответа не существует.

Войдите, чтобы отправлять решения.
← Вернуться к уроку