akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)
const ll MOD = 1e9+7;

const int MAX_N = 200000;

ll fact[MAX_N+100];
ll frev[MAX_N+100];

ll rev(ll a, ll p){
    if(p == 0) return 1;
    ll tmp = rev(a, p/2);
    tmp = tmp * tmp % MOD;
    if(p % 2 == 1) tmp = tmp * a % MOD;
    return tmp;
}


void calc_fact(){
    fact[0] = frev[0] = 1;
    for(int i = 1; i <= MAX_N; i++){
        fact[i] = (fact[i-1] * i) % MOD;
        frev[i] = rev(fact[i], MOD-2);
    }
}


ll comb(int n, int k){
    if(n < 0 || k < 0 || n < k) return 0;
    if(n == 0 || k == 0) return 1;
    return fact[n] * frev[k] % MOD * frev[n-k] % MOD;
}


int A[100100];
int T[100100];
int main(){
    int n;
    cin >> n;
    int d;
    int x, y;
    int N = n+1;
    REP(i, n+1){
        int a;
        cin >> a;
        A[i] = a;
        T[a]++;
        if(T[a] == 2){
            y = i;
            d = a;
        }
    }
    REP(i,N){
        int a = A[i];
        if(d == a){
            x = i;
            break;
        }
    }
    //cout << x << endl;
    //cout << y << endl;
    
    fact[0] = frev[0] = 1;
    for(int i = 1; i <= MAX_N; i++){
        fact[i] = (fact[i-1] * i) % MOD;
        frev[i] = rev(fact[i], MOD-2);
    }

    for(int i = 0; i < n+1; i++){
        ll ans;
        int k = i+1;
        ans = comb(N, k);
        //ans -= comb(N-y-1, k-1);
        ans -= comb(N-(y-x)-1, k-1);
        if(ans < 0) ans += MOD;
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 5120
#include<bits/stdc++.h>
#define ll long long 
#define ld long double
#define pb push_back
#define vl vector
#define ff first
#define ss second
using namespace std;
int main()
{
    ll a,b,i,j,n,t,c,m;
    ll arr[3];
    for(i=0;i<3;i++) cin>>arr[i];
    sort(arr,arr+3);
    cout<<arr[0]+arr[1];
}

Measured memory_bytes: 3572
#include <cstdio>
#include <cstdlib>
#include <utility>
#include <typeinfo>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#define REP(i,n) for(int i=0;i<n;i++)
typedef long long ll;
using namespace std;
typedef vector<ll> vl;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;
typedef vector<string> vs;

int main() 
{
	ll n;
	cin>>n;
	int ans(0);
	
	if(n==1) printf("%d\n",1);
	else
	{
		while(true)
		{
			int amari;
			amari=n%3;
			n/=3;
			ans++;
			if((amari==0&&n==1)||n==0)
			{
				printf("%d\n",ans);
				break;
			}
			if(amari!=0)n++;
		}
	}
	return 0;
}

Measured memory_bytes: 1148
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define vi vector<int>
#define pb push_back
#define INF 999999999
//#define INF (1LL<<59)
 
class UF{
private:
    vector<int> par,rank,elm;
public:
    int groups;
    
    UF(int __size):par(__size) , rank(__size,0) , elm(__size,1) , groups(__size){
        for(int i=0;i<__size;i++)par[i]=i;
    }
    
    int elements(int n){
        return elm[find(n)];
    }
    
    int find(int x){
        if(par[x]==x) {
            return x;
        }else{
            return par[x]=find(par[x]);
        }
    }
    
    void unite(int x,int y){
        x=find(x);
        y=find(y);
        if(x==y) return;
        
        groups--;
        if(rank[x]<rank[y]){
            par[x]=y;
            elm[y]+=elm[x];
        }else{
            par[y]=x;
            elm[x]+=elm[y];
            if(rank[x]==rank[y])rank[x]++;
        }
    }
    
    bool isSame(int x,int y){
        return find(x)==find(y);
    }
};
 
#define MAX_N 1000
struct edge{int to,cost;};
vector<edge> G[MAX_N];
int kraskal(int n,vector<int> &list){
    int ret = 0;
    vector< pair< int,pii > > edges;
    
    rep(i,MAX_N){
        rep(j,G[i].size()){
            edges.pb( make_pair(G[i][j].cost,make_pair(i,G[i][j].to)) );
        }
    }
    
    sort(all(edges));
    
    UF uf(n);
    
    rep(i,edges.size()){
        pii e = edges[i].second;
        
        if(!uf.isSame(e.first,e.second)){
            uf.unite(e.first,e.second);
            ret+=edges[i].first;
            list.pb(edges[i].first);
        }
    }
    return ret;
}
 
 
 
int main(){
    int n,m;
    while(cin>>n>>m&&(n||m)){
        rep(i,MAX_N)G[i].clear();
        rep(i,m){
            int s,t,c;
            cin>>s>>t>>c;
            s--,t--;
            G[s].pb(edge{t,c});
            G[t].pb(edge{s,c});
        }
        vector<int> list;
        kraskal(n,list);
        sort(all(list));
        cout<<list[list.size()/2]<<endl;
    }
}

Measured memory_bytes: 3680
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (ll i = a; i < b; i++)
#define REP(i,b) FOR(i,0,b)
#define RFOR(i,a,b) for (ll i = a-1; i >= b; i--)
#define RREP(i,a) RFOR(i,a,0)
#define REPALL(i,x) for (ll i = 0; i < x.size(); i++)
#define RREPALL(i,x) for (ll i = x.size()-1; i >= 0; i--)
#define REPITR(itr,x) for (auto itr = (x).begin(); itr != (x).end(); itr++)
#define ALL(x) (x).begin(), (x).end()
#define SORT(x) sort(ALL(x))
#define MIN_ELEMENT(x) min_element(ALL(x))
#define MAX_ELEMENT(x) max_element(ALL(x))
#define COUNT(x,num) count(ALL(x), num)
#define MEMSET(x,val) memset(x, val, sizeof(x))
#define CHMAX(a,b) a = max(a,b)
#define CHMIN(a,b) a = min(a,b)
#define debug(x) cerr<<__LINE__<<": "<<(#x)<<" = "<<(x)<<endl;
void YES(bool flag) {cout<<(flag ? "YES" : "NO")<<endl;}
void Yes(bool flag) {cout<<(flag ? "Yes" : "No")<<endl;}
void yes(bool flag) {cout<<(flag ? "yes" : "no")<<endl;}
#define e1 first
#define e2 second
#define newline putchar('\n')
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef vector<ll> VLL;
typedef vector<vector<ll>> VVLL;
const int INF = 1e7;
const ll MOD = 1e9 + 7;
const double pi = 3.141592653589793;
const VI dx = {1, 0, -1, 0};
const VI dy = {0, 1, 0, -1};

int main()
{
    int n, x, y;
    cin>>n>>x>>y;
    x--; y--;
    VI ans(n-1, 0);
    REP(i,n) {
        FOR(j,i+1,n) {
            ll tmp = j - i;
            CHMIN(tmp, abs(i-x) + 1 + abs(j-y));
            CHMIN(tmp, abs(i-y) + 1 + abs(j-x));
            ans[tmp-1]++;
        }
    }

    REP(i,n-1)
        cout<<ans[i]<<endl;

    return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using ll = long long;
using vi = vector<int>;

int main(){
    string s;
    cin>>s;
    
    vi c(2,0);
    
    rep(i,s.size()){
        c[s[i]-'0']++;
    }
    cout << min(c[0],c[1])*2<<endl;
    return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<string>
#include<vector>
#include<numeric>
#include<math.h>
#include<algorithm>
#include<iomanip>
#include<list>
#include<bitset>
#include<sstream>
using namespace std;

int main() {

	int n;
	cin >> n;

	vector<string> S(n, "");

	string alp = "abcdefghijklmnopqrstuvwxyz";

	for (int i = 0; i < n; i++) {
		cin >> S[i];
		sort(S[i].begin(), S[i].end());
	}

	vector<vector<int>> v(n, vector<int>(26, 0));

	for (int i = alp.length() - 1; i >= 0; i--) {
		for (int j = 0; j < n; j++) {
			while (S[j].back() == alp[i]) {
				v[j][i] += 1;
				S[j].pop_back();
			}
		}
	}

	vector<int> d(26, 0);

	for (int i = 0; i < 26; i++) {
		d[i] = v[0][i];
	}

	for (int i = 1; i < v.size(); i++) {
		for (int j = 0; j < 26; j++) {
			d[j] = min(d[j], v[i][j]);
		}
	}

	string ans = "";

	for (int i = 0; i < 26; i++) {
		for (int j = 0; j < d[i]; j++) {
			ans += alp[i];
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3576
#include <iostream>
#include <vector>
#define N_MAX 50
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
ll N,M,A,B,C,T,d[N_MAX];

mat cal(mat mA,mat mB){
  mat res=mat(N,vec(N,0));
  for(int i=0;i<N;i++)
    for(int j=0;j<N;j++)
      for(int k=0;k<N;k++) res[i][j]+=mA[i][k]*mB[k][j]%M;
  return res;
}

mat mod_power(mat mA){
  mat res=mat(N,vec(N,0));
  for(int i=0;i<N;i++)
    for(int j=0;j<N;j++) res[i][j]=(i==j);
  for(int i=0;i<=30;i++){
    if(T&(1LL<<i)) res=cal(res,mA);
    mA=cal(mA,mA);
  }
  return res;
}

int main(){
  while(1){
    cin>>N>>M>>A>>B>>C>>T;
    if(!N&&!M&&!A&&!B&&!C&&!T) break;
    mat mA=mat(N,vec(N,0));
    for(int i=0;i<N;i++) cin>>d[i];
    for(int i=0;i<N;i++)
      for(int j=0;j<N;j++){
	if(i==j) mA[i][j]=B;
	if(i+1==j) mA[i][j]=C;
	if(i==j+1) mA[i][j]=A;
      }
    mA=mod_power(mA);
    mat mB=mat(N,vec(N,0));
    for(int i=0;i<N;i++) mB[i][0]=d[i];
    mA=cal(mA,mB);
    for(int i=0;i<N;i++){
      cout<<mA[i][0]%M;
      if(i!=N-1) cout<<' ';
    }
    cout<<endl;
  }
  return 0;
}

Measured memory_bytes: 1352
#include <bits/stdc++.h>
using namespace std;

long long n, k;
vector<pair<long long, long long>> v;

int main() {
  cin >> n >> k;
  for (int i = 0; i < n; ++i) {
    pair<long long, long long> p;
    cin >> p.first >> p.second;
    v.push_back(p);
  }

  vector<long long> mask;
  long long a = 0;
  for (long long j = 0; j < 30; ++j) {
    if (!((1 << j) & k))
      a += (1 << j);
  }
  mask.push_back(a);
  for (long long i = 0; i < 30; ++i) {
    if ((1 << i) & k) {
      long long a = (1 << i);
      for (long long j = i + 1; j < 30; ++j) {
        if (!((1 << j) & k))
          a += (1 << j);
      }
      mask.push_back(a);
    }
  }

  long long ans = 0;
  for (int i = 0; i < mask.size(); ++i) {
    long long cnt = 0;
    for (int j = 0; j < n; ++j) {
      if (v[j].first & mask[i])
        continue;
      cnt += v[j].second;
    }

    ans = max(ans, cnt);
  }

  cout << ans << endl;
}


Measured memory_bytes: 2420
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int main(){
    int n,k;
    cin>>n>>k;
    ll h[n];
    rep(i,n)cin>>h[i];
    sort(h,h+n);
    ll ret=longinf;
    rep(i,n-k+1)ret=min(ret,h[i+k-1]-h[i]);
    cout<<ret<<endl;
    return 0;
}

Measured memory_bytes: 1024
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define shandom_ruffle random_shuffle

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);	
	
	int N; cin >> N;
	int data[N]; F0R(i, N) cin >> data[i];
	int ans[N+1]; int count = 0;
	FORd(i, 1, N+1) {
		int sum = 0;
		for (int j = i*2; j <= N; j += i) {
			sum += ans[j];
		}
		if (sum % 2 == data[i-1]) {
			ans[i] = 0;
			//cout << i << " 0" << endl;
		} else {
			ans[i] = 1;
			count++;
			//cout << i << " 1" << endl;
		}
	}
	
	cout << count << endl;
	FOR(i, 1, N+1) {
		if (ans[i] == 1) cout << i << " ";
	}
	
	cout << endl;
	

    return 0;
}

// read the question correctly (ll vs int)
// template by bqi343


Measured memory_bytes: 2560
#include <bits/stdc++.h>

#define ll long long
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define vll vector<ll>
#define vi vector<int>
#define pi pair<int,int>

using namespace std;

const string str = "ABC";

pi parse(string query)
{
  pi ret;
  if (query=="AB") ret=pi(0,1);
  if (query=="AC") ret=pi(0,2);
  if (query=="BC") ret=pi(1,2);
  return ret;
}

int main()
{
  int N; cin>>N;
  vll v(3);
  rep(i,3) cin>>v[i];
  vector<string> s(N);
  rep(i,N) cin>>s[i];
  if ((v[0]==0&&v[1]==0&&v[2]==0)){
    cout<<"No"<<endl;
    return 0;
  }
  vi ans(N);
  rep(i,N){
    int x,y;
   	tie(x,y) = parse(s[i]);
    if (v[x]==0&&v[y]==0){
      cout<<"No"<<endl;
      return 0;
    }
    if (i<N-1 && v[x]==1&&v[y]==1){
      int nx,ny;
      tie(nx,ny) = parse(s[i+1]);
      if (nx==x||ny==x){
        ans[i] = x;
        v[x]++; v[y]--;
      }else{
        ans[i] = y;
        v[x]--; v[y]++;
      }
    }else{
      if (v[x]>v[y]){
        ans[i] = y;
        v[x]--; v[y]++;
      }else{
        ans[i] = x;
        v[x]++; v[y]--;
      }
    }
  }
  cout<<"Yes"<<endl;
  rep(i,N) cout<<str[ans[i]]<<endl;
  return 0;
}

Measured memory_bytes: 6644
n = int(input())

W = [input() for _ in range(n)]

#print(W)

dict = {}

for i in range(n):
    if W[i] in dict:
        print("No")
        exit()
    else:
        dict[W[i]] = 1 
header = (list(W[0]))[0]
footer = (list(W[0]))[len(list(W[0]))-1]
#print(header)
#print(footer)
for i in range(1,n):
    header = (list(W[i]))[0]
    if footer != header:
        print("No")
        exit()
    footer = (list(W[i]))[len(list(W[i]))-1]

print("Yes")

    


Measured memory_bytes: 3192
// E.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>

using namespace std;

int main(int argc, char* argv[]) {
#ifdef _MSC_VER
	while (true)
#endif
	{
		string s;
		int len, k = -1;
		cin >> s >> k;
		if (k <= 0) return 0;
		len = (int)s.length();
		vector<int> r(len), w(len);
		for (int i = 0; i < len; ++i) {
			r[i] = s[i] - '0';
		}
		int ans = 0;
		switch (k) {
		case 1:
			for (int i = 0; i < len; ++i) {
				for (int a = 1; a <= 9; ++a) {
					if (i == 0 && a > r[0]) break;
					w[i] = a;
					if (w <= r) {
						++ans;
					}
					w[i] = 0;
				}
			}
			break;
		case 2:
			for (int i = 0; i < len; ++i) {
				for (int a = 1; a <= 9; ++a) {
					if (i == 0 && a > r[0]) break;
					bool x = i == 0 && a == r[0];
					if (x) w[0] = a;
					for (int j = i + 1; j < len; ++j) {
						for (int b = 1; b <= 9; ++b) {
							if (x) w[j] = b;
							if (w <= r) {
								++ans;
							}
						}
						if (x) w[j] = 0;
					}
				}
			}
			break;
		case 3:
			for (int i = 0; i < len; ++i) {
				for (int a = 1; a <= 9; ++a) {
					if (i == 0 && a > r[0]) break;
					bool x = i == 0 && a == r[0];
					if (x) w[0] = a;
					for (int j = i + 1; j < len; ++j) {
						for (int b = 1; b <= 9; ++b) {
							if (x) w[j] = b;
							for (int k = j + 1; k < len; ++k) {
								for (int c = 1; c <= 9; ++c) {
									if (x) {
										w[k] = c;
										if (w <= r) {
											++ans;
										}
									} else {
										++ans;
									}
								}
								if (x) w[k] = 0;
							}
						}
						if (x) w[j] = 0;
					}
				}
			}
			break;
		}
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int main(){
	int N, i;
	scanf("%d", &N);
	vector<double> v(N);
	for(i = 0; i < N; i++){
		scanf("%lf", &v[i]);
	}
	sort(v.begin(), v.end());
	double ans = v[0];
	for(i = 1; i < N; i++){
		ans = (ans + v[i]) / 2;
	}
	printf("%.10lf\n", ans);
	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define int long long
int mod=1e9+7;

signed main(){
  int n;
  cin>>n;
  vector<int> a(n);
  for(int i=0;i<n;i++)cin>>a[i];
  vector<int> b=a;
  sort(b.begin(),b.end());
  map<int,int> c;
  for(int i=0;i<n;i++){
    c[b[i]]=i;
  }
  vector<int> ans(n);
  for(int i=0;i<n;i++)ans[i]=c[a[i]];
  int x=0;
  for(int i=0;i<n;i+=2){
    if(ans[i]%2==1)x++;
  }
  cout<<x<<endl;
}


Measured memory_bytes: 8832
#include<iostream>
#include <vector>

using namespace std;

long int n, m, q;
vector<int> A;

int add(int a) {
	A[a]++;
	//cout <<"add" <<A[0] << A[1] << A[2] << endl;
	if (A[a] > m) {
		A[a] = add(a - 1);
	}
	return A[a];
}

int check() {
	for (int i = 0; i < A.size(); i++) {
		if (A[i] =! m) {
			return 0;
		}
	}
	return 1;
}


int main() {
	
	cin >> n >> m >> q;
	int aa, bb, cc, dd;
	vector<int> a, b, c, d;
	
	for (int i = 0; i < q; i++) {
		cin >> aa >> bb >> cc >> dd;
		a.push_back(aa);
		b.push_back(bb);
		c.push_back(cc);
		d.push_back(dd);
	}
	for (int i = 0; i < n; i++) {
		A.push_back(1);
	}
	int ans1 = 0;
	int ans2 = 0;
	while (1) {

		for (int i = 0; i < q; i++) {
			if (A[b[i] - 1] - A[a[i] - 1] == c[i]) {
				ans1 += d[i];
			}
		}
		if (ans2 < ans1) ans2 = ans1;

		if (A[0] == m) {
			break;
		}
		add(A.size() - 1);
		//cout << A[0] << A[1] << A[2] << endl;
		ans1 = 0;
	}
	cout << ans2 << endl;
	return 0;
}

Measured memory_bytes: 3628
#include <functional>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <iomanip>
#include <utility>
#include <cstdlib>
#include <sstream>
#include <bitset>
#include <vector>
#include <cstdio>
#include <ctime>
#include <queue>
#include <deque>
#include <cmath>
#include <stack>
#include <list>
#include <map>
#include <set>

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;

#define dump(x)  cerr << #x << " = " << (x) << endl
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back


int main() {
    int q1,b,c1,c2,q2;
    while(cin>>q1){
        if(q1==0)break;
        cin>>b>>c1>>c2>>q2;
        
        int x=-1,y=-1;
        for(int i=q2;i>0;i--){
            int niku=( b-(i*c1) )/c2;
            if(niku+i>=q1 && i*c1+niku*c2<=b &&niku>=0){
                x=i;y=niku;
                break;
            }
        }
        
        if( x==-1 && y==-1 )cout<<"NA"<<endl;
        else cout<<x<<" "<<y<<endl;
    }

    return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,(n)-1,0)
#define all(v) v.begin(), v.end()
#define endk '\n'
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;
const ll mod2 = 998244353;
const ld eps = 1e-10;
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b){if(a>b) a=b;}
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b){if(a<b) a=b;}

#define MAX_N 2000005
ll inv[MAX_N], fac[MAX_N], finv[MAX_N];
void make() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for(int i=2; i<MAX_N; i++) {
    inv[i] = mod - inv[mod%i] * (mod/i) % mod;
    fac[i] = fac[i-1] * (ll)i % mod;
    finv[i] = finv[i-1] * inv[i] % mod;
  }
}
ll perm(ll n, ll r) {
  if(n < 0)       return 0;
  else if(n < r)  return 0;
  else            return (fac[n] * finv[n-r]) % mod;
}
ll comb(ll n, ll r) {
  ll ans = 1;
  ans = perm(n, r);
  ans = (ans * finv[r]) % mod;
  return ans;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  make();
  int s; cin >> s;
  ll ans = 0;
  for(int i=1; i<s; i++) {
    ll rem = s-3*i;
    if(rem < 0) break;
    (ans += comb(rem+i-1, i-1)) %= mod;
  }
  cout << ans << endk;
  return 0;
}


Measured memory_bytes: 50508
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)
using vi = vector<int64_t>;
using vvi = vector<vi>;
int64_t INF = 1000000007;

int main() {
    // fasten cin
    cin.tie(0);
    ios::sync_with_stdio(false);
    // implement
    vi c(9);
    rep(i,9) cin >> c.at(i);
    int64_t a1 = 0;
    int64_t a2 = c.at(3) - c.at(0);
    int64_t a3 = c.at(6) - c.at(0);
    int64_t b1 = c.at(0);
    int64_t b2 = c.at(1);
    int64_t b3 = c.at(2);
    if(
        c.at(0) == a1 + b1 &&
        c.at(1) == a1 + b2 &&
        c.at(2) == a1 + b3 &&
        c.at(3) == a2 + b1 &&
        c.at(4) == a2 + b2 &&
        c.at(5) == a2 + b3 &&
        c.at(6) == a3 + b1 &&
        c.at(7) == a3 + b2 &&
        c.at(8) == a3 + b3
    ){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,k,a[100010],ans=0;
int b[100010],c[100010],cnt=0;

int main()
{
	cin>>n>>k;
	b[0]=0;
	for(int i=1;i<=n;i++)
	{
		char ch;
		cin>>ch;
		if(ch=='1') a[i]=1;
		else a[i]=0;
	}
	int ch=2;
	for(int i=1;i<=n;i++)
	{
		if(a[i]!=ch) ch=a[i],c[++cnt]=ch,b[cnt]++;
		else b[cnt]++;
	}
	if(c[1]==1)
	{
		for(int j=1;j<=cnt;j+=2)
		{
			int s=0;
			for(int i=j;i<=min(j+k*2,cnt);i++) s+=b[i];
//			if(c[min(j+k*2,cnt)]==0) s-=b[min(j+k*2,cnt)];
			ans=max(ans,s);
		}
		if(c[cnt]==0)
		{
			int s=0;
			for(int i=cnt;i>=max(1,cnt-k*2+1);i--) s+=b[i];
			ans=max(ans,s);
		}
	}
	else
	{
		for(int j=2;j<=cnt;j+=2)
		{
			int s=0;
			for(int i=max(1,j-2);i<=min(cnt,j+k*2-2);i++) s+=b[i];
//			if(c[min(cnt,j+k*2-2)]==0) s-=b[min(cnt,j+k*2-2)];
			ans=max(ans,s);
		}
		if(c[cnt]==0)
		{
			int s=0;
			for(int i=cnt;i>=max(1,cnt-k*2+1);i--) s+=b[i];
			ans=max(ans,s);
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1408
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <tuple>

using namespace std;



int main(){
    long long X,t;
    cin >> X >> t;

    if(X-t > 0){
        cout << X-t << endl;
    }else{
        cout << 0 << endl;
    }
    return 0;
}


Measured memory_bytes: 256
N = int(input())
H = list(map(int,input().split()))
n = H[N-1]
state = "Yes"
for i in range(N-1,0,-1):
    m = H[i-1]
    if n < m:
        m -= 1
        if n < m:
            state = "No"
            break
    n = m
print(state)

Measured memory_bytes: 14396
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Dice dice1 = new Dice(sc.nextInt(), sc.nextInt(), sc.nextInt(), sc.nextInt(), sc.nextInt(), sc.nextInt());
		Dice dice2 = new Dice(sc.nextInt(), sc.nextInt(), sc.nextInt(), sc.nextInt(), sc.nextInt(), sc.nextInt());
		boolean a = solve(dice1, dice2, 0);
		System.out.println((a) ? "Yes" : "No");
	}

	public static boolean solve(Dice f, Dice dice, int count) {

		if (dice.Top == f.Top && dice.S == f.S && dice.Bottom == f.Bottom && dice.E == f.E && dice.N == f.N
				&& dice.W == f.W)

			return true;

		if (count == 6)

			return false;

		Dice tmp = new Dice(dice.Top, dice.S, dice.E, dice.W, dice.N, dice.Bottom);
		tmp.TurnN();

		if (solve(f, tmp, count + 1)) {

			return true;

		}

		tmp = new Dice(dice.Top, dice.S, dice.E, dice.W, dice.N, dice.Bottom);

		if (solve(f, tmp, count + 1)) {

			return true;

		}

		tmp = new Dice(dice.Top, dice.S, dice.E, dice.W, dice.N, dice.Bottom);
		tmp.TurnE();
		tmp = new Dice(dice.Top, dice.S, dice.E, dice.W, dice.N, dice.Bottom);
		tmp.TurnW();

		if (solve(f, tmp, count + 1)) {
			return true;
		}

		return false;
	}

}

class Dice {
	int Top;
	int Bottom;
	int N;
	int S;
	int W;
	int E;

	Dice(int a, int b, int c, int d, int e, int f) {
		Top = a;
		S = b;
		E = c;
		W = d;
		N = e;
		Bottom = f;
	}

	public void TurnN() {
		int tmp = Top;
		Top = S;
		S = Bottom;
		Bottom = N;
		N = tmp;
	}

	public void TurnW() {
		int tmp = Top;
		Top = E;
		E = Bottom;
		Bottom = W;
		W = tmp;
	}

	public void TurnE() {
		int tmp = Top;
		Top = W;
		W = Bottom;
		Bottom = E;
		E = tmp;
	}

	public void TurnS() {
		int tmp = Top;
		Top = N;
		N = Bottom;
		Bottom = S;
		S = tmp;
	}
}



Measured memory_bytes: 26408
#include <bits/stdc++.h>

#define f first
#define s second
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int N = (int)2e5 + 123, inf = 1e9, mod = 1e9 + 7;
const ll INF = 1e18;

int n, m, x, y, pre[110][110], dp[110][110][110], tmp[110][110][110];
string s[110];
int get(int xa, int ya, int xb, int yb){
	int res = pre[xb][yb];     
	if(xa)
		res -= pre[xa - 1][yb];
	if(ya)
		res -= pre[xb][ya - 1];
	if(xa && ya)
		res += pre[xa - 1][ya - 1];
	return res;
}
int calc(int xa, int ya, int xb, int yb, int type){
	if(type == 0 && xb - x < xa)
		return get(xa - 1, max(ya, yb - y), xa - 1, min(yb, m - 1 - y + ya));	
	if(type == 2 && n - 1 - xb > x - xa)                                     
		return get(xb + 1, max(ya, yb - y), xb + 1, min(yb, m - 1 - y + ya));
	if(type == 1 && yb - y < ya)                                             
		return get(max(xa, xb - x), ya - 1, min(xb, n - 1 - x + xa), ya - 1);
	if(type == 3 && m - 1 - yb > y - ya) 
		return get(max(xa, xb - x), yb + 1, min(xb, n - 1 - x + xa), yb + 1);
	return 0;
}


int main()
{                         
	cin >> n >> m;
	for(int i = 0; i < n; i++)	
		cin >> s[i];
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++){
			if(s[i][j] == 'E')
				x = i, y = j;	
			if(s[i][j] == 'o')
				pre[i][j]++;               
			if(i)
				pre[i][j] += pre[i - 1][j];
			if(j)
				pre[i][j] += pre[i][j - 1];
			if(i && j)
				pre[i][j] -= pre[i - 1][j - 1];
		}
	
	for(int i = n + m; i >= 0; i--){
		for(int xa = 0; xa <= x; xa++)
			for(int ya = 0; ya <= y; ya++)
				for(int xb = x; xb < n; xb++){
					int yb = y + (i - (x - xa) - (y - ya) - (xb - x));
					if(y > yb || yb >= m)
						continue;
					if(0 < xa)                             
						dp[xa][ya][xb] = max(dp[xa][ya][xb], tmp[xa - 1][ya][xb] + calc(xa, ya, xb, yb, 0));
					if(0 < ya)
						dp[xa][ya][xb] = max(dp[xa][ya][xb], tmp[xa][ya - 1][xb] + calc(xa, ya, xb, yb, 1));
					if(xb + 1 < n)
						dp[xa][ya][xb] = max(dp[xa][ya][xb], tmp[xa][ya][xb + 1] + calc(xa, ya, xb, yb, 2));
					if(yb + 1 < m)
						dp[xa][ya][xb] = max(dp[xa][ya][xb], tmp[xa][ya][xb] + calc(xa, ya, xb, yb, 3));	
				}                                  
		for(int xa = 0; xa <= x; xa++)
			for(int ya = 0; ya <= y; ya++)
				for(int xb = x; xb < n; xb++)
					tmp[xa][ya][xb] = dp[xa][ya][xb], dp[xa][ya][xb] = 0;
	}
	cout << tmp[x][y][x];
	return 0;
}


Measured memory_bytes: 10496
using System;

namespace _0168
{
    class Program
    {
        static void Main(string[] args)
        {
            long[] syurui = new long[30];
            syurui[0] = 1;
            syurui[1] = 2;
            syurui[2] = 4;
            for (int i = 3; i < 30; i++)
            {
                syurui[i] = syurui[i - 1] + syurui[i - 2] + syurui[i - 3];
            }
            while (true)
            {
                int N = int.Parse(Console.ReadLine());
                if (N == 0)
                {
                    break;
                }
                Console.WriteLine((syurui[N - 1] / 3650) + 1);
            }
        }
    }
}

Measured memory_bytes: 9080
#include <bits/stdc++.h>
#define REP(i,n) for(int i = 0; i < n; i++)
#define REPR(i,n) for(int i = n; i >= 0; i--)
#define FOR(i,m, n) for(int i = m-1; i < n; i++)
#define INF 2000000000
#define ALL(v) v.begin(), v.end()
#define chmax(x,y) (x = max(x,y))
#define chmin(x,y) (x = min(x,y))
#define FILL2D(A,c) fill(A[0], A[0] +sizeof(A)/sizeof(**A),c)
#define FILL3D(A,c) fill(A[0][0], A[0][0] +sizeof(A)/sizeof(***A),c)
//vector<vector<要素の型>> 変数名(要素数1, vector<要素の型>(要素数2, 初期値))
//vector<intなど> 変数名(要素数,初期値)
using namespace std;
typedef long long ll;
//gcd,lcmセット
ll gcd(ll a, ll b){
   if (a%b == 0) return b;
   else return gcd(b, a%b);
}
ll lcm(ll a, ll b){	
   return a*b/gcd(a, b);
}
bool isPrime(ll x){
    int i;
    if(x < 2)return false;
    else if(x == 2) return true;
    if(x%2 == 0) return false;
    for(i = 3; i*i <= x; i += 2) if(x%i == 0) return false;
    return true;
}
//dfsではvector<vector<int>> g(n);で◎
int main(){
    int n;
    cin>>n;
    cout<<(n+1)/2<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

//#define int long long

#define upper(n,m) (n+m-1)/m
#define rounding(n) (int)((double)n+0.5)

#define REP(i,n) for(int i=0;i<(n);i++)
#define REAP(i,a,n) for(int i=(a);i<(n);i++)
#define ALL(a) a.begin(),a.end()

#define coutALL(i,a) {int i=0;for(int e:a) cout<<(i++?" ":"")<<e; cout<<endl;}
#define coutYN(a) cout<<(a?"Yes":"No")<<endl;
#define coutyn(a) cout<<(a?"yes":"no")<<endl;

#define deb cout<<"debug"<<endl
#define debn(n) cout<<"debug: "<<n<<endl

const int INF=INT_MAX;
const int MOD=(int)1e9+7;
const double EPS=1e-12;
//const int dx[]={0,1,0,-1},dy[]={-1,0,1,0};
const int dx[]={-1,-1,-1,0,1,1,1,0},dy[]={-1,0,1,1,1,0,-1,-1};

using namespace std;

typedef pair<int,int> P;
typedef long long LL;

signed main(){

  ios::sync_with_stdio(false);

  int n;
  cin>>n;

  vector <int> a(n);
  REP(i,n) cin>>a[i];

  int x=a[n-1];
  int i=-1;

  REP(j,n-1){

    if(a[j]<=x){

      i++;
      swap(a[i],a[j]);

    }

  }

  swap(a[i+1],a[n-1]);

  int j=0;
  for(int e:a){

    if(j++) cout<<" ";
    if(j==i+2) cout<<"["<<e<<"]";
    else cout<<e;

  }

  cout<<endl;

  return 0;

}


Measured memory_bytes: 3184
#include <bits/stdc++.h>
using namespace std;

int main(){
	int n;
	cin >> n;
	vector<int> vec;
	int a;
	for(int i=0;i<n;i++){
		cin >> a;
		if(i%2==0){
			vec.push_back(a);
		}else{
			vec.insert(vec.begin(),a);
		}
	}
	if(n%2==1){
		reverse(vec.begin(),vec.end());
	}
	for(int i=0;i<n;i++){
		cout << vec[i] << " ";
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 3060
n = int(input())
plan_list = list()
#最初に0,0の座標を定義しなさい
plan_list.append([0,0,0])

for i in range(n):
    plan_list.append(list(map(int,input().split())))
    
for i in range(n):
    t_margin = abs(plan_list[i+1][0] - plan_list[i][0])
    x_margin = abs(plan_list[i+1][1] - plan_list[i][1])
    y_margin = abs(plan_list[i+1][2] - plan_list[i][2])
    xy_margin = x_margin + y_margin
    if t_margin < xy_margin or xy_margin % 2 != t_margin % 2:
        print("No")
        break
else:
    print("Yes")

Measured memory_bytes: 27300
n = int(input())
t, a = map(int, input().split())
h = list(map(int, input().split()))
a1 = []
a2 = []
for i in range(n):
    tt = abs((t - h[i]*0.006) - a)
    a1.append(tt)
    a2.append(i+1)
ans = {}
ans.update(zip(a1, a2))
small = sorted(a1, reverse=False)[0]
print(ans[small])


Measured memory_bytes: 9312
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <numeric>
#include <cstdint>
#include <iomanip>
#include <set>
#include <map>
#include <unordered_map>
using ll = long long;
#define fast_io(); std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);

int main(){
    std::vector<int> a(5);
    int last=0, buf=10;
    for(int i=0; i<5; i++){
        std::cin >> a[i];
        if(a[i]%10<buf && a[i]%10!=0){
            buf = a[i]%10;
            last = i;
        }
    }

    int ans = 0;
    for(int i=0; i<5; i++){
        if(i==last){
            ans += a[i];
        }else{
            if(a[i]%10){
                ans += a[i] + 10 - a[i]%10;
            }else{
                ans += a[i];
            }
        }
    }

    std::cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 3596
n = gets.chomp.to_i
h = gets.chomp.split.map(&:to_i)

dp = Array.new(n, Float::INFINITY)

dp[0] = 0

for i in 0..n-2
  dp[i+1] = [dp[i+1], dp[i] + (h[i+1] - h[i]).abs].min
  dp[i+2] = [dp[i+2], dp[i] + (h[i+2] - h[i]).abs].min if i < n - 2
end

puts dp.last


Measured memory_bytes: 11780
#include <iostream>
#include<bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
ll n,m,k,a[100000],b,c,ans,fa[100001],ra[100001],L;
ll find(ll x){
    if(x==fa[x])return x;
    return fa[x]=find(fa[x]);
}
void uni(ll x,ll y){
    x=find(x),y=find(y);
    if(x==y)return ;
    if(ra[x]<ra[y])swap(x,y);
    fa[y]=x;
    if(ra[x]==ra[y])ra[x]++;
    return ;
}
int main(void){
    for(int i=0;i<100001;i++)fa[i]=i;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<m;i++){
        cin>>b>>c;
        uni(b,c);
    }
    for(int i=0;i<n;i++){
        if(find(i+1)==find(a[i]))ans++;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 5748
#include <iostream>
using namespace std;

int main(){
    int a,b,c;
    int d;
    cin >>a >>b >> c;
    
    d = 100*a + 10*b + c;
    
    if(d%4==0){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
r = input().split()
n = int(r[0])
nin = []
nin.append(int(r[1]))
nin.append(int(r[2]))

nmax = min(nin)
nmin = n - min(n, (n - nin[0]) + (n - nin[1]))
print(str(nmax) + " " + str(nmin))

Measured memory_bytes: 3060
import java.util.Scanner;
class Main
{
    public static void main(String args[])
    {
    Scanner sc=new Scanner(System.in);
    int a=sc.nextInt();
    int b=sc.nextInt();

        if(a<=9 && b<=9){
            System.out.println(a*b);
        }
        else{
            System.out.println(-1);
        }
    }
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;

int main()
{

        string s;
        cin >> s;
        for (int i = 0; i < 3; ++i) {
                if (s[i] == '7') {
                        cout << "Yes" << endl;
                        exit(0);
                }
        }
        cout << "No" << endl;


}


Measured memory_bytes: 3596
#include <bits/stdc++.h>

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

typedef long long ll;
using namespace std;
int mod = 1000000007;

int input[4];

bool elem(int n){
    if(input[0] == n || input[1] == n || input[2] == n || input[3] == n) return true;
    else return false;
}

int main(void){
    cin >> input[0] >> input[1] >> input[2] >> input[3];
    if(elem(1) & elem(9) & elem(7) & elem(4)) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 256
n=int(input())
S=list(input())
dp=[[0]*(n+1) for i in range(n+1)]#i文字目まで、j文字目までの長さ
for i in range(1,n):
  for j in range(i+1,n+1):
    if S[i-1]==S[j-1]:
      if j-i<dp[i-1][j-1]+1:
        dp[i][j]=dp[i-1][j-1]
      else:
        dp[i][j]=dp[i-1][j-1]+1
ans=0
for i in range(n+1):
  for j in range(n+1):
    if dp[i][j]>ans:
      ans=dp[i][j]
print(ans)

Measured memory_bytes: 230536
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <utility>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
#define all(c) (c).begin(), (c).end()
#define loop(i,a,b) for(ll i=a; i<ll(b); i++)
#define rep(i,b) loop(i,0,b)
#define each(e,c) for(auto&e:c)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define lb lower_bound
#define ub upper_bound
#ifdef DEBUG
#define dump(...) (cerr<<#__VA_ARGS__<<" = "<<(DUMP(),__VA_ARGS__).str()<<" ["<<__LINE__<<"]"<<endl)
struct DUMP:ostringstream{template<class T>DUMP &operator,(const T&t){if(this->tellp())*this<<", ";*this<<t;return *this;}};
#else
#define dump(...)
#endif
template<class T> ostream& operator<<(ostream& os, vector<T> const& v){
    rep(i,v.size()) os << v[i] << (i+1==v.size()?"":" ");
    return os;
}

int main(){
    string s;
    while(cin >> s){
        string ans;
        rep(i,s.size()){
            char c = s[i];
            if(c=='A'){
                if(ans.size()==0 || ans.back()=='Z') ans += c;
            }
            if(c=='Z'){
                if(ans.size()!=0 && ans.back()=='A') ans += c;
            }
        }
        if(ans.back()=='A') ans.erase(ans.begin()+ans.size()-1);
        if(ans.empty()) ans = "-1";
        cout << ans << endl;
    }
}

Measured memory_bytes: 1180
#include<bits/stdc++.h>
#define rep(i, n) for (int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
 
int main(void){
    int n;
    cin>>n;
    vector<string> v(n);
    int ans=0;
    rep(i, n){
        cin>>v[i];
        rep(j, v[i].size()-1){
            if(v[i][j] =='A' && v[i][j+1] =='B') ans++;
        }
    }
    int ba=0;
    int b=0;
    int a=0;
    rep(i, n){
        int l = v[i].size();
        if(v[i][0] == 'B' && v[i][l-1] == 'A'){
            ba++;
        }
        else if(v[i][0]=='B') b++;
        else if(v[i][l-1]=='A') a++;
    }
    ans+=max(0, ba-1);
    if(a>0 && ba!=0) {
        ans++;
        --a;
    }
    if(b>0 && ba!=0){
        ans++;
        --b;
    }
    ans+=min(a, b);
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 768
#include<stdio.h>
int main (){
  int i,j,a,b;
  scanf("%d%d",&i,&j);
    if(i>j){
      printf("a > b\n");
    }
    else if(i<j){
      printf("a < b\n");
    }
    else{
      printf("a == b\n");
    }
  return 0;
}

Measured memory_bytes: 2664
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <fstream>
#include <set>
#include <utility>
#include <algorithm>
#include <queue>
#define rep(i,p,n) for(int i=(int)p;i<(int)n;i++)
#define rrep(i,p,n) for(int i=(int)p;i>=(int)n;i--)
#define lli long long int
#define vi vector<int> 

using namespace std;

void p(int x) {
	cout << x << endl;
}

void pp(string s) {
	cout << s << endl;
}

int main() {
	int n, k;
	int sum = 0;
	cin >> n >> k;
	rep(i, 0, n) {
		if (i == 0)sum = k;
		else sum *= (k - 1);

	}

	cout << sum << endl;
	

	return 0;
}

Measured memory_bytes: 764
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int N, M;
vector <pair<int, int>> queries;
int A[100005];

int main() {
    ios_base::sync_with_stdio(false);
    cin >> N >> M;

    for(int i = 1; i <= N; i++)
        cin >> A[i];

    for(int i = 1; i <= M; i++) {
        int a, c;
        cin >> a >> c;
        queries.emplace_back(c, a);
    }
    sort(A + 1, A + N + 1);

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

    int idx = 1;
    for(int i = queries.size() - 1; i >= 0; i--) {
        for(int j = 0; j < queries[i].second && idx <= N; j++) {
            A[idx] = max(A[idx], queries[i].first);
            idx++;
        }
    }

    long long ans = 0;
    for(int i = 1; i <= N; i++)
        ans += A[i];
    cout << ans;
}


Measured memory_bytes: 1784
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;

using ll = long long;

const int INF = 1001001001;
const ll INF_LL = 1001001001001001001LL;

void solver(ll a,ll b,ll x){
  ll ans;
  if(a%x==0 || b%x==0) ans = 1+(b-a)/x;
  else{
    ans = b/x;
    ans -= a/x;
  }
  cout << ans << endl;
}

/*void solver2(ll a,ll b,ll x){
  ll ans = 0;
  for(ll i = a;i<=b;i++)
  if(i%x==0) ans++;*/
    /*if(i%x==0){
      cout << "i: " << i << endl << "b: " << b << endl;;
      ans++;
      }*//*
  cout << ans << endl;
  }*/

int main(void){
  ll a,b,x; cin >> a >> b >> x;
  //int tester; cin >> tester;
  
  solver(a,b,x);
  
  /*if(tester==0) solver(a,b,x);
    else solver2(a,b,x);*/
  
  return 0;
}


Measured memory_bytes: 3588
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
inline ll read() {
	ll kk=0,f=1;
	char cc=getchar();
	while(cc<'0'||cc>'9'){if(cc=='-')f=-1;cc=getchar();}
	while(cc>='0'&&cc<='9'){kk=(kk<<1)+(kk<<3)+cc-'0';cc=getchar();}
	return kk*f;
}
inline void write(ll xx){
	if(xx < 0){putchar('-');xx=-xx;}
	if(xx > 9)write(xx/10);
	putchar(xx%10+'0');
	return;
}
map<pair<ll,int>,ll> mp;
ll a[200005];
int n;
int main(){
	n = read();
	ll res = 0;
	for(int i = 1;i <= n;i++){
		a[i] = read();
		mp[make_pair(a[i] + i,0)]++;
		mp[make_pair(i -a[i],1)]++;
	}
	for(int i = 1;i <= n;i++){
		if(mp[make_pair(a[i] + i,1)]){
			res += (mp[make_pair(i + a[i],0)] * mp[make_pair(i + a[i],1)]);
			mp[make_pair(a[i] + i,1)] = 0;
			mp[make_pair(a[i] + i,0)] = 0;
		}else if(mp[make_pair(i - a[i],0)]){
			res += (mp[make_pair(i - a[i],0)] * mp[make_pair(i - a[i],1)]);
			mp[make_pair(i - a[i],0)] = 0;
			mp[make_pair(i - a[i],1)] = 0;
		}
	}
	write(res);
	return 0;
}

Measured memory_bytes: 49720
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll INF = 1e9+7;
ll MOD = 998244353;
typedef pair<long long,ll> ii;
#define iii pair<ii,ll>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define rf(i,a,b) for(long long i=a;i>=b;i--)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define w(t) while(t--)
#define c(n); cin>>n;
#define p(n) cout<<n;
#define pl(n) cout<<n<<"\n";
#define ps(n); cout<<n<<" ";
#define F first
#define S second
#define pb(a) push_back(a)
#define all(x) (x).begin(), (x).end()
#define ull unsigned long long
#define vll vector<ll>
#define vii vector<ii>
#define mkp make_pair
#define ld long double
#define arrin(a,n) f(i,0,n){cin>>a[i];}
#define arrout(a,n) f(i,0,n){cout<<a[i]<<" ";}
#define printclock cerr<<"Time : "<<*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
#define PI (2*acos(0))
#define EPS 1e-18
struct node{
    ll sum = 0,eq = -1;
};
ll arr[200005];
ll pre[200005];
vector<node> seg(800005);
void build(ll idx,ll s,ll e){
    if(s == e){
        seg[idx].sum = arr[s-1];
        return;
    }
    ll mid = (s+e)/2;
    build(idx*2,s,mid);
    build(idx*2+1,mid+1,e);
    seg[idx].sum = (seg[idx*2].sum + seg[idx*2+1].sum) % MOD;
}
ll ev(ll x,ll y){
    return (MOD + pre[x] - pre[y-1]) % MOD;
}
void upd(ll idx,ll s,ll e,ll qs,ll qe,bool eq,ll h){
    if(qs <= s && e <= qe){
        if(eq){
            seg[idx].sum = h * (MOD + pre[e] - pre[s-1]) % MOD;
            seg[idx].sum %= MOD;
            seg[idx].eq = h;
        }
        return;
    }
    if(qs > e || s > qe){
        return;
    }
    ll mid = (s+e)/2;
    if(seg[idx].eq != -1){
        seg[idx*2].sum = seg[idx].eq * ev(mid,s);
        seg[idx*2].sum %= MOD;
        seg[idx*2+1].sum = seg[idx].eq * ev(e,mid+1);
        seg[idx*2+1].sum %= MOD;
        seg[idx*2].eq = seg[idx*2+1].eq = seg[idx].eq;
    }
    seg[idx].eq = -1;
    upd(idx*2,s,mid,qs,qe,eq,h);
    upd(idx*2+1,mid+1,e,qs,qe,eq,h);
    seg[idx].sum = (seg[idx*2].sum + seg[idx*2+1].sum) % MOD;
}
node query(ll idx,ll s,ll e,ll qs,ll qe){
    if(qs <= s && e <= qe){
        return seg[idx];
    }
    if(qs > e || s > qe){
        node x;
        return x;
    }
    ll mid = (s+e)/2;
    if(seg[idx].eq != -1){
        seg[idx*2].sum = seg[idx].eq * ev(mid,s);
        seg[idx*2].sum %= MOD;
        seg[idx*2+1].sum = seg[idx].eq * ev(e,mid+1);
        seg[idx*2+1].sum %= MOD;
        seg[idx*2].eq = seg[idx*2+1].eq = seg[idx].eq;
    }
    seg[idx].eq = -1;
    node a = query(idx*2,s,mid,qs,qe);
    node b = query(idx*2+1,mid+1,e,qs,qe);
    node c;
    c.sum = (a.sum + b.sum) % MOD;
    return c;
}
int main(void){
    fastio;
    ll n,q;
    cin>>n>>q;
    ll num = 1;
    pre[0] = 0;
    rf(i,n-1,0){
        arr[i] = num;
        num *= 10;
        num %= MOD;
    }
    f(i,0,n){
        pre[i+1] = (pre[i] + arr[i]) % MOD;
    }
    build(1,1,n);
    w(q){
        ll l,r,d;
        cin>>l>>r>>d;
        upd(1,1,n,l,r,1,d);
        cout<<seg[1].sum<<"\n";
    }
}




Measured memory_bytes: 18696
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = j;i<k;i++)
int j,y;
void DFS(string s,int a,int b){
  if(a ==j && b == y){
    cout << s<<endl;
    return;
  }
  if(((a==5 || b == 5 )&&(abs(a-b)!=1)) || (a == 6 || b == 6))return;
  DFS(s+"A",a+1,b);
  DFS(s+"B",a,b+1);
}
int main(){
  cin >>j>>y;
  DFS("",0,0);
  return 0;
}



Measured memory_bytes: 3204
# import sys
from sys import stdout
# from copy import copy, deepcopy
# from functools import lru_cache
# from string import ascii_lowercase
# from math import inf
# inf = float('inf')


def main():
    ans = solve_case()
    stdout.write("{}\n".format(ans))

def solve_case():
    S = read_str()

    len_s = len(S)
    int_s = [ord(c) - ord('a') for c in S]

    # next_char_pos[from_idx][letter_idx] := the position of the next letter `letter_idx` from `from_idx`
    next_char_pos = make_list((len_s + 1, 26), len_s)
    for from_idx in reversed(range(len_s)):
        for letter_idx in range(26):
            if int_s[from_idx] == letter_idx:
                pos = from_idx
            else:
                pos = next_char_pos[from_idx+1][letter_idx]
            next_char_pos[from_idx][letter_idx] = pos

    # non_subseq_len[from_idx] := the length of the shortest "non subsequence" in S[from_idx:]
    non_subseq_len = make_list([len_s + 2], len_s + 1)
    non_subseq_len[len_s] = 1
    non_subseq_len[len_s + 1] = 0
    ans_next_pos = make_list([len_s + 1], len_s)
    ans_letter = make_list([len_s + 1], -1)
    for from_idx in reversed(range(len_s)):
        for letter_idx in range(26):
            new_len = non_subseq_len[next_char_pos[from_idx][letter_idx] + 1] + 1
            if non_subseq_len[from_idx] > new_len:
                non_subseq_len[from_idx] = new_len
                ans_letter[from_idx] = letter_idx
                ans_next_pos[from_idx] = next_char_pos[from_idx][letter_idx] + 1

    ans = ''
    idx = 0
    while idx < len(S):
        ans += chr(ord('a') + ans_letter[idx])
        idx = ans_next_pos[idx]
    return ans

#################################

def read_str(): return input()
def read_int(): return int(input())
def read_str_list(): return input().split(' ')
def read_int_list(): return list(map(int, input().split(' ')))
def read_lines(n, read_func): return [read_func() for _ in range(n)]
def list_to_str(l, sep=' '): return sep.join(map(str, l))
l2s = list_to_str
# shape: tuple of ints | list of ints
def make_list(shape, value=None):
    if len(shape) == 1:
        return [value] * shape[0]
    return [make_list(shape[1:], value) for _ in range(shape[0])]

if __name__ == '__main__':
    # sys.setrecursionlimit(1000000)
    main()


Measured memory_bytes: 86328
#include <iostream>
using namespace std;


int main()
{
	int a, b;
	cin >> a >> b;

	if (a < b) {
		cout << "a < b" << endl;
	}
	else if (a > b) {
		cout << "a > b" << endl;
	}
	else {
		cout << "a == b" << endl;
	}

    return 0;
}



Measured memory_bytes: 3072
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <stack>
#include <queue>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rep(i,N) for (int i=0;i<N;i++)

//変数
ll X,Y;

//解法
void solve() {

	ull ans = 0;

	while (X<=Y) {
		Y /= 2;
		ans++;
	}

	cout << ans << endl;

	return;
}

int main() {
	//入力
	cin >> X >> Y;
	solve();
	cout << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

template<typename T>
T gcd(T a, T b)
{
	if (a < b)	return gcd(b, a);
	T r;
	while ((r = a % b))
	{
		a = b;
		b = r;
	}
	return b;
}

template<typename T>
T lcm(T a, T b)
{
	return a * b / gcd(a, b);
}

template<typename T>
T ext_gcd(T a, T b, T& x, T& y)
{
	x = 1;
	y = 0;
	T x0 = 0, y0 = 1;
	while (b != 0)
	{
		T q = a / b;
		a -= q * b;
		swap(a, b);
		x -= q * x0;
		swap(x, x0);
		y -= q * y0;
		swap(y, y0);
	}
	return a;
}

template<typename T>
T inv_mod(T a, T mod)
{
	T t1, t2;
	ext_gcd(a, mod, t1, t2);
	t1 %= mod;
	if (t1 < 0)		t1 += mod;
	return t1;
}

template<typename T>
T combination_large(T n, T k, T mod)
{
	if (n < k || n < 0 || k < 0)	return 0;
	vector<T> inv(n + 1, 1), fact(n + 1, 1), fact_inv(n + 1, 1);
	for (T i = 2; i <= n; ++i)
	{
		inv[i] = mod - inv[mod % i] * (mod / i) % mod;
		fact[i] = (fact[i - 1] * i) % mod;
		fact_inv[i] = fact_inv[i - 1] * inv[i] % mod;
	}
	return fact[n] * (fact_inv[k] * fact_inv[n - k] % mod) % mod;
}

template<typename T>
T combination(T n, T k, T mod = 1)
{
	vector<vector<T>> table(n + 1, vector<T>(k + 1, 1));
	for (T i = 1; i <= n; ++i)
	{
		table[i][0] = 1;
		for (T j = 1; j <= n; ++j)
		{
			table[i][j] = (table[i - 1][j - 1] + table[i - 1][j]) % mod;
		}
	}
}


int main(int, char**)
{
	long long X;
	scanf("%lld",&X);

	ll happiness = 0;
	happiness += X / 500 * 1000;
	X %= 500;
	happiness += X / 5 * 5;

	cout << happiness << endl;

	return 0;
}


Measured memory_bytes: 256