Дорога тянется от точки 0 до точки . Есть бригад, бригада с номером готова обслуживать участок .
Выберите наименьшее число бригад так, чтобы вся дорога от 0 до была обслужена. Если это невозможно, выведите -1.
Формат ввода
В первой строке числа от до и от до . Во второй — чисел: пары и подряд, .
Формат вывода
Одно число.
Примеры
ввод
3 8 0 3 2 5 4 8
вывод
3
Примечание
Держите точку, до которой дорога уже обслужена. Из всех бригад, начинающих не позже неё, берите ту, что тянется дальше всех. Если такой нет — ответа не существует.
Войдите, чтобы отправлять решения.