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;
struct E {
  int tp;
  long long val;
  int num;
};
inline bool operator<(const E &a, const E &b) {
  if (a.val != b.val) return a.val < b.val;
  if (a.tp != b.tp) return a.tp < b.tp;
  return a.num < b.num;
}
E ev[111111 * 2 + (1 << 19)];
long long lucky[1 << 19];
long long lco[1 << 19];
long long rco[1 << 19];
int n, m, l;
long long k;
pair<long long, long long> lt, rt;
int lc, rc = 0;
inline void add(pair<long long, long long> &p, long long first) {
  p.first += first;
  if (p.first >= 1000000000000000001LL) {
    p.second++;
    p.first -= 1000000000000000001LL;
  }
  if (p.first < 0) {
    p.second--;
    p.first += 1000000000000000001LL;
  }
}
inline pair<long long, long long> mulmod(long long a, long long b) {
  pair<long long, long long> ans = make_pair(0, 0);
  while (a) {
    if (a % 2 == 1) {
      add(ans, b);
      a--;
    }
    a /= 2;
    b *= 2;
    if (b >= 1000000000000000001LL) {
      ans.second += a;
      b -= 1000000000000000001LL;
    }
  }
  return ans;
}
int main() {
  for (int len = 1; len <= 18; ++len)
    for (int mask = 0; mask < (1 << len); ++mask) {
      long long val = 0;
      for (int(i) = 0; (i) < (len); ++(i))
        if (mask & (1 << i))
          val = val * 10 + 4;
        else
          val = val * 10 + 7;
      ev[m].tp = 0;
      ev[m].val = val;
      ev[m].num = m;
      lucky[l++] = val;
      m++;
    }
  scanf("%d%I64d", &n, &k);
  rt.first = rt.second = 0;
  lt.first = lt.second = 0;
  long long mlen = 1000000000000000001LL;
  for (int(i) = 0; (i) < (n); ++(i)) {
    long long lft, rgt;
    scanf("%I64d%I64d", &lft, &rgt);
    ev[m].tp = -1;
    ev[m].val = lft;
    ev[m].num = m;
    m++;
    ev[m].tp = 1;
    ev[m].val = rgt;
    ev[m].num = m;
    m++;
    rc++;
    add(rt, lft);
    mlen = min(mlen, rgt - lft + 1);
  }
  sort(ev, ev + m);
  sort(lucky, lucky + l);
  for (int(i) = 0; (i) < (m); ++(i)) {
    if (ev[i].tp == -1) {
      rc--;
      add(rt, -ev[i].val);
    } else if (ev[i].tp == 0) {
      pair<long long, long long> cl = mulmod(lc, ev[i].val);
      pair<long long, long long> cr = mulmod(rc, ev[i].val);
      pair<long long, long long> now1 =
          make_pair(cl.first - lt.first, cl.second - lt.second);
      if (now1.first < 0) {
        now1.first += 1000000000000000001LL;
        now1.second--;
      };
      pair<long long, long long> now2 =
          make_pair(rt.first - cr.first, rt.second - cr.second);
      if (now2.first < 0) {
        now2.first += 1000000000000000001LL;
        now2.second--;
      };
      pair<long long, long long> now =
          make_pair(now1.first + now2.first, now1.second + now2.second);
      if (now.first >= 1000000000000000001LL) {
        now.first -= 1000000000000000001LL;
        now.second++;
      }
      int pos = lower_bound(lucky, lucky + l, ev[i].val) - lucky;
      if (now.second == 0 && now.first <= k) {
        lco[pos] = now1.first;
        rco[pos] = now2.first;
      } else {
        lco[pos] = k + 1;
        rco[pos] = k + 1;
      }
    } else {
      lc++;
      add(lt, ev[i].val);
    }
  }
  int pos = 0;
  int ans = 0;
  for (int(i) = 0; (i) < (l); ++(i)) {
    if (pos < i) pos = i;
    while (pos < l && lucky[pos] - lucky[i] + 1 <= mlen &&
           rco[i] + lco[pos] <= k)
      pos++;
    ans = max(ans, pos - i);
  }
  cout << ans << endl;
}
