表現の都合上、アルバイトに対して割り当てられる営業日のことを「仕事」と表します。

考察

スキルレベルの高い人は、スキルレベルの低い人ができる仕事を全てできます。よって、「スキルレベルの低い人に、その人でもできる仕事をまず割り当ててから、スキルレベルの高い人に残りの仕事を割り当てる」というのがよさそうです。

解法

スキルレベルの低い人から順に、その人ができる仕事のうち最も売上が高いものを貪欲に割り当てればよいです。

計算量は \(O(N\log N)\) です。

証明

スキルレベルが同じ人が複数いる場合、インデックスなどでタイブレークするとし、順序が一致に定まるとしてよい。
割当 \(X\) を任意に取る。上で説明した貪欲法で定められる割当を \(G\) とする。
以下の操作を繰り返すことで、売上を下げることなく \(X\) を \(G\) に一致させることができる：

\(X\) と \(G\) を比較して、割り当てられた仕事が異なる人のうち、スキルレベルが最も低い人を \(i\) とする。\(G\) においてその人に割り当てられている仕事を \(j\) とする。
\(X\) において仕事 \(j\) に割り当てられている人が存在しない場合、人 \(i\) に割り当てる仕事を \(j\) に変更しても損しない（貪欲法の定義より、今の仕事より仕事 \(j\) の方が売上が低いことはないため）。
\(X\) において仕事 \(j\) に割り当てられている人が存在する場合、その人を \(i'\) とすると、 \(i\) の取り方から \(i'\) は \(i\) よりもスキルレベルが高いため、\(i\) の仕事と \(i'\) の仕事を入れ替えることができる。

この繰り返しでは「\(X\) と \(G\) で割り当てられた仕事が異なる人」のスキルレベルが狭義単調に増加するため、この操作は有限回で終わる。

実装

売上の高い順に仕事を取り出せるプライオリティーキューを用意し、スキルレベルの低い順に人を見ながら、必要スキルレベルの低い仕事をキューに追加すればよいです。

実装例 (C++)

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

int main(){
  int n, m;
  cin >> n >> m;
  vector<pair<int, int>>hs(n);
  for(int i=0; i<n; i++) cin >> hs[i].first >> hs[i].second;
  sort(hs.begin(), hs.end());
  vector<int>p(m);
  for(int i=0; i<m; i++) cin >> p[i];
  sort(p.begin(), p.end());

  int pos = 0;
  priority_queue<int>q;
  long long ans = 0;
  for(int i=0; i<m; i++){
    // 必要スキルレベルが低い仕事をキューに追加
    while(pos < n && hs[pos].first <= p[i]){
      q.push(hs[pos].second);
      pos++;
    }
    // キューから取り出して仕事を割り当て
    if(q.size()){
      ans += q.top();
      q.pop();
    }else{
      cout << -1 << endl;
      return 0;
    }
  }
  cout << ans << endl;
}

実装例 (Python)
python の heapq は最小値を優先して取り出すものであるため、キューに追加する要素を \(-1\) 倍することで、実質的に最大値が取り出せるようにしています。

import heapq

N, M = map(int,input().split())
HS = []
for _ in range(N):
  H, S = map(int,input().split())
  HS.append((H, S))
HS.sort()
P = list(map(int,input().split()))
P.sort()

pos = 0
q = []
ans = 0
for p in P:
  # 必要スキルレベルが低い仕事をキューに追加
  while pos < N and HS[pos][0] <= p:
    heapq.heappush(q, -HS[pos][1])
    pos += 1
  # キューから取り出して仕事を割り当て
  if len(q) > 0:
    ans += -heapq.heappop(q)
  else:
    print(-1)
    exit()

print(ans)