Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

binary search

implementation

two pointers

*2500

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Lucky Segments

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPetya 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.

Input

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.

Output

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

Examples

Input

4 7

1 4

6 9

4 7

3 5

Output

1

Input

2 7

40 45

47 74

Output

2

Note

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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/23/2024 08:34:00 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|