Problem: Kekoland is a country with n beautiful cities numbered from left to right and connected by n - 1 roads. The i-th road connects cities i and i + 1 and length of this road is wi kilometers. 

When you drive in Kekoland, each time you arrive in city i by car you immediately receive gi liters of gas. There is no other way to get gas in Kekoland.

You were hired by the Kekoland president Keko to organize the most beautiful race Kekoland has ever seen. Let race be between cities l and r (l ≤ r). Race will consist of two stages. On the first stage cars will go from city l to city r. After completing first stage, next day second stage will be held, now racers will go from r to l with their cars. Of course, as it is a race, racers drive directly from start city to finish city. It means that at the first stage they will go only right, and at the second stage they go only left. Beauty of the race between l and r is equal to r - l + 1 since racers will see r - l + 1 beautiful cities of Kekoland. Cars have infinite tank so racers will take all the gas given to them.

At the beginning of each stage racers start the race with empty tank (0 liters of gasoline). They will immediately take their gasoline in start cities (l for the first stage and r for the second stage) right after the race starts. 

It may not be possible to organize a race between l and r if cars will run out of gas before they reach finish.

You have k presents. Each time you give a present to city i its value gi increases by 1. You may distribute presents among cities in any way (also give many presents to one city, each time increasing gi by 1). What is the most beautiful race you can organize?

Each car consumes 1 liter of gas per one kilometer.

Input

The first line of the input contains two integers n and k (2 ≤ n ≤ 100 000, 0 ≤ k ≤ 109) — the number of cities in Kekoland and the number of presents you have, respectively.

Next line contains n - 1 integers. The i-th of them is wi (1 ≤ wi ≤ 109) — the length of the road between city i and i + 1. 

Next line contains n integers. The i-th of them is gi (0 ≤ gi ≤ 109) — the amount of gas you receive every time you enter city i.

Output

Print a single line — the beauty of the most beautiful race you can organize.

Examples

Input

4 4
2 2 2
1 1 1 1


Output

4


Input

8 5
2 2 2 3 7 3 1
1 3 1 5 4 0 2 5


Output

7

Note

In first sample if you give one present to each city then it will be possible to make a race between city 1 and city 4.

In second sample you should add 1 to g5 and 4 to g6, then it will be possible to make a race between cities 2 and 8. 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
struct MinDelta {
  struct node {
    long long minv = 0;
    long long delta = 0;
  };
  int n;
  vector<node> tree;
  MinDelta(int n) : n(n), tree(4 * n) {}
  void propag(int v, int l, int r) {
    long long &delta = tree[v].delta;
    if (delta != 0) {
      tree[v].minv += delta;
      if (l != r)
        tree[2 * v + 1].delta += delta, tree[2 * v + 2].delta += delta;
      delta = 0;
    }
  }
  void update(int a, int b, long long value) {
    update(a, b, value, 0, 0, n - 1);
  }
  void update(int a, int b, long long value, int v, int l, int r) {
    propag(v, l, r);
    if (a > r || b < l) {
    } else if (a <= l && r <= b) {
      tree[v].delta = value;
      propag(v, l, r);
    } else {
      int m = (l + r) / 2;
      update(a, b, value, 2 * v + 1, l, m);
      update(a, b, value, 2 * v + 2, m + 1, r);
      tree[v].minv = min(tree[2 * v + 1].minv, tree[2 * v + 2].minv);
    }
  }
  long long query(int a, int b) { return query(a, b, 0, 0, n - 1); }
  long long query(int a, int b, int v, int l, int r) {
    propag(v, l, r);
    if (a > r || b < l)
      return LLONG_MAX;
    else if (a <= l && r <= b)
      return tree[v].minv;
    else {
      int m = (l + r) / 2;
      return min(query(a, b, 2 * v + 1, l, m),
                 query(a, b, 2 * v + 2, m + 1, r));
    }
  }
};
struct halfpath {
  long long need, give, minstart;
  int dist;
  inline long long v0() { return need - give; }
  inline long long v1() { return need + minstart; }
  int v0id;
};
vector<halfpath> get_halfpaths(vector<int> &dist, vector<int> &gas) {
  const int n = dist.size();
  vector<halfpath> result(n);
  vector<vector<pair<int, long long>>> rnext(n + 1);
  stack<pair<long long, int>> st;
  long long acc = 0LL;
  st.push({acc, n});
  for (int i = n - 1; i >= 0; --i) {
    result[i].dist = n - i;
    acc += (gas[i] - dist[i]);
    while (!st.empty() && st.top().first <= acc) st.pop();
    if (st.empty()) {
      result[i].need = 0;
      result[i].give = acc;
      rnext[n].emplace_back(i, 0LL);
    } else {
      int next = st.top().second;
      result[i].need =
          (st.top().first - acc) + (next == n ? 0LL : result[next].need);
      result[i].give = (next == n ? 0LL : result[next].give);
      rnext[next].emplace_back(i, st.top().first - acc);
    }
    st.push({acc, i});
  }
  MinDelta md(n);
  acc = 0;
  for (int i = n - 1; i >= 0; --i) {
    acc += gas[i + 1] - dist[i];
    md.update(i, i, acc);
  }
  function<void(int)> dfs = [&](int j) {
    if (j != n) result[j].minstart = -min(md.query(j, n - 1), 0LL);
    for (pair<int, long long> ed : rnext[j]) {
      int i;
      long long put;
      tie(i, put) = ed;
      if (put > 0 && j - 2 >= 0) md.update(0, j - 2, put);
      dfs(i);
      if (put > 0 && j - 2 >= 0) md.update(0, j - 2, -put);
    }
  };
  dfs(n);
  return result;
}
struct Bit {
  int n;
  vector<int> tree;
  Bit() {}
  Bit(int n) : n(n), tree(n + 1, -1) {}
  void update(int i, int value) {
    for (++i; i <= n; i += i & -i) tree[i] = max(tree[i], value);
  }
  int query(int i) {
    int result = -1;
    for (++i; i > 0; i -= i & -i) result = max(result, tree[i]);
    return result;
  }
};
struct Max2D {
  struct node {
    Bit bit;
    vector<long long> ys;
  };
  int n;
  vector<node> tree;
  Max2D(int n) : n(n), tree(4 * n) {}
  void preadd(int x, long long y) { preadd(x, y, 0, 0, n - 1); }
  void preadd(int x, long long y, int v, int l, int r) {
    if (l == r)
      tree[v].ys.push_back(y);
    else {
      int m = (l + r) / 2;
      if (x <= m)
        preadd(x, y, 2 * v + 1, l, m);
      else
        preadd(x, y, 2 * v + 2, m + 1, r);
    }
  }
  static vector<long long> merge(vector<long long> &a, vector<long long> &b) {
    vector<long long> result(a.size() + b.size());
    std::merge(a.begin(), a.end(), b.begin(), b.end(), result.begin());
    result.resize(unique(result.begin(), result.end()) - result.begin());
    return move(result);
  }
  void build() { build(0, 0, n - 1, true); }
  void build(int v, int l, int r, bool useful) {
    if (l != r) {
      int m = (l + r) / 2;
      build(2 * v + 1, l, m, true);
      build(2 * v + 2, m + 1, r, false);
      tree[v].ys = merge(tree[2 * v + 1].ys, tree[2 * v + 2].ys);
    }
    if (useful) tree[v].bit = Bit(tree[v].ys.size());
  }
  void update(int x, long long y, int value) {
    update(x, y, value, 0, 0, n - 1, true);
  }
  void update(int x, long long y, int value, int v, int l, int r, bool useful) {
    if (useful) {
      int id = lower_bound(tree[v].ys.begin(), tree[v].ys.end(), y) -
               tree[v].ys.begin();
      tree[v].bit.update(id, value);
    }
    if (l != r) {
      int m = (l + r) / 2;
      if (x <= m)
        update(x, y, value, 2 * v + 1, l, m, true);
      else
        update(x, y, value, 2 * v + 2, m + 1, r, false);
    }
  }
  int query(int maxx, long long maxy) {
    return query(0, maxx, maxy, 0, 0, n - 1);
  }
  int query(int a, int b, long long maxy, int v, int l, int r) {
    if (a > r || b < l)
      return -1;
    else if (a <= l && r <= b) {
      int maxid = upper_bound(tree[v].ys.begin(), tree[v].ys.end(), maxy) -
                  tree[v].ys.begin() - 1;
      return tree[v].bit.query(maxid);
    } else {
      int m = (l + r) / 2;
      return max(query(a, b, maxy, 2 * v + 1, l, m),
                 query(a, b, maxy, 2 * v + 2, m + 1, r));
    }
  }
};
int combine(vector<halfpath> &left, vector<halfpath> &right, long long k) {
  vector<long long> v0s;
  for (halfpath &hp : right) v0s.push_back(hp.v0());
  sort(v0s.begin(), v0s.end());
  v0s.resize(unique(v0s.begin(), v0s.end()) - v0s.begin());
  Max2D m2d(v0s.size());
  for (halfpath &hp : right) {
    hp.v0id = lower_bound(v0s.begin(), v0s.end(), hp.v0()) - v0s.begin();
    m2d.preadd(hp.v0id, hp.v1());
  }
  m2d.build();
  struct needcmp {
    bool operator()(const halfpath &a, const halfpath &b) const {
      return a.need < b.need;
    }
  };
  sort(left.begin(), left.end(), needcmp());
  sort(right.begin(), right.end(), needcmp());
  int result = 0;
  int j = -1;
  for (int i = left.size() - 1; i >= 0; --i) {
    while (j + 1 < (int)right.size() && right[j + 1].need + left[i].need <= k) {
      ++j;
      m2d.update(right[j].v0id, right[j].v1(), right[j].dist);
    }
    long long maxv0 = k - left[i].v1(), maxv1 = k - left[i].v0();
    int maxv0id = upper_bound(v0s.begin(), v0s.end(), maxv0) - v0s.begin() - 1;
    if (maxv0id >= 0) {
      int res = m2d.query(maxv0id, maxv1);
      if (res != -1) {
        assert(res != 0);
        result = max(result, res + left[i].dist + 1);
      }
    }
  }
  return result;
}
int solve(vector<int> &dist, vector<int> &gas, int k) {
  int n = gas.size();
  if (n <= 1)
    return n;
  else if (n == 2) {
    int needl = max(0, dist[0] - gas[0]);
    int needr = max(0, dist[0] - gas[1]);
    if (needl + needr <= k)
      return 2;
    else
      return 1;
  } else {
    int mid = n / 2;
    int resultcross, resultleft, resultright;
    {
      vector<int> dleft(dist.begin(), dist.begin() + mid);
      vector<int> gleft(gas.begin(), gas.begin() + mid + 1);
      vector<int> dright(dist.begin() + mid, dist.end());
      vector<int> gright(gas.begin() + mid, gas.end());
      reverse(dright.begin(), dright.end());
      reverse(gright.begin(), gright.end());
      vector<halfpath> lpaths = get_halfpaths(dleft, gleft);
      vector<halfpath> rpaths = get_halfpaths(dright, gright);
      resultcross = combine(lpaths, rpaths, k);
    }
    {
      vector<int> dleft(dist.begin(), dist.begin() + mid);
      vector<int> gleft(gas.begin(), gas.begin() + mid + 1);
      resultleft = solve(dleft, gleft, k);
    }
    {
      vector<int> dright(dist.begin() + mid, dist.end());
      vector<int> gright(gas.begin() + mid, gas.end());
      resultright = solve(dright, gright, k);
    }
    return max({resultcross, resultleft, resultright});
  }
}
int main() {
  int n, k;
  scanf("%d %d", &n, &k);
  vector<int> dist(n - 1), gas(n);
  for (int &v : dist) scanf("%d", &v);
  for (int &v : gas) scanf("%d", &v);
  printf("%d\n", solve(dist, gas, k));
  return 0;
}