Codeforces Beta Round 91 (Div. 1 Only) |
---|
Закончено |
Петя любит счастливые числа. Всем известно, что счастливыми являются положительные целые числа, в десятичной записи которых содержатся только счастливые цифры 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 будут полными.
Название |
---|