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 [l1; r1], [l2; r2], ..., [ln; rn]. During one move Petya can take any segment (let it be segment number i) and replace it with segment [li + 1; ri + 1] or [li - 1; ri - 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 li ≤ x ≤ ri 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 ≤ 105, 1 ≤ k ≤ 1018) — the number of segments and the maximum number of moves. Next n lines contain pairs of integers li and ri (1 ≤ li ≤ ri ≤ 1018).

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.
import java.io.*;
import java.util.*;


public class Solution {
    static long lucky[] = new long[1<<20];
    static int size = 0;
    
    static void gen(long x, long max) {
        if (x > max) return;
        if (x > 0) lucky[size++] = x;
        gen(x*10 + 4, max);
        gen(x*10 + 7, max);
    }
    
	public static void main (String args[]) throws Exception {		
		
        
        int n = ni();
        long k = nl();
        
        long lo[] = new long[n];
        long hi[] = new long[n];
        
        long minWidth = (long)2e18;
        for (int i=0; i < n; i++) {
            lo[i] = nl();
            hi[i] = nl();
            minWidth = Math.min(minWidth, hi[i] - lo[i]);
        }
        
        Arrays.sort(lo); Arrays.sort(hi);
        long T = DS.lim;
        gen(0, T); Arrays.sort(lucky, 0, size);
        
        //Find sum of (lucky[i]-hi[z]) for hi[z] <= lucky[i] for z
        DS d = new DS();
        long c1[] = new long[size];
        for (int i=0, z=0; i < size; i++) {
            
            long prev = i == 0 ? 0 : lucky[i-1];
            long inc = lucky[i] - prev;
            d.increment( inc );
            
            while (z < n && hi[z] <= lucky[i]) {
                d.add( lucky[i]-hi[z] );
                z++;
            }
            if (d.inf) {
                c1[i] = d.lim;
            } else {
                c1[i] = d.sum;
            }
        }
        
        //Find sum of (lo[z]-lucky[i]) for lo[z] >= lucky[i] for z
        long c2[] = new long[size];
        d = new DS();
        for (int i=size-1, z=n-1; i >= 0; i--) {
            long inc = i == size-1 ? -lucky[i] : lucky[i+1] - lucky[i];
            d.increment( inc );
            
            while (z >= 0 && lo[z] >= lucky[i]) {
                d.add( lo[z] - lucky[i] );
                z--;
            }
            
            if (d.inf) {
                c2[i] = d.lim;
            } else {
                c2[i] = d.sum;
            }
        }
        
        
        for (int i=0; i < size; i++) {
            //System.err.println( lucky[i] + " -> " + c2[i] + " " + c1[i] );
        }
        int ans = 0;
        for (int L=0; L < size; L++) {
            long v = c2[L];
            //Find H such that c1[H] <= k-v and H >= L
            int lH = L, hH = size, H = L;
            while (lH+1 < hH) {
                H = (lH + hH)/2;
                if (c1[H] <= k-v) {
                    lH = H;
                } else {
                    hH = H;
                }
            }
            H = lH;
            
            lH = L; hH = size; int H2 = L;
            while (lH+1 < hH) {
                H2 = (lH + hH)/2;
                if (lucky[H2] - lucky[L] <= minWidth) {
                    lH = H2;
                } else {
                    hH = H2;
                }
            }
            H = Math.min(H2 = lH, H);
            
            if (c1[H] + v <= k) {
                ans = Math.max(ans, H-L+1);
            }
        }
        System.out.println(ans);
	}
    
    
    
    final static int oo = (int)13e7;
	static BufferedInputStream in = new BufferedInputStream( System.in  );
	static int ni() throws IOException
	{
		
		int ret = 0;
		int x = in.read();
		while( x != -1 && (x < '0' || x > '9' )  && x != '-' )x=in.read();
		boolean neg = false;
		if( x=='-' ) { neg=true; x=in.read(); }
		ret = x-'0';
		x=in.read();
		while(  x >= '0' && x <= '9' && x != -1 )
		{ ret = (ret<<3)+(ret<<1) + x-'0'; x=in.read(); }
		return ret * ( neg ? -1 : 1 );
	}
	static long nl() throws IOException
	{
		
		long ret = 0;
		int x = in.read();
		while( x != -1 && (x < '0' || x > '9' )  && x != '-' )x=in.read();
		boolean neg = false;
		if( x=='-' ) { neg=true; x=in.read(); }
		ret = x-'0';
		x=in.read();
		while(  x >= '0' && x <= '9' && x != -1 )
		{ ret = (ret<<3)+(ret<<1) + x-'0'; x=in.read(); }
		return ret * ( neg ? -1 : 1 );
	}
}


class DS {
    final static long lim = 1000000000000000007L;
    
    long sum = 0;
    long count = 0;
    boolean inf = false;
    void add(long v) {
        count++;
        sum += v;
        if (sum > lim) {
            inf = true;
            sum = lim;
        }
    }
    
    void increment(long dx) {
        if (dx == 0) return;
        
        if ( (count * dx) / dx != count ) {
            inf = true;
            sum = lim;
            return;
        }
        long extra = count * dx;
        sum += extra;
        if (sum > lim) {
            inf = true;
            sum = lim;
        }
    }
}
