D. Счастливые отрезки
ограничение по времени на тест
4 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Петя любит счастливые числа. Всем известно, что счастливыми являются положительные целые числа, в десятичной записи которых содержатся только счастливые цифры 4 и 7. Например, числа 47, 744, 4 являются счастливыми, а 5, 17, 467 — не являются.

У Пети есть n числовых отрезков [l1; r1], [l2; r2], ..., [ln; rn]. За один ход Петя может взять любой отрезок (пусть его номер i) и заменить его отрезком [li + 1; ri + 1] или [li - 1; ri - 1]. Другими словами, за один ход можно сдвинуть любой отрезок влево или вправо на единичное расстояние. Петя называет число полным, если оно входит в каждый из отрезков. То есть число x полное, если для каждого i (1 ≤ i ≤ n) выполняется li ≤ x ≤ ri.

Петя делает не более k ходов, а потом считает количество получившихся полных счастливых чисел. Какое наибольшее количество может у него получиться?

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

В первой строке задано два целых числа n и k (1 ≤ n ≤ 105, 1 ≤ k ≤ 1018) — количество отрезков и максимальное количество ходов. В следующих n строках задано пары целых чисел li и ri (1 ≤ li ≤ ri ≤ 1018).

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Следует использовать спецификатор %I64d.

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

В единственной строке выведите одно число — ответ на задачу.

Примеры
Входные данные
4 7
1 4
6 9
4 7
3 5
Выходные данные
1
Входные данные
2 7
40 45
47 74
Выходные данные
2
Примечание

В первом примере Петя сдвигает второй отрезок на две единицы влево (он превращается в [4; 7]), после этого число 4 становится полным.

Во втором примере Петя сдвигает первый отрезок на две единицы вправо (он превращается в [42; 47]), а второй отрезок на три единицы влево (он превращается в [44; 71]), после этого числа 44 и 47 будут полными.