WA ON：small_01/02/09/10/18

(提交)[https://atcoder.jp/contests/arc105/submissions/55987948]

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll MOD=998244353;
// head
const int N=10,M=1e5+5,INF=1e18;
struct node{int l,v;}brg[M];bool cmp(node p,node q){return p.v<q.v;}
int a[N];
int le[M],v[M];
int sum[N];
int ls(int x) {return x<<1;}
int rs(int x) {return x<<1|1;}
struct Seg
{
	int ans[M<<2];
	void push_up(int dir)
	{
		ans[dir]=max(ans[ls(dir)],ans[rs(dir)]);
	}
	void build_tree(int dir,int l,int r)
	{
		if(l==r) {ans[dir]=le[l];return ;}
		int mid=(l+r)>>1;
		build_tree(ls(dir),l,mid);
		build_tree(rs(dir),mid+1,r);
		push_up(dir);
	}
	int query(int qx,int qy,int x,int y,int dir)
	{
		int sum=0;
		if(qx<=x&&y<=qy) return ans[dir];
		int mid=(x+y)>>1;
		if(qx<=mid) sum=query(qx,qy,x,mid,ls(dir));
		if(qy>mid) sum=max(sum,query(qx,qy,mid+1,y,rs(dir)));
		return sum;
	}
}tree;
signed main() 
{
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int n,m;cin>>n>>m;
	int maxn=0;
	for(int i=1;i<=n;i++) {cin>>a[i];maxn=max(maxn,a[i]);}
	for(int i=1;i<=m;i++) cin>>brg[i].l>>brg[i].v;
	sort(brg+1,brg+1+m,cmp);
	for(int i=1;i<=m;i++) le[i]=brg[i].l,v[i]=brg[i].v;
	tree.build_tree(1,1,m);
	if(maxn>v[1]) {cout<<-1<<endl;return 0;}
	vector<int> pos;for(int i=1;i<=n;i++) pos.pb(i);
	int ans=INF;
	do
	{
		for(int i=1;i<=n;i++) sum[i]=0;
		for(int i=2;i<=n;i++){
			for(int j=i;j<=n;j++){
				int cnt=0,cnt1=0;
				for(int k=j-i+1;k<j;k++) cnt+=sum[k];
				for(int k=j-i+1;k<=j;k++) cnt1+=a[pos[k-1]];
				int dir=lower_bound(v+1,v+1+m,cnt1)-v-1;
				if(dir==0) continue;
				int tmpp=tree.query(1,dir,1,m,1);
				if(tmpp>cnt) sum[j-1]+=tmpp-cnt;
			}
		}
		int cnt=0;
		for(int i=1;i<n;i++) cnt+=sum[i];
		ans=min(ans,cnt);
	}while(next_permutation(all(pos)));
	cout<<ans<<endl;
}