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.
#include <bits/stdc++.h>
using namespace std;
long long A[2000000], sz;
long long l[200000], r[200000];
long double sl[200000], sr[200000], costl, costr;
long long K, minlen, Ans, ll, rr, lp, rp;
int N;
void Dfs(int k, long long s) {
  if (s) A[++sz] = s;
  if (k == 19) {
    return;
  }
  Dfs(k + 1, s * 10 + 4);
  Dfs(k + 1, s * 10 + 7);
}
void Init() {
  Dfs(1, 0);
  sort(A + 1, A + sz + 1);
}
long double calcl() {
  while (lp <= N && l[lp] <= A[ll]) lp++;
  return sl[lp] - (long double)(N - lp + 1) * A[ll];
}
long double calcr() {
  while (rp < N && r[rp + 1] < A[rr]) rp++;
  return (long double)rp * A[rr] - sr[rp];
}
int main() {
  Init();
  scanf("%d%I64d", &N, &K);
  minlen = (long long)1e19;
  for (int i = 1; i <= N; i++) {
    scanf("%I64d%I64d", l + i, r + i);
    minlen = min(minlen, r[i] - l[i]);
  }
  sort(l + 1, l + N + 1);
  sort(r + 1, r + N + 1);
  for (int i = N; i; i--) sl[i] = sl[i + 1] + l[i];
  for (int i = 1; i <= N; i++) sr[i] = sr[i - 1] + r[i];
  ll = rr = 1;
  lp = rp = 0;
  costl = calcl();
  costr = calcr();
  while (rr <= sz) {
    while (A[rr] - A[ll] > minlen) ll++;
    costl = calcl();
    while (costl + costr - 0.5 > K && ll < rr) ll++, costl = calcl();
    if (costl + costr - 0.5 <= K) Ans = max(Ans, rr - ll + 1);
    rr++;
    costr = calcr();
  }
  printf("%d\n", Ans);
}
