#include <bits/stdc++.h>
using namespace std;
static const int MOD = 1000000007;
static const double eps = 1e-8;
template <class T>
inline T MIN(const T x, const T y) {
  return (x < y) ? x : y;
}
template <class T>
inline T MAX(const T x, const T y) {
  return (x > y) ? x : y;
}
template <class T>
inline void UPDMIN(T &x, const T y) {
  if (x > y) x = y;
}
template <class T>
inline void UPDMAX(T &x, const T y) {
  if (x < y) x = y;
}
template <class T>
inline int SIZE(const T &x) {
  return (int)x.size();
}
template <class T>
inline int LENGTH(const T &x) {
  return (int)x.length();
}
template <class T1, class T2>
inline pair<T1, T2> MP(const T1 &x, const T2 &y) {
  return make_pair(x, y);
}
inline int BINT(const int x) { return 1 << x; }
inline long long BLLD(const int x) { return 1LL << x; }
inline int BINT_TEST(const int s, const int x) { return (s & BINT(x)) != 0; }
inline int BLLD_TEST(const long long s, const int x) {
  return (s & BLLD(x)) != 0LL;
}
template <class T>
inline T LOWBIT(const T x) {
  return (x ^ (x - 1)) & x;
}
template <class T>
inline int BITCOUNT(const T x) {
  return (!x) ? x : (1 + BITCOUNT(x & (x - 1)));
}
const double PI = acos(-1.0);
const double EPS = 1e-5;
template <class T>
inline T SQR(const T x) {
  return x * x;
}
template <class T1, class T2>
inline T1 POW(const T1 x, const T2 y) {
  if (!y)
    return 1;
  else if ((y & 1) == 0) {
    return SQR(POW(x, y >> 1));
  } else
    return POW(x, y ^ 1) * x;
}
template <class T>
inline T GCD(const T x, const T y) {
  if (x < 0) return GCD(-x, y);
  if (y < 0) return GCD(x, -y);
  return (!y) ? x : GCD(y, x % y);
}
template <class T>
inline T LCM(const T x, const T y) {
  if (x < 0) return LCM(-x, y);
  if (y < 0) return LCM(x, -y);
  return x * (y / GCD(x, y));
}
template <class T>
inline T EEA(const T a, const T b, T &x, T &y) {
  if (a < 0) {
    T d = EEA(-a, b, x, y);
    x = -x;
    return d;
  }
  if (b < 0) {
    T d = EEA(a, -b, x, y);
    y = -y;
    return d;
  }
  if (!b) {
    x = 1;
    y = 0;
    return a;
  } else {
    T d = EEA(b, a % b, x, y);
    T t = x;
    x = y;
    y = t - (a / b) * y;
    return d;
  }
}
template <class T>
inline vector<pair<T, int>> FACTORIZE(T x) {
  vector<pair<T, int>> ret;
  if (x < 0) x = -x;
  for (T i = 2; x > 1;) {
    if (x % i == 0) {
      int count = 0;
      for (; x % i == 0; x /= i) count++;
      ret.push_back(MP(i, count));
    }
    i++;
    if (i > x / i) i = x;
  }
  return ret;
}
template <class T>
inline int ISPRIME(const T x) {
  if (x <= 1) return 0;
  for (T i = 2; SQR(i) <= x; i++)
    if (x % i == 0) return 0;
  return 1;
}
template <class T>
inline T EULARFUNCTION(T x) {
  vector<pair<T, int>> f = FACTORIZE(x);
  for (typename vector<pair<T, int>>::iterator it = f.begin(); it != f.end();
       it++) {
    x = x / it->first * (it->first - 1);
  }
  return x;
}
template <class T>
inline T INVERSEE(const T a, const T b = MOD) {
  T x, y;
  EEA(a, b, x, y);
  return x ? x : 1;
}
int *PRIMELIST(const int til, int *length = NULL) {
  int *foo = (int *)malloc(sizeof(int) * (til + 1));
  int len = 0;
  memset(foo, 0, sizeof(int) * (til + 1));
  for (int i = 2; i <= til; i++) {
    if (!foo[i]) foo[len++] = i;
    for (int j = 0; j < len && foo[j] <= til / i; j++) {
      foo[foo[j] * i] = 1;
      if (i % foo[j] == 0) break;
    }
  }
  if (length != NULL) {
    *length = len;
  }
  foo[len++] = 0;
  foo = (int *)realloc(foo, sizeof(int) * len);
  return foo;
}
template <class T>
inline T MOD_STD(const T x, const T m = MOD) {
  return (x % m + m) % m;
}
template <class T>
inline void MOD_STD(T *x, const T m = MOD) {
  *x = (*x % m + m) % m;
}
template <class T>
inline T MOD_ADD(const T x, const T y, const T m = MOD) {
  return (x + y) % m;
}
template <class T>
inline void MOD_ADD(T *x, const T y, const T m = MOD) {
  *x = (*x + y) % m;
}
template <class T>
inline T MOD_MUL(const T x, const T y, const T m = MOD) {
  return (T)((1LL * x * y) % m);
}
template <class T>
inline void MOD_MUL(T *x, const T y, const T m = MOD) {
  *x = (T)((1LL * (*x) * y) % m);
}
template <class T1, class T2>
inline T1 MOD_POW(const T1 x, const T2 y, const T1 m = MOD) {
  if (y == 0)
    return 1 % m;
  else if ((y & 1) == 0) {
    T1 z = MOD_POW(x, y >> 1, m);
    return MOD_MUL(z, z, m);
  } else
    return MOD_MUL(MOD_POW(x, y ^ 1, m), x, m);
}
inline long long MODL_MUL(long long x, long long y, const long long m = MOD) {
  MOD_STD(&x, m);
  MOD_STD(&y, m);
  if (x < y) swap(x, y);
  long long z = 0LL;
  while (y > 0) {
    if (y & 1) {
      MOD_ADD(&z, x, m);
    }
    MOD_ADD(&x, x, m);
    y >>= 1;
  }
  return z;
}
inline long long MODL_POW(const long long x, const long long y,
                          const long long m = MOD) {
  if (y == 0LL)
    return 1LL % m;
  else if ((y & 1) == 0LL) {
    long long z = MODL_POW(x, y >> 1, m);
    return MODL_MUL(z, z, m);
  } else
    return MODL_MUL(MODL_POW(x, y ^ 1, m), x, m);
}
template <class T>
class MATX {
 private:
  unsigned long hig, wid;
  T *data;
  void __init() {
    this->data = (T *)malloc(sizeof(T) * this->hig * this->wid);
    memset(this->data, 0, sizeof(T) * this->hig * this->wid);
  }

 public:
  MATX() {
    this->hig = this->wid = 1;
    __init();
  }
  MATX(const unsigned long _len) {
    this->hig = this->wid = _len;
    __init();
  }
  MATX(const unsigned long _hig, const unsigned long _wid) {
    this->hig = _hig;
    this->wid = _wid;
    __init();
  }
  MATX(const MATX &rhs) {
    this->hig = rhs.hig;
    this->wid = rhs.wid;
    this->data = (T *)malloc(sizeof(T) * this->hig * this->wid);
    for (unsigned long x = 0; x < this->hig; x++)
      for (unsigned long y = 0; y < this->wid; y++)
        this->data[x * this->wid + y] = rhs.at(x, y);
  }
  ~MATX() { free(this->data); }
  T &operator()(const unsigned long x, const unsigned long y) {
    if (x >= this->hig || y >= this->wid) return (*(T *)NULL);
    return this->data[x * this->wid + y];
  }
  T *operator[](const unsigned long x) {
    if (x >= this->hig) return (T *)NULL;
    return this->data + (x * this->wid);
  }
  MATX &operator=(const MATX &rhs) {
    if (this->hig != rhs.hig || this->wid != rhs.wid) {
      free(this->data);
      this->hig = rhs.hig;
      this->wid = rhs.wid;
      this->data = (T *)malloc(sizeof(T) * this->hig * this->wid);
    }
    for (unsigned long x = 0; x < this->hig; x++)
      for (unsigned long y = 0; y < this->wid; y++)
        this->data[x * this->wid + y] = rhs.at(x, y);
    return *this;
  }
  const MATX operator+(const MATX &opn) const {
    MATX ret(*this);
    for (unsigned long x = 0; x < ret.hig; x++)
      for (unsigned long y = 0; y < ret.wid; y++)
        ret.data[x * ret.wid + y] += opn.at(x, y);
    return ret;
  }
  const MATX operator-(const MATX &opn) const {
    MATX ret(*this);
    for (unsigned long x = 0; x < ret.hig; x++)
      for (unsigned long y = 0; y < ret.wid; y++)
        ret.data[x * ret.wid + y] -= opn.at(x, y);
    return ret;
  }
  const MATX operator*(const MATX &opn) const {
    MATX ret(this->hig, opn.wid);
    const unsigned long len = MIN(this->wid, opn.hig);
    for (unsigned long x = 0; x < ret.hig; x++)
      for (unsigned long y = 0; y < ret.wid; y++)
        for (unsigned long z = 0; z < len; z++)
          ret.data[x * ret.wid + y] += this->at(x, z) * opn.at(z, y);
    return ret;
  }
  const MATX mul(const MATX &opn) const { return *this * opn; }
  template <class T2>
  const MATX mul(const MATX &opn, const T2 m) const {
    MATX ret(this->hig, opn.wid);
    const unsigned long len = MIN(this->wid, opn.wid);
    for (unsigned long x = 0; x < ret.hig; x++)
      for (unsigned long y = 0; y < ret.wid; y++)
        for (unsigned long z = 0; z < len; z++)
          MOD_ADD(&ret.data[x * ret.wid + y],
                  MOD_MUL(this->at(x, z), opn.at(z, y), m), m);
    return ret;
  }
  MATX &operator+=(const MATX &rhs) {
    *this = *this + rhs;
    return *this;
  }
  MATX &operator-=(const MATX &rhs) {
    *this = *this - rhs;
    return *this;
  }
  MATX &operator*=(const MATX &rhs) {
    *this = *this * rhs;
    return *this;
  }
  const MATX pow(const unsigned long p) const {
    MATX buff(*this), ret(this->hig, this->wid);
    ret.set_one();
    if (p > 0)
      for (unsigned long i = 1;; i <<= 1) {
        if (p & i) ret *= buff;
        buff *= buff;
        if (i > (p >> 1)) break;
      }
    return ret;
  }
  template <class T2>
  const MATX pow(const unsigned long p, const T2 m) const {
    MATX buff(*this), ret(this->hig, this->wid);
    ret.set_one();
    if (p > 0)
      for (unsigned long i = 1;; i <<= 1) {
        if (p & i) ret = ret.mul(buff, m);
        buff = buff.mul(buff, m);
        if (i > (p >> 1)) break;
      }
    return ret;
  }
  const T at(const unsigned long x, const unsigned long y) const {
    if (x >= this->hig || y >= this->wid) return 0;
    return this->data[x * wid + y];
  }
  void show() const {
    for (unsigned long x = 0; x < this->hig; x++) {
      for (unsigned long y = 0; y < this->wid; y++)
        cout << this->at(x, y) << " ";
      cout << endl;
    }
  }
  void set_one() {
    for (unsigned long x = 0; x < this->hig; x++)
      for (unsigned long y = 0; y < this->wid; y++)
        this->data[x * this->wid + y] = (x == y) ? 1 : 0;
  }
};
template <class T>
class complex_t {
 public:
  T r, i;
  complex_t(T x = 0.0, T y = 0.0) {
    this->r = x;
    this->i = y;
  }
  complex_t operator+(const complex_t &opn) const {
    return complex_t(this->r + opn.r, this->i + opn.i);
  }
  complex_t operator-(const complex_t &opn) const {
    return complex_t(this->r - opn.r, this->i - opn.i);
  }
  complex_t operator*(const complex_t &opn) const {
    return complex_t(this->r * opn.r - this->i * opn.i,
                     this->r * opn.i + this->i * opn.r);
  }
};
template <class T>
void fast_fourier_trans(complex_t<T> f[], const int len, const int is_dft) {
  for (int i = 1, j = len >> 1; i < len - 1; i++) {
    if (i < j) swap(f[i], f[j]);
    int k = len >> 1;
    while (j >= k) {
      j -= k;
      k >>= 1;
    }
    if (j < k) j += k;
  }
  for (int h = 2; h <= len; h <<= 1) {
    complex_t<T> wn(cos(is_dft ? (-2 * PI / h) : (2 * PI / h)),
                    sin(is_dft ? (-2 * PI / h) : (2 * PI / h)));
    for (int i = 0; i < len; i += h) {
      complex_t<T> wm(1.0, 0.0);
      for (int j = i; j < i + (h >> 1); j++) {
        complex_t<T> u = f[j];
        complex_t<T> t = wm * f[j + (h >> 1)];
        f[j] = u + t;
        f[j + (h >> 1)] = u - t;
        wm = wm * wn;
      }
    }
  }
  if (!is_dft) {
    for (int i = 0; i < len; i++) f[i].r /= len * 1.0;
  }
}
class MILLERRABIN {
 private:
  static const int prime_table[12];
  int witness(long long a, long long d, long long s, long long n) {
    long long r = MODL_POW(a, d, n);
    if (r == 1 || r == n - 1) return 0;
    for (int i = 0; i < s - 1; i++) {
      r = MODL_MUL(r, r, n);
      if (r == 1) return 1;
      if (r == n - 1) return 0;
    }
    return 1;
  }

 public:
  int test(const long long n) {
    if (n <= 2LL) return 0;
    long long p = n - 1LL, s = 0LL;
    while (!(p & 1)) {
      p >>= 1;
      s++;
    }
    for (int i = 0; i < 12 && this->prime_table[i] < n; i++) {
      if (witness(this->prime_table[i], p, s, n)) return 0;
    }
    return 1;
  }
};
const int MILLERRABIN::prime_table[12] = {2,  3,  5,  7,  11, 13,
                                          17, 19, 23, 29, 31, 37};
template <class T>
inline int fsign(const T x) {
  if (x > -eps && x < eps) return 0;
  return (x < 0.0) ? -1 : 1;
}
template <class T>
class point_t {
 public:
  T x, y;
  point_t() {
    this->x = 0.0;
    this->y = 0.0;
  }
  point_t(const T _x, const T _y) {
    this->x = _x;
    this->y = _y;
  }
  point_t operator-(const point_t &rhs) const {
    return point_t(this->x - rhs.x, this->y - rhs.y);
  }
  T operator^(const point_t &rhs) const {
    return this->x * rhs.y - this->y * rhs.x;
  }
  T operator*(const point_t &rhs) const {
    return this->x * rhs.x + this->y * rhs.y;
  }
  bool operator<(const point_t &rhs) const {
    if (fsign(this->y - rhs.y) != 0) return fsign(this->y - rhs.y) < 0;
    return fsign(this->x - rhs.x) < 0;
  }
  T cross(const point_t &p, const point_t &q) const {
    return (p - *this) ^ (q - *this);
  }
  void rotate(const double radian) {
    T x0 = x, y0 = y;
    T sinr = sin(radian);
    T cosr = cos(radian);
    x = x0 * cosr - y0 * sinr;
    y = x0 * sinr + y0 * cosr;
  }
  void rotate(const point_t &p, const double radian) {
    T x0 = x - p.x, y0 = y - p.y;
    T sinr = sin(radian);
    T cosr = cos(radian);
    x = x0 * cosr - y0 * sinr + p.x;
    y = x0 * sinr + y0 * cosr + p.y;
  }
  T dist2(const point_t &lhs, const point_t &rhs) const {
    return (lhs - rhs) * (lhs - rhs);
  }
  T dist2(const point_t &rhs) const { return (*this - rhs) * (*this - rhs); }
  T dist(const point_t &lhs, const point_t &rhs) const {
    return sqrt((lhs - rhs) * (lhs - rhs));
  }
  T dist(const point_t &rhs) const {
    return sqrt((*this - rhs) * (*this - rhs));
  }
};
template <class T>
class segment_t {
 public:
  point_t<T> p, q;
  segment_t() {
    this->p.x = this->p.y = 0.0;
    this->q.x = this->q.y = 0.0;
  }
  template <class T2>
  segment_t(const point_t<T2> &_p, const point_t<T2> &_q) {
    this->p.x = _p.x;
    this->p.y = _p.y;
    this->q.x = _q.x;
    this->q.y = _q.y;
  }
  segment_t(const T px, const T py, const T qx, const T qy) {
    this->p.x = px;
    this->p.y = py;
    this->q.x = qx;
    this->q.y = qy;
  }
  T length() const { return this->p.dist(this->q); }
  T length2() const { return this->p.dist2(this->q); }
  int contain(const point_t<T> &pnt, const int ignore_endpoint = 0) const {
    if (ignore_endpoint) {
      return fsign((this->p - pnt) ^ (this->q - pnt)) == 0 &&
             fsign((pnt.x - this->p.x) * (pnt.x - this->q.x)) < 0 &&
             fsign((pnt.y - this->p.y) * (pnt.y - this->q.y)) < 0;
    } else {
      return fsign((this->p - pnt) ^ (this->q - pnt)) == 0 &&
             fsign((pnt.x - this->p.x) * (pnt.x - this->q.x)) <= 0 &&
             fsign((pnt.y - this->p.y) * (pnt.y - this->q.y)) <= 0;
    }
  }
  int intersection(const segment_t &sa, const segment_t &sb,
                   const int ignore_endpoint = 0) const {
    if (!ignore_endpoint) {
      if (sa.contain(sb.p) || sa.contain(sb.q) || sb.contain(sa.p) ||
          sb.contain(sa.q))
        return 1;
    }
    return fsign(sa.p.cross(sa.q, sb.p)) * fsign(sa.p.cross(sa.q, sb.q)) < 0 &&
           fsign(sb.p.cross(sb.q, sa.p)) * fsign(sb.p.cross(sb.q, sa.q)) < 0;
  }
  int intersection(const segment_t &rhs, const int ignore_endpoint = 0) const {
    return this->intersection(*this, rhs, ignore_endpoint);
  }
};
template <class T>
static int compare_pas(const void *x, const void *y, void *z) {
  const point_t<T> *p1 = (point_t<T> *)x;
  const point_t<T> *p2 = (point_t<T> *)y;
  const point_t<T> *p0 = (point_t<T> *)z;
  int sgn = fsign(((*p1) - (*p0)) ^ ((*p2) - (*p0)));
  if (sgn != 0) return -sgn;
  return fsign(p0->dist2(*p1) - p0->dist2(*p2));
}
template <class T>
void polar_angle_sort(point_t<T> *pnts, const int n) {
  int p = 0;
  for (int i = 1; i < n; i++) {
    if (pnts[p] < pnts[i]) p = i;
  }
  swap(pnts[0], pnts[p]);
  qsort_r(pnts + 1, n - 1, sizeof(point_t<T>), compare_pas<T>, pnts);
}
template <class T>
void graham(point_t<T> *pnts, const int n, int *idx, int &m) {
  polar_angle_sort(pnts, n);
  m = 0;
  if (n < 3) return;
  idx[m++] = 0;
  idx[m++] = 1;
  for (int i = 2; i < n; i++) {
    while (m > 1 &&
           fsign(pnts[idx[m - 2]].cross(pnts[idx[m - 1]], pnts[i])) <= 0)
      m--;
    idx[m++] = i;
  }
}
struct stnode_t {
  int lef, rig;
  long long foo, cov;
  stnode_t *chd[2];
} pool[210000], *root, *tail;
long long s[210000];
void riseup(stnode_t *node) {
  node->foo = MIN(node->chd[0]->foo + node->chd[0]->cov,
                  node->chd[1]->foo + node->chd[1]->cov);
}
void build(stnode_t **hook, const int lef, const int rig) {
  stnode_t *node = *hook = tail++;
  node->lef = lef;
  node->rig = rig;
  node->cov = 0LL;
  if (lef == rig) {
    node->foo = s[lef + 1];
    node->chd[0] = node->chd[1] = NULL;
  } else {
    const int mid = (lef + rig) >> 1;
    build(&node->chd[0], lef, mid);
    build(&node->chd[1], mid + 1, rig);
    riseup(node);
  }
}
long long query(stnode_t *node, const int lef, const int rig) {
  if (lef <= node->lef && node->rig <= rig) {
    return node->foo + node->cov;
  } else {
    long long rep = 0x3f3f3f3f3f3f3f3fLL;
    if (lef <= node->chd[0]->rig) {
      UPDMIN(rep, query(node->chd[0], lef, rig));
    }
    if (rig >= node->chd[1]->lef) {
      UPDMIN(rep, query(node->chd[1], lef, rig));
    }
    return rep + node->cov;
  }
}
void check(stnode_t *node, const int lef, const int rig, const long long det) {
  if (lef <= node->lef && node->rig <= rig) {
    node->cov += det;
  } else {
    if (lef <= node->chd[0]->rig) {
      check(node->chd[0], lef, rig, det);
    }
    if (rig >= node->chd[1]->lef) {
      check(node->chd[1], lef, rig, det);
    }
    riseup(node);
  }
}
int n, m;
pair<int, int> a[210000], b[210000], p[210000];
int d[210000];
int ans;
int main() {
  while (scanf("%d%d", &n, &m) != EOF) {
    s[0] = 0LL;
    for (int i = 0; i < n; i++) {
      scanf("%d", &a[i].first);
      a[i].second = i;
      s[i + 1] = s[i] + a[i].first * 1LL;
    }
    sort(a, a + n);
    for (int i = 0; i < m; i++) {
      scanf("%d", &b[i].first);
      b[i].second = i;
    }
    sort(b, b + m);
    for (int i = 0; i < m; i++) {
      scanf("%d", &p[i].first);
      p[i].second = i;
    }
    sort(p, p + m);
    set<int, greater<int>> cnd;
    for (int i = 0; i < n; i++) cnd.insert(i);
    for (int i = 0, j = 0; i < m; i++) {
      for (; j < n && a[j].first < b[i].first; j++) cnd.erase(a[j].second);
      if (!cnd.empty()) {
        d[b[i].second] = *cnd.begin();
      } else {
        d[b[i].second] = -1;
      }
    }
    ans = 0;
    tail = pool;
    build(&root, 0, n - 1);
    for (int i = 0; i < m; i++) {
      if (!~d[p[i].second]) continue;
      if (query(root, d[p[i].second], n - 1) >= p[i].first) {
        check(root, d[p[i].second], n - 1, -p[i].first * 1LL);
        ans++;
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

### Prompt

Create a solution in cpp for the following problem:

The mayor of the Berland city S sees the beauty differently than other city-dwellers. In particular, he does not understand at all, how antique houses can be nice-looking. So the mayor wants to demolish all ancient buildings in the city.

The city S is going to host the football championship very soon. In order to make the city beautiful, every month the Berland government provides mayor a money tranche. The money has to be spent on ancient buildings renovation.

There are n months before the championship and the i-th month tranche equals to ai burles. The city S has m antique buildings and the renovation cost of the j-th building is bj burles.

The mayor has his own plans for spending the money. As he doesn't like antique buildings he wants to demolish as much of them as possible. For the j-th building he calculated its demolishing cost pj.

The mayor decided to act according to the following plan.

Each month he chooses several (possibly zero) of m buildings to demolish in such a way that renovation cost of each of them separately is not greater than the money tranche ai of this month (bj ≤ ai) — it will allow to deceive city-dwellers that exactly this building will be renovated.

Then the mayor has to demolish all selected buildings during the current month as otherwise the dwellers will realize the deception and the plan will fail. Definitely the total demolishing cost can not exceed amount of money the mayor currently has. The mayor is not obliged to spend all the money on demolishing. If some money is left, the mayor puts it to the bank account and can use it in any subsequent month. Moreover, at any month he may choose not to demolish any buildings at all (in this case all the tranche will remain untouched and will be saved in the bank).

Your task is to calculate the maximal number of buildings the mayor can demolish.

Input

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 100 000) — the number of months before the championship and the number of ancient buildings in the city S.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109), where ai is the tranche of the i-th month.

The third line contains m integers b1, b2, ..., bm (1 ≤ bj ≤ 109), where bj is renovation cost of the j-th building.

The fourth line contains m integers p1, p2, ..., pm (1 ≤ pj ≤ 109), where pj is the demolishing cost of the j-th building.

Output

Output single integer — the maximal number of buildings the mayor can demolish.

Examples

Input

2 3
2 4
6 2 3
1 3 2


Output

2


Input

3 5
5 3 1
5 2 9 1 10
4 2 1 3 10


Output

3


Input

5 6
6 3 2 4 3
3 6 4 5 4 2
1 4 3 2 5 3


Output

6

Note

In the third example the mayor acts as follows.

In the first month he obtains 6 burles tranche and demolishes buildings #2 (renovation cost 6, demolishing cost 4) and #4 (renovation cost 5, demolishing cost 2). He spends all the money on it.

After getting the second month tranche of 3 burles, the mayor selects only building #1 (renovation cost 3, demolishing cost 1) for demolishing. As a result, he saves 2 burles for the next months.

In the third month he gets 2 burle tranche, but decides not to demolish any buildings at all. As a result, he has 2 + 2 = 4 burles in the bank.

This reserve will be spent on the fourth month together with the 4-th tranche for demolishing of houses #3 and #5 (renovation cost is 4 for each, demolishing costs are 3 and 5 correspondingly). After this month his budget is empty.

Finally, after getting the last tranche of 3 burles, the mayor demolishes building #6 (renovation cost 2, demolishing cost 3).

As it can be seen, he demolished all 6 buildings.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
static const int MOD = 1000000007;
static const double eps = 1e-8;
template <class T>
inline T MIN(const T x, const T y) {
  return (x < y) ? x : y;
}
template <class T>
inline T MAX(const T x, const T y) {
  return (x > y) ? x : y;
}
template <class T>
inline void UPDMIN(T &x, const T y) {
  if (x > y) x = y;
}
template <class T>
inline void UPDMAX(T &x, const T y) {
  if (x < y) x = y;
}
template <class T>
inline int SIZE(const T &x) {
  return (int)x.size();
}
template <class T>
inline int LENGTH(const T &x) {
  return (int)x.length();
}
template <class T1, class T2>
inline pair<T1, T2> MP(const T1 &x, const T2 &y) {
  return make_pair(x, y);
}
inline int BINT(const int x) { return 1 << x; }
inline long long BLLD(const int x) { return 1LL << x; }
inline int BINT_TEST(const int s, const int x) { return (s & BINT(x)) != 0; }
inline int BLLD_TEST(const long long s, const int x) {
  return (s & BLLD(x)) != 0LL;
}
template <class T>
inline T LOWBIT(const T x) {
  return (x ^ (x - 1)) & x;
}
template <class T>
inline int BITCOUNT(const T x) {
  return (!x) ? x : (1 + BITCOUNT(x & (x - 1)));
}
const double PI = acos(-1.0);
const double EPS = 1e-5;
template <class T>
inline T SQR(const T x) {
  return x * x;
}
template <class T1, class T2>
inline T1 POW(const T1 x, const T2 y) {
  if (!y)
    return 1;
  else if ((y & 1) == 0) {
    return SQR(POW(x, y >> 1));
  } else
    return POW(x, y ^ 1) * x;
}
template <class T>
inline T GCD(const T x, const T y) {
  if (x < 0) return GCD(-x, y);
  if (y < 0) return GCD(x, -y);
  return (!y) ? x : GCD(y, x % y);
}
template <class T>
inline T LCM(const T x, const T y) {
  if (x < 0) return LCM(-x, y);
  if (y < 0) return LCM(x, -y);
  return x * (y / GCD(x, y));
}
template <class T>
inline T EEA(const T a, const T b, T &x, T &y) {
  if (a < 0) {
    T d = EEA(-a, b, x, y);
    x = -x;
    return d;
  }
  if (b < 0) {
    T d = EEA(a, -b, x, y);
    y = -y;
    return d;
  }
  if (!b) {
    x = 1;
    y = 0;
    return a;
  } else {
    T d = EEA(b, a % b, x, y);
    T t = x;
    x = y;
    y = t - (a / b) * y;
    return d;
  }
}
template <class T>
inline vector<pair<T, int>> FACTORIZE(T x) {
  vector<pair<T, int>> ret;
  if (x < 0) x = -x;
  for (T i = 2; x > 1;) {
    if (x % i == 0) {
      int count = 0;
      for (; x % i == 0; x /= i) count++;
      ret.push_back(MP(i, count));
    }
    i++;
    if (i > x / i) i = x;
  }
  return ret;
}
template <class T>
inline int ISPRIME(const T x) {
  if (x <= 1) return 0;
  for (T i = 2; SQR(i) <= x; i++)
    if (x % i == 0) return 0;
  return 1;
}
template <class T>
inline T EULARFUNCTION(T x) {
  vector<pair<T, int>> f = FACTORIZE(x);
  for (typename vector<pair<T, int>>::iterator it = f.begin(); it != f.end();
       it++) {
    x = x / it->first * (it->first - 1);
  }
  return x;
}
template <class T>
inline T INVERSEE(const T a, const T b = MOD) {
  T x, y;
  EEA(a, b, x, y);
  return x ? x : 1;
}
int *PRIMELIST(const int til, int *length = NULL) {
  int *foo = (int *)malloc(sizeof(int) * (til + 1));
  int len = 0;
  memset(foo, 0, sizeof(int) * (til + 1));
  for (int i = 2; i <= til; i++) {
    if (!foo[i]) foo[len++] = i;
    for (int j = 0; j < len && foo[j] <= til / i; j++) {
      foo[foo[j] * i] = 1;
      if (i % foo[j] == 0) break;
    }
  }
  if (length != NULL) {
    *length = len;
  }
  foo[len++] = 0;
  foo = (int *)realloc(foo, sizeof(int) * len);
  return foo;
}
template <class T>
inline T MOD_STD(const T x, const T m = MOD) {
  return (x % m + m) % m;
}
template <class T>
inline void MOD_STD(T *x, const T m = MOD) {
  *x = (*x % m + m) % m;
}
template <class T>
inline T MOD_ADD(const T x, const T y, const T m = MOD) {
  return (x + y) % m;
}
template <class T>
inline void MOD_ADD(T *x, const T y, const T m = MOD) {
  *x = (*x + y) % m;
}
template <class T>
inline T MOD_MUL(const T x, const T y, const T m = MOD) {
  return (T)((1LL * x * y) % m);
}
template <class T>
inline void MOD_MUL(T *x, const T y, const T m = MOD) {
  *x = (T)((1LL * (*x) * y) % m);
}
template <class T1, class T2>
inline T1 MOD_POW(const T1 x, const T2 y, const T1 m = MOD) {
  if (y == 0)
    return 1 % m;
  else if ((y & 1) == 0) {
    T1 z = MOD_POW(x, y >> 1, m);
    return MOD_MUL(z, z, m);
  } else
    return MOD_MUL(MOD_POW(x, y ^ 1, m), x, m);
}
inline long long MODL_MUL(long long x, long long y, const long long m = MOD) {
  MOD_STD(&x, m);
  MOD_STD(&y, m);
  if (x < y) swap(x, y);
  long long z = 0LL;
  while (y > 0) {
    if (y & 1) {
      MOD_ADD(&z, x, m);
    }
    MOD_ADD(&x, x, m);
    y >>= 1;
  }
  return z;
}
inline long long MODL_POW(const long long x, const long long y,
                          const long long m = MOD) {
  if (y == 0LL)
    return 1LL % m;
  else if ((y & 1) == 0LL) {
    long long z = MODL_POW(x, y >> 1, m);
    return MODL_MUL(z, z, m);
  } else
    return MODL_MUL(MODL_POW(x, y ^ 1, m), x, m);
}
template <class T>
class MATX {
 private:
  unsigned long hig, wid;
  T *data;
  void __init() {
    this->data = (T *)malloc(sizeof(T) * this->hig * this->wid);
    memset(this->data, 0, sizeof(T) * this->hig * this->wid);
  }

 public:
  MATX() {
    this->hig = this->wid = 1;
    __init();
  }
  MATX(const unsigned long _len) {
    this->hig = this->wid = _len;
    __init();
  }
  MATX(const unsigned long _hig, const unsigned long _wid) {
    this->hig = _hig;
    this->wid = _wid;
    __init();
  }
  MATX(const MATX &rhs) {
    this->hig = rhs.hig;
    this->wid = rhs.wid;
    this->data = (T *)malloc(sizeof(T) * this->hig * this->wid);
    for (unsigned long x = 0; x < this->hig; x++)
      for (unsigned long y = 0; y < this->wid; y++)
        this->data[x * this->wid + y] = rhs.at(x, y);
  }
  ~MATX() { free(this->data); }
  T &operator()(const unsigned long x, const unsigned long y) {
    if (x >= this->hig || y >= this->wid) return (*(T *)NULL);
    return this->data[x * this->wid + y];
  }
  T *operator[](const unsigned long x) {
    if (x >= this->hig) return (T *)NULL;
    return this->data + (x * this->wid);
  }
  MATX &operator=(const MATX &rhs) {
    if (this->hig != rhs.hig || this->wid != rhs.wid) {
      free(this->data);
      this->hig = rhs.hig;
      this->wid = rhs.wid;
      this->data = (T *)malloc(sizeof(T) * this->hig * this->wid);
    }
    for (unsigned long x = 0; x < this->hig; x++)
      for (unsigned long y = 0; y < this->wid; y++)
        this->data[x * this->wid + y] = rhs.at(x, y);
    return *this;
  }
  const MATX operator+(const MATX &opn) const {
    MATX ret(*this);
    for (unsigned long x = 0; x < ret.hig; x++)
      for (unsigned long y = 0; y < ret.wid; y++)
        ret.data[x * ret.wid + y] += opn.at(x, y);
    return ret;
  }
  const MATX operator-(const MATX &opn) const {
    MATX ret(*this);
    for (unsigned long x = 0; x < ret.hig; x++)
      for (unsigned long y = 0; y < ret.wid; y++)
        ret.data[x * ret.wid + y] -= opn.at(x, y);
    return ret;
  }
  const MATX operator*(const MATX &opn) const {
    MATX ret(this->hig, opn.wid);
    const unsigned long len = MIN(this->wid, opn.hig);
    for (unsigned long x = 0; x < ret.hig; x++)
      for (unsigned long y = 0; y < ret.wid; y++)
        for (unsigned long z = 0; z < len; z++)
          ret.data[x * ret.wid + y] += this->at(x, z) * opn.at(z, y);
    return ret;
  }
  const MATX mul(const MATX &opn) const { return *this * opn; }
  template <class T2>
  const MATX mul(const MATX &opn, const T2 m) const {
    MATX ret(this->hig, opn.wid);
    const unsigned long len = MIN(this->wid, opn.wid);
    for (unsigned long x = 0; x < ret.hig; x++)
      for (unsigned long y = 0; y < ret.wid; y++)
        for (unsigned long z = 0; z < len; z++)
          MOD_ADD(&ret.data[x * ret.wid + y],
                  MOD_MUL(this->at(x, z), opn.at(z, y), m), m);
    return ret;
  }
  MATX &operator+=(const MATX &rhs) {
    *this = *this + rhs;
    return *this;
  }
  MATX &operator-=(const MATX &rhs) {
    *this = *this - rhs;
    return *this;
  }
  MATX &operator*=(const MATX &rhs) {
    *this = *this * rhs;
    return *this;
  }
  const MATX pow(const unsigned long p) const {
    MATX buff(*this), ret(this->hig, this->wid);
    ret.set_one();
    if (p > 0)
      for (unsigned long i = 1;; i <<= 1) {
        if (p & i) ret *= buff;
        buff *= buff;
        if (i > (p >> 1)) break;
      }
    return ret;
  }
  template <class T2>
  const MATX pow(const unsigned long p, const T2 m) const {
    MATX buff(*this), ret(this->hig, this->wid);
    ret.set_one();
    if (p > 0)
      for (unsigned long i = 1;; i <<= 1) {
        if (p & i) ret = ret.mul(buff, m);
        buff = buff.mul(buff, m);
        if (i > (p >> 1)) break;
      }
    return ret;
  }
  const T at(const unsigned long x, const unsigned long y) const {
    if (x >= this->hig || y >= this->wid) return 0;
    return this->data[x * wid + y];
  }
  void show() const {
    for (unsigned long x = 0; x < this->hig; x++) {
      for (unsigned long y = 0; y < this->wid; y++)
        cout << this->at(x, y) << " ";
      cout << endl;
    }
  }
  void set_one() {
    for (unsigned long x = 0; x < this->hig; x++)
      for (unsigned long y = 0; y < this->wid; y++)
        this->data[x * this->wid + y] = (x == y) ? 1 : 0;
  }
};
template <class T>
class complex_t {
 public:
  T r, i;
  complex_t(T x = 0.0, T y = 0.0) {
    this->r = x;
    this->i = y;
  }
  complex_t operator+(const complex_t &opn) const {
    return complex_t(this->r + opn.r, this->i + opn.i);
  }
  complex_t operator-(const complex_t &opn) const {
    return complex_t(this->r - opn.r, this->i - opn.i);
  }
  complex_t operator*(const complex_t &opn) const {
    return complex_t(this->r * opn.r - this->i * opn.i,
                     this->r * opn.i + this->i * opn.r);
  }
};
template <class T>
void fast_fourier_trans(complex_t<T> f[], const int len, const int is_dft) {
  for (int i = 1, j = len >> 1; i < len - 1; i++) {
    if (i < j) swap(f[i], f[j]);
    int k = len >> 1;
    while (j >= k) {
      j -= k;
      k >>= 1;
    }
    if (j < k) j += k;
  }
  for (int h = 2; h <= len; h <<= 1) {
    complex_t<T> wn(cos(is_dft ? (-2 * PI / h) : (2 * PI / h)),
                    sin(is_dft ? (-2 * PI / h) : (2 * PI / h)));
    for (int i = 0; i < len; i += h) {
      complex_t<T> wm(1.0, 0.0);
      for (int j = i; j < i + (h >> 1); j++) {
        complex_t<T> u = f[j];
        complex_t<T> t = wm * f[j + (h >> 1)];
        f[j] = u + t;
        f[j + (h >> 1)] = u - t;
        wm = wm * wn;
      }
    }
  }
  if (!is_dft) {
    for (int i = 0; i < len; i++) f[i].r /= len * 1.0;
  }
}
class MILLERRABIN {
 private:
  static const int prime_table[12];
  int witness(long long a, long long d, long long s, long long n) {
    long long r = MODL_POW(a, d, n);
    if (r == 1 || r == n - 1) return 0;
    for (int i = 0; i < s - 1; i++) {
      r = MODL_MUL(r, r, n);
      if (r == 1) return 1;
      if (r == n - 1) return 0;
    }
    return 1;
  }

 public:
  int test(const long long n) {
    if (n <= 2LL) return 0;
    long long p = n - 1LL, s = 0LL;
    while (!(p & 1)) {
      p >>= 1;
      s++;
    }
    for (int i = 0; i < 12 && this->prime_table[i] < n; i++) {
      if (witness(this->prime_table[i], p, s, n)) return 0;
    }
    return 1;
  }
};
const int MILLERRABIN::prime_table[12] = {2,  3,  5,  7,  11, 13,
                                          17, 19, 23, 29, 31, 37};
template <class T>
inline int fsign(const T x) {
  if (x > -eps && x < eps) return 0;
  return (x < 0.0) ? -1 : 1;
}
template <class T>
class point_t {
 public:
  T x, y;
  point_t() {
    this->x = 0.0;
    this->y = 0.0;
  }
  point_t(const T _x, const T _y) {
    this->x = _x;
    this->y = _y;
  }
  point_t operator-(const point_t &rhs) const {
    return point_t(this->x - rhs.x, this->y - rhs.y);
  }
  T operator^(const point_t &rhs) const {
    return this->x * rhs.y - this->y * rhs.x;
  }
  T operator*(const point_t &rhs) const {
    return this->x * rhs.x + this->y * rhs.y;
  }
  bool operator<(const point_t &rhs) const {
    if (fsign(this->y - rhs.y) != 0) return fsign(this->y - rhs.y) < 0;
    return fsign(this->x - rhs.x) < 0;
  }
  T cross(const point_t &p, const point_t &q) const {
    return (p - *this) ^ (q - *this);
  }
  void rotate(const double radian) {
    T x0 = x, y0 = y;
    T sinr = sin(radian);
    T cosr = cos(radian);
    x = x0 * cosr - y0 * sinr;
    y = x0 * sinr + y0 * cosr;
  }
  void rotate(const point_t &p, const double radian) {
    T x0 = x - p.x, y0 = y - p.y;
    T sinr = sin(radian);
    T cosr = cos(radian);
    x = x0 * cosr - y0 * sinr + p.x;
    y = x0 * sinr + y0 * cosr + p.y;
  }
  T dist2(const point_t &lhs, const point_t &rhs) const {
    return (lhs - rhs) * (lhs - rhs);
  }
  T dist2(const point_t &rhs) const { return (*this - rhs) * (*this - rhs); }
  T dist(const point_t &lhs, const point_t &rhs) const {
    return sqrt((lhs - rhs) * (lhs - rhs));
  }
  T dist(const point_t &rhs) const {
    return sqrt((*this - rhs) * (*this - rhs));
  }
};
template <class T>
class segment_t {
 public:
  point_t<T> p, q;
  segment_t() {
    this->p.x = this->p.y = 0.0;
    this->q.x = this->q.y = 0.0;
  }
  template <class T2>
  segment_t(const point_t<T2> &_p, const point_t<T2> &_q) {
    this->p.x = _p.x;
    this->p.y = _p.y;
    this->q.x = _q.x;
    this->q.y = _q.y;
  }
  segment_t(const T px, const T py, const T qx, const T qy) {
    this->p.x = px;
    this->p.y = py;
    this->q.x = qx;
    this->q.y = qy;
  }
  T length() const { return this->p.dist(this->q); }
  T length2() const { return this->p.dist2(this->q); }
  int contain(const point_t<T> &pnt, const int ignore_endpoint = 0) const {
    if (ignore_endpoint) {
      return fsign((this->p - pnt) ^ (this->q - pnt)) == 0 &&
             fsign((pnt.x - this->p.x) * (pnt.x - this->q.x)) < 0 &&
             fsign((pnt.y - this->p.y) * (pnt.y - this->q.y)) < 0;
    } else {
      return fsign((this->p - pnt) ^ (this->q - pnt)) == 0 &&
             fsign((pnt.x - this->p.x) * (pnt.x - this->q.x)) <= 0 &&
             fsign((pnt.y - this->p.y) * (pnt.y - this->q.y)) <= 0;
    }
  }
  int intersection(const segment_t &sa, const segment_t &sb,
                   const int ignore_endpoint = 0) const {
    if (!ignore_endpoint) {
      if (sa.contain(sb.p) || sa.contain(sb.q) || sb.contain(sa.p) ||
          sb.contain(sa.q))
        return 1;
    }
    return fsign(sa.p.cross(sa.q, sb.p)) * fsign(sa.p.cross(sa.q, sb.q)) < 0 &&
           fsign(sb.p.cross(sb.q, sa.p)) * fsign(sb.p.cross(sb.q, sa.q)) < 0;
  }
  int intersection(const segment_t &rhs, const int ignore_endpoint = 0) const {
    return this->intersection(*this, rhs, ignore_endpoint);
  }
};
template <class T>
static int compare_pas(const void *x, const void *y, void *z) {
  const point_t<T> *p1 = (point_t<T> *)x;
  const point_t<T> *p2 = (point_t<T> *)y;
  const point_t<T> *p0 = (point_t<T> *)z;
  int sgn = fsign(((*p1) - (*p0)) ^ ((*p2) - (*p0)));
  if (sgn != 0) return -sgn;
  return fsign(p0->dist2(*p1) - p0->dist2(*p2));
}
template <class T>
void polar_angle_sort(point_t<T> *pnts, const int n) {
  int p = 0;
  for (int i = 1; i < n; i++) {
    if (pnts[p] < pnts[i]) p = i;
  }
  swap(pnts[0], pnts[p]);
  qsort_r(pnts + 1, n - 1, sizeof(point_t<T>), compare_pas<T>, pnts);
}
template <class T>
void graham(point_t<T> *pnts, const int n, int *idx, int &m) {
  polar_angle_sort(pnts, n);
  m = 0;
  if (n < 3) return;
  idx[m++] = 0;
  idx[m++] = 1;
  for (int i = 2; i < n; i++) {
    while (m > 1 &&
           fsign(pnts[idx[m - 2]].cross(pnts[idx[m - 1]], pnts[i])) <= 0)
      m--;
    idx[m++] = i;
  }
}
struct stnode_t {
  int lef, rig;
  long long foo, cov;
  stnode_t *chd[2];
} pool[210000], *root, *tail;
long long s[210000];
void riseup(stnode_t *node) {
  node->foo = MIN(node->chd[0]->foo + node->chd[0]->cov,
                  node->chd[1]->foo + node->chd[1]->cov);
}
void build(stnode_t **hook, const int lef, const int rig) {
  stnode_t *node = *hook = tail++;
  node->lef = lef;
  node->rig = rig;
  node->cov = 0LL;
  if (lef == rig) {
    node->foo = s[lef + 1];
    node->chd[0] = node->chd[1] = NULL;
  } else {
    const int mid = (lef + rig) >> 1;
    build(&node->chd[0], lef, mid);
    build(&node->chd[1], mid + 1, rig);
    riseup(node);
  }
}
long long query(stnode_t *node, const int lef, const int rig) {
  if (lef <= node->lef && node->rig <= rig) {
    return node->foo + node->cov;
  } else {
    long long rep = 0x3f3f3f3f3f3f3f3fLL;
    if (lef <= node->chd[0]->rig) {
      UPDMIN(rep, query(node->chd[0], lef, rig));
    }
    if (rig >= node->chd[1]->lef) {
      UPDMIN(rep, query(node->chd[1], lef, rig));
    }
    return rep + node->cov;
  }
}
void check(stnode_t *node, const int lef, const int rig, const long long det) {
  if (lef <= node->lef && node->rig <= rig) {
    node->cov += det;
  } else {
    if (lef <= node->chd[0]->rig) {
      check(node->chd[0], lef, rig, det);
    }
    if (rig >= node->chd[1]->lef) {
      check(node->chd[1], lef, rig, det);
    }
    riseup(node);
  }
}
int n, m;
pair<int, int> a[210000], b[210000], p[210000];
int d[210000];
int ans;
int main() {
  while (scanf("%d%d", &n, &m) != EOF) {
    s[0] = 0LL;
    for (int i = 0; i < n; i++) {
      scanf("%d", &a[i].first);
      a[i].second = i;
      s[i + 1] = s[i] + a[i].first * 1LL;
    }
    sort(a, a + n);
    for (int i = 0; i < m; i++) {
      scanf("%d", &b[i].first);
      b[i].second = i;
    }
    sort(b, b + m);
    for (int i = 0; i < m; i++) {
      scanf("%d", &p[i].first);
      p[i].second = i;
    }
    sort(p, p + m);
    set<int, greater<int>> cnd;
    for (int i = 0; i < n; i++) cnd.insert(i);
    for (int i = 0, j = 0; i < m; i++) {
      for (; j < n && a[j].first < b[i].first; j++) cnd.erase(a[j].second);
      if (!cnd.empty()) {
        d[b[i].second] = *cnd.begin();
      } else {
        d[b[i].second] = -1;
      }
    }
    ans = 0;
    tail = pool;
    build(&root, 0, n - 1);
    for (int i = 0; i < m; i++) {
      if (!~d[p[i].second]) continue;
      if (query(root, d[p[i].second], n - 1) >= p[i].first) {
        check(root, d[p[i].second], n - 1, -p[i].first * 1LL);
        ans++;
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

```