akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

long long MOD;
struct mint{

    long long v;

    mint() : v(0) {}
    mint(long long x){
        x = x % MOD;
        if(x < 0){ x += MOD; }
        v = x;
    }
    mint& operator+=(mint a){
        v += a.v;
        if(v >= MOD){ v -= MOD; }
        return *this;
    }
    mint& operator*=(mint a){
        v *= a.v;
        v %= MOD;
        return *this;
    }
    mint& operator-=(mint a){
        v -= a.v;
        if(v < 0){ v += MOD; }
        return *this;
    }
    mint& operator/=(mint a){
        return (*this) *= a.inv();
    }

    mint operator*(mint a) const{
        return mint(v) *= a;
    }

    mint operator+(mint a) const {
        return mint(v) += a;
    }

    mint operator-(mint a) const {
        return mint(v) -= a;
    }

    mint operator/(mint a) const {
        return mint(v) /= a;
    }

    mint pow(long long k) const {
        mint res(1),tmp(v);
        while(k){
            if(k&1) res *= tmp;
            tmp *= tmp;
            k >>= 1;
        }
        return res;
    }
    mint inv(){return pow(MOD - 2); }

    static mint comb(long long n, int k){
        mint res(1);
        for(int i = 0; i < k; ++i){
            res *= mint(n - i);
            res /= mint(i + 1);
        }
        return res;
    }

    static mint factorial(long long n){
        mint res(1);
        for(int i = n; i > 1; --i){
            res *= mint(i);
        }
        return res;
    }

    bool operator<(const mint &a) const {
        return v < a.v;
    };
};

mint operator*(long long l, mint r){ return r * l; }

void calc_factorials(long long n, vector<mint>& out){
    out.resize(n + 1);
    out.at(0) = 1;
    out.at(1) = 1;
    for(long long i = 2; i <= n; ++i){
        out.at(i) = out.at(i - 1) * i;
    }
}

int main(){
    cin >> MOD;
    vector<int> a(MOD);
    for(int i = 0; i < MOD; ++i){
        cin >> a.at(i);
    }

    vector<mint> facts, invs;
    calc_factorials(MOD - 1, facts);
    invs.resize(facts.size());
    for(int i = 0; i < facts.size(); ++i){
        invs.at(i) = facts.at(i).inv();
    }

    vector<mint> b(MOD);
    for(int i = 0; i < MOD; ++i){
        if(a.at(i) == 0){ continue; }
        b.at(0) += 1;
        mint tmp = 1;
        for(int k = MOD - 1; k >= 0; --k){
            b.at(k) -= tmp
                * facts.at(MOD - 1) * invs.at(k) * invs.at(MOD - 1 - k);
            tmp *= -i;
        }
    }

    for(int i = 0; i < b.size(); ++i){
        cout << b.at(i).v;
        if(i != b.size() - 1){
            cout << ' ';
        }
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 888
#include <bits/stdc++.h>    
#include <unordered_map>
using namespace std;
#define fastio() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb  push_back
#define show(x) cerr<<(#x)<<" : "<<x<<endl;
#define ll  long long
#define ld  long double
#define fill(a,val) memset(a,val,sizeof(a))
#define mp  make_pair
#define ff  first
#define ss  second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sq(x) ((x)*(x))
#define all(v) v.begin(),v.end()
#define endl "\n"
#define fo(i,n) for(int i=0;i<n;i++)
#define foo(i,x,n) for(int i=x;i<n;i++)
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define w(x) int x;cin>>x;while(x--)
#define display(a,n) {fo(i,n) {cout<<a[i]<<" ";}cout<<endl;}
#define fil(a,n,val) {fo(i,n) a[i]=val; }
#define sp(x,y) cout<<fixed<<setprecision(y)<<x<<endl;
const ll MOD   = 1000*1000*1000+7;
const ll MOD2  = 998244353;
const ll N = 1000*1000+5;
const double PI  = 3.14159265;
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
ll search(vl arr, ll l, ll r, ll x){if (r >= l) {ll mid = l + (r - l) / 2;if (arr[mid] == x)return mid;if (arr[mid] > x)return search(arr, l, mid - 1, x);return search(arr, mid + 1, r, x);} return -1;}
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);}
ll lcm(ll a , ll b){return (a*b)/ gcd(a,b);}
ll power(ll x, ll y, ll p){ll res = 1;x = x % p;while (y > 0){ if (y & 1) res = (res*x) % p; y = y>>1;x = (x*x) % p; } return res; }
ll modInverse(ll n, ll p){return power(n, p-2, p);}
const int maxn=1e5+5;

vi g[maxn];
int n;
ll dp[maxn][2];

ll solve(int node, int con,int par){
	if(dp[node][con]!=-1)
		return dp[node][con];

	ll ans=0;
	ll w1=1;
	for(int child:g[node]){
		if(child!=par){
			w1=(w1*solve(child,0,node))%MOD;
		}
	}
	ans+=w1;
	if(!con){
		ll w2=1;
		for(int child:g[node]){
			if(child!=par){
				w2=(w2*solve(child,1,node))%MOD;
			}
		}
		ans=(ans+w2)%MOD;
	}
	return dp[node][con]=ans;
}


int main(){
	fastio();
	cin>>n;
	fo(i,n-1){
		int x,y;
		cin>>x>>y;
		g[x].pb(y);
		g[y].pb(x);
	}
	fill(dp,-1);


	cout<<solve(1,0,0)<<endl;

}

Measured memory_bytes: 17556
a, b, k = gets.split(" ").map(&:to_i)

if a - k <= 0
    if b - (k - a) >= 0
        puts "0" + " " + (b - (k - a)).to_s
    else
        puts "0" + " " + "0"
    end
else
    puts (a - k).to_s + " " + b.to_s
end

Measured memory_bytes: 1788
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<climits>

#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;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

using namespace std;

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

template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
	for (auto& e : t) fill_v(e, v);
}


#define ARRAY_MAX 100005
const ll INF = 1e9;
const ll MOD = 1e9 + 7;

const int dx4[] = { 1, 0, -1, 0 }, dy4[] = { 0, 1, 0, -1 };
const int dx8[] = { 1, 1, 0, -1, -1, -1, 0, 1 }, dy8[] = { 0, -1, -1, -1, 0, 1, 1, 1 };



template<typename T>
bool chmax(T& a, T b, bool equal = false) {
	if (a < b || equal && a == b) {
		a = b;
		return true;
	}
	return false;
}

template<typename T>
bool chmin(T& a, T b, bool equal = false) {
	if (b < a || equal && a == b) {
		a = b;
		return true;
	}
	return false;
}



/******************************************************************************************/



int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	
	string s;
	cin >> s;
	int cnt = 0;//グーを出した回数
	int win = 0;//正味の勝利数

	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] == 'g') {

			if (cnt > 0) {
				//パーを出せる
				cnt--;
				win++;
			}
			else
			{
				//パーを出せないのでグーしか出せない
				cnt++;
			}
		}
		else
		{
			if (cnt > 0) {
				//あいこにできる
				cnt--;
			}
			else
			{
				cnt++;
				win--;
			}


		}
	}

	cout << win << endl;
	return 0;
}


Measured memory_bytes: 512
#include <iostream>

using namespace std;

int main(void)
{
    long long N, A, B, P[101], i, count1=0, count2=0, count3=0, ans;

    cin >> N;
    cin >> A >> B;

    for(i=1; i<=N; i++){
        cin >> P[i];
        if(P[i] <= A){
            count1++;
        }
        else if(P[i]>=B+1){
            count3++;
        }
        else{
            count2++;
        }
    }

    ans = count1;

    if(ans > count2){
        ans = count2;
    }

    if(ans > count3){
        ans = count3;
    }

    cout << ans << endl;

    return 0;
}

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

#define ll long long int
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define sep(i,b,a) for(ll i=b-1;i>=a;i--)
#define vi vector <ll>
#define hell 998244353
#define pii pair <ll,ll>
#define inf (ll)(1e16)
#define pb push_back

using namespace std;

void solve()
{
    ll a,b;
    cin>>a>>b;
    b--;
    a--;
    if(b%a==0)
        cout<<b/a;
    else
        cout<<b/a+1;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll t;
	t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}


Measured memory_bytes: 256
k=int(input())
A=[]
for i in range(1,9):
    A.append([i,1])
now=0
for i in range(15):
    now+=9*10**i
    for j in range(1000):
        c=now+j*10**(i+1)
        S=str(c)
        cnt=0
        for s in S:
            cnt+=int(s)
        A.append([c,c/cnt])
A=list(reversed(sorted(A)))
now=0
m=A[0][1]
Ans=[]
for a in A:
    if a[0]==now:
        continue
    else:
        now=a[0]
        if a[1]<=m:
            Ans.append(now)
            m=a[1]
Ans=list(reversed(Ans))
for i in range(k):
    print(Ans[i])

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

int main()
{
	long long panduan(int x);
	int n,i;
	long long sum=0;
	cin >> n;
	for(i=1;i<=n;i++)
	{
		sum+=panduan(i);
	}
	
	cout << sum;
	return 0;
}
long long panduan(int x)
{
	if(x%3!=0 && x%5!=0)
	{
		return x;
	}
	else
	    return 0;
}

Measured memory_bytes: 3596
#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;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 1000000000000000000LL
#define MOD 1000000007
#define writeln(n) cout<<n<<endl
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
//vector<tuple<long long, long long, long long>>vec;

template<class T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

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

bool isprime(int p) {
	if (p == 1) return false;
	for (int i = 2; i < p; i++) {
		if (p%i == 0) return false;
	}
	return true;
}

int main()
{
int a,b,c;
cin>>a>>b>>c;
if(a+b+1>=c) cout<<b+c<<endl;
else cout<<b+a+b+1<<endl;

}

Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        MyScanner in = new MyScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        D solver = new D();
        solver.solve(1, in, out);
        out.close();
    }

    static class D {
        int N;
        int K;
        int[] L;
        int[] R;
        static long MOD = 998244353;

        public void solve(int testNumber, MyScanner in, PrintWriter out) {
            N = in.Int();
            K = in.Int();
            L = new int[K];
            R = new int[K];
            for (int i = 0; i < K; i++) {
                L[i] = in.Int();
                R[i] = in.Int();
            }

            long[] dp = new long[N + 1];
            long[] suma = new long[N + 1];
            long sum = 0;

            dp[1] = 1;
            for (int i = 1; i <= N; i++) {
                sum += suma[i];
                dp[i] += sum;
                dp[i] %= MOD;
                for (int j = 0; j < K; j++) {
                    int l = i + L[j];
                    int r = i + R[j] + 1;
                    if (l <= N) {
                        suma[l] += dp[i];
                        suma[l] %= MOD;
                    }
                    if (r <= N) {
                        suma[r] -= dp[i];
                        suma[r] %= MOD;
                    }
                }
            }
            out.println(dp[N] % MOD);
        }

    }

    static class MyScanner {
        private BufferedReader in;
        private StringTokenizer st;

        public MyScanner(InputStream stream) {
            in = new BufferedReader(new InputStreamReader(stream));
        }

        public String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    String rl = in.readLine();
                    if (rl == null) {
                        return null;
                    }
                    st = new StringTokenizer(rl);
                } catch (IOException e) {
                    return null;
                }
            }
            return st.nextToken();
        }

        public int Int() {
            return Integer.parseInt(next());
        }

    }
}



Measured memory_bytes: 37256
#include <stdio.h>

int main(int argc, const char * argv[]) {

    int a,b;
    char op;
    
    
    
    while (1) {
        
        scanf("%d %c %d",&a,&op,&b);
        
        if (op == '?') {
            break;
        }
    
    switch (op) {
        case '+':
            printf("%d\n",a+b);
            break;
        case '-':
            printf("%d\n",a-b);
            break;
        case '*':
            printf("%d\n",a*b);
            break;
        case '/':
            printf("%d\n",a/b);
            break;
        default:
            break;
    }
    }
    
    return 0;
}

Measured memory_bytes: 600
//Ruined Square
#include <stdio.h>
#include <math.h>

int main(void)
{
    int x1, y1, x2, y2;
    
    int x3, y3, x4, y4;
    
    printf("\n");
    //scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
    
    if(0<=scanf("%d %d %d %d", &x1, &y1, &x2, &y2)<=100)
    {
        if(x1==x2&&y1==y2)
        {
            printf("error\n");
        }
        else
        {
            x3= x2-(y2-y1);
            y3= y2+(x2-x1);
            x4= x3-(y3-y2);
            y4= y3+(x3-x2);
            
            
            printf("%d %d %d %d", x3, y3, x4, y4);
            
        }
    }
    else
    {
        printf("error\n");
    }
    
    return 0;
}
//&&x1!=x2&&y1!=y2


Measured memory_bytes: 128
#include<iostream>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<math.h>
#include<cstring>
using namespace std;
 
int main()
{
	
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int k,a,b;
    cin>>k>>a>>b;
    int i=0;
    for(i=a;i<=b;i++)
    {
    	
    	if(i%k==0)
    	{
    		
    		cout<<"OK"<<endl;
    		return 0;
    		
		}
    	
    	
    	
	}
	
	
	if(i>=b)
	{
		
		cout<<"NG"<<endl;
		
	}
	
    
    
    
    
    return 0;
    
}
    

Measured memory_bytes: 3588
#include <bits/stdc++.h>
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef long double ld;
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cout.setf(ios::fixed); cout.precision(20);
    ll n, m, k; cin >> n >> m >> k;
    vector<ll> a(n), b(m);
    for (ll &x : a) {
        cin >> x;
    }
    for (ll &x : b) {
        cin >> x;
    }
    vector<ll> pref(m);
    pref[0] = b[0];
    ll res = 0;
    if (b[0] <= k) {
        res = 1;
    }
    for (int i = 1; i < m; i++) {
        pref[i] = b[i] + pref[i - 1];
        if (pref[i] <= k) {
            res = i + 1;
        }
    }
    ll cur = 0;
    for (ll i = 0; i < n; i++) {
        cur += a[i];
        if (cur > k) {
            break;
        }
        ll can = k - cur;
        res = max(res, i + 1);
        auto it = upper_bound(pref.begin(), pref.end(), can);
        if (it == pref.begin()) {
            continue;
        }
        int j = (int) (it - pref.begin());
        res = max(res, i + 1 + j);
    }
    cout << res << "\n";
}


Measured memory_bytes: 7952
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

int main()
{
    int n, k, r, s, p;
    string t;
    cin >> n >> k >> r >> s >> p >> t;

    vector<int> score(128, 0);
    score['r'] = p;
    score['s'] = r;
    score['p'] = s;

    int ans = 0;
    for(int i=0; i<k; ++i){
        int j = i;
        while(j < n){
            ans += score[t[j]];
            j += k;
            if(j < n && t[j] == t[j-k])
                j += k;
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<stack>
#include<queue>
#include<string>
#include<set>
#include<map>
using namespace std;
#define rep(i,n) for(int i=0;(i)<(n);(i)++)
#define FOR(i,m,n) for(int i=(m);(i)<(n);(i)++)
typedef long long ll;
vector<vector<int> > G(55);
int used[55]={};

void dfs(int v){
    used[v]=1;
    for(int x:G[v]){
        if(used[x]==0){
            dfs(x);
        }
    }
}

int main(){
    int n,m;
    cin >>n >> m;
    int a[55],b[55];
    rep(i,m){
        cin >> a[i] >> b[i];
    }
    int res=0;
    for(int i=0;i<m;i++){
        for(int j=0;j<m;j++){
            if(j!=i){
                G[a[j]].push_back(b[j]);
                G[b[j]].push_back(a[j]);
            }
        }
    
        dfs(1);
        for(int j=1;j<=n;j++){
            if(used[j]==0){
                res++;
                break;
            }
        }
        G.clear();
        G.resize(55);
        fill(used,used+55,0);
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <limits.h>
#include <utility>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
using P = pair<int,int>;
using ll = long long;
template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
int main(){
    int n;
    cin>>n;
    ll k;
    cin>>k;
    vector<ll> a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    vector<ll> bit(40,0);
    for(int i=0;i<n;i++){
        for(int j=39;j>=0;j--){
            if(a[i]>=(ll)pow(2,j)){
                bit[j]++;
                a[i]-=(ll)pow(2,j);
            }
        }
    }
    ll ret=0;
    vector<ll> s(40),t(40);
    s[0]=max(bit[0],n-bit[0]);
    for(int i=1;i<40;i++){
        s[i]=s[i-1]+(ll)pow(2,i)*max(bit[i],n-bit[i]);
    }
    if((k>>39)&1)t[39]=(ll)pow(2,39)*(n-bit[39]);
    else t[39]=(ll)pow(2,39)*bit[39];
    for(int i=38;i>=0;i--){
        if((k>>i)&1)t[i]=t[i+1]+(ll)pow(2,i)*(n-bit[i]);
        else t[i]=t[i+1]+(ll)pow(2,i)*bit[i];
    }
    ret=t[0];
    for(int i=0;i<40;i++){
        if((k>>i)&1){
            ll tmp=0;
            tmp+=(ll)pow(2,i)*bit[i];
            if(i+1<40)tmp+=t[i+1];
            if(i-1>=0)tmp+=s[i-1];
            chmax(ret,tmp);
        }
    }
    cout<<ret<<endl;
}

Measured memory_bytes: 4104
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

//AtCoder Beginner Contest 118
//C	Monsters Battle Royale
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();

		List<Integer> inList = new ArrayList<>();
		for (int i = 0; i < N; i++) {
				inList.add(sc.nextInt());
		}
		sc.close();

		int min = 0;
		int minIndex = 0;

		while (inList.size() > 1) {
			min = Collections.min(inList);
			minIndex = getMinIndex(inList, min);
			if (min == 1) {
				break;
			}
			for (int i = 0; i < inList.size(); i++) {
				if (i == minIndex) {
					continue;
				} else {
					inList.set(i, inList.get(i) % min);
				}
			}
			for (int i = inList.size() - 1; i >= 0; i--) {
				if (inList.get(i) == 0) {
					inList.remove(i);
				}
			}
		}

		System.out.println(min);
	}

	private static int getMinIndex(List<Integer> inList, int min) {
		for (int i = 0; i < inList.size(); i++) {
			if (inList.get(i) == min) {
				return i;
			}
		}
		return -1;
	}
}


Measured memory_bytes: 60280
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 5;
int n,u,v;
int a[MAXN],f[MAXN],p[MAXN],ans[MAXN];
bool vis[MAXN];
template<class T>
void read(T& x, int f = 1) {
	char ch = getchar();
	x = 0;
	while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
	while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
	x *= f;
}
struct Edge {
	int next,to;
} e[MAXN<<1];
void addEdge(int from,int to) {
	static int t;
	e[t].to=to,e[t].next=p[from],p[from]=t++;
}
void dfs(int now,int len) {
	vis[now]=1,ans[now]=len;
	for(int i=p[now]; ~i; i=e[i].next) {
		int to=e[i].to;
		if(!vis[to]) {
			int id = lower_bound(f+1,f+len+1,a[to]) - f;
			int tmp = f[id];
			f[id]=a[to];
			dfs(to,max(len,id));
			f[id]=tmp;
		}
	}
}
int main() {
	read(n);
	for(int i=1; i<=n; i++) read(a[i]);
	memset(p,-1,sizeof(p));
	for(int i=1; i<=n-1; i++) {
		read(u),read(v);
		addEdge(u,v),addEdge(v,u);
	}
	f[1]=a[1];
	dfs(1,1);
	for(int i=1; i<=n; i++)
		printf("%d\n",ans[i]);
	return 0;
}

Measured memory_bytes: 23640
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

while True:
    S = raw_input()
    if S == '0':
        break
    m = [0 for i in range(11)]
    m[0] = 1
    diff = 0
    even = 1
    S = reversed(S)
    ans = 0
    for c in S:
        num = int(c)
        diff += num * even
        diff %= 11
        if num != 0:
            ans += m[diff]
        m[diff] += 1
        even *= -1
    print ans


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

#define int long long
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;

#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple

#define len(a) ((int) (a).size())
#define all(a) (a).begin(), (a).end()

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a, b;
    cin >> a >> b;
    cout << a * b;
    return 0;
}


Measured memory_bytes: 3656
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <numeric>
#define ll long long int
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
int mx4[] = {0,1,0,-1};
int my4[] = {1,0,-1,0};


//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


int main(){
    int a,b,c; cin >> a >> b >> c;
    cout << min(b/a,c) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REP1(i,a,b) for (int i = a; i <= (int)(b); i++)
using namespace std;
const int MOD=998244353;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> c(n),d(n);
    REP(i,n) cin >> d[i], c[d[i]]++;
    if ( d[0]!=0 || c[0]>1 ) { cout << 0 << '\n'; return 0; }
    int ans=1;
    REP1(i,1,n-1) {
        if ( c[i-1]==0 && c[i]==0 ) continue;
        if ( c[i-1]==0 && c[i]>0 ) ans*=0;
        REP(j,c[i]) ans=(long long)ans*c[i-1]%MOD;
    }
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 3940
#include <iostream>
#include <set>
#include <map>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <climits>
#include <math.h>
#include <cassert>
#include <unordered_map>
using namespace std;
#pragma warning(disable : 4996)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;


int main() {
#ifdef _DEBUG
	freopen("input1.txt", "r", stdin);
	freopen("output2.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	ll s = 0;
	for (int i = 1; i <= n; i++) {
		if (i % 3 != 0 && i % 5 != 0)s += i;
	}
	cout << s;
}

Measured memory_bytes: 3628
#include<iostream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<set>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<stack>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;
typedef pair<ll, bool> pib;

typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;

typedef vector<double> vf;

typedef long double ld;

#define mp make_pair
#define pb push_back

#define rep(i, N) for(ll i = 0; i < N; i++)
#define repa(i, a, N) for(ll i = a; i < N; i++)
#define repr(i, N) for(ll i = N-1; i >= 0; i--)

#define drep(i, N, j, M) rep(i, N) rep(j, M)
#define trep(i, N, j, M, k, L) rep(i, N) rep(j, M) rep(k, L)

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

#define printItr(A) for(auto itr = A.begin(); itr != A.end(); ++itr){cout << * itr << ", ";}cout << endl;

const double PI = 3.141592653589793;

const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;

const ll LLMAX = numeric_limits<long long>::max();

void No() {
	cout << "No" << endl;
}

void Yes() {
	cout << "Yes" << endl;
}

ll id(char c) {
	return c - 'a';
}

bool isOK(vi& a, ll k, ll index) {
	return a[index] < k * (index + 1);
}

ll binary_search(vi& a, ll k) {
	ll left = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
	ll right = (ll)a.size(); // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()

	/* どんな二分探索でもここの書き方を変えずにできる！ */
	while (right - left > 1) {
		ll mid = left + (right - left) / 2;

		if (isOK(a, k, mid))
			right = mid;
		else left = mid;
	}

	/* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
	return right;
}

template<class t, class u>
ostream& operator<<(ostream& os, const pair<t, u>& p) {
	return os << "{" << p.first << "," << p.second << "}";
}

template<class t> ostream& operator<<(ostream& os, const vector<t>& v) {
	os << "{";
	for (auto e : v)os << e << ",";
	return os << "}";
}

bool eq(vi P, vi Q) {
	rep(i, P.size()) {
		if (P[i] != Q[i]) {
			return false;
		}
	}
	return true;
}

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);
}

ll modinv(ll a, ll m) {
	ll b = m, u = 1, v = 0;
	while (b) {
		ll t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

int main() {
	char C;
	cin >> C;

	cout << (char)(C + 1) << endl;

	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<functional>
#include<cstdio>
#include<cstdlib>
#include<unordered_map>
#include<unordered_set>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592
#define PI acos(-1.0);

const double EPS = 1e-10;

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;


int main(){
	vector<vector<int>> A(3,vector<int>(3));
	rep(i,3)rep(j,3) cin >> A[i][j];
	int N; cin >> N;
	vector<vector<bool>> ok(3,vector<bool>(3,false));
	rep(i,N){
		int b; cin >> b;
		rep(j,3)rep(k,3){
			if(A[j][k] == b) ok[j][k] = true;
		}
	}
	bool f1 = false;
	rep(i,3){
		bool f2 = true;
		rep(j,3) if(!ok[i][j]) f2 = false;
		if(f2) f1 = true;
	}
	rep(j,3){
		bool f2 = true;
		rep(i,3) if(!ok[i][j]) f2 = false;
		if(f2) f1 = true;
	}
	if(ok[0][0] && ok[1][1] && ok[2][2]) f1 = true;
	if(ok[0][2] && ok[1][1] && ok[2][0]) f1 = true;
	cout << (f1?"Yes":"No") << endl;
}



Measured memory_bytes: 256
import sys
from math import ceil
from fractions import gcd

a, b, c, d = map(int, input().split())
if c == 1:
  print(0)
  sys.exit()
cd_lcm = c*d//gcd(c, d)
c_left, c_right = ceil(a/c), b//c
d_left, d_right = ceil(a/d), b//d
cd_left, cd_right = ceil(a/cd_lcm), b//(cd_lcm)
cv, dv, cdv = c_right - c_left + 1, d_right - d_left + 1, cd_right - cd_left + 1
print((b - a + 1) - (cv + dv - cdv))

Measured memory_bytes: 5076
#include <iostream>
#include <vector>
#include <utility>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <string.h>
#include <deque>
#define REP(i,j,n) for(int i=j;i<n;i++)
#define SORT(x) sort(x.begin(),x.end())

using namespace std;



int main() {
	int n;
	long long sum = 1;
	cin >> n;
	while (n > 1 ){
		sum *= n;
		n--;
	}

	cout << sum << endl;
	return 0;
}

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

using namespace std;

vector<int> adj[200000];
int value[200000];

void dfs(int node, int parent = -1)
{
	for (auto x : adj[node])
	{
		if (x == parent)
			continue;
		value[x] += value[node];
		dfs(x, node);
	}
}

int main()
{
	int N, Q;
	cin >> N >> Q;
	
	for (int x = 0; x < N - 1; ++x)
	{
		int a, b;
		cin >> a >> b;
		--a;
		--b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	for (int x = 0; x < Q; ++x)
	{
		int a, b;
		cin >> a >> b;
		value[--a] += b;
	}
	
	dfs(0);
	
	for (int x = 0; x < N; ++x)
		cout << value[x] << " ";
	cout << '\n';
}


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


#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define pii pair<int,int>
#define ll long long
#define el '\n'

using namespace std;


int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int x,a;
    cin >> x >> a;
    if (x<a) cout << 0 << el;
    else cout << 10 << el;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define endl "\n"
#define int long long
#define push_back pb
#define getMat(v, n, m) vector<vector<int>> v(n,vector<int>(m))
#define lb lower_bound
#define up upper_bound
#define all(v) v.begin(),v.end()
#define size(v) (int)v.size()
using namespace std;
const int mod = 1e9+7;

int32_t main(){
    fastio;

    int x, k, d; cin >> x >> k >> d;
    x = abs(x);

    int steps = (x/d);
    if(k>steps){
        int op1 = x, op2 = x;
        if((k-steps)%2==0){
            op1 = x-steps*d;
        }else{
            op1 = x-(steps+1)*d;
        }

        if((k-(steps+1))%2==0){
            op2 = x-(steps+1)*d;
        }else{
            op1 = x-steps*d;
        }

        x = min(abs(op1),abs(op2));
    }else{
        x -= k*d;
        x = abs(x);
    }
    
    cout << x << endl;
    return 0;
}

Measured memory_bytes: 3648
n = int(input())
a = list(map(int, input().split()))
x = [0] * n
# 合計を求める
x[0] = sum(a)
# 初項x_1
for i in range(1, n - 1, 2):
    x[0] -= 2 * a[i]
# 漸化式で前から求める
for i in range(1, n):
    x[i] = 2 * a[i - 1] - x[i - 1]
print(*x)

Measured memory_bytes: 64484
#include <bits/stdc++.h>
#define int long long int
#define get(a)  int a[n]; for(int i=0;i<n;i++){cin>>a[i];}
#define out(a) for(int i=0;i<n;i++){cout<<a[i]<<" ";}cout<<endl;
#define db(x) cout<<x<<" "<<endl;
#define deb  cout<<"hi"<<" "<<endl;
#define endl "\n"
using namespace std;
int mod(int a,int b)
{
    if(a-b<=0)
    {
        return b-a;
    }
    else
    {
        return a-b;
    }
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1;
//    cin>>t;
    while(t--)
    {
        int n;int k;
        cin>>n>>k;
       get(a);
       int b[n];b[0]=0;b[1]=b[0]+mod(a[0],a[1]);
       for(int i=0;i<n;i++)
       {
          // b[i]=LLONG_MAX;
         // if(i!=0)
          //b[i]=LLONG_MAX;
          int z=LLONG_MAX;
         // cout<<k<<endl;
           for(int j=1;j<=min(i,k);j++)
           {
              z=min(z,b[i-j]+mod(a[i-j],a[i])); 
             
           }
           if(i!=0)
           {
           b[i]=z;
           }
       }
       cout<<b[n-1]<<endl;
       //out(b);
    }
  
}

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

class modint {
  public:
    using ll = long long;
    ll num;
    static const ll MOD = 1e9+7;
    static vector<modint> factorial;

    modint(): num(0) {};
    modint(ll n_): num((n_ + MOD) % MOD) {}
    modint(const modint &r): num(r.num) {}
    operator ll() const { return (num+MOD)%MOD; }
    friend istream& operator>>(istream& is, modint &r){
        ll num_;
        is >> num_;
        r = num_;
        return is;
    }
    modint operator+(const modint &r) const { return modint(num + r.num); }
    modint operator-(const modint &r) const { return modint(num - r.num); }
    modint operator*(const modint &r) const { return modint(num * r.num); }

    template<typename T>
    modint operator^(const T &r) const {
        if(r == 0) return 1;
        return (((*this)*(*this)) ^ (r/2)) * modint(r&1 ? num : 1);
    }
    modint operator/(const modint &r) const { return num * (r^(MOD-2)); }

    modint operator+=(const modint &r) { return *this = *this + r; }
    modint operator-=(const modint &r) { return *this = *this - r; }
    modint operator*=(const modint &r) { return *this = *this * r; }
    modint operator/=(const modint &r) { return *this = *this / r; }

    template<typename T>
    modint operator^=(const T &r) { return *this = *this ^ r; }

    static modint pow(const modint x, ll r) {
        return x^r;
    }

    static modint fact(int n){
        if((int)factorial.size() <= n) {
            int size = factorial.size();
            factorial.resize(n+1);
            for (int i = size; i <= n; i++) {
                factorial[i] = factorial[i-1] * modint(i);
            }
        }
        return factorial[n];
    }

    static modint C(ll n,ll r){
        return n >= r ? fact(n)/(fact(n-r)*fact(r)) : modint(0);
    }
};
vector<modint> modint::factorial = {1};
#define fact(n) modint::fact(n)
#define C(n,r) modint::C(n,r)
#define H(a,b) C(a+b, a)


int main(void){
    ll K;
    string s;
    cin >> K >> s;
    ll S = s.size();
    ll N = K + S;
    modint res = 0;
    rep(i,N) {
        res += C(i, S-1) * modint::pow(25, i - (S-1)) * modint::pow(26, N - i - 1);
    }
    cout << res << endl;
    return 0;
}


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

using namespace std;

#define N 100005

struct data {
  char name[11];
  int time;
};

data que[N];
int head,tail;

data front() {
  data a=que[tail];
  (++tail)%=N;
  return a;
}
void push(data a) { que[head]=a; (++head)%=N; }

int main() {
  data tmp;
  int n,q; cin >> n >> q;
  while(n--) {
    cin >> tmp.name >> tmp.time;
    push(tmp);
  }
  int sec=0;
  while(head!=tail) {
    data a=front();
    int c=min(a.time,q);
    a.time-=c;
    sec+=c;
    if(a.time) push(a);
    else cout << a.name << " " << sec << endl;
  }
  
  return 0;
}


Measured memory_bytes: 4568
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<numeric>
#include<complex>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define reps(i,s,n) for(int i=s;i<n;i++)
using namespace std;
typedef long long ll;
typedef long double ld;

typedef complex<double> P;
int main(){
  IOS;
  // ld a[2],b[2],c[2],d[2]

  ld x,y;
  char c;
  P p[4];
  while(1){
    int che=0;
    rep(i,4){
      // cin>>x>>c>>y;
      if(!((cin>>x).ignore()>>y).ignore()) return 0;
      p[i]=P(x,y);
    }
    bool a[2]={};
    rep(i,4){
      // cout<<i<< " "<<p[i]<<endl;
      P c=p[i]-p[(i+1)%4], d=p[(i+1)%4]-p[(i+2)%4];
      // cout<< c<<" "<<d<<endl;
      // cout<<i<<c<<d<<endl;
      if(c.real()*d.imag()-c.imag()*d.real()>0){
        che+=1;
        // cout<<i<<c<<d<<endl;
      }
      // cout<<a[0]<<" "<<a[1]<<endl;
    }
    cout << ((che<4&&che>0)?"NO":"YES")<<endl;
  }
  return 0;
}


Measured memory_bytes: 3196
/*
Created by Rishu Sahu @ covid 20-20
*/
/*
*****************************************************************
*/

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

#define IOS cin.sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long int
#define pai pair<int,int>
#define pal pair<ll,ll>
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,a,b) for(int i=a;i<=b;i++)
#define ff first 
#define ss second
#define sz(x) (int)x.size()
#define vi vector<int>
#define vl vector<ll>
#define mpl map<ll,ll>
#define mpi map<int,int>
#define pb push_back
#define all(x) x.begin(),x.end()

const int mod = 1e9+7;
const ll INF = INT_MAX;
const int mxm = 3005;

string s,t;
int dp[mxm][mxm];

void solve(){
    cin>>s>>t;
    memset(dp,0,sizeof(dp));
    //dp[0][0]=1;
    int n=s.length();
    int m=t.length();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(s[i-1]==t[j-1])
            dp[i][j]=1+dp[i-1][j-1];
            else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }

    int len=dp[n][m];
    string str="";
    int i=n,j=m;
    while(i&&j){
        if(s[i-1]==t[j-1]){
            str=s[i-1]+str;
            i--;
            j--;
        }else if(dp[i-1][j]>dp[i][j-1])
                i--;
            else j--;
    }
    cout<<str;
}

int main(){
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
}

Measured memory_bytes: 38948
void main() {
	auto ip = readAs!(int[]), A = ip[0], B = ip[1];
	max(A*2-1, B*2-1, A+B).writeln;
}

// ===================================

import std.stdio;
import std.string;
import std.functional;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getInts(N int) []int {
	ret := make([]int, N)
	for i := 0; i < N; i++ {
		ret[i] = getInt()
	}
	return ret
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer([]byte{}, 1000000)
	s := getString()
	ans := true
	if s[0] != 'A' {
		ans = false
	}
	cnt := 0
	if s[1] >= 'A' && s[1] <= 'Z' {
		ans = false
	}
	for i := 2; i <= len(s)-2; i++ {
		if s[i] == 'C' {
			cnt++
		} else if s[i] >= 'A' && s[i] <= 'Z' {
			ans = false
		}
	}
	if s[len(s)-1] >= 'A' && s[len(s)-1] <= 'Z' {
		ans = false
	}

	if cnt != 1 {
		ans = false
	}
	if ans {
		out("AC")
		return
	}
	out("WA")
}


Measured memory_bytes: 1772
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

/* #include <bits/stdc++.h> */

using namespace std;

/* g++ -g -fsanitize=address -lasan -std=c++11 -Dfoo_ */

/* freopen("input.txt", "rt", stdin); */
/* freopen("output.txt", "wt", stdout); */

#define ALL(c)          (c).begin(), (c).end()
#define ALLR(c)         (c).rbegin(), (c).rend()
#define FOR(i,a,b)      for (int i=(a); i < (b); ++i)
#define FORR(i,a,b)     for (int i=(a); i > (b); --i)
#define FOR_ALL(i,c)    for (__typeof((c).begin()) i=(c).begin();   \
                             i != (c).end(); ++i)
#define FOR_ALLR(i,c)   for (__typeof((c).rbegin()) i=(c).rbegin(); \
                             i != (c).rend(); ++i)
#define SZ(array)       (sizeof(array)/sizeof(array[0]))
#define lc(x)           (x<<1)     /* 2*x */
#define rc(x)           (x<<1 | 1) /* 2*x+1 */
#define lowbit(x)       (x & (-x)) /* 0b10100 -> 0b100 */

typedef long long       LL;
typedef map<int,int>    MII;
typedef pair<int,int>   PII;
typedef set<int>        SI;
typedef vector<bool>    VB;
typedef vector<double>  VD;
typedef vector<int>     VI;
typedef vector<string>  VS;

/* check if a key is in container C */
template <class C>
inline bool in_(const typename C::key_type& k, const C& A)
{ return A.find(k) != A.end(); }
inline bool in_(const string& s, const string& S)
{ return S.find(s) != string::npos; }

int main()
{
#ifdef foo_
    freopen("foo", "rt", stdin);
#endif
    int n,m;
    while (cin >> n >> m) {
        map<int,int> cnt;
        FOR(i,1,n+1) {
            int a; cin >> a;
            cnt[a]++;
        }
        FOR(_,0,m) {
            int b,c; cin >> b >> c;
            cnt[c] += b;
        }
        int total = 0; LL ans = 0;
        for (auto i = cnt.rbegin(); total < n; ++i) {
            const LL x = i->first;
            const LL c = min(i->second, n-total);
            ans += x * c; total += c; 
        }
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 9600
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
int n;
const int maxN = 2e5 + 10;
int x[maxN], y[maxN];
struct dsu{
    vector < int > p;
    vector < int > sz;
    vector<int> his_val;
    dsu(int n) {
        p.resize(n);
        sz.resize(n, 1);
        his_val.resize(n);
        iota(p.begin(), p.end(), 0);
    }
    int find(int a) {
        if (a == p[a]) return a;
        return p[a] = find(p[a]);
    }
    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) swap(a, b);
        sz[a] += sz[b];
        p[b] = a;
        return true;
    }
    bool are_connected(int a, int b) {
        return find(a) == find(b);
    }
};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("input.txt", "r", stdin);
    cin >> n;
    vector<pair<int,int>> all;
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
        all.emplace_back(x[i], i);
    }
    dsu D(n);
    sort(all.begin(), all.end());
    vector<pair<int,int>> st;
    for (int i = 0; i < n; i++) {
        int mn = y[all[i].second];
        while (!st.empty() && st.back().first <= y[all[i].second]) {
            D.unite(st.back().second, all[i].second);
            mn = min(mn, st.back().first);
            st.pop_back();
        }
        st.emplace_back(mn, all[i].second);
    }
    for (int c = 0; c < n; c++) {
        cout << D.sz[D.find(c)] << '\n';
    }
    return 0;
}

Measured memory_bytes: 8728
program Takoyaki
    implicit none
    integer n, x, t  !最大個数、個数、時間
    integer s, a, b, c

    read *, n, x, t

    a=n/x
    b=mod(n,x)
    c=0
    if(b/=0) then
        c=1
    end if
    s=t*(a+c)
    print *, s 
end program Takoyaki

Measured memory_bytes: 2796
function extractVal(input) {
  input = input.split("\n");
  const [h,w,k] = input.shift().trim().split(" ").map(v => parseInt(v, 10));
  const rows = new Array(h);
  for (let i=0;i<h;i++) {
  	rows[i] = input[i].trim().split("");
  }
  
  let blacks = 0;
  for (let i=0;i<rows.length;i++) {
  	for (let j=0;j<rows[0].length;j++) {
    	blacks += rows[i][j] === "#" ? 1 : 0;
    }
  }
 
  return {
    h, w, k, rows, blacks
  }
}
 
const copy = (arr) => {
  const rows = new Array(arr.length);
  for (let i=0;i<rows.length;i++) {
    rows[i] = [...arr[i]];
  }
  return rows;
}
 
function Main(input) {
  const {
    h, w, k, rows, blacks
  } = extractVal(input);
  

  
  if (blacks < k) {
  	console.log(0);
    return
  }
  
  let total = 0;
  const paintRow = (arr, r) => {
    let black = 0;
    for (let i=0;i<arr[0].length;i++) {
      if (arr[r][i] === "#") {
        black += 1;
      }
      arr[r][i] = "r";
    }
    return black;
  }
 
  const paintColumn = (arr, c) => {
    let black = 0;
    for (let i=0;i<arr.length;i++) {
      if (arr[i][c] === "#") {
        black += 1;
      }
      arr[i][c] = "r";
    }
    return black;
  }
 
  const traverse = (arr, r, c, left) => {    
      if (r < arr.length) {
        const new1 = copy(arr);
        traverse(new1, r+1, c, left - paintRow(new1, r));
        traverse(arr, r+1, c, left);
      } else if (c < arr[0].length) {
        const new3 = copy(arr);
        traverse(new3, r, c+1, left - paintColumn(new3, c));
        traverse(arr, r, c+1, left);
      } else {
      	if (left == k) total++
      }
  }
 
  traverse(rows, 0, 0, blacks);
  
  console.log(total);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 33628
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, a, b;
    cin >> n >> a >> b;
    cout << min(n * a, b) << endl;
}

Measured memory_bytes: 256
A,B,M = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
X = []
Y = []
C = []
for _ in range(M):
    x,y,c = map(int,input().split())
    X.append(x)
    Y.append(y)
    C.append(c)
ans = min(a) + min(b)
for i in range(M):
    ans = min(ans,a[X[i]-1] + b[Y[i] - 1] - C[i])
print(ans)





Measured memory_bytes: 24620
#include <iostream>
#include <algorithm>
typedef long long ll;
using namespace std;


ll N;
ll a[100001];
void swap(ll *p, ll *q)
{
    ll temp;
    temp = *p; 
    *p = *q;
    *q = temp;
}

void partition(ll p, ll q, ll *jp, ll *ip)
{
    ll i, j, s;
    i = p; j = q; s = a[p];
    while(i <= j){
        while(a[i] < s) i++;
        while(a[j] > s) j--;
        if(i <= j){
            swap(&a[i], &a[j]);
            ++i; --j;
        }
    }
    *jp =j; *ip = i;
}

void qsort(ll p, ll q)
{
    ll i, j;

    if(p < q){
        partition(p, q, &j, &i);
        qsort(p, j);
        qsort(i, q);
    }
}

int main()
{
    cin >> N;
    for (int i = 0; i < N; i++){
        cin >> a[i];
    }
    qsort(0, N-1);
    
    ll h1 = 0, h2 = 0;
    ll i = N-1;
    while(!h1 && i > 0){
        if(a[i] == a[i - 1]){
            h1 = a[i];
            i--;
        }
        i--;
    }
    while(!h2 && i > 0){
        if(a[i] == a[i - 1]){
            h2 = a[i];
        }
        i--;
    }

    cout << h1 * h2 << '\n';

    return 0;
    
}


Measured memory_bytes: 1024