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;
template <class T>
bool umin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool umax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
class BigInteger {
 public:
  long double val;
  BigInteger() { val = 0; }
} L[600009], R[600009], k;
queue<pair<long long, int> > q;
vector<long long> v, lef, righ;
long long mn = 1e18;
int ok(int x) {
  for (int i = 0; i + x <= int(v.size()); i++) {
    long long bir = v[i], iki = v[i + x - 1];
    if (iki - bir + 1 > mn) continue;
    int uc = lower_bound(lef.begin(), lef.end(), bir) - lef.begin();
    int dort = (upper_bound(righ.begin(), righ.end(), iki) - righ.begin()) - 1;
    BigInteger bas, alty;
    bas.val = (lef.size() - uc);
    alty.val = dort + 1;
    bas.val *= bir;
    alty.val *= iki;
    if ((L[uc].val - bas.val) + (alty.val - (dort >= 0 ? R[dort].val : 0)) <=
        k.val)
      return 1;
  }
  return 0;
}
int main() {
  q.push(make_pair(4LL, 1));
  q.push(make_pair(7LL, 1));
  while (!q.empty()) {
    long long node = q.front().first;
    long long cost = q.front().second;
    q.pop();
    v.push_back(node);
    if (cost >= 18) continue;
    q.push(make_pair(node * 10 + 4, cost + 1));
    q.push(make_pair(node * 10 + 7, cost + 1));
  }
  int n;
  scanf("%d", &n);
  cin >> k.val;
  for (int i = 1; i <= n; i++) {
    long long l, r;
    scanf("%lld%lld", &l, &r);
    umin(mn, r - l + 1);
    lef.push_back(l);
    righ.push_back(r);
  }
  sort(lef.begin(), lef.end());
  sort(righ.begin(), righ.end());
  for (int i = int(lef.size() - 1); i >= 0; i--)
    L[i].val = L[i + 1].val + lef[i];
  R[0].val = righ[0];
  for (int i = 1; i < int(righ.size()); i++) R[i].val = R[i - 1].val + righ[i];
  int st = 1, en = (1 << 19) - 2;
  while (st + 1 < en) {
    int mid = (st + en) >> 1;
    if (ok(mid))
      st = mid;
    else
      en = mid;
  }
  for (int i = en; i >= st; i--)
    if (ok(i)) return printf("%d\n", i), 0;
  printf("0\n");
  return 0;
}
