Problem: Example

Input

3 9
6 3
5 2
3 1
2
2
2


Output

2

Solution (in CPP):

Solution:
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010

/* SimpleSegTree(0-index) */

template <typename Type = int>
struct SimpleSegTree{
  int segn2;
  Type initVal;
  vector<Type> data;
  function<Type(Type, Type)> merge;

  SimpleSegTree(int n, Type initVal, function<Type(Type, Type)> merge):
    initVal(initVal), merge(merge)
  {
    for(segn2=1; segn2<n; segn2*=2);
    data.assign(segn2*2, initVal);
  }

  SimpleSegTree(int n): //RangeMinimunQuery
    SimpleSegTree(n, LLINF, [](Type a, Type b){ return min(a, b); }) {}

  SimpleSegTree(int n, Type initVal): //RangeMinimunQuery
    SimpleSegTree(n, initVal, [](Type a, Type b){ return min(a, b); }) {}

  //get value [a,b)
  Type query(int a, int b, int l = 0, int r = -1, int k = 0){
    if(r == -1) r = segn2;
    if(a <= l && r <= b) return data[k];
    if(r <= a || b <= l) return initVal;
    return merge(query(a,b,l,(l+r)/2,k*2+1),query(a,b,(l+r)/2,r,k*2+2));
  }

  //set kth number x
  void set(int k, Type x){
    k += segn2-1;
    data[k] = x;
    while(k > 0){
      k = (k-1)/2;
      data[k] = merge(data[k*2+1], data[k*2+2]);
    }
  }
};



ll A[SIZE], B[SIZE], C[SIZE];
pair<ll,int> d[SIZE];
int pos[SIZE];
bool ok[SIZE];

int main(){
  int N, L;

  scanf("%d%d", &N, &L);

  bool once = false;

  for (int i=0; i<N; i++) {
    scanf("%lld%lld", A+i, B+i);
    d[i] = {A[i] - B[i], i};
    once |= A[i] >= L;
  }

  if (once) {
    puts("1");
    return 0;
  }

  sort(d, d+N, greater<pair<ll,int>>());

  for (int i=0; i<N-1; i++) {
    d[i+1].first = max(0LL, d[i+1].first) + d[i].first;
    pos[d[i].second] = i;
  }
  pos[d[N-1].second] = N-1;


  for (int i=0; i<N; i++)
    scanf("%lld", C+i);

  for (int i=0; i<N-1; i++)
    C[i+1] += C[i];

  for (int i=0; i<N; i++) {
    ok[i] = C[i] < d[i].first;
    if (i > 0) ok[i] &= ok[i-1];
    debug(d[i].first);
    debug(ok[i]);
  }

  SimpleSegTree<ll> seg(N);

  for (int i=0; i<N-1; i++) {
    seg.set(i, d[i+1].first - C[i]);
  }


  int ans = INF;

  for (int i=0; i<N; i++) {
    int p = pos[i];

    int q1 = lower_bound(d, d+p, make_pair(L-A[i], 0)) - d;
    int q2 = lower_bound(d+p+1, d+N, make_pair(L+(A[i]-B[i])-A[i], 0)) - d;

    debug(p); debug(q1); debug(q2);

    if (q1 < p) {
      if (ok[q1]) ans = min(ans, q1+2);
    }

    if (q2 < N) {
      if ((p < 0 || ok[p-1]) && seg.query(p, q2) > (A[i] - B[i]))
        ans = min(ans, q2+1);
    }
  }

  if (ans == INF) ans = -1;

  printf("%d\n", ans);
  return 0;
}