← 返回题目列表

Codeforces · 121/D

D. 幸运段

中文机器翻译题面 查看原题

Petya 喜欢幸运数字。大家都知道,幸运数字是正整数,其十进制表示只包含幸运数字4和7。例如,数字47、744、4是幸运数字,而5、17、467则不是幸运数字。

Petya 有 n 个数字段 [l1; r1],[l2; r2],...,[ln; rn]。在一次移动过程中,Petya 可以选取任何一段(设其为段号 i)并将其替换为段 [li + 1; ri + 1] 或 [li - 1; ri-1]。换句话说,在一次移动过程中,Petya 可以将任何线段向左或向右移动单位距离。如果某个号码属于每个网段,Petya 会将该号码称为已满。也就是说,如果对于任何 i (1 ≤ i ≤ n) 满足条件 li ≤ x ≤ ri,则数字 x 是满的。

Petya 的移动次数不超过 k。之后,他计算完整幸运数字的数量。求他能得到的最大数量。

输入

第一行包含两个整数 n 和 k (1 ≤ n ≤ 105, 1 ≤ k ≤ 1018) — 段数和最大移动数。接下来的 n 行包含整数对 li 和 ri (1 ≤ li ≤ ri ≤ 1018)。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 %I64d 说明符。

输出

在单行上打印单个数字 - 问题的答案。

示例

输入 #1

4 7
1 4
6 9
4 7
3 5

输出 #1

1

输入 #2

2 7
40 45
47 74

输出 #2

2

注意

在第一个示例中,Petya 将第二段向左移动两个单位(变成 [4; 7]),之后数字 4 变满。

在第二个示例中,Petya 将第一个段向右移动两个单位(变为 [42; 47]),并将第二段向左移动三个单位(变为 [44; 71]),之后数字 44 和 47 变满。