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;
int LS;
unsigned long long N, K;
unsigned long long L[640000];
unsigned long long ls[100001], rs[100001];
unsigned long long sls[100001], srs[100001];
unsigned long long sll[640000], srl[640000];
void lucky(unsigned long long v) {
  if (v > 1e18) return;
  if (v) L[LS++] = v;
  lucky(v * 10 + 4);
  lucky(v * 10 + 7);
}
unsigned long long moves(unsigned long long n, unsigned long long d) {
  if (d == 0) return 0;
  if (n > K / d) return (K + 1);
  return n * d;
}
int main() {
  lucky(0);
  sort(L, L + LS);
  cin >> N >> K;
  unsigned long long ml = 1e18;
  for (int i = 0; i < N; ++i) {
    cin >> ls[i] >> rs[i];
    ml = min(ml, rs[i] - ls[i]);
  }
  sort(ls, ls + N);
  sort(rs, rs + N);
  reverse(ls, ls + N);
  for (int i = 1; i < N; ++i) {
    sls[i] = min(sls[i - 1] + moves(i, ls[i - 1] - ls[i]), (K + 1));
    srs[i] = min(srs[i - 1] + moves(i, rs[i] - rs[i - 1]), (K + 1));
  }
  for (int i = LS - 1, j = -1; i >= 0; --i) {
    while (j + 1 < N && ls[j + 1] >= L[i]) ++j;
    if (j >= 0) sll[i] = min(sls[j] + moves(j + 1, ls[j] - L[i]), (K + 1));
  }
  for (int i = 0, j = -1; i < LS; ++i) {
    while (j + 1 < N && rs[j + 1] <= L[i]) ++j;
    if (j >= 0) srl[i] = min(srs[j] + moves(j + 1, L[i] - rs[j]), (K + 1));
  }
  int l = 0, r = 0, res = 0;
  while (r < LS) {
    while (L[r] - L[l] > ml) {
      ++l;
    }
    while (l <= r && sll[l] + srl[r] > K) {
      ++l;
    }
    if (l <= r) res = max(res, r - l + 1);
    ++r;
  }
  cout << res << endl;
  return 0;
}
