stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;i++)

#define all(x) (x).begin(),(x).end()

using namespace std;

const int INF=1145141919,MOD=1e9+7;

const long long LINF=8931145141919364364,LMOD=998244353;

inline long long mod(long long n,long long m){return(n%m+m)%m;}

// const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};



// unsigned long long modpow(long long a,long long n){

//     long long x=1;

//     while(n>0){

//         //nの2進数表記の右端が1

//         if(n&1){

//             x=x*a;

//         }

//         a=a*a;

//         n>>=1; //nを右に1bitずらす

//     }

//     return x;

// }

int main(){

    long long n,p; cin>>n>>p;

    if(n==1){

        cout<<p<<endl;

        return 0;

    }

    long long MAX=1;

    for(long long i=2;;i++){

        if(pow(i,n)>1e13) break;

        MAX=i+1;

    }

    long long ans=1;

    for(long long i=2;i<=MAX;i++){

        long long tmp=pow(i,n);

        if(p%tmp==0){

            ans=i;

        }else if(p<=tmp){

            break;

        }

    }

    cout<<ans<<endl;

    return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;i++)

#define all(x) (x).begin(),(x).end()

using namespace std;

const int INF=1145141919,MOD=1e9+7;

const long long LINF=8931145141919364364,LMOD=998244353;

inline long long mod(long long n,long long m){return(n%m+m)%m;}

// const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};



map<long long,int> mp;

vector<long long> prime_factorization(long long a){

    vector<long long> v;

    if(a==1) v.push_back(1);

    long long i=2,n=a;

    while(n>1){

        if(a<i*i){

            v.push_back(i);

            mp[n]++;

            return v;

        }

        if(n%i==0){

            n/=i;

            v.push_back(i);

            mp[i]++;

        }else{

            i++;

        }

    }

    return v;

}

int main(){

    long long n,p; cin>>n>>p;

    if(n==1){

        cout<<p<<endl;

        return 0;

    }

    vector<long long> v=prime_factorization(p);

    long long ans=1;

    for(auto i:mp){

        ans*=pow(i.first,i.second/n);

    }

    cout<<ans<<endl;

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <algorithm>

using namespace std;



int dp[501][501];

bool field[501][501];



int main() {

    for(int N; cin >> N, N; ) {

        fill(dp[0], dp[501], 0);

        fill(field[0], field[501], 0);

        int W, H; cin >> W >> H;

        while(N--) {

            int X, Y; cin >> X >> Y;

            field[Y][X] = true;

        }

        for(int x = 1; x <= W; x++) {

            for(int y = 1; y <= H; y++) {

                dp[y][x] = dp[y - 1][x] + dp[y][x - 1] - dp[y - 1][x - 1] + field[y][x];

            }

        }

        int S, T; cin >> S >> T;

        int res = 0;

        for(int x = S; x <= W; x++) {

            for(int y = T; y <= H; y++) {

                res = max(res, dp[y][x] - dp[y - T][x] - dp[y][x - S] + dp[y - T][x - S]);

            }

        }

        cout << res << endl;

    }

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <algorithm>

#include <cstring>

using namespace std;

int main() {

  while(true) {

    int N; cin >> N;

    if(N == 0) break;

    int W, H; cin >> W >> H;

    int F[W][H];

    memset(F, 0, sizeof(F));

    for(int i = 0; i < N; ++i) {

      int x, y; cin >> x >> y;

      x--, y--;

      F[x][y] = 1;

    }

    int S, T; cin >> S >> T;

    int G[W+1][H+1];

    memset(G, 0, sizeof(G));

    for(int y = 1; y <= H; ++y) {

      for(int x = 1; x <= W; ++x) {

        G[x][y] = G[x-1][y] + G[x][y-1] - G[x-1][y-1] + F[x-1][y-1];

        // cerr << "G(" << y << "," << x << ") = " << G[x][y] << endl;

      }

    }

    int ans = 0;

    for(int y = T; y <= H; ++y) {

      for(int x = S; x <= W; ++x) {

        ans = max(ans, G[x][y] - G[x-S][y] - G[x][y-T] + G[x-S][y-T]);

      }

    }

    cout << ans << endl;

  }

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <fstream>

#include <stdio.h>

#include <math.h>

#include <time.h>

#include <string>

#include <tuple>

#include <vector>

#include <map>

#include <unordered_map>

#include <list>

#include <set>

#include <stack>

#include <queue>

#include <cstdlib>

#include <algorithm>

#include <random>

#include <cassert>

using namespace std;

#define LL long long

#define MP(a, b) make_pair(a, b)

#define POWER9 1000000000

#define MOD POWER9+1

#undef INT_MIN

#undef INT_MAX

#define INT_MIN -2147483647

#define INT_MAX 2147483647

#define LL_MIN (LL)-9223372036854775807

#define LL_MAX (LL)9223372036854775807

#define PI 3.14159265359



string S,T;

string dp[2][3001];



string max(string A, string B, string C){

	if(A.size() >= B.size() && A.size() >= C.size()) return A;

	if(B.size() >= C.size()) return B;

	return C;

}



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);



	cin >> S >> T;

    for(int i=0; i<=1; i++) dp[i][T.size()] = "";

    for(int j=0; j<=T.size(); j++) dp[S.size()%2][j] = "";

    for(int i=S.size()-1; i>=0; i--){

        for(int j=T.size()-1; j>=0; j--){

            dp[i%2][j] = max(dp[(i+1)%2][j], dp[i%2][j+1], S[i]==T[j] ? S[i]+dp[(i+1)%2][j+1] : "");

        }

    }

    cout << dp[0][0] << endl;



	return 0;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <fstream>

#include <stdio.h>

#include <math.h>

#include <time.h>

#include <string>

#include <tuple>

#include <vector>

#include <map>

#include <unordered_map>

#include <list>

#include <set>

#include <stack>

#include <queue>

#include <cstdlib>

#include <algorithm>

#include <random>

#include <cassert>

using namespace std;

#define LL long long

#define MP(a, b) make_pair(a, b)

#define POWER9 1000000000

#define MOD POWER9+1

#undef INT_MIN

#undef INT_MAX

#define INT_MIN -2147483647

#define INT_MAX 2147483647

#define LL_MIN (LL)-9223372036854775807

#define LL_MAX (LL)9223372036854775807

#define PI 3.14159265359



string S,T;

int dp[3001][3001];



int max(int a, int b, int c){ return max(a, max(b, c)); }



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);



	cin >> S >> T;

    for(int i=0; i<=S.size(); i++) dp[i][T.size()] = 0;

    for(int j=0; j<=T.size(); j++) dp[S.size()][j] = 0;

    for(int i=S.size()-1; i>=0; i--){

        for(int j=T.size()-1; j>=0; j--){

            dp[i][j] = max(dp[i+1][j], dp[i][j+1], S[i]==T[j] ? dp[i+1][j+1]+1 : 0);

        }

    }



    int i = 0;

    int j = 0;

    while(dp[i][j] > 0){

        if(S[i] == T[j] && dp[i][j] == dp[i+1][j+1]+1){

            cout << S[i];

            i++; j++;

        }

        else if(dp[i][j] == dp[i+1][j]) i++;

        else j++;

    }

    cout << endl;



	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#define ll long long

#define ld long double

#define ull unsigned ll

#define ioi exit(0);

 

#define f first

#define s second

 

#define inf (int)1e9 + 7

 

#define NFS ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

 

#define mp(x,y) make_pair(x,y)

 

#define lb(x) lower_bound(x)

#define ub(x) upper_bound(x)

 

#define pb push_back

#define ppb pop_back

 

#define bitcoin __builtin_popcount

 

#define endl "\n"

 

#define in(x) insert(x)

 

#define sz(x) (int)x.size()

 

#define all(x) x.begin(),x.end()

 

#define pw2(x) (1ll<<x) //2^x

 

#define forit(it,v) for (typeof(v.begin()) it = v.begin(); it != v.end(); ++it)

 

#define sqr(x) ((x) * 1ll * (x))

 

#define UpdateRandom srand (time(NULL));

 

using namespace std;

 

const int N = (int)3e3 + 7, MOD = (int)1e9 + 7;



string s,t;



string dp[4][N];



int main(){

		

	NFS



	cin >> s >> t;



	for(int i=1;i<=sz(s);i++){

		for(int j=1;j<=sz(t);j++){

			if(sz(dp[2][j-1])>sz(dp[2][j]))dp[2][j]=dp[2][j-1];

			if(sz(dp[2-1][j])>sz(dp[2][j]))dp[2][j]=dp[2-1][j];

			if(sz(dp[2-1][j-1])>sz(dp[2][j]))dp[2][j]=dp[2-1][j-1];

			if(s[i-1]==t[j-1]){

				if(sz(dp[2-1][j-1])+1>sz(dp[2][j]))dp[2][j]=dp[2-1][j-1]+s[i-1];

			}

		}

		for(int j=1;j<=sz(t);j++)dp[1][j]=dp[2][j],dp[2][j].clear();

	}

	

	cout << dp[1][sz(t)] << endl;

	

	ioi

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h> 

using namespace std; 

#define MAXC 3000



char cads[MAXC+1], cadt[MAXC+1];

int dp[MAXC+1][MAXC+1];



int s,t;

char lcs[MAXC+1];



int main() { 

	int i,j;

        int posicion;

	scanf("%s",cads);

	scanf("%s",cadt);

	s=strlen(cads); t = strlen(cadt);

	for (i=0; i<=s; i++) {

		dp[i][0]=0;

	}

	for (j=1; j<=t; j++) {

		dp[0][j]=0;

	}



	for (i=1;i<=s; i++) {

		for (j=1; j<=t; j++) {

			if (cads[i-1]==cadt[j-1]) {

				dp[i][j]=dp[i-1][j-1]+1;

			}

			else {

				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

			}

		}

	}

	/*for (i=0; i<=s; i++) {

		for (j=0; j<=t; j++) {

			printf("%5d", dp[i][j]);

		}

		printf("\n");

	}

	printf("%d\n",dp[s][t]);*/

	posicion=dp[s][t];

	lcs[posicion]=0;

	for (i=s, j=t; i>0 && j>0; ) {

		if (cads[i-1]==cadt[j-1]) {

			posicion--; i--; j--;

			lcs[posicion]=cads[i];

		}

		else if (dp[i-1][j]>dp[i][j-1]) {

			i--;

		}

		else { 

			j--; 

		}

	}

	printf("%s\n", lcs);

	return 0; 

} 


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;



#define INF 2000000000

#define ll long long



int res;

int N, P;

vector<pair<int, int> > v;

vector<int> com;

int seg[530000];



void Init()

{

	for(int i=0; i<530000; i++)

		seg[i] = -INF;

}



int Update(int idx, int val, int n, int l, int r)

{

	if (r < idx || idx < l) return seg[n];

	if (l == r) return seg[n] = max(seg[n], val);

	int mid = l+r>>1;

	return seg[n] = max(Update(idx, val, n<<1, l, mid), Update(idx, val, n<<1|1, mid+1, r));

}



int Query(int L, int R, int n, int l, int r)

{

	if (r < L || R < l) return -INF;

	if (L <= l && r <= R) return seg[n];

	int mid = l+r>>1;

	return max(Query(L, R, n<<1, l, mid), Query(L, R, n<<1|1, mid+1, r));

}



int main()

{

	scanf("%d", &N);

	for(int i=1; i<=N; i++)

	{

		int x, y;

		scanf("%d %d", &x, &y);

		v.push_back({x, y});

		com.push_back(y);

	}

	sort(v.begin(), v.end());



	// 좌표 압축

	sort(com.begin(), com.end());

	com.erase(unique(com.begin(), com.end()), com.end());

	P = com.size();



	Init();

	vector<int> qry;

	for(int i=0; i<v.size(); i++)

	{

		int x = v[i].first, y = v[i].second;

		int idx = lower_bound(com.begin(), com.end(), y) - com.begin();

		Update(idx, -x-y, 1, 0, P-1);

		qry.push_back(i);



		if (i+1==v.size() || v[i].first != v[i+1].first)

		{

			for(int j : qry)

			{

				int x = v[j].first, y = v[j].second;

				int idx = lower_bound(com.begin(), com.end(), y) - com.begin();

				res = max(res, Query(0, idx, 1, 0, P-1)+x+y);

			}

			qry.clear();

		}

	}



	Init();

	for(int i=0; i<v.size(); i++)

	{

		int x = v[i].first, y = v[i].second;

		int idx = lower_bound(com.begin(), com.end(), y) - com.begin();

		Update(idx, -x+y, 1, 0, P-1);

		qry.push_back(i);



		if (i+1==v.size() || v[i].first != v[i+1].first)

		{

			for(int j : qry)

			{

				int x = v[j].first, y = v[j].second;

				int idx = lower_bound(com.begin(), com.end(), y) - com.begin();

				res = max(res, Query(idx, P-1, 1, 0, P-1)+x-y); // idx+1로 하면 Query가 -2e9라 음수 overflow...

			}

			qry.clear();

		}

	}



	printf("%d\n", res);

	return 0;

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;



#define INF 2000000000

#define ll long long



int N;

int X[200201], Y[200201];



int main()

{

	scanf("%d", &N);

	int mx1 = -INF, mx2 = -INF, mx3 = -INF, mx4 = -INF;

	for(int i=1; i<=N; i++)

	{

		scanf("%d %d", &X[i], &Y[i]);

		mx1 = max(mx1, -X[i]-Y[i]);

		mx2 = max(mx2, -X[i]+Y[i]);

		mx3 = max(mx3, +X[i]-Y[i]);

		mx4 = max(mx4, +X[i]+Y[i]);

	}

	int res = 0;

	for(int i=1; i<=N; i++)

	{

		res = max(res, mx1+X[i]+Y[i]);

		res = max(res, mx2+X[i]-Y[i]);

		res = max(res, mx3-X[i]+Y[i]);

		res = max(res, mx4-X[i]-Y[i]);

	}

	printf("%d", res);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;

const int mod = 1e9+7;

int add(int a, int b) {

	return a + b < mod ? a + b : a + b - mod;

}

int mul(int a, int b) {

	return int(1LL * a * b % mod);

}

int fexp(int b, int e = mod - 2) {

	int ans = 1;

	while(e) {

		if(e & 1) ans = mul(ans, b);

		b = mul(b, b);

		e /= 2;

	}

	return ans;

}



using ll = long long;

const ll oo = 1e18;



const int N = 200005;



struct Segtree {

	ll st[2 * N];

	int n;



	ll query(int l, int r){ // [l, r]

		ll ans = -oo;

		for(l += n, r += n+1; l < r; l >>= 1, r >>= 1){

			if(l & 1) ans = max(ans, st[l++]);

			if(r & 1) ans = max(ans, st[--r]);

		}

		return ans;

	}



	void build() {

		for(int i = 0; i < 2 * N; i++) st[i] = -oo;

	}



	void update(int p, ll val){

		p += n;

		st[p] = max(st[p], val);

		while(p >>= 1) st[p] = max(st[2*p], st[2*p+1]);

	}

} up, down;



int n;

ll x[N], y[N];

ll compr[N];



int gety(ll val) {

	return int(lower_bound(compr, compr + n, val) - compr);

}

int id[N];



int main() {

	scanf("%d", &n);

	up.n = down.n = n;

	up.build(), down.build();



	for(int i = 0; i < n; i++) {

		scanf("%lld %lld", x + i, y + i);

		compr[i] = y[i];

		id[i] = i;

	}

	sort(compr, compr + n);



	sort(id, id + n, [](int i, int j) {

		if(x[i] != x[j]) return x[i] < x[j];

		return y[i] < y[j];

	});

	

	ll ans = 0;



	for(int w = 0; w < n; w++) {

		int i = id[w];



		int me = gety(y[i]);



		ans = max(ans, up.query(me, n - 1) + x[i] - y[i]);

		ans = max(ans, down.query(0, me) + x[i] + y[i]);



		up.update(me, y[i] - x[i]);

		down.update(me, -y[i] - x[i]);

	}



	printf("%lld\n", ans);

	return 0;



	for(int i = 0; i < n; i++) for(int j = i + 1; j < n; j++) {

		ll tmp = abs(x[i] - x[j]) + abs(y[i] - y[j]);

		if(tmp > ans) {

			printf("%d(%lld %lld) %d(%lld %lld)\n", i, x[i], y[i], j, x[j], y[j]);

			assert(0);

		}

	}



}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>



using namespace std;



const int N = 200005;



struct vec {

	int x, y;

	int operator*(const vec &o) const {

		return x * o.x + y * o.y;

	}

	int dist(const vec &o) const {

		return abs(x - o.x) + abs(y - o.y);

	}

} pt[N];



int n;



int main() {

	scanf("%d", &n);

	

	for(int i = 0; i < n; i++) {

		scanf("%d %d", &pt[i].x, &pt[i].y);

	}



	array<vec, 4> best{pt[0], pt[0], pt[0], pt[0]};



	for(int i = 0; i < n; i++) {

		int id = 0;

		for(int j : {-1, 1}) for(int k : {-1, 1}) {

			vec tmp{j, k};

			if(tmp * pt[i] > tmp * best[id]) best[id] = pt[i];

			id++;

		}

	}



	int ans = 0;

	for(int i = 0; i < 4; i++) for(int j = i + 1; j < 4; j++) {

		ans = max(ans, best[i].dist(best[j]));

	}



	printf("%d\n", ans);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>



#define SORT(v) sort(v.begin(),v.end())

#define si(n) scanf("%d",&n)

#define sii(n,m) scanf("%d %d",&n,&m)

#define sl(n) scanf("%lld",&n)

#define sll(n,m) scanf("%lld %lld",&n,&m)

#define ss(cad) scanf("%s",cad)

#define PB push_back

#define fst first

#define scn second

#define DBG(x) cerr << #x << " = " << (x) << endl; 

#define M 1000000007

#define N_MAX 100010



using namespace std;



typedef long long ll;

typedef vector<int> vi;

typedef vector<bool> vb;

typedef vector<ll> vl;

typedef pair<int,int> pi;

typedef vector<pi> vp;



int main(){

	int n;

	si(n);

	vector<pair<ll, int> > v1(n), v2(n), vv1(n), vv2(n);

	for(int i = 0; i < n; i++){

		int a, b;

		sii(a, b);

		v1[i] = {(ll)2*1000000000 - a - b, i};

		v2[i] = {a + b, i};

		vv1[i] = {(ll)1000000000 - b + a, i};

		vv2[i] = {(ll)1000000000 - a + b, i};

	}

	sort(v1.begin(), v1.end());

	sort(v2.begin(), v2.end());

	sort(vv1.begin(), vv1.end());

	sort(vv2.begin(), vv2.end());

	ll ans = 0;

	if(v1[0].scn != v2[0].scn)

		ans = (ll)2*1000000000 - v1[0].fst - v2[0].fst;

	else

		ans = max((ll)2*1000000000 - v1[0].fst - v2[1].fst, (ll)2*1000000000 - v1[1].fst - v2[0].fst);



	if(vv1[0].scn != vv2[0].scn)

		ans = max(ans, (ll)2*1000000000 - vv1[0].fst - vv2[0].fst);

	else

		ans = max(ans, max((ll)2*1000000000 - vv1[0].fst - vv2[1].fst, (ll)2*1000000000 - vv1[1].fst - vv2[0].fst));

	printf("%lld\n", ans);

	return 0;

}


// Optimized solution to the same problem (faster):
#include<algorithm>

#include<string>

#include<math.h>



using namespace std;



const int N = 200010;



int n,x,y;

int a[N],b[N];

int main(){

	scanf("%d",&n);

	for(int i=0;i<n;i++){

		scanf("%d%d",&x,&y);

		a[i]=x+y;

		b[i]=x-y;

	}

	sort(a,a+n);

	sort(b,b+n);

	printf("%d",max(a[n-1]-a[0],b[n-1]-b[0]));

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<algorithm>

#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

using namespace std;

typedef long long ll;

int N;

const int maxn=2e6+10;

ll a[maxn],b[maxn];



int main()

{

	ios;

	cin>>N;

	int cnt=0;

	for(int i=1;i<=N;i++)

	{

		ll x,y;

		cin>>x>>y;

		a[cnt]=x+y;

		b[cnt++]=x-y;

	}

	sort(a,a+cnt);

	sort(b,b+cnt);

	ll maxsum=max(a[cnt-1]-a[0],b[cnt-1]-b[0]);

	cout<<maxsum<<"\n";

	return 0;

 } 

// Optimized solution to the same problem (faster):
#include<algorithm>

#include<string>

#include<math.h>



using namespace std;



const int N = 200010;



int n,x,y;

int a[N],b[N];

int main(){

	scanf("%d",&n);

	for(int i=0;i<n;i++){

		scanf("%d%d",&x,&y);

		a[i]=x+y;

		b[i]=x-y;

	}

	sort(a,a+n);

	sort(b,b+n);

	printf("%d",max(a[n-1]-a[0],b[n-1]-b[0]));

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<math.h>

#include<algorithm>

typedef long long ll;



using namespace std;



ll n, a, b;

ll x[200005], y[200005], z[200005];



int main() {

	cin >> n;

	for (int i = 0; i < n; i++) {

		cin >> a >> b;

		x[i] = a + b;

		y[i] = a - b;

		z[i] = b - a;

	}

	sort(x, x + n); sort(y, y + n); sort(z, z + n);

	cout << max((x[n - 1] - x[0]), max((y[n - 1] - y[0]), (z[n - 1]-z[0])));

	return 0;

}

// Optimized solution to the same problem (faster):
#include<algorithm>

#include<string>

#include<math.h>



using namespace std;



const int N = 200010;



int n,x,y;

int a[N],b[N];

int main(){

	scanf("%d",&n);

	for(int i=0;i<n;i++){

		scanf("%d%d",&x,&y);

		a[i]=x+y;

		b[i]=x-y;

	}

	sort(a,a+n);

	sort(b,b+n);

	printf("%d",max(a[n-1]-a[0],b[n-1]-b[0]));

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#define PB push_back

#define MP make_pair

#define REP(i,n) for (int i=0;i<(n);i++)

#define FOR(i,a,b) for(int i=(a);i<(b);i++)

#define ALL(a) (a).begin(),(a).end()

using namespace std;

typedef pair<int,int> P;

typedef long long ll;

const int INF=1e9;

int dp[100100];

int main(){

  int m,n;

  cin>>m>>n;

  int c[550],e[550];

  vector<int>p(m);

  REP(i,100100)dp[i]=INF;

  REP(i,m)cin>>p[i];

  dp[0]=0;

  int sum=0;

  REP(i,n){

    cin>>c[i]>>e[i];

    for(int j=sum;j>=0;j--){

      dp[j+c[i]]=min(dp[j+c[i]],dp[j]+e[i]);

    }

    sum+=c[i];

    sum=min(sum,20000);

  }

  for(int i=sum;i>=0;i--){

    dp[i]=min(dp[i],dp[i+1]);

  }

  sort(ALL(p),greater<int>());

  sum=0;

  int ans=0;

  REP(i,m){

    sum+=p[i];

    ans=max(ans,sum-dp[i+1]);

  }

  cout<<ans<<endl;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

#define PB push_back

#define MP make_pair

#define REP(i,n) for (int i=0;i<(n);i++)

#define FOR(i,a,b) for(int i=(a);i<(b);i++)

#define ALL(a) (a).begin(),(a).end()

int INF=1e9;

int MOD=1000000007;

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

double EPS = 1e-10;

const int mod=1e9+7;

int dp[20001];

int sum[20001];

int N,M;

int C[500],E[500];

vector<int>P;

int main(){

	ios::sync_with_stdio(0);

	cin.tie(0);

	cin>>M>>N;

	P.resize(M);

	REP(i,M)cin>>P[i];

	sort(ALL(P),greater<int>());

	REP(i,M)sum[i+1]=sum[i]+P[i];

	REP(i,N)cin>>C[i]>>E[i];

	REP(i,20001)dp[i]=1e9;

	dp[0]=0;

	REP(i,N){

		for(int j=M;j>=0;j--){

			dp[j+C[i]]=min(dp[j+C[i]],dp[j]+E[i]);

		}

	}

	for(int i=20000;i>0;i--){

		dp[i-1]=min(dp[i],dp[i-1]);

	}

	int ans=0;

	REP(i,M+1)ans=max(ans,sum[i]-dp[i]);

	cout<<ans<<endl;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

int main()

{

    long long n,m,ans;

    scanf("%lld%lld",&n,&m);

    if(n > m/2)

    {

        printf("%lld\n",m/2);

    }

    else

    {

        ans = n;

        m = m - n*2;

        ans += m/4;

        printf("%lld\n",ans);

    }

    return 0;

}


// Optimized solution to the same problem (faster):
#include<stdio.h>



int main(void)

{

    long long n,m;

    long long S,L;

    long long i,k,j;

    scanf("%lld%lld",&n,&m);

    k=m-n-n;

    if(k>0)

    {

        m=m-n-n;

        m=m/4;

        S=n+m;

    }

    else if(k<0)

    {

        S=m/2;

    }

    printf("%lld",S);

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



#define MX 100050

#define INF 0x7f7f7f7f7f7f7f7fll

typedef long long ll;

struct edge {

	int v; ll w;

	edge(int v = 0, ll w = 0) : v(v), w(w) {}

	bool operator < (const edge& rhs) const { return w > rhs.w; }

};



vector<edge> g[MX];

ll d[MX];

bool vis[MX];



int main() {

	int n, m;

	scanf("%d%d", &n, &m);

	for(int i = 2; i <= n; i++) g[i].push_back(edge(i - 1, 0));

	while(m--) {

		int l, r, c;

		scanf("%d%d%d", &l, &r, &c);

		g[l].push_back(edge(r, c));

	}

	priority_queue<edge> pq;

	pq.push(edge(1, 0));

	for(int i = 2; i <= n; i++) d[i] = INF;

	

	while(pq.size()) {

		edge e = pq.top(); pq.pop();

		int u = e.v;

		if(vis[u]) continue;

		vis[u] = true;

		

		for(auto e : g[u])

			if(d[e.v] > d[u] + e.w) {

				d[e.v] = d[u] + e.w;

				pq.push(edge(e.v, d[e.v]));

			}

	}

	if(d[n] == INF) puts("-1");

	else printf("%lld\n", d[n]);

	return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;



const int N = 220000;



int L[N], R[N], id[N];

long long C[N], t[N];



void add(int u, long long w) {

	for (; u; u -= u & -u) t[u] = min(t[u], w);

}



long long get(int u) {

	long long ret = LLONG_MAX;

	for (; u < N; u += u & -u) ret = min(ret, t[u]);

	return ret;

}



int main() {

	ios::sync_with_stdio(0);

	cin.tie(0); cout.tie(0);

	int n, m; cin >> n >> m;

	for (int i = 0; i < m; i++) cin >> L[i] >> R[i] >> C[i];

	for (int i = 0; i < m; i++) id[i] = i;

	sort(id, id + m, [&](int u, int v) {

		if (L[u] != L[v]) return L[u] < L[v];

		return R[u] < R[v];

	});

	for (int i = 0; i < N; i++) t[i] = LLONG_MAX;

	add(1, 0);

	for (int i = 0; i < m; i++) {

		int u = id[i];

		int st = L[u], en = R[u]; long long w = C[u];

		long long now = get(st);

		if (now != LLONG_MAX) add(en, now + w);

	}

	long long ans = get(n);

	if (ans == LLONG_MAX) ans = -1;

	cout << ans << "\n";

	return 0;

}




// Fastest known solution for this problem: