この問題は答えを二分探索することで解くことができます。

「全ての依頼を \(X\) 分以内に処理できるか？」という判定問題を考えます。

このとき「処理できる最大ページ数の小さなプリンターから順に、割り当て可能な依頼を割り当てられるだけ割り当てる」とするのが最適になります。

よって、予めプリンターを最大ページ数順、依頼をページ数順に並べておくことで、\(O(N+M)\) でこの判定問題を解くことができるので、答えを二分探索することにより、全体で \(O((N+M)(\log \max T_i+\log N+\log M))\) でこの問題を解くことができます。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n, m;
  cin >> n >> m;
  vector<pair<int, int>> wt(n);
  for(int i=0; i<n; i++) cin >> wt[i].first >> wt[i].second;
  vector<int> p(m);
  for(int i=0; i<m; i++) cin >> p[i];
  
  sort(wt.begin(), wt.end());
  sort(p.begin(), p.end());
  
  if(p.back() > wt.back().first){
    // どのプリンターでも処理できない依頼が存在する
    cout << -1 << endl;
    return 0;
  }
  
  auto f=[&](long long x){
    // 時間 x 以内に全ての依頼を処理できるか？
    int i = 0;
    for(auto[w, t]: wt){
      for(int j=0; j<x/t; j++){
        if(i < m && p[i] <= w){
          i++;
        }else{
          break;
        }
      }
    }
    return i == m;
  };
  
  long long ng = 0, ok = 1e15;
  while(ok - ng > 1){
    long long m = (ok + ng) / 2;
    if(f(m)){
      ok = m;
    }else{
      ng = m;
    }
  }
  cout << ok << endl;
}

実装例 (Python)

N, M = map(int, input().split())
WT = [tuple(map(int, input().split())) for _ in range(N)]
WT.sort()
P = [int(input()) for _ in range(M)]
P.sort()

if P[-1] > WT[-1][0]:
  # どのプリンターでも処理できない依頼が存在する
  print(-1)
  exit()

def f(x):
  # 時間 x 以内に全ての依頼を処理できるか？
  i = 0
  for W, T in WT:
    for _ in range(x//T):
      if i < M and P[i] <= W:
        i += 1
      else:
        break
  return i == M

ng = 0
ok = 10**15
while ok - ng > 1:
  m = (ok+ng) // 2
  if f(m):
    ok = m
  else:
    ng = m

print(ok)