300638: CF121D. Lucky Segments

Memory Limit:256 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Lucky Segments

题目描述

Petya loves lucky numbers. Everybody knows that lucky numbers are positive integers whose decimal representation contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not. Petya has $ n $ number segments $ [l_{1}; r_{1}] $ , $ [l_{2}; r_{2}] $ , ..., $ [l_{n}; r_{n}] $ . During one move Petya can take any segment (let it be segment number $ i $ ) and replace it with segment $ [l_{i}+1; r_{i}+1] $ or $ [l_{i}-1; r_{i}-1] $ . In other words, during one move Petya can shift any segment to the left or to the right by a unit distance. Petya calls a number full if it belongs to each segment. That is, number $ x $ is full if for any $ i $ $ (1<=i<=n) $ the condition $ l_{i}<=x<=r_{i} $ is fulfilled. Petya makes no more than $ k $ moves. After that he counts the quantity of full lucky numbers. Find the maximal quantity that he can get.

输入输出格式

输入格式


The first line contains two integers $ n $ and $ k $ ( $ 1<=n<=10^{5} $ , $ 1<=k<=10^{18}) $ — the number of segments and the maximum number of moves. Next $ n $ lines contain pairs of integers $ l_{i} $ and $ r_{i} $ $ (1<=l_{i}<=r_{i}<=10^{18}) $ . Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use the %I64d specificator.

输出格式


Print on the single line the single number — the answer to the problem.

输入输出样例

输入样例 #1

4 7
1 4
6 9
4 7
3 5

输出样例 #1

1

输入样例 #2

2 7
40 45
47 74

输出样例 #2

2

说明

In the first sample Petya shifts the second segment by two units to the left (it turns into $ [4; 7] $ ), after that number $ 4 $ becomes full. In the second sample Petya shifts the first segment by two units to the right (it turns into $ [42; 47] $ ), and shifts the second segment by three units to the left (it turns into $ [44; 71] $ ), after that numbers $ 44 $ and $ 47 $ become full.

Input

题意翻译

### 题目大意: 如果一个数在十进制下仅含数字 $4$ 和 $7$,那么他就是幸运的。给你 $n$ 个区间,一次操作可以将其中一个区间的左右端点均右移或左移 $1$,你可以操作至多 $k$ 次。求操作完后,所有区间的交中最多包含多少个幸运的数。 数据:$n\leq 10^5,k\leq 10^{18},1\leq l_i\leq r_i\leq 10^{18}$。

加入题单

上一题 下一题 算法标签: