重さ \(d_1\) の荷物を重量制限 \(e_1\) のトラックに、重さ \(d_2\) の荷物を重量制限 \(e_2\) のトラックに積み込んだとします。
もし \(d_1 < d_2\) かつ \(e_1 > e_2\) であるとき、これらの荷物を交換しても依然積み込むことが可能です。

なので、ある特定の \(k\) 個の荷物を積み込むと決め打った時、もしそれらの荷物が全て詰め込めるのであれば、重さ \(d_i\) の荷物を重量制限 \(e_i\) のトラックに積み込んだとすると、 \(d_1 \le d_2 \le \dots \le d_k\) が成り立つように並べ替えた時に \(e_1 \le e_2 \le \dots \le e_k\) が成り立つような積み込み方が存在することが証明できます。

ここから、以下の貪欲法が成立します。

• 荷物を重い順にソートする。
• トラックを重量制限の大きい順にソートする。
• 以下を全ての荷物の処遇が決まるまで繰り返す。
  • 先頭の荷物が先頭のトラックに積み込めるのであれば、積み込む。
  • そうでなく先頭のトラックの残り容量が \(0\) なら、そのトラックを削除する。
  • そうでないなら、現在の状況からどのようにしても先頭の荷物を積み込むことはできないので、先頭の荷物を削除する。

時間計算量は \(O(N \log N + M \log M)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using pi=pair<int,int>;

int main(){
  int N,M;
  cin >> N >> M;
  vector<pi> EC(N);
  for(auto &nx : EC){
    cin >> nx.first >> nx.second;
  }
  sort(EC.begin(),EC.end());
  vector<int> D(M);
  for(auto &nx : D){cin >> nx;}
  sort(D.rbegin(),D.rend());
  int res=0;
  for(auto &nx : D){
    while((!EC.empty()) && EC.back().second==0){
      EC.pop_back();
    }
    if(EC.empty()){break;}
    
    if(nx <= EC.back().first){
      EC.back().second--;
      res++;
    }
  }
  cout << res << "\n";
  return 0;
}