C++ 解法, 执行用时: 834ms, 内存消耗: 64676K, 提交时间: 2021-05-29 22:55:28

#include<bits/stdc++.h>
#define ll long long
#define x first
#define y second
using namespace std;
struct data{
	ll x,y;
	data():x(0),y(0){}
	data(ll _x,ll _y):x(_x),y(_y){}
	bool operator < (const data m) const{
		return x>m.x;
	}
};
const int N = 2e6 + 10;
int n,m;
priority_queue<ll,vector<ll>,greater<ll> > H0;
priority_queue<data> H1;
pair<ll,ll> p[N];
ll ans = 0 ,sum ;
int main(){
	//freopen("data.in","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		int x;
		scanf("%d",&x);
		p[i]=make_pair(x,-1);
	}
	sum=n;
	while(m--){
		int x,y;
		scanf("%d%d",&x,&y);
		p[++n]=make_pair(x,y);
		sum-=y;
	}
	if(sum>0) return puts("-1"),0;
	sort(p+1,p+1+n);
	for(int i=1;i<=n;++i){
		if(p[i].y==-1){
			ll w = 1e15;
			if(!H1.empty()){
				ll x = H1.top().x , y = H1.top().y;H1.pop();
				w = p[i].x+x;
				y--;
				if(y) 
					H1.push(data(x,y));
			}
			ans += w;
			H0.push(-p[i].x-w);
		}
		else{
			while(p[i].y&&!H0.empty()&&p[i].x+H0.top()<0){
				ll w = p[i].x + H0.top() ; H0.pop(); 
				ans += w ; 
				p[i].y-- ;
				H1.push(data(-p[i].x-w,1));	
			}
			if(p[i].y){
				H1.push(data(-p[i].x,p[i].y));
			}
		}
	}
	printf("%lld",ans);
	return 0;
}