Problem: Example

Input

3 9
6 3
5 2
3 1
2
2
2


Output

2

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long int64;
typedef pair< int64, int64 > Pi;
const int64 INF = 1LL << 58;
 
int N, L, A[100000], B[100000], C[100000];
vector< Pi > drinks;
priority_queue< Pi > que, que2;
int64 v[100000];
 
int solve()
{
  int my_height = 0;
  int enemy_height = 0;
  int deletable = 0;
 
  for(int i = 0; i < N; i++) {
    while(!que.empty() && v[que.top().second] < i) que.pop();
    if(!que.empty() && my_height + que.top().first >= L) return (i + 1);
    my_height += drinks[i].first;
    que2.emplace(B[drinks[i].second], drinks[i].second);
    while(my_height - drinks[deletable].first <= enemy_height) ++deletable;
    while(!que2.empty() && v[que2.top().second] < deletable) que2.pop();
    if(!que2.empty() && my_height + que2.top().first >= L) return (i + 1);
    v[drinks[i].second] = i;
    enemy_height += C[i];
    if(enemy_height >= my_height) return (-1);
  }
  return (-1);
}
 
int main()
{
  cin >> N >> L;
  for(int i = 0; i < N; i++) {
    cin >> A[i] >> B[i];
    que.emplace(A[i], i);
    drinks.emplace_back(A[i] - B[i], i);
    v[i] = INF;
  }
  sort(begin(drinks), end(drinks));
  reverse(begin(drinks), end(drinks));
  for(int i = 0; i < N; i++) {
    cin >> C[i];
  }
  cout << solve() << endl;
}