Вы играете с очень длинной полоской, состоящей из \(10^{18}\) белых клеток и пронумерованной слева направо числами \(0\), \(1\), \(2\) и так далее. Вы управляете особым указателем, который первоначально указывает на клетку \(0\). Также у вас есть кнопка «Shift», которую вы можете зажимать.
За один шаг, вы можете сделать одно из трех действий:
- сдвинуть указатель вправо (из клетки \(x\) в клетку \(x + 1\));
- нажать и держать кнопку «Shift»;
- отпустить кнопку «Shift»: в момент, когда вы отпустите Shift, все клетки, которые были посещены с зажатым Shift, будут покрашены в черный.
(Конечно же, вы не можете нажать на уже зажатый Shift. Аналогично, вы не можете отпустить уже отпущенный Shift.)
Ваша задача — покрасить хотя бы \(k\) клеток, но есть ограничение: вам заданы \(n\) отрезков \([l_i, r_i]\) — вы можете красить только клетки, которые принадлежат этим отрезкам, т. е. вы можете покрасить клетку \(x\) только если \(l_i \le x \le r_i\) для некоторого \(i\).
Какое наименьшее количество шагов вам нужно выполнить, чтобы покрасить хотя бы \(k\) клеток в черный?
Выходные данные
Для каждого набора входных данных выведите наименьшее количество шагов, необходимых для покраски хотя бы \(k\) клеток в черный, или \(-1\), если это невозможно.
Примечание
В первом наборе входных данных, одна из оптимальных стратегий — следующая:
- Сдвинуть вправо: указатель сдвигается в ячейку \(1\);
- Зажать Shift;
- Отпустить Shift: клетка \(1\) покрасится в черный;
- Сдвинуть вправо: указатель сдвигается в ячейку \(2\);
- Сдвинуть вправо: указатель сдвигается в ячейку \(3\);
- Зажать Shift;
- Сдвинуть вправо: указатель сдвигается в ячейку \(4\);
- Отпустить Shift: клетки \(3\) и \(4\) покрасятся в черный.
Мы покрасили
\(3\) клетки за
\(8\) шагов.
Во втором наборе входных данных, мы можем покрасить только \(8\) клеток, а нам нужно покрасить \(20\) клеток.
В третьем наборе, одна из оптимальных стратегий — следующая:
- Сдвинуть вправо: указатель сдвигается в ячейку \(1\);
- Сдвинуть вправо: указатель сдвигается в ячейку \(2\);
- Сдвинуть вправо: указатель сдвигается в ячейку \(3\);
- Зажать Shift;
- Сдвинуть вправо: указатель сдвигается в ячейку \(4\);
- Сдвинуть вправо: указатель сдвигается в ячейку \(5\);
- Отпустить Shift: клетки \(3\), \(4\) и \(5\) покрасятся в черный.
Мы покрасили
\(3\) клетки за
\(7\) шагов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 3
1 3
1 4
4 20
10 13 16 19
11 14 17 20
2 3
1 3
1 10
2 4
99 999999999
100 1000000000
|
8
-1
7
1000000004
|