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.
// practice with rainboy
import java.io.*;
import java.util.*;

public class CF121D extends PrintWriter {
	CF121D() { super(System.out, true); }
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF121D o = new CF121D(); o.main(); o.flush();
	}

	static final long INF = 1000000000000000001L;
	long heap(int x) {
		return x == 1 ? 0 : heap(x / 2) * 10 + (x % 2 == 0 ? 4 : 7);
	}
	Random rand = new Random();
	void sort(long[] aa, int n) {
		for (int i = 0; i < n; i++) {
			int j = rand.nextInt(i + 1);
			long tmp = aa[i]; aa[i] = aa[j]; aa[j] = tmp;
		}
		Arrays.sort(aa, 0, n);
	}
	void init(long[] aa, long[] pp, int m, long[] rr, int n) {
		int k_ = 0;
		for (int j = 0, i = 0; j < m; j++) {
			long d = 0;
			int k = 0;
			while (i < n && rr[i] <= aa[j]) {
				d = Math.min(d + aa[j] - rr[i], INF);
				k++;
				i++;
			}
			if (j > 0) {
				d = Math.min(d + pp[j - 1], INF);
				long a = aa[j] - aa[j - 1];
				if (k_ > 0 && a > INF / k_)
					d = INF;
				else
					d = Math.min(d + k_ * a, INF);
			}
			pp[j] = d;
			k_ += k;
		}
	}
	void reverse(long[] aa, int n) {
		for (int i = 0, j = n - 1; i < j; i++, j--) {
			long tmp = aa[i]; aa[i] = aa[j]; aa[j] = tmp;
		}
	}
	void flip(long[] aa, int n) {
		for (int i = 0; i < n; i++)
			aa[i] = INF - aa[i];
	}
	void main() {
		int n = sc.nextInt();
		long k = sc.nextLong();
		long[] ll = new long[n];
		long[] rr = new long[n];
		long a = INF;
		for (int i = 0; i < n; i++) {
			long l = sc.nextLong();
			long r = sc.nextLong();
			a = Math.min(a, r - l);
			ll[i] = l; rr[i] = r;
		}
		sort(ll, n);
		sort(rr, n);
		long[] aa = new long[1 << 19];
		int m = 0;
		for (int x = 2; x < 1 << 19; x++)
			aa[m++] = heap(x);
		long[] pp = new long[m];
		long[] qq = new long[m];
		init(aa, pp, m, rr, n);
		reverse(aa, m); flip(aa, m);
		reverse(ll, n); flip(ll, n);
		init(aa, qq, m, ll, n);
		reverse(aa, m); flip(aa, m);
		reverse(qq, m);
		int ans = 0;
		for (int i = 0, j = 0; j < m; j++) {
			while (i <= j && (aa[j] - aa[i] > a || pp[j] + qq[i] > k))
				i++;
			ans = Math.max(ans, j - i + 1);
		}
		println(ans);
	}
}
