akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#define printjudge(cond) {if(cond) printf("Yes\n"); else printf("No\n");}
#define printans(ans) {printf("%d\n",(ans));}
#define intscan(x) {scanf("%d", &x);}
#define Ntimes(N) for(int i=0; i<N; i++)
#define min(x,y) (((x)<(y)) ? (x) : (y))
#define max(x,y) (((x)>(y)) ? (x) : (y))
typedef int* intarray;
typedef char* string;

int f(char s){
    return (s=='A'||s=='C'||s=='G'||s=='T');
}

int main(){
    char S[11];
    scanf("%s", S);
    int len = strlen(S);
    intarray* c = new intarray[len];
    Ntimes(len) c[i] = new int[len];
    int max = 0;
    for(int i=0; i<len; i++){
        for(int j=i; j<len; j++){
            if(j==i) c[i][j] = f(S[i]);
            else{
                c[i][j] = (c[i][j-1] + 1) * f(S[j]);
            }
            max = max(c[i][j],max);
        }
    }
    printans(max);
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 266666;
int n,k;Vi a[N];int len;
int f(int i, int j){return i*(k-1)+j+1;}
int main() {
	k=37+1;n=k*(k-1)+1;
	for(int i=1;i<n;i+=k-1){
		Vi t;rep(j,i,i+k-2)t.pb(j);t.pb(n);a[++len]=t;
	}
	rep(i,0,k-2)rep(j,0,k-2){
		Vi t;t.pb(f(0,i));rep(c,1,k-1)t.pb(f(c,(j+(c-1)*i)%(k-1)));a[++len]=t;
	}
	assert(len==n);
	printf("%d %d\n",n,k);
	rep(i,1,len){rep(j,0,SZ(a[i])-1)printf("%d ",a[i][j]);puts("");}
	return 0;
}


Measured memory_bytes: 6912
#include<bits/stdc++.h>
#include<cstring>
#include<cmath>
#include<iterator>
#include<cstdlib>
#define IOS   ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ses   "\n"
#define whp   " "
#define mxi 99999

#define rep0(i,a,b) for(int i=a; i<b; i++)
#define rep1(i,a,b) for(int i=a; i<=b; i++)
#define rep0in(i,a,b) for(int i=a-1; i>=b; i--)
#define rep1in(i,a,b) for(int i=a; i>b; i--)
#define repv(i,a) for(auto i=a.begin(); i!=a.end();++i)

///set <int, greater <int> > ::iterator it;
///vector<pair<int,int> >a;
#define MS(a,b) memset(a,b,sizeof(a));

typedef long long ll;
typedef unsigned long long ull;
using namespace std;
ll fx[4]= {1,-1,0,0};
ll fy[4]= {0,0,1,-1};
int smallest(int x, int y, int z)
{
    int c = 0;
    while (x && y && z) {
        x--;
        y--;
        z--;
        c++;
    }
    return c;
}
bool rs(ll a, ll b){
    return(a>b);

    }
int main()
{
string s,t;
cin>>s>>t;
ll c=0;
for( ll i=0; i<s.length(); i++){
    if(s[i]!=t[i])c++;
}
cout<<c<<endl;
return 0;
}



Measured memory_bytes: 3920
#pragma GCC optimize("Ofast")
#pragma GCC target ("avx")
#include <bits/stdc++.h>
constexpr int INF = 2147483647;
constexpr long long int INF_LL = 9223372036854775807;
constexpr int MOD = 1000000007;
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

struct edge {
	ll to;
	ll cost;
};

void dist(vector<vector<edge>>& g, vector<ll>& d, vector<ll>& used, int pos) {
	used[pos] = 1;
	for (int i = 0; i < g[pos].size(); i++) {
		if (!used[g[pos][i].to]) {
			d[g[pos][i].to] = d[pos] + g[pos][i].cost;
			dist(g, d, used, g[pos][i].to);
		}
	}
}

ll diameter(vector<vector<edge>>& g) {
	vector<ll> d(g.size(), 0), u(g.size(), 0);
	dist(g, d, u, 0);
	int p = max_element(d.begin(), d.end()) - d.begin();
	for (int i = 0; i < g.size(); i++)d[i] = u[i] = 0;
	dist(g, d, u, p);
	return *max_element(d.begin(), d.end());
}

int main() {
	int N;
	cin >> N;
	vector<vector<edge>> g(N);
	for (int i = 0; i < N-1; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		g[a].push_back({ b,c });
		g[b].push_back({ a,c });
	}
	cout << diameter(g) << endl;
}


Measured memory_bytes: 14148
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
import math

def input():
    return sys.stdin.readline()


def resolve():
    x = int(input())

    count = 0

    a = 100

    while True:
        a = a * 1.01
        a = math.floor(a)
        count += 1

        if a >= x:
            break

    print(count)


if __name__ == "__main__":
    resolve()



Measured memory_bytes: 63252
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define x first
#define y second

int n, k, l, d1[200005], d2[200005], r1, r2;
map< pair<int, int>, int > M;

int f1(int x) {
	if ( x == d1[x] ) return x;
	return d1[x] = f1(d1[x]);
}

int f2(int x) {
	if ( x == d2[x] ) return x;
	return d2[x] = f2(d2[x]);
}

int main() {
	scanf("%d%d%d", &n, &k, &l);
	for ( int i = 1; i <= n; i++ ) {
		d1[i] = d2[i] = i;
	}
	for ( int i = 1; i <= k; i++ ) {
		scanf("%d%d", &r1, &r2);
		d1[f1(r1)] = f1(r2);
	}
	for ( int i = 1; i <= l; i++ ) {
		scanf("%d%d", &r1, &r2);
		d2[f2(r1)] = f2(r2);
	}	
	for ( int i = 1; i <= n; i++ ) {
		M[mp(d1[f1(i)], d2[f2(i)])]++;
	}
	for ( int i = 1; i <= n; i++ ) {
		printf(i == n?"%d\n":"%d ", M[mp(d1[f1(i)], d2[f2(i)])]);
	}
	return 0;
}

Measured memory_bytes: 16680
#include <iostream>

using namespace std;

int main(){
    int a,b,c,x;
    cin >> a >> b >> c;
    if(a>b){
        x = b;
        b = a;
        a = x;
    }
    if(b>c){
        x = c;
        c = b;
        b = x;
    }
    if(a>b){
        x = b;
        b = a;
        a = x;
    }
    cout << a << " " <<  b << " " <<  c << endl;
    return 0;

}


Measured memory_bytes: 3064
#pragma warning(disable:4996)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#define MAX_LINE 100001

char sLongInputLine[MAX_LINE+1]="";

int main() {

	char* psInput=NULL;
	char* psTemp=NULL;
	char cPrevChar;

	int nLen = 0;
	int nCharChangeCount=0;
	int nCharChangeCountRev=0;
	int i=0;
	int j=0;


	// read line 1
	psTemp = fgets(sLongInputLine,MAX_LINE,stdin);
	if (strchr(sLongInputLine, '\n') != NULL) {
	    sLongInputLine[strlen(sLongInputLine) - 1] = '\0';
	} else {
		while(getchar() != '\n');
	}
	cPrevChar = sLongInputLine[0];
	nLen = strlen(sLongInputLine);

	for (i=1;i<nLen;i++){
		if (cPrevChar != sLongInputLine[i]){
			cPrevChar = sLongInputLine[i];
			nCharChangeCount++;
		}
	}
	cPrevChar = sLongInputLine[nLen-1];
	for (i=nLen-1;i>=0;i--){
		if (cPrevChar != sLongInputLine[i]){
			cPrevChar = sLongInputLine[i];
			nCharChangeCountRev++;
		}
	}
	if(nCharChangeCountRev<nCharChangeCount){
		nCharChangeCount = nCharChangeCountRev;
	}

	printf("%d\n",nCharChangeCount);
	
	return 0;

}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i,b) for(ll i=0;i<b;i++)
#define ll long long
using namespace std;
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vvvl vector<vector<vector<ll>>>
#define debug(x) cerr<<#x<<" "<<x<<'\n';

int main() {
    ll n,x;cin>>n;
    set<ll>a;
    rep(i,n){cin>>x;a.insert(x);}
    cout<<(a.size()%2==0?a.size()-1:a.size())<<endl;
}


Measured memory_bytes: 4992
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
#include <bitset>
#include <functional>
#include <numeric>
#include <ctime>
#include <cassert>
#include <cstring>
#include <fstream>

using namespace std;

#define FOR(i, a, b) for(int (i)=(a);(i)<(b);(i)++)
#define IFOR(i, a, b) for(int (i)=(a);(i)<=(b);(i)++)
#define RFOR(i, a, b) for(int (i)=(a);(i)>=(b);(i)--)
#define REP(i, n) FOR((i), 0, (n))

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<class T>
void print_container(T &container, string delim=" ") {
    bool first = true;
    for(auto &t: container){
        if(!first){
            cout << delim;
        }
        first = false;
        cout << t;
    }
    cout << endl;
}

int main() {
    int m, d;
    cin >> m >> d;

    int cnt = 0;
    for(int i=1;i<=m;i++){
        for(int j=10;j<=d;j++){
            int d1 = j % 10;
            int d2 = j / 10;
            if(d1 >= 2 && d2 >= 2 && d1*d2==i){
                cnt++;
            }
        }
    }
    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 256
fun main(arr:Array<String>) {
    val n = readLine()!!.toInt()
    val score = (1..n).map { readLine()!!.toInt() }
    var ans = score.sum()
    if(ans % 10 == 0) {
        ans -= score.filter { it % 10 != 0 }.min()?:0
    }
    if(ans % 10 == 0) {
        println(0)
    } else {
        println(ans)
    }
}


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

#define MAX 100
#define INFTY (1 << 21)
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n, M[MAX][MAX];

void solve(void) {
    int minv;
    int d[MAX], color[MAX];
    
    for(int i = 0; i < n; ++i) {
        d[i] = INFTY;
        color[i] = WHITE;
    }
    
    d[0] = 0;
    color[0] = GRAY;
    while(true) {
        minv = INFTY;
        int u = -1;
        for(int i = 0; i < n; ++i) {
            if(minv > d[i] && color[i] != BLACK) {
                u = i;
                minv = d[i];
            }
        }
        if(u == -1) break;
        color[u] = BLACK;
        for(int i = 0; i < n; ++i) {
            if(color[i] != BLACK && M[u][i] != INFTY) {
                if(d[i] > d[u] + M[u][i]) {
                    d[i] = d[u] + M[u][i];
                    color[i] = GRAY;
                }
            }
        }
    }
    for(int i = 0; i < n; ++i) {
        cout << i << ' ' << (d[i] == INFTY ? -1 : d[i]) << endl;
    }
}

int main(void) {
    cin >> n;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            M[i][j] = INFTY;
        }
    }
    
    int k, c, u, v;
    for(int i = 0; i < n; ++i) {
        cin >> u >> k;
        for(int j = 0; j < k; ++j) {
            cin >> v >> c;
            M[u][v] = c;
        }
    }
    
    solve();
    
    return 0;
}


Measured memory_bytes: 3128
#include<stdio.h>
#include<stdlib.h>
int cmp(const void *a, const void *b){return *(int*)a - *(int*)b;}
int min(int a, int b){return a < b ? a : b;}
int main(){
    int x, n;
    scanf("%d%d",&x,&n);
    if(n == 0){
        printf("%d\n",x);
        return 0;
    }
    int p[n];
    for(int i = 0;  i < n; i++)
        scanf("%d",&p[i]);
    int q[101];
    for(int i = 0; i <= 100; i++)
        q[i] = 0;
    qsort(p,n,4,cmp);
    for(int i = 0; i < n; i++)
        q[p[i]] = 1;
    int di = 11110;
    int ans = 0;
    if(x < p[0] || x > p[n - 1])
        ans = x;
    else{
        for(int i = 0; i < 102; i++){
            if(!q[i]){
                int d = abs(i - x);
                if(di > d){
                    di = d;
                    ans = i;
                }
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 1732
<?php
# 整数の入力
fscanf(STDIN, "%d", $n);

$ans = array_fill(1, $n, 0);
$num = (int)sqrt($n);
for ($x = 1; $x <= $num; $x++) {

    for ($y = 1; $y <= $num; $y++) {

        for ($z = 1; $z <= $num; $z++) {
            $result = ($x ** 2) + ($y ** 2) + (($z + $x) * ($z + $y));
            if ($result <= $n) {
                $ans[$result] ++;
            }
        }
    }
}
for ($j = 1; $j <= $n; $j++) {
    echo $ans[$j]."\n";
}
?>

Measured memory_bytes: 16468
#include<iostream>
#include<vector>
#include<queue>

using namespace std;
  
#define NOT -100000*2100
#define VMAX 100
#define EMAX 9900

int main(void){
	
	int V,E;
	int s,t,d;
	long long v[VMAX][VMAX];
	int cnt;
	vector<int> ed[VMAX];
	vector<int> edco[VMAX];
	queue<int> no;

	cin>>V>>E;

	for(int i=0;i<V;i++){
		for(int j=0;j<V;j++){
		v[i][j]=NOT;
		}
	}
;
	for(int i=0;i<E;i++){
		cin>>s>>t>>d;
		ed[s].push_back(t);
		edco[s].push_back(d);
	}

	for(int r=0;r<V;r++){
		no.push(r);
		v[r][r]=0;
		cnt=0;
		while(!no.empty()){
			if(cnt>EMAX*10){
				cout<<"NEGATIVE CYCLE"<<endl;
				return 0;
			}
			for(int i=0;i<ed[no.front()].size();i++){
				if(v[r][no.front()]+edco[no.front()][i]<v[r][ed[no.front()][i]]||v[r][ed[no.front()][i]]==NOT){
					v[r][ed[no.front()][i]]=v[r][no.front()]+edco[no.front()][i];
					cnt++;
					no.push(ed[no.front()][i]);
				}
			}
			no.pop();
		}
	}
	for(int i=0;i<V;i++){
		for(int j=0;j<V;j++){
			if(v[i][j]!=NOT) cout<<v[i][j];
			else cout<<"INF";
			if(j==V-1) cout<<endl;
			else cout<<" ";
		}
	}
}

Measured memory_bytes: 1404
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
sm = 0
for i in range(1,n+1):
    if i%3 != 0 and i%5 != 0:
        sm += i
print(sm)


Measured memory_bytes: 64540
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<string>
#include<set>

const long long int MOD=1e9+7;

using namespace std;

int main(){
    long long int n,k,a[200009],to[200009];
    map<long long, long long > m;
    set<long long > S;
    cin >> n >> k;
    for(int i=0;i<n;i++){
        cin >> a[i];
        to[m[a[i]]] = i;
        m[a[i]] = i;
    }
    for(int i=0;i<n;i++){
        to[m[a[i]]] = i;
        m[a[i]] = i;
    }
    long long cur=0, cnt=0;
    while(1){
        long long next = to[cur];
        if(next<=cur)cnt++;
        if(next==n-1){
            break;
        }
        cur=next+1;
    }
    cnt++;
    k %= cnt;

    cur = 0;
    while(1){
        if(cnt==1){
            break;
        }
        if(k>1){
            long long next = to[cur];
            if(next<=cur)k--;
            cur = next+1;
        }
        if(k==1){
            while(1){
                long long next = to[cur];
                if(next<=cur){
                    cout << a[cur] << ' ';
                    cur++;
                }
                else{
                    cur = next+1;
                }
                if(cur==n-1){
                    cout << a[n-1];
                }
                if(cur>=n-1)break;
            }
            break;
        }
    }
    cout << endl;
}


Measured memory_bytes: 17152
#include <iostream>
 
int main()
{
  int n;
  std::cin >> n;
  int As[n], Bs[n-1];
  for(int i=0; i<n-1; i++)
    std::cin >> Bs[i];
  
  As[0] = As[1] = Bs[0];
  for(int i=1; i<n-1; i++){
    if(Bs[i] < As[i]) As[i] = Bs[i];
    As[i+1] = Bs[i];
  }
  int sum = 0;
  for(int i=0; i<n; i++)
    sum += As[i];
  
  std::cout << sum;
}

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

void call(int n){
    for (int i = 1; i <= n; i++)
        if ( i % 3 == 0 )
            cout << " " << i;
        else
            for (int x = i; x ; x /= 10)
                if ( x % 10 == 3 ){
                    cout << " " << i;
                    break;
                }
}

int main(void)
{
    int n;
    cin >> n;

    call(n);
    cout << endl;

    return 0;
}



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

int main() {
  string s, t;
  cin >> s >> t;
  int ans = 0;
  for(int i = 0; i < 3; i++){
    if(s.at(i) == t.at(i))
      ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> Pll;
typedef pair<P,P> PP;
#define rep(i,a,n) for(int i = a;i < n;i++)
#define LINF (ll)1e17
#define INF 1e9
#define MOD 1e9+7
#define sMOD 1e5
#define fs first
#define sc second

ll gcd(ll a,ll b){
	if(!b) return a;
	return gcd(b,a%b);
}


signed main(){
	
	ll cnt[4] = {0};
	ll memo = 0;
	
	rep(i,0,6){
		cin >> memo;
		if(cnt[memo-1] >= 2){
			cout << "NO" << endl;
			return 0;
		}
		else{
			cnt[memo-1]++;
		}
	}
	
	cout << "YES" << endl;
	return 0;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e3+4;
const int MOD = 1e9+7;
int mpow(int x,int y)
{
	if(y<=0) return 1;
	if(y&1) return (x*mpow(x,y-1)%MOD)%MOD;
	return mpow((x*x)%MOD,y/2)%MOD;
}

int32_t main(){
	cin.tie(0)->sync_with_stdio(0);
	#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	#endif
	int n;
	cin>>n;
	cout<<(mpow(10,n)-2*mpow(9,n)+mpow(8,n)+2*MOD)%MOD;
} 

// nc1*(n-1)c1*9^(n-2)



Measured memory_bytes: 3612
import math
a = []
a = input().split()
N = int(a[0])
M = int(a[1])

#print('N=', N, 'M=', M)

if N < 2 and M < 2:
  T = 0
if N < 2 and M > 1:
  T = math.factorial(M) // (math.factorial(M - 2) * math.factorial(2))
if M < 2 and N > 1:
  T = math.factorial(N) // (math.factorial(N - 2) * math.factorial(2))
if N > 1 and M > 1:
  T = math.factorial(N) // (math.factorial(N - 2) * math.factorial(2)) + math.factorial(M) // (math.factorial(M - 2) * math.factorial(2))

print(T)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=100003,INF=1<<30;

int main(){
    
    string S;cin>>S;
    map<string,int> MA;
    MA["SUN"]=7;
    MA["MON"]=6;
    MA["TUE"]=5;
    MA["WED"]=4;
    MA["THU"]=3;
    MA["FRI"]=2;
    MA["SAT"]=1;
    
    cout<<MA[S]<<endl;
}



Measured memory_bytes: 256
import sys
n,k=map(int,input().split())
h=[int(i) for i in sys.stdin]
h.sort()
s=[0]
for i in range(n-1):
  s.append(h[i+1]-h[i])
ans=[sum(s[:k])]
for i in range(n-k):
  ans.append(ans[-1]+s[i+k]-s[i+1])
print(min(ans))

Measured memory_bytes: 15128
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T> void assign(V<T>& v, int n, const T& a = T()) { v.assign(n, a); }
template<class T, class... U> void assign(V<T>& v, int n, const U&... u) { v.resize(n); for (auto&& i : v) assign(i, u...); }

int main() {
  cin.tie(NULL); ios::sync_with_stdio(false);
  int n, m, k; cin >> n >> m >> k;
  for (int i = 0; i < n + 1; i++) for (int j = 0; j < m + 1; j++) {
    if (j * (n - i) + i * (m - j) == k) return cout << "Yes" << '\n', 0;
  }
  cout << "No" << '\n';
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
int main(void){
    long int n,k;
    scanf("%ld %ld",&n,&k);
    int i=0,a=0;
    while(pow(k,i)<=n){
        i++;
    }
    printf("%d\n",i);
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#define rep(i, n) for (int i = 0; i < (n); i++)
const long long MOD = 1000000007;
using namespace std;
typedef long long ll;
map<ll, int> mp;
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	ll nfa = 1;
	ll mfa = 1;
	for (int i = 1; i <= n; i++) {
		nfa *= i;
		nfa %= MOD;
	}
	for (int i = 1; i <= m; i++) {
		mfa *= i;
		mfa %= MOD;
	}
	if (abs(n - m) >= 2) {
		cout << 0 << endl;
	}
	else if (abs(n - m) == 1){
		cout << ((nfa % MOD) * (mfa % MOD)) % MOD << endl;
	}
	else {
		cout << ((nfa % MOD) * (mfa % MOD) * 2) % MOD << endl;
	}
	return 0;
}

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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair
#define F first
#define S second

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


int main() {
    i64 N; cin >> N;
    i64 T, A; cin >> T >> A;
    vector<i64> H(N);
    REP(i, N) cin >> H[i];

    i64 mini;
    i64 mind = numeric_limits<i64>::max();
    auto temp = [&](i64 h) {
        return 1000 * T - h * 6;
    };
    REP(i, N) {
        if (chmin(mind, abs(1000 * A - temp(H[i])))) {
            mini = i;
        }
    }

    cout << (mini + 1) << endl;

    return 0;
}

Measured memory_bytes: 3660
#include <stdio.h>
int main(){
	int x,y,d,tmp;
	
	scanf("%d %d",&x,&y);
	
	if(x<y){
	    tmp=x;
	    x=y;
	    y=tmp;
	}
	
	while(y>0){
		d=x%y;
		x=y;
		y=d;
	}
	
	printf("%d\n",x);
	
	return 0;
}


Measured memory_bytes: 2756
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long N;
  cin>>N;
  long long a=0;
  long long b=0;
  long long c=0;
  for(int i=0;i<N;i++){
    string d;
    cin>>d;
    if(d=="AC"){
      a+=1;
    }
    else if(d=="WA"){
      b+=1;
    }
    else if(d=="TLE"){
      c+=1;
    }
  }
  cout<<"AC x "<<a<<endl;
  cout<<"WA x "<<b<<endl;
  cout<<"TLE x "<<c<<endl;
  cout<<"RE x "<<N-a-b-c<<endl;
}
    


Measured memory_bytes: 3624
#include<iostream>
#include <algorithm>
#include <functional>
using namespace std;

long long get_attack_num(long long HP);

int main(){
  long long H;
  cin >> H;

  long long attack_num = get_attack_num(H);
  
  cout << attack_num << endl;

}


long long get_attack_num(long long HP){
  long long attack_num;

  if (HP == 1){
    return 1;
  } else {
    long long half_HP = (long long) (HP/2);
    return 2*get_attack_num(half_HP) + 1;
  }

}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        
        Scanner sc = new Scanner(System.in);
        
        String b = sc.next();
        
        switch(b){
            
            case "A":
                System.out.println("T");
                break;

            case "T":
                System.out.println("A");
                break;

            case "G":
                System.out.println("C");
                break;

            case "C":
                System.out.println("G");
                break;
        }
    }
}


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

#define REP(i, e) for(int (i) = 0; (i) < (e); ++(i))
#define FOR(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define ALL(c) (c).begin(), (c).end()
#define SIZE(x) ((int)(x).size())
#define MIN(c) (*min_element(ALL(c))) 
#define MAX(c) (*max_element(ALL(c)))
#define ACC(c) (accumulate(ALL(c), 0))
#define SLL(x, n) ((x) << (n))
#define SRL(x, n) ((x) >> (n))
#define MIN2(a, b) ((a) < (b)) ? (a) : (b)
#define MAX2(a, b) ((a) > (b)) ? (a) : (b)
#define MP(a, b) (make_pair((a), (b)))
#define ENDL "\n"
#define PRINT(x) cout << (x) << ENDL

using namespace std;
using ll = long long;
using pint = pair<int, int>;

inline int in(int& a) {return scanf("%d", &a);}
inline void out(int n) {printf("%d\n", n);}
auto pint_compare = [](pint x, pint y) -> bool{return (x.first < y.first);};


signed main(){
    string S;
    cin >> S;
    int len = S.length();
    int cnt = 0;
    REP(i, len){
        if(S[i] == 'x') cnt++;
    }
    if(cnt <= 7) PRINT("YES");
    else PRINT("NO");
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
#define MAX 251

class Node
{
public:
	Node(int K,Node* PARENT)
	{
		key = K;
		parent = PARENT;
	}
	int key;
	Node* parent = 0;
	Node* right = 0;
	Node* left = 0;
};

class Tree
{
public:
	Tree() { for (int i = 0; i < MAX; i++) { nodes[i] = 0; } }
	Node* CreateNode(int ID, int K, Node* PARENT){return nodes[ID] = new Node(K,PARENT);}
	Node* node_root = 0;
	Node* nodes[MAX];
	void print()
	{
		for (int i = 1; i < MAX; i++)
		{
			if (nodes[i] == 0)break;
			cout << "node " << i << ": key = " << nodes[i]->key << ", ";
			if (nodes[i]->parent != 0)cout << "parent key = " << nodes[i]->parent->key << ", ";
			if(nodes[i]->left != 0)cout << "left key = " << nodes[i]->left->key << ", ";
			if(nodes[i]->right != 0)cout << "right key = " << nodes[i]->right->key << ", ";
			cout << endl;
		}
	}
};

int main()
{
	int n;
	cin >> n;
	Tree T;
	int k;
	cin >> k;
	T.node_root=T.CreateNode(1, k, 0);
	if (2 <= n)T.node_root->left = T.nodes[2];
	if (2 + 1 <= n)T.node_root->right = T.nodes[2 + 1];
	for (int i = 2; i <= n; i++)
	{
		cin >> k;
		Node* temp;
		temp=T.CreateNode(i, k, T.nodes[i / 2]);
	}	 	
	for (int i = 1; i <= n; i++)
	{
		if (i * 2 <= n)T.nodes[i]->left = T.nodes[i * 2];
		if (i * 2+1 <= n)T.nodes[i]->right = T.nodes[i * 2+1];
	}
	T.print();
	return 0;
}

Measured memory_bytes: 3056
n = int(input())
s = input()


en = s.count('E')

ans = en if s[0]=='W' else en -1


wc = 0
for i in range(1,len(s)):
    if s[i-1] == 'W':
        wc += 1
    else:
        en -= 1

#    print('wc = {}, en = {}'.format(wc,en))
    ans = min(ans, en + wc - (1 if s[i] == 'E' else 0 ) )

print(ans)
    

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

 
int main() {

    int n;
    cin>>n;
    vector<tuple<string,int,int>> p(n);
    rep(i,n) {
        string a;
        int b;
        cin>>a>>b;
        p.at(i)=make_tuple(a,-b,i+1);
    }

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

    rep(i,n) {
        cout<<get<2>(p.at(i))<<endl;
    }

 return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
typedef long long ll;
#define all(x) (x).begin(), (x).end()  // sortなどの引数を省略
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define max3(x, y, z) max(x, max(y, z))

#ifdef _MSC_FULL_VER  //デバッグ出力
#define dout cout
#define debug() if (true)
#define check(x) std::cout << "★" << #x << "の値:" << (x) << endl
#define pass(x) std::cout << "☆" << x << endl
#else
#define dout \
  if (false) cout
#define debug() if (false)
#define check(x) \
  if (false) cout << "★" << #x << "の値:" << (x) << endl
#define pass(x) \
  if (false) cout << "☆" << x << endl
#endif
using namespace std;
int main() {
  ll A;
  cin >> A;
  if (A > 4000) {
    cout << 1;
    return 0;
  }
  rep(i, A/100+1) {
    rep(j, A / 100 + 1) {
      rep(k, A / 100 + 1) {
        rep(l, A / 100 + 1) {
          rep(m, A / 100 + 1) {
            rep(n, A / 100 + 1) {
              if (i * 100 + j * 101 + k * 102 + l * 103 + m * 104 + n * 105 == A) {
                cout << 1;
                return 0;
              }
            }
          }
        }
      }
    }
  }
  cout << 0;
  return 0;
}
/*
//よく使うやつ
int N;
cin >> N;
vector<int> list(N);
for (int i = 0; i < N; i++) {
cin >> list[i];
}
// for文
for (int i = 0; i < N; i++) {
}
//配列
vector<int> list;
list.at(i)
vector<vector<int>> list(10, vector<int>(10));
sort(all(list));
sort(all(list), greater<int>());
  //配列の内容表示
dout << "====listの内容====\n";
for (int i = 0; i < N; i++) dout << list[i] << endl;
dout << "====ここまで====\n";
*/


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,a,b[2];
int main()
{
	scanf("%d",&n),b[0]=b[1]=0;
	for(int i=1;i<=n;i++) scanf("%d",&a),b[a%2]++;
	if(!b[0]||!b[1]) return puts("0"),0;
	else if(b[1]%2) return printf("%d\n",n-1),0;
	else return printf("%d\n",n-2),0;
}


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

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<pair<int, int> > vpii;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
#define INF 1000000000000000LL
#define MOD 1000000007
#define EPSILON 0.00001
#define f first
#define s second
#define pb push_back
#define mp make_pair

#define FOR(i, a, b) for (int i=(a); i<=(signed)(b); i++)
#define F0R(i, a) for (int i=0; i<(signed)(a); i++)
#define RFOR(i, a, b) for (int i=(a); i >= b; i--)

#define MN 200005
string s;

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

    cin >> s;
    int cnt = 0;
    F0R(i, s.length()){
        if(i != s.length()-1 && s[i] == s[i+1]){
            if(i == s.length()-2){
                cnt++;
                break;
            }
            cnt += 2;
            i += 2;
        } else{
            cnt++;
        }
    }

    cout << cnt << "\n";
    
    return 0;
}


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

using namespace std;

int main(){
  int n;
  cin >> n;
  int h_prev;
  cin >> h_prev;
  int h;
  int count = 0;
  int count_max = 0;
  for(int i = 1; i < n; i++){
    cin >> h;
    if(h <= h_prev){
      count++;
    }else{
      if(count_max < count){
        count_max = count;
      }
      count = 0;
    }
    h_prev = h;
  }
  if(count_max < count){
    count_max = count;
  }
  
  cout << count_max << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <stack>
using namespace std;
static const int N=101;
static const int WHITE=0;
static const int GRAY=1;
static const int BLACK=2;

int M[N][N]={0};
int n;
int color[N]={WHITE},one[N],two[N];
int tt=0,aaa[N]={1};

int next(int num){
    for(int i=aaa[num];i<=n;i++){
        aaa[num]=i+1;
        if(M[num][i]) return i;
    }
    return -1;
}

void dfs_visit(int r){
    stack<int> S;
    S.push(r);
    color[r]=GRAY;
    one[r]=++tt;
    
    while(!S.empty()){
        int u=S.top();
        int v=next(u);
        if(v!=-1){
            if(color[v]==WHITE){
                color[v]=GRAY;
                one[v]=++tt;
                S.push(v);
            }
        }else{
            S.pop();
            color[u]=BLACK;
            two[u]=++tt;
        }
    }
}

void dfs(){
    for(int i=1;i<=n;i++){
        if(color[i]==WHITE) dfs_visit(i);
    }
    for(int i=1;i<=n;i++){
        cout << i << " " << one[i] << " " << two[i] << endl;
    }
}




int main(void){
    cin >> n;
    for(int i=0;i<n;i++){
        int u,k;
        cin >> u >> k;
        for(int j=0;j<k;j++){
            int v;
            cin >> v;
            M[u][v]=1;
        }
    }
    
    dfs();

    return 0;
}










Measured memory_bytes: 3108
/* 1130: Red and Black */
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <algorithm>
#include <functional>

using namespace std;

#define rep(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

#define MAX_W 20
#define MAX_H 20

using namespace std;

/* 隣接タイルへの移動用配列 */
int move[4][2] = {{1,0},{0,-1},{-1,0},{0,1}};
char tiles[MAX_H][MAX_W]; /* タイルの並びを入れる配列 */
int w,h; /* 床の幅、高さ */
int sum; /* 移動可能なタイル数 */

int i,j,k,l,m,n;

int dfs(int y, int x) {

//  rep(i,h){ rep(j,w) cout << tiles[i][j]; cout << endl; } cout << endl;
	for(int i=0; i<4; i++) {
		int nx = x+move[i][0], ny = y+move[i][1];
		
		if(
			/* 床の範囲内で */
			0<=nx&&nx<w &&
			0<=ny&&ny<h &&
			/* 黒いタイルだったら */
			tiles[ny][nx] == '.'
		) {
			/* 二重カウントしないよう予め書き換え */
			tiles[ny][nx] = '#';
			sum++;
			dfs(ny,nx);
		}
	}
	return 0;
}

int main(void) {
	
	int yy,xx;
	
	while(1) {
		
		cin >> w >> h;
		if(w==0 && h==0) break;
		
		for(int i=0; i<h; i++) {
			for(int j=0; j<w; j++) {
				cin >> tiles[i][j];
			}
		}

//    rep(i,h){ rep(j,w) cout << tiles[i][j]; cout << endl; } cout << endl;
//    cout << "before xx " << xx << endl;
//    cout << "before yy " << yy << endl;
		
		/* @の位置を探す */
		for(yy=0; yy<h; yy++) {
//      cout << 'a' << endl;
			for(xx=0; xx<w; xx++) {
//        cout << 'b' << endl;
				if(tiles[yy][xx] == '@') break;
			}
//      cout << "yy " << yy << "xx " << xx << "tile " << tiles[yy][xx] << endl;
			if(0 <= yy && yy < h && 0 <= xx && xx < w && tiles[yy][xx] == '@') break;
		}

//    cout << "xx " << xx << endl;
//    cout << "yy " << yy << endl;
		
		sum = 1;
		dfs(yy,xx);
		
		cout << sum << endl;
	}
	
	return 0;
}

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

int main(){
    ll n;
    cin >> n;
    ll ans =0;
    for(int i=1;i<=n;i++){
        if(i%3!=0 and i%5!=0) ans+=i;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3636
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>

int my_gets(char *buf,int nBuf,FILE *fp){
    int ch;

    while(--nBuf >0){
        ch=getc(fp);
        if(ch==EOF || ch=='\n')
            break;
        *(buf++)=(char)ch;
    }
    *(buf)='\0';

    return nBuf;
}

int main(){
    long long N,M,z;

    scanf("%lld %lld",&N,&M);

    if(2*N > M){
        z=0;
    }
    else{
        z=(M-2*N)/4;
    }
    printf("%lld\n", (N+z < (M-2*z)/2) ? (N+z) : ((M-2*z)/2) );

    return 0;
}

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

using namespace std;

#define REP(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

const int oo = 0x3f3f3f3f;

const int maxn = 100100;

int n;
int a[maxn + 5];

int main()
{
#ifdef matthew99
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	scanf("%d", &n);
	REP(i, 0, n) scanf("%d", a + i);
	a[n] = 1;
	LL l = 2, r = 2;
	for (int i = n - 1; i >= 0; --i)
	{
		l = l * a[i + 1], r = r * a[i + 1] + a[i + 1] - 1;
		l = (l + a[i] - 1) / a[i];
		r = r / a[i];
	}
	if (l > r) puts("-1");
	else cout << l * a[0] << ' ' << r * a[0] + a[0] - 1 << endl;
	return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int maxn=2e3+5;
const ll p=998244353;

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


Measured memory_bytes: 256
n, k = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort(key=abs, reverse=1)

mod = 10**9+7
ans = 1
sign = 1
for i in range(k):
    ans *= a[i]
    ans %= mod
    if a[i] < 0:
        sign *= -1
    elif a[i] == 0:
        sign = 0
if sign >= 0:
    print(ans)
else:
    t = None
    ok = True
    for i in reversed(range(k)):
        if a[i] < 0:
            break
    else:
        ok = False
    for j in range(k, n):
        if a[j] > 0:
            break
    else:
        ok = False

    if ok:
        t = (a[i], a[j])

    ok = True
    for i in reversed(range(k)):
        if a[i] > 0:
            break
    else:
        ok = False
    for j in range(k, n):
        if a[j] < 0:
            break
    else:
        ok = False

    if ok:
        if t is None:
            t = (a[i], a[j])
        else:
            if (t[1]*a[i] - t[0]*a[j]) * t[0]*a[j] < 0:
                t = (a[i], a[j])

    if t is None:
        ans = 1
        a.reverse()
        for i in range(k):
            ans *= a[i]
            ans %= mod
        print(ans)
    else:
        print(ans*t[1] * pow(t[0], mod-2, mod) % mod)


Measured memory_bytes: 31780
#include<iostream>
#include<string>
using namespace std;
int main(){
  int n;
  cin >>n;
  while(n--){
    string one,two,ans;
    cin >>one>>two;
    int os = one.size()-1, ts = two.size()-1;
    int ls = (os>ts)?os:ts;
    int t = 0;
    for(int i=0; i<=ls; i++){
      if(i<=os && i<=ts){t = one[os-i]+two[ts-i]-'0'*2+t/10;}
      else if(i<=os){t = one[os-i]-'0'+t/10;}
      else if(i<=ts){t = two[ts-i]-'0'+t/10;}
      ans+=(t%10)+'0';
    }
    if(t/10){ans+='1';}
    if(ans.size()>80){cout <<"overflow"<<endl;}
    else{
      for(int i=ans.size()-1; i>=0; i--){
	cout <<ans[i];
      }
      cout <<endl;
    }
  }
  return 0;
}

Measured memory_bytes: 0
#include <algorithm>
#include <bits/stdc++.h>
#include <cstdint>
#include <iostream>
#include <iterator>
#include <vector>

// lib/util.hpp
#ifndef UTIL_HPP
#define UTIL_HPP


typedef std::int_fast64_t i64;
typedef std::uint_fast64_t u64;
typedef std::int_fast32_t i32;
typedef std::uint_fast32_t u32;

namespace tools {
  template <typename T>
  void read(std::vector<T>& vector, const typename std::vector<T>::size_type size) {
    vector.reserve(size);
    std::copy_n(std::istream_iterator<T>(std::cin), size, std::back_inserter(vector));
  }

  template <typename T, std::size_t N>
  void read(std::array<T, N>& array) {
    std::copy_n(std::istream_iterator<T>(std::cin), N, array.begin());
  }
}

#endif

// main.cpp

int main() {
  i64 N;
  std::cin >> N;
  std::vector<i64> A;
  tools::read(A, N);

  std::vector<i64> answers(N);
  answers[N - 1] = A[N - 1];
  for (i64 i = 0; i < N - 1; i += 2) {
    answers[N - 1] -= A[i];
  }
  for (i64 i = 1; i < N - 1; i += 2) {
    answers[N - 1] += A[i];
  }

  for (i64 i = N - 2; i >= 0; --i) {
    answers[i] = 2 * A[i] - answers[i + 1];
  }

  std::string delimiter = "";
  for (const i64& answer : answers) {
    std::cout << delimiter << answer;
    delimiter = " ";
  }
  std::cout << std::endl;
  return 0;
}

Measured memory_bytes: 2944
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
 
#define rep(i,n) for(int i = 0;i<n;i++)
const long long MOD = 1000000007;

int main(){
  int n;cin >> n;
  int even = 0;
  int odd = 0;
  rep(i,n){
    int ai;cin >> ai;
    if(ai % 2 == 0) even++;
    else odd++;
  }
  if(odd % 2 == 0){
    cout << "YES" << "\n";
  }else{
    cout << "NO" << "\n";
  }
}


Measured memory_bytes: 256
var
	T,i:Longint;
	A,B,C,D,G:int64;
function gcd(a,b:int64):int64;
begin
	if b=0 then gcd:=a else gcd:=gcd(b,a mod b);
end;
begin
	read(T);
	for i:=1 to T do begin
		read(A,B,C,D);
		G:=gcd(B,D);
		if(B>A)or(B>D)or(B>((-A-1)mod G+G)mod G+C+1)then writeln('No')else writeln('Yes');
	end;
end.

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
int n, m;
cin >> n >> m;
vector<ll> a(n);
for(int i = 0; i< n; i++) cin >> a[i];
sort(a.begin(), a.end());
vector<pair<ll, int>> p(m);
for(int i = 0; i< m; i++){ 
cin >> p[i].second >> p[i].first;
}
sort(p.begin(), p.end());
reverse(p.begin(), p.end());
vector<ll> d;
for(int i = 0; i< m; i++){
   for(int j = 0; j < p[i].second;j++){
             d.push_back(p[i].first);
             if(d.size()> n) break;
         }
}
int k = d.size();
for(int i =0; i< min(k,n); i++)a[i]=max(a[i],d[i]);
ll sum = 0;
for(int i=0; i< n; i++) sum += a[i];

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

Measured memory_bytes: 7720
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
using namespace std;

const int A = 2 * 3600; 

void solve( int s ) {

  int a = s / 3600;
  int b = s / 60 % 60;
  int c = s % 60;
  
  printf("%02d:%02d:%02d\n", a, b, c);
}

int main() {
  int h, m, s;
  while(cin >> h >> m >> s && h >= 0 ) {
    int a = h*3600 + m*60 + s;
    int aa = A - a;

    solve( aa );
    solve( aa*3 );
  }
  
  return 0;
}

Measured memory_bytes: 1160
#include <algorithm>
#include <bitset>
#include <cmath>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <unordered_map>
#include <unordered_set>
using namespace std;

#define ABS(a) (((a) >= 0) ? (a) : -(a))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) > (b) ? (b) : (a))
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define RFOR(i, a, b) for (int i = (a); i >= (b); --i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define NINTH_POWER_OF_TEN 1000000000
#define int long long

typedef long long ll;
typedef pair<int, int> Pair;

const int kMaxN = 500;
const int kMaxC = 30;

int N, C;
int D[kMaxC][kMaxC];
int c[kMaxN][kMaxN];
int ans = NINTH_POWER_OF_TEN;

int cost[3][kMaxC];

signed main() {
  cin >> N >> C;
  REP(i, C) { REP(j, C) { cin >> D[i][j]; }}
  REP(i, N) {
    REP(j, N) {
      int cc;
      cin >> cc;
      c[i][j] = cc-1;
    }
  }

  REP(i, N) {
    REP(j, N) {
      REP(k, C) {
        cost[(i+j)%3][k] += D[c[i][j]][k];
      }
    }
  }

  REP(i, C) {
    REP(j, C-1) {
      REP(k, C-2) {
        ans = MIN(
          ans,
          cost[0][i] + cost[1][(i+j+1)%C] + cost[2][(i+(j+k+1)%(C-1)+1)%C]
        );
      }
    }
  }

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 2176
# -*- coding: utf-8 -*-
N = int(input())
pairs = []
for i in range(N):
    tmp = input()
    pairs.append([int(a) for a in tmp.split()])

pos_and_vals = []
for i, (from_, to_) in enumerate(pairs):
    pos_and_vals.append(((i, 0), from_))
    pos_and_vals.append(((i, 1), to_))

pos_and_vals_sorted = sorted(pos_and_vals, key=(lambda x: x[1]))
pos_and_vals_sorted_toN = pos_and_vals_sorted[:N]

directions = [[False, False] for _ in range(N)]
for (i, direction), val in pos_and_vals_sorted_toN:
    directions[i][direction] = True

smallest_sum = sum([val for (i, direction), val in pos_and_vals_sorted_toN])
first_direction = pos_and_vals_sorted[0][0][1]
if all([direction == first_direction for (i, direction), val in pos_and_vals_sorted_toN]):
    # if all to or all from
    # let it go
    answer = smallest_sum
elif any([(not direction[0]) and (not direction[1]) for direction in directions]):
    # if x exists and x is unused, then let it go
    answer = smallest_sum
else:
    highest_inner = pos_and_vals_sorted[N-1]
    lowest_outer = pos_and_vals_sorted[N]
    if highest_inner[0][0] != lowest_outer[0][0]:
        # replace and make it unused
        answer = smallest_sum - highest_inner[1] + lowest_outer[1]
    elif all([direction == lowest_outer[0][1]
              for (i, direction), val in pos_and_vals_sorted_toN[:N-1]]):
        # if all except target is all the same direction, then let it go
        answer = smallest_sum - highest_inner[1] + lowest_outer[1]
    else:
        assert N >= 2
        # candidates are only two
        second_highest_inner = pos_and_vals_sorted[N-2]
        second_lowest_outer = pos_and_vals_sorted[N + 1]
        candidate_one = smallest_sum - second_highest_inner[1] + lowest_outer[1]
        candidate_two = smallest_sum - highest_inner[1] + second_lowest_outer[1]
        answer = min(candidate_one, candidate_two)

print(answer)









Measured memory_bytes: 67644
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for(int i = a; i < b; i++)
#define rrep(i, a, b) for(int i = b - 1; i >= a; i--)
#define ALL(a) a.begin(), a.end()
#define pii pair<int,int>
#pragma GCC optimize("Ofast")
#define pcnt __builtin_popcount
#define buli(x) __builtin_popcountll(x)
#define pb push_back
#define mp make_pair
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
template<class T>bool chmax(T &a, const T &b) {if(a<b){a = b; return 1;} return 0; };
template<class T>bool chmin(T &a, const T &b) {if(a>b){a = b; return 1;} return 0; };
inline void IN(void){return;}
template <typename First, typename... Rest> void IN(First& first, Rest&... rest){cin >> first;IN(rest...);return;}
inline void OUT(void){cout << "\n";return;}
template <typename First, typename... Rest> void OUT(First first, Rest... rest){cout << first << " ";OUT(rest...);return;}
const double EPS = 1e-9;
const int mod = 1e9 + 7;
const int INF = 1e9;
const long long LLINF = 1e18;
long long lcm(ll a, ll b){return a * b / __gcd(a,b);}
struct IoSetup { IoSetup() {
    cin.tie(nullptr);ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
} } iosetup;
template< int mod > struct ModInt {
    int x; ModInt() : x(0) {}
    ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
    ModInt &operator+=(const ModInt &p) {if((x += p.x) >= mod) x -= mod;return *this;}
    ModInt &operator-=(const ModInt &p) {if((x += mod - p.x) >= mod) x -= mod;return *this;}
    ModInt &operator*=(const ModInt &p) {x = (int) (1LL * x * p.x % mod);return *this;}
    ModInt &operator/=(const ModInt &p) {*this *= p.inverse();return *this;}
    ModInt operator-() const { return ModInt(-x); }
    ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
    ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
    ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
    ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
    bool operator==(const ModInt &p) const { return x == p.x; }
    bool operator!=(const ModInt &p) const { return x != p.x; }
    ModInt inverse() const {int a = x, b = mod, u = 1, v = 0, t;
    while(b > 0) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); }return ModInt(u);}
    ModInt pow(int64_t n) const {ModInt ret(1), mul(x); while(n > 0) {if(n & 1) ret *= mul;mul *= mul;n >>= 1;}return ret;}
    friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x;}
    friend istream &operator>>(istream &is, ModInt &a) { int64_t t; is >> t; a = ModInt< mod >(t); return (is); }
    static int get_mod() { return mod; }
}; using modint = ModInt< mod >;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int main(){
    iosetup;
    string S; cin >> S;
    int N = S.size();
    rep(i, 0, N) cout << 'x';
    cout << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  char a,b;
  cin >> a >> b;
  if(a=='H' && b=='H'){
    cout << 'H' << endl;
  }
  else if(a=='H' && b=='D'){
    cout << 'D' << endl;
  }
  else if(a=='D' && b=='H'){
    cout << 'D' << endl;
  }
  else{
    cout << 'H' << endl;
  }
}
  



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
using P = pair<int,int>;
/* ちゃんと考えてわかって実装 */

int main(void){
    int n, m;
    cin >> n >> m;

    double sum = 0;
    vector<int> a;
    for(int i=0; i<n; i++){
        int tmp; cin >> tmp;
        a.push_back(tmp);
        sum += tmp;
    }

    int ok = 0;
    double thre = sum / (4*m);
    for(int i=0; i<n; i++){
        if(a[i] >= thre) ok++;
    }

    if(ok >= m) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順

int main() {
    int N; cin >> N;
    string B[2];
    rep(i,2) {
        cin >> B[i];
    }

    ll way = 0;
    ll MOD = (ll)pow(10,9) + 7;
    bool isPrevX = false;
    rep(i,N) {
        char a = B[0][i];
        if (a == B[1][i]) {
            // X
            if (i == 0) {
                way = 3;
            } else {
                if (isPrevX) {
                    way = way * 2 % MOD;
                } // else way *= 1 % mod;
            }
            isPrevX = true;
        } else if (a == B[0][i+1]) {
            // Y
            if (i == 0) {
                way = 6;
            } else if (isPrevX) {
                way = way * 2 % MOD;
            } else {
                way = way * 3 % MOD;
            }
            isPrevX = false;
            i++;
        }
    }
    cout << way << endl;
}


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

int main() {
  int64_t n;
  std::cin >> n;
  std::vector<int64_t> a(n);
  for (auto &i : a) {
    std::cin >> i;
    i--;
  }

  int64_t i = 0;
  int64_t c = 0;

  while (a[i] != i) {
    i = a[i];
    c++;
    if (i == 1) {
      std::cout << c << std::endl;
      return 0;
    }
    if (n < c) {
      break;
    }
  }

  std::cout << -1 << std::endl;
  return 0;
}

Measured memory_bytes: 1024