akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
string alp = "abcdefghijklmnopqrstuvwxyz";
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}
void neg() {cout << -1 << endl;}

int main() {
  int n, m;
  cin >> n >> m;
  priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> isl;
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    isl.push({b, a});
  }
  int broken = isl.top().at(0) - 1, cnt = 0;
  isl.pop();
  cnt++;
  for (int i = 1; i < m; i++) {
    if (isl.top().at(1) > broken) {
      cnt++;
      broken = isl.top().at(0) - 1;
    }
    isl.pop();
  }
  cout << cnt << endl;
}

Measured memory_bytes: 7984
def mapt(fn, *args):
    return tuple(map(fn, *args))


def Input():
    return mapt(int, input().split(" "))


def main():
    n, m, c = Input()
    b = Input()
    a = [Input() for _ in range(n)]
    ans = 0
    for row in a:
        tmp = c
        for x, y in zip(row, b):
            tmp += x * y
        if tmp > 0:
            ans += 1
    print(ans)

main()

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

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

using namespace std;

struct Edge {
  int dst,weight;
  bool type[2]; // 0 -> hito, 1 -> nyanko
  Edge(int dst=-1,int weight=0,bool a=false,bool b=false) : dst(dst), weight(weight) {
    type[0] = a, type[1] = b;
  }
};

const int MAX_V = 100100;
int V,E,Natsume,Lennon;
vector<Edge> G[MAX_V];
int par[MAX_V],rank[MAX_V];

inline void init(int n=MAX_V){ rep(i,n) par[i] = i, rank[i] = 0; }

int find(int x) {
  if( x == par[x] ) return x;
  return par[x] = find(par[x]);
}

void unit(int x,int y){
  x = find(x), y = find(y);
  if( x != y ) {
    if( rank[x] > rank[y] ) par[y] = x;
    else {
      par[x] = y;
      if( par[x] == par[y] ) ++rank[y];
    }
  }
}

void draw(int sp,int type){
  deque<int> deq;
  deq.push_back(sp);
  while( !deq.empty() ){
    int cur = deq.front(); deq.pop_front();
    rep(i,(int)G[cur].size()){
      int next = G[cur][i].dst;
      if( !G[cur][i].type[type] ) continue;
      if( find(cur) != find(next) ) {
        unit(cur,next);
        deq.push_back(next);
      }
    }
  }
}

const int IINF = INT_MAX;
int mindist[3][MAX_V]; // 0-> Natsume, 1-> Summer, 2-> Lennon

void calc(int stype,vector<int> &sp){
  rep(i,V) mindist[stype][i] = IINF;
  deque<int> deq;
  rep(i,sp.size()) {
    mindist[stype][sp[i]] = 0;
    deq.push_back(sp[i]);
  }
  while( !deq.empty() ){
    int cur = deq.front(); deq.pop_front();
    rep(i,G[cur].size()){
      int next = G[cur][i].dst;
      if( !G[cur][i].type[0] ) continue;
      if( mindist[stype][next] > mindist[stype][cur] + 1 ){
        mindist[stype][next] = mindist[stype][cur] + 1;
        deq.push_back(next);
      }
    }
  }
}

void compute(){
  draw(0,1);
  draw(Lennon,1);
  if( find(0) == find(Lennon) ) { puts("0"); return; }
  vector<int> sp;
  sp.push_back(Natsume);
  calc(0,sp);
  sp.clear();

  rep(i,V) if( find(0) == find(i) ) sp.push_back(i);
  calc(1,sp);
  sp.clear();

  rep(i,V) if( find(Lennon) == find(i) ) sp.push_back(i);
  calc(2,sp);
  
  int mini = IINF;
  rep(i,V) if( mindist[0][i] != IINF && mindist[1][i] != IINF && mindist[2][i] != IINF ) {
    mini = min(mini,mindist[0][i]+mindist[1][i]+mindist[2][i]);
  }

  cout << mini << endl;

}

int main(int argc,char** argv){
  int T;
  cin >> T;
  while( T-- ) {
    cin >> V >> E;
    cin >> Natsume >> Lennon;
    ++V;
    rep(i,V) G[i].clear();
    init(V);
    rep(_,E){
      int s,t;
      char c;
      cin >> s >> t >> c;
      if( c == 'N' ) {
        G[s].push_back(Edge(t,1,true,false));
        G[t].push_back(Edge(s,1,true,false));
      } else {
        G[s].push_back(Edge(t,0,false,true));
        G[t].push_back(Edge(s,0,false,true));
      }
    }
    compute();
  }
  return 0;
}

Measured memory_bytes: 12768
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

int main()
{
    string s;
    getline(cin, s);

    int i = 0;
    for(;;){
        int j = s.find("apple", i);
        int k = s.find("peach", i);
        if(j == string::npos && k == string::npos)
            break;
        if(k == string::npos || (j != string::npos && j < k)){
            s.replace(j, 5, "peach");
            i = j + 5;
        }else{
            s.replace(k, 5, "apple");
            i = k + 5;
        }
    }

    cout << s << endl;
    return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
#define ALL(obj) (obj).begin(), (obj).end()
#define REP(i, n) for(int i = 0;i < (n);++i)
#define RREP(i, n) for(int i = (n)-1; i >= 0; --i)

#define endl '\n'
#define pb emplace_back
#define mkp make_pair
#define p_q priority_queue
#define INF 2000000000
#define PI 3.1415926
#define coutdb cout << fixed << setprecision(15)

const int dx[]={1,0,-1,0,1,1,-1,-1}, dy[]={0,-1,0,1,1,-1,1,-1};
const long long MOD = 1e9+7;

// typedef long long ll;
#define int int_fast64_t

template<typename T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template<typename T> inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template<typename T> inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template<typename T> inline T nHr(T a,T b){return nCr(a+b-1,b);}

signed main(void){
  cin.tie(0);
  ios::sync_with_stdio(false);

  int a; string s; cin >> a >> s;
  if(a >= 3200) cout << s << endl;
  else cout << "red" << endl;
}

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

def main():
    N = int(input())
    A = tuple(map(int, input().split()))
    ans = 1
    for a in A:
        if a == 0:
            print('0')
            exit()
    for a in A:
        ans *= a
        if ans > 10 ** 18:
            print('-1')
            exit()
    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 21740
n,m=input().split()
n=(int)(n)
m=(int)(m)


B=[]
cnt=0
while n!=0 and m!=0:
    A=input().split()
    cnt=0
    max=0
    for i in range(n):
        A[i]=(int)(A[i])
    for i in range(n):
        for j in range(i+1,n):
            x=A[i]+A[j]
            if x>max and x<=m:
                max=x
    if max>0:
        B.append(max)
    else:
        B.append('NONE')
    cnt+=1
    n,m=input().split()
    n=(int)(n)
    m=(int)(m)

for i in range(len(B)):
    print(B[i])


Measured memory_bytes: 5712
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

n,m,k=map(int,input().split())
uf=UnionFind(n)
friend=[[] for _ in range(n)]
brock=[[] for _ in range(n)]
ans=[]
for _ in range(m):
    a,b=map(int,input().split())
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)
    uf.union(a-1,b-1)
for _ in range(k):
    c,d=map(int,input().split())
    brock[c-1].append(d-1)
    brock[d-1].append(c-1)
for i in range(n):
    ans.append(uf.size(i)-len(friend[i])-sum([uf.same(i,j) for j in brock[i]])-1)
print(*ans)

Measured memory_bytes: 51384
//satyaki3794
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define MOD (1000000007LL)
#define LEFT(n) (2*(n))
#define RIGHT(n) (2*(n)+1)
 
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
 
ll pwr(ll base, ll p, ll mod=MOD){
ll ans = 1;while(p){if(p&1)ans=(ans*base)%mod;base=(base*base)%mod;p/=2;}return ans;
}
 
 
ll gcd(ll a, ll b){
    if(b == 0)  return a;
    return gcd(b, a%b);
}



map<int, int> cnt;


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

    int n;
    cin>>n;
    while(n--){
    	int a;
    	cin>>a;
    	cnt[a]++;
    }

    ll ans = 0, last = 0;
    for(auto it : cnt){
    	ll z = it.ss;
    	if(z >= 4)	ans = max(ans, it.ff*1LL*it.ff);
    	if(z >= 2){
    		ans = max(ans, it.ff*1LL*last);
    		last = it.ff;
    	}
    }

    cout<<ans;
    return 0;
}







 




Measured memory_bytes: 4992
import collections

n=int(input())
s=input()
m=(n-1)//2
x=0

l=collections.Counter(s)
ans=l['R']*l['G']*l['B']

for i in range(1, m+1):
    for j in range(n-i*2):
        a=j
        b=a+i
        c=b+i
        if s[a] != s[b] != s[c] != s[a]:
            x += 1

print(ans-x)


Measured memory_bytes: 9472
#include<stdio.h>

int main()
{
    int n, i;
    char s[10001];
    
    scanf("%d", &n);
    getchar();
    scanf("%s", s);
    
    for(i=0; s[i]; ++i){
        s[i]-= 'A';
        s[i]+=n;
        s[i] %= 26;
        s[i]+='A';
    }
    printf(s);
    
    
    return 0;
}

Measured memory_bytes: 128
import math
import fractions
import copy
import numpy as np
def j(q):
    if q==1: print("Yes")
    elif q == 0:print("No")
    exit(0)
rem = pow(10,9)+7
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def printrow(a):
    for i in a:
        print(i)
"""
#decomment when needed
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
"""
n ,m= ips()
a= []
b= []
for i in range(n):
    a.append(input())
for i in range(m):
    b.append(input())
left = 0
right =m
for sy in range(n-m+1):
    for sx in range(n-m+1):
        c = []
        for i in range(sy,sy+m):
            c.append(a[i][sx:(sx+m)])
        if c==b:j(1)
j(0)

Measured memory_bytes: 13636
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
 
int main(void){
  vector<int> stacks = vector<int>(3);
  for(int i = 0; i < 3; i++) cin >> stacks[i];
  
  vector<int> diffs = vector<int>(3);
  int max = abs(stacks[0] - stacks[1]);
  int sum = 0;
  for(int i = 0; i < 3; i++){
    int next = i + 1;
    if(next >= 3) next = 0;
    diffs[i] = abs(stacks[i] - stacks[next]);
    sum += diffs[i];
    if(max < diffs[i]) max = diffs[i];
  }
  cout << sum - max << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while ('0'>ch||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do {(t*=10)+=ch-'0';ch=getchar();} while ('0'<=ch&&ch<='9'); t*=f;
}
const int maxn=(1e5)+10;
int n,a[maxn],b[maxn],x;
int s1,s2,c1,c2,t1,t2;
int main() {
	//freopen("1.txt","r",stdin);
	read(n);
	for (int i=1;i<=n;i++) {
		read(x);
		if (i%2==0) a[x]++;
		else b[x]++;
	}
	for (int i=1;i<maxn;i++) {
		if (a[i]>s1) t1=s1,c1=i,s1=a[i];
		else t1=max(t1,a[i]);
		if (b[i]>s2) t2=s2,c2=i,s2=b[i];
		else t2=max(t2,b[i]);
	}
	if (c1==c2) printf("%d\n",min(n-s1-t2,n-s2-t1));
	else printf("%d\n",n-s1-s2);
	return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>

int main(void)
{
	int number;
	double weight;
	double hight;
	double BMI;
	char conma;
	
	while (scanf("%d", &number) != EOF){
		scanf("%c %lf %c %lf", &conma, &weight, &conma, &hight);
		BMI = weight / (hight * hight);
		if (BMI >= 25){
			printf("%d\n",  number);
		}
	}
	
	
	return 0;
}

Measured memory_bytes: 636
def reboot(arr, index, count, q):
    if index >= len(arr):
        return False
    if count > q:
        return False
    if count + arr[index] == q:
        return True
    elif count + arr[index] > q:
        return reboot(arr, index + 1, count, q)
    return reboot(arr, index + 1, count + arr[index], q) or reboot(arr, index + 1, count, q)


if __name__ == '__main__':
    n = int(input())
    arr = list(map(int, input().split()))
    q = int(input())
    q_arr = list(map(int, input().split()))
    min_ele = arr[0]
    arr_sum = arr[0]
    for i in range(1, len(arr)):
        min_ele = min(min_ele, arr[i])
        arr_sum += arr[i]
    for ele in q_arr:
        if ele < min_ele or ele > arr_sum:
            print('no')
        else:
            if reboot(arr, 0, 0, ele):
                print('yes')
            else:
                print('no')



Measured memory_bytes: 5624
def get_intersections(p0, p1):
    dist = abs(p0 - p1)

    if dist > 2:
        return []
    elif dist == 2:
        return [(p0 + p1) / 2]
    else:
        m = (p0 + p1) / 2
        v = m - p0
        w = complex(v.imag, -v.real)
        n = w / abs(w)
        d = abs(v)
        l = (1 - d ** 2)**.5

        inter0 = m + l * n
        inter1 = m - l * n
        return [inter0, inter1]

for e in iter(input, '0'):
    n = int(e)
    P = [complex(*map(float,input().split(',')))for _ in[0]*n]
    intersections = []
    for i in range(n):
        for j in range(i+1,n):
            intersections += get_intersections(P[i], P[j])
    c = 1
    for intersection in intersections:
        cnt = 0
        for p in P:
            if abs(intersection - p) <= 1.01:
                cnt += 1
        c=max(c,cnt)
    print(c)


Measured memory_bytes: 5704
#include<stdio.h>
#include<stdlib.h>
long long dp[1005][1005];
int min(int a,int b){return a<b?a:b;}
long long dfs(int gx,int gy){
	int i,j;
	for(i=0;i<=gx+1;i++)for(j=0;j<=gy+1;j++)dp[i][j]=0;
	dp[1][1]=1;
	for(i=1;i<=gx+1;i++)for(j=1;j<=gy+1;j++)if(i!=1||j!=1)dp[i][j]=(dp[i-1][j]+dp[i][j-1])%100000007;
	return dp[gx+1][gy+1];
}
int main(){
	int gx,gy;
	int r,c,sx,sy;
	int i;
	scanf("%d %d %d %d %d %d",&r,&c,&sx,&sy,&gx,&gy);
	int x=abs(gx-sx);
	int y=abs(gy-sy);
	x=min(x,r-x);
	y=min(y,c-y);
	long long ans=1;
	if(r%2==0&&r/2==x)ans*=2;
	if(c%2==0&&c/2==y)ans*=2;
	ans*=dfs(x,y);
	printf("%lld\n",ans%100000007);
	return 0;
}

Measured memory_bytes: 5116
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
int n,A,B,C;
vector<int> l(8);
int dfs(int depth,int a,int b,int c){
    if(depth == n){
        if(min(a,min(b,c))>0){
            return abs(a-A) + abs(b-B) + abs(c-C) - 30;
        }else{
            return 1e9;
        }
    }
    int ret0 = dfs(depth+1,a,b,c);
    int ret1 = dfs(depth+1,a+l[depth],b,c) + 10;
    int ret2 = dfs(depth+1,a,b+l[depth],c) + 10;
    int ret3 = dfs(depth+1,a,b,c+l[depth]) + 10;
    return min(ret0,min(ret1,min(ret2,ret3)));
}
int main(){
    cin >> n >> A >> B >> C;
    rep(i,n) cin >> l[i];
    cout << dfs(0,0,0,0) << endl;
}


Measured memory_bytes: 256
A, B = map(int, input().split())

def calcXorSum(a):
    bin_a = format(a, 'b')
    N = len(bin_a)
    a += 1
    ans = 0
    for i in range(N):
        unit = 1 << i
        div = int(a / unit)
        res = int(a % unit)
        cnt = unit * int(div / 2)
        if div % 2 == 1:
            cnt += res
        if cnt % 2 == 1:
            ans += 1 << i
    return ans

print(calcXorSum(B) ^ calcXorSum(A - 1))


Measured memory_bytes: 3064
a,b,c,d,e,f=map(int,input().split())
a*=100
b*=100
res=chk=0
ans=[]

for i in range(16):
    for j in range(16):
        for k in range(1501):
            w=(i*a)+(j*b)
            s=(k*c)
            o=(w//100)*e
            if w==0:
                pass
            elif w+s>f or s>o:
                break
            else:
                s+=(min(f-w-s,o-s)//d)*d
                if len(ans)==0:
                    ans=[s/(w+s),w+s,s]
                elif s/(w+s)>ans[0]:
                    ans=[s/(w+s),w+s,s]
print(ans[1],ans[2])

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

int main() {
    int n;
    cin >> n;
    map<string, int> s;
    long long int res = 0;
    for(int i = 0;i < n;i++){
        string t;
        cin >> t;
        sort(begin(t), end(t));
        res += s[t]++;
    }
    cout << res << endl;
    return 0;
}

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

using namespace std;

string Input;

int countStr(const string &target) {
	int cnt, curPos;

	cnt = 0;
	curPos = Input.find(target);
	while (curPos != string::npos) {
		++cnt;
		curPos = Input.find(target, curPos + 1);
	}

	return cnt;
}

int main() {
	int cntOfJOI, cntOfIOI;
	
	while (cin >> Input) {
		//cout << Input << endl;
		cntOfJOI = countStr("JOI");
		cntOfIOI = countStr("IOI");
		cout << cntOfJOI << endl << cntOfIOI << endl;
	}

	return 0;
}


Measured memory_bytes: 3020
#include <bits/stdc++.h>
#define ALL(a) (a).begin(),(a).end()
using namespace std;

int main(){
	int A, B; cin >> A >> B;
	if ( A < 1 || A > 9 || B < 1 || B > 9) {
		cout << -1 << endl;
	}
	else {
		cout << A * B << endl;
	}
}

//auto it2 = upper_bound(ALL(L), A);

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

int main() {
    int n, m;
    cin >> n >> m;
    int c[21];
    int t[50001];
    int ini = (1 << 29);
    for (int i = 1; i <= m; i++) {
        cin >> c[i];
    }
    t[0] = 0;
    for (int i = 1; i <= 50000; i++) {
        t[i] = ini;
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j + c[i] <= n; j++) {
            t[j + c[i]] = min(t[j] + 1, t[j + c[i]]);
        }
    }
    cout << t[n] << endl;
    return 0;
}

Measured memory_bytes: 3240
#include <iostream>
#include<bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
ll h,w,n,a,b,v[10],ans;
map<P,ll> mp;
int main(void){
    cin>>h>>w>>n;
    for(int i=0;i<n;i++){
        cin>>a>>b;
        a--,b--;
        for(int i=-1;i<=1;i++){
            for(int j=-1;j<=1;j++){
                mp[{a+i,b+j}]++;
            }
        }
    }
    for(auto x:mp){
        if(1<=x.F.F&&x.F.F<h-1&&1<=x.F.S&&x.F.S<w-1){
            v[x.S]++;
            ans++;
        }
    }
    cout<<(h-2)*(w-2)-ans<<endl;
    for(int i=1;i<10;i++)cout<<v[i]<<endl;
}


Measured memory_bytes: 56448
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set> 
#include <map>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
#include <iomanip>
#define REP(i,n) for(int i=0; i<(n); ++i)
#define FOR(i,a,b) for(int i=(a); i<(b); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

int main () {
    
    int n; cin >>n;
    vector<int> w(n); REP(i,n) cin >> w[i];

    int res = INF;
    for (int t = 1; t < n; t++) {
        int res1 = 0;
        for (int i = 0; i < t; i++) {
            res1 += w[i];
        }
        int res2 = 0;
        for (int i = t; i < n; i++) {
            res2 += w[i];
        }
        res = min(res, abs(res1 - res2));
    }
    
    cout << res << endl;
    return 0;
}



Measured memory_bytes: 256
from collections import*
n,m,*t=map(int,open(0).read().split())
i,o=[0]*n,[[]for _ in range(n)]
for a,b in zip(*[iter(t)]*2):
  o[a-1]+=b-1,
  i[b-1]+=1
q=deque(v for v in range(n)if i[v]<1)
r=[]
while q:
  v=q.popleft()
  r+=v,
  for w in o[v]:
    i[w]-=1
    if i[w]==0:q+=w,
print(-(len(r)==n))

Measured memory_bytes: 3828
#include<iostream>

using namespace std;

int main(){
	
	int input[10];
	int top[3] = {0, 0, 0};
	int i;
	
	for (i = 0; i < 10; i++){
		cin >>input[i];
	}
	
	for (i = 0; i < 10; i++){
		if (top[0] <= input[i]){
			top[2] = top[1];
			top[1] = top[0];
			top[0] = input[i];
		}else if (top[1] <= input[i]){
			top[2] = top[1];
			top[1] = input[i];
		}else if (top[2] <= input[i]){
			top[2] = input[i];
		}
	}
	
	for (i = 0; i < 3; i++){
		cout << top[i] << endl;
	}
	
	return 0;
}


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

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

typedef long long LL;
typedef long double LD;

const LL INF = (1LL << 60);

typedef vector<LL> VLL;
LL knapsack_01(VLL& v, VLL& w, int n, LL W);

int main() {

  ios_base::sync_with_stdio(0); cin.tie(0);

  int n; LL W;
  cin >> n >> W;

  VLL v, w;
  v.assign(n + 1, 0);
  w.assign(n + 1, 0);
  for (int i = 1; i <= n; i++) {
    cin >> v[i] >> w[i];
  }

  LL ans = knapsack_01(v, w, n, W);

  cout << ans << endl;

  return 0;
}

/**
 *
 * tested on http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B
 */
LL dp[105][100005];
LL knapsack_01(VLL& v, VLL& w, int n, LL W) {
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= W; j++) {
      dp[i][j] = dp[i-1][j];
      if (w[i] <= j)
        dp[i][j] = max(dp[i][j],
                       dp[i-1][j-w[i]] + v[i]);
    }
  }
  return dp[n][W];
}


Measured memory_bytes: 11320
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Console = System.Console;

namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            if (ReadInt() < 1200)
            {
                Console.WriteLine("ABC");
            }
            else
            {
                Console.WriteLine("ARC");
            }
        }
        private static readonly Func<string> Read = () => Console.ReadLine();
        private static readonly Func<string[]> ReadStringArray = () => Console.ReadLine().Split();
        private static readonly Func<int> ReadInt = () => int.Parse(Console.ReadLine());
        private static readonly Func<long> ReadLong = () => long.Parse(Console.ReadLine());
        private static readonly Func<int[]> ReadIntArray = () => Console.ReadLine().Split().Select(int.Parse).ToArray();
        private static readonly Func<long[]> ReadLongArray = () => Console.ReadLine().Split().Select(long.Parse).ToArray();
        private static readonly Action<string> Cw = str => Console.WriteLine(str);
    }
}

Measured memory_bytes: 13140
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
while(true) {
int n, m;
static char str[1200000];
vector<int> c;
scanf("%d", &n);
if(n == 0)
break;
scanf("%d", &m);
scanf("%s", str);
c.reserve(m);
for(int i = 0; i < m; ++i) {
if(str[i] != 'I')
continue;
int it = i + 1;
int ioi = 0;
while(it < m - 1) {
if(str[it] == 'O' && str[it + 1] == 'I')
ioi += 1, it += 2;
else
break;
}
i = it - 1;
c.push_back(ioi);
}
int ans = 0;
for(int i = 0; i < c.size(); ++i) {
if(c[i] >= n)
ans += c[i] - n + 1;
}
printf("%d\n", ans);
}
return 0;
}

Measured memory_bytes: 2028
s=list(input())
t=list(input())
ans=[]

for i in range(len(s)-len(t)+1):
    u=s[i:len(t)+i]
    a=0
    for j in range(len(t)):
        if not t[j-1]==u[j-1]:
            a=a+1
    ans.append(a)
print(min(ans))

Measured memory_bytes: 9040
#include "bits/stdc++.h"
using namespace std;
using ll = long long; using pii = pair<int, int>;
const int MOD = (int)1e9 + 7, INF = (1 << 27); const ll INFLL = (1LL << 55);
#define FOR(i,a,b) for(int (i)=(a);i<(int)(b);i++)
#define rep(i,n) FOR(i,0,n)
template<typename T> void dbg(T x) { cout << x << "\n"; }
template<typename T, typename U> static void chmin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void chmax(T &x, U y) { if (x < y) x = y; }

int n;
vector<vector<int>> G;

int dp[2][114514];
void dfs(int v, int p, int d, int turn) {
    dp[turn][v] = d;
    for (int to : G[v]) if (to != p) dfs(to, v, d + 1, turn);
}

int main() {
    cin.tie(0), ios::sync_with_stdio(0);
    int n; cin >> n;
    rep(i, 2) rep(j, 114514) dp[i][j] = INF;
    G.resize(n);
    rep(i, n - 1) {
        int a, b; cin >> a >> b; a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    dfs(0, -1, 0, 0);
    dfs(n - 1, -1, 0, 1);
    int f = 0, s = 0;
    rep(i, n) {
        assert(dp[0][i] < INF);
        assert(dp[1][i] < INF);
        if (dp[0][i] <= dp[1][i]) f++;
        else s++;
    }

    cout << (f > s ? "Fennec" : "Snuke") << "\n";

    return 0;
}


Measured memory_bytes: 12928
#include <stdio.h>
#include <stdlib.h>

int compare_int_ao(const void *a, const void *b){
  return *(int *)a - *(int *)b;
}

int euclid(int a, int b){
  if(a < b){
    int tmp = a;
    a = b;
    b = tmp;
  }
  int r = a % b;
  if(r < 0){
    r += b;
  }
  while(r != 0){
    a = b;
    b = r;
    r = a % b;
    if(r < 0){
      r += b;
    }
  }
  return b;
}

int main(){
  int N, X;
  int x[100010] = {};

  scanf("%d %d", &N, &X);
  for(int i = 0; i < N; i++){
    scanf("%d", &x[i]);
  }
  x[N] = X;
  qsort(x, N + 1, sizeof(int), compare_int_ao);

  if(N == 1){
    printf("%d\n", x[1] - x[0]);
  }else{
    int D = euclid(x[2] - x[1], x[1] - x[0]);
    for(int i = 2; i < N; i++){
      D = euclid(D, x[i+1] - x[i]);
    }
    printf("%d\n", D);
  }
  return 0;
}


Measured memory_bytes: 892
#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}

template<class T> ll llpow(T x,T n){ll ans=1;if(x==0)ans=0;while(n){if(n&1)ans*=x;x*=x;n>>=1;}return ans;}
template<class T> inline T gcd(T x,T y){if(y==0)return x; else {return gcd(y,x%y);}}
template<class T> inline T lcm(T x,T y){return x/gcd(x,y)*y;}

#define rep(i,n) for(ll i=0;i<(ll)n;i++)
#define rep2(i, begin_i, end_i) for (ll i = (ll)begin_i; i < (ll)end_i; i++)

long long INF = 1LL<<60;
int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    rep(i,n)cin>>a[i];
    sort(a.begin(),a.end());
    int temp=0;
    rep(i,n){
        if(temp==a.at(i)){cout<<"NO"<<endl;return 0;}
        temp=a[i];
    }
    cout<<"YES"<<endl;
    return 0;
}




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

using namespace std;
typedef long long LL;

#ifdef BTK
#define DEBUG if(1)
#else
#define CIN_ONLY if(1)
struct cww {cww() {CIN_ONLY{ios::sync_with_stdio(false); cin.tie(0);}}
}star;
#define DEBUG if(0)
#endif

#define ALL(v) (v).begin(),(v).end()
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l, T r){bool a = l>r; if (a)l = r; return a;}
template <typename T>inline bool chmax(T &l, T r){bool a = l<r; if (a)l = r; return a;}
template <typename T>istream& operator>>(istream &is, vector<T> &v){for (auto &it : v)is >> it;return is;}

class range {private: struct I { int x; int operator*() { return x; }bool operator!=(I& lhs) { return x<lhs.x; }void operator++() { ++x; } }; I i, n;public:range(int n) :i({ 0 }), n({ n }) {}range(int i, int n) :i({ i }), n({ n }) {}I& begin() { return i; }I& end() { return n; }};

int main() {
	int N;
	cin >> N;
	vector<LL> a(N);
	cin >> a;
	for (int i : range(1, N))a[i] += a[i - 1];
	LL ret = 1e18;
	for (int i : range(0, N - 1)) {
		chmin(ret, abs(a.back() - 2 * a[i]));
	}
	cout << ret << endl;

	return 0;
}


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

#define fast ios_base::sync_with_stdio(false);   cin.tie(NULL); cout.tie(NULL);
#define fl(i,a,n) for(int i=a; i<n; i++)
#define ll long long 
#define pb push_back
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define test()  int tt;  cin>>tt;  while(tt--)
#define nl  cout<<"\n"
#define pii pair<int,int>
#define dbg(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args)    {
    cout << *it << " = " << a << endl;
    err(++it, args...);
}
const int mod=1e9+7;


void solve()    {
        int k;  cin>>k;
        ll sum=0;
        fl(i,1,k+1)     {
                fl(j,1,k+1)     {
                        fl(l,1,k+1)     {
                                sum+=__gcd(i*1LL,__gcd(j*1LL,l*1LL));
                        }
                }
        }
        cout<<sum;
}
/*  Integer Overflow  */
int main()  {
    fast;
    //test()
        solve();
}

Measured memory_bytes: 3652
#include <iostream>
#include <algorithm>

int main(){
  int A,B,C;
  int max,mid,min;

  std::cin >> A >> B >> C;
  max = std::max({A,B,C});
  min = std::min({A,B,C});
  mid = A + B + C - max - min;

  if(max%2 == mid%2 && mid%2 == min%2){
    std::cout << (max - mid)/2 + (max - min)/2 << std::endl;
  }else if(max%2 == mid%2 && mid%2 != min%2){
    std::cout << (max - mid)/2 + (max + 1 - min)/2 + 1 << std::endl;
  }else if(max%2 == min%2 && mid%2 != min%2){
    std::cout << (max + 1 - mid)/2 + (max - min)/2 + 1 << std::endl;
  }else if(max%2 != min%2 && mid%2 == min%2){
    std::cout << (max - mid -1)/2 + (max - min - 1)/2 + 1 << std::endl;
  }

  return 0;
}

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

#define ll long long
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define vi vector<int>
#define vl vector<long long>
#define sz size()
#define x first
#define y second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ld long double

using namespace std;
int n;
string s;
string ans;
stack<char> st;

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

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

			st.push(ch);
			ans += "(";
		} else {
			if(st.empty()) {
				ans = "(" + ans;
				ans += ")";
			} else {	
				st.pop();
				ans += ")";
			}
		}
	}

	int k = st.sz;

	// for(int i = 0; i < k; i++) ans += "(";
	for(int i = 0; i < k; i++) ans += ")";

		cout << ans;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a); i < (b); ++i)
#define rrep(i,a,b) for(int i = (b); i --> (a);)
#define all(v) (v).begin(),(v).end()
#define trav(x,v) for(auto &x : v)
#define sz(v) int(v.size())
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> pii;

typedef int Flow;
const Flow inf = 1e6;
struct Edge {
	int dest, back;
	Flow f, c;
};

struct PushRelabel {
	vector<vector<Edge>> g;
	vector<Flow> ec;
	vector<Edge*> cur;
	vector<vi> hs; vi H;
	PushRelabel(int n) : g(n), ec(n), cur(n), hs(2*n), H(n) {}

	void add_edge(int s, int t, Flow cap, Flow rcap=0) {
		if (s == t) return;
		g[s].push_back({t, sz(g[t]), 0, cap});
		g[t].push_back({s, sz(g[s])-1, 0, rcap});
	}

	void add_flow(Edge& e, Flow f) {
		Edge &back = g[e.dest][e.back];
		if (!ec[e.dest] && f) hs[H[e.dest]].push_back(e.dest);
		e.f += f; e.c -= f; ec[e.dest] += f;
		back.f -= f; back.c += f; ec[back.dest] -= f;
	}
	Flow maxflow(int s, int t) {
		int v = sz(g); H[s] = v; ec[t] = 1;
		vi co(2*v); co[0] = v-1;
		rep(i,0,v) cur[i] = g[i].data();
		trav(e, g[s]) add_flow(e, e.c);

		for (int hi = 0;;) {
			while (hs[hi].empty()) if (!hi--) return -ec[s];
			int u = hs[hi].back(); hs[hi].pop_back();
			while (ec[u] > 0)  // discharge u
				if (cur[u] == g[u].data() + sz(g[u])) {
					H[u] = 1e9;
					trav(e, g[u]) if (e.c && H[u] > H[e.dest]+1)
						H[u] = H[e.dest]+1, cur[u] = &e;
					if (++co[H[u]], !--co[hi] && hi < v)
						rep(i,0,v) if (hi < H[i] && H[i] < v)
							--co[H[i]], H[i] = v + 1;
					hi = H[u];
				} else if (cur[u]->c && H[u] == H[cur[u]->dest]+1)
					add_flow(*cur[u], min(ec[u], cur[u]->c));
				else ++cur[u];
		}
	}
};

int main(){
	cin.sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;

	vi p(n), q(n);
	trav(x, p) cin >> x;
	trav(x, q) cin >> x;

	int ps = 0, qs = 0;
	vector<bool> vis(n, false);
	vi pek(n), qek(n);
	rep(i,0,n) if(!vis[i]){
		int j = i;
		do {
			vis[j] = true;
			pek[j] = ps;
			j = p[j];
		} while(j != i);
		++ps;
	}
	rep(i,0,n) vis[i] = false;
	rep(i,0,n) if(!vis[i]){
		int j = i;
		do {
			vis[j] = true;
			qek[j] = qs;
			j = q[j];
		} while(j != i);
		++qs;
	}
	trav(x, qek) x += ps;

	PushRelabel pr(1 + ps + qs + 1);
	int source = ps + qs, sink = ps+qs+1;
	int base = 0;
	rep(i,0,n){
		if(i == p[i] && i == q[i]){
			base++;
			continue;
		}
		else if(i == p[i]){
			pr.add_edge(source, pek[i], inf);
		} else if(i == q[i]){
			pr.add_edge(qek[i], sink, inf);
		} else if(p[i] == q[i]){
			pr.add_edge(qek[i], pek[i], 1);
		}
		pr.add_edge(pek[i], qek[i], 1);
	}

	cout << n - pr.maxflow(source, sink) - base << endl;
}


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

int min(int a, int b) {
  int x = a + b;
  int y = a - b;
  int z = a * b;

  if (x >= y && x >= z) {
    return x;
  } else if (y > x && y >= z) {
    return y;
  } else {
    return z;
  }
}

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

  int ans = min(a, b);

  cout << ans << endl;
}


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

int main() {

    string n;
    cin >> n;

    char a = n[0];
    char b = n[1];

    int Q = 9;
    char q = '0' + Q;


    if(a != q && b != q) cout <<  "No" << endl;
    else cout << "Yes" << endl;

    return 0;

}

Measured memory_bytes: 760
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef vector<int> VI;
typedef vector<VI> VVI;
const ll MOD = 1000000007;
const ll INF = 1000000007;
#define REP(i, n) for(int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()

int main() {
	int n; cin >> n;
	cout << (n - 1) / 2;
}

Measured memory_bytes: 256
#include <stdio.h>

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <cmath>

using namespace std;

void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template <typename T, typename V>
void __print(const pair<T, V> &x) {
    cerr << '{';
    __print(x.first);
    cerr << ',';
    __print(x.second);
    cerr << '}';
}
template <typename T>
void __print(const T &x) {
    int f = 0;
    cerr << '{';
    for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
    cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
    __print(t);
    if (sizeof...(v)) cerr << ", ";
    _print(v...);
}
#ifdef LOCAL
#define debug(x...)               \
    cerr << "[" << #x << "] = ["; \
    _print(x)
#else
#define debug(x...)
#endif

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    string S;
    cin >> N;
    cin >> S;

    string repeated = S.substr(0, S.length()/2)+S.substr(0, S.length()/2);
    if (repeated==S){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using P = pair<ll,ll>;
const ll mod = 1e9+7;
#define ALL(x) (x).begin(),(x).end()
#define pow(x,y) modpow(x,y)
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define REPS(i,n) for(ll (i)=1;(i)<=(n);(i)++)
#define RREP(i,n) for(ll (i)=(n-1);(i)>=0;(i)--)
#define RREPS(i,n) for(ll (i)=(n);(i)>0;(i)--)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());

template <class T = int>T in(){
    T x;
    cin >> x;
    return (x);
}

template<class T> inline void chmin(T& a, T b){
    if (a > b){
        a = b;
    }
}

template<class T> inline void chmax(T& a, T b){
    if (a < b){
        a = b;
    }
}

/* modとる */
inline ll modu(ll a){
    return(a % mod + mod) % mod;
}

/* modつき二分累乗法 */
ll modpow(ll a, ll b) {
    ll res = 1;
    for (a = modu(a); b; a = modu(a * a) , b >>= 1){
        if (b & 1) res = modu(res * a);
    }
    return res;
}


signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(10);
    int N = in();
    vector<int> A(N);;
    REP(i,N)A[i] = in();
    sort(ALL(A));
    bool ok = 1;
    if(N%2 == 0){
        REP(i,N){
            if(i % 2 == 0){
                if(A[i]!=i+1)ok = 0;
            }else{
                if(A[i]!=i)ok = 0;
            }
        }
    }else{
        REP(i,N){
            if(i % 2 == 0){
                if(A[i]!=i)ok = 0;
            }else{
                if(A[i]!=i+1)ok = 0;
            }
        }
    }
    cout << (ok ? modpow(2,N/2): 0) << "\n";
}

Measured memory_bytes: 640
#include <iostream>

using namespace std;

int A, B, C, D;

int main()
{
	cin >> A >> B >> C >> D;
	
	int start, end;
	
	start = (A > C) ? A : C;
	end = (B < D) ? B : D;
	
	int ans = end - start;
	if (ans > 0){
		cout << ans << endl;
	} else cout << 0 << endl;
	
	return 0;
}


Measured memory_bytes: 256
import math

n, a, b = list(map(int, input().split()))

p = 10**9 + 7

def pow_mod(n, m, p):
  if m == 0:
    return 1
  elif m % 2 == 0:
    nm2p = pow_mod(n, m//2, p)
    return (nm2p * nm2p) % p
  elif m % 2 == 1:
    return (pow_mod(n, m-1, p) * (n % p)) % p

def compute_ncr_mod(n, r, p):
  r = min(n-r, r)
  n_factorial = 1
  r_factorial = 1
  for i in range(1, r+1):
    n_factorial *= n-i+1
    n_factorial %= p
    r_factorial *= i
    r_factorial %= p
  ncr_modp = (n_factorial * pow_mod(r_factorial, p-2, p)) % p
  return ncr_modp

print((pow_mod(2, n, p) - 1 - compute_ncr_mod(n, a, p) - compute_ncr_mod(n, b, p)) % p)

Measured memory_bytes: 3064
def resolve():
    N, A, B = map(int, input().split())
    S = input()
    Atmp = 0
    Btmp = 0
    ans = []
    my_append = ans.append
    for i in S:
        if i == 'a':
            if Atmp + Btmp < A+B:
                Atmp += 1
                my_append('Yes')
            else:
                my_append('No')
        elif i == 'b':
            if Btmp < B and Atmp + Btmp < A+B:
                Btmp += 1
                my_append('Yes')
            else:
                my_append('No')
        else:
            my_append('No')
    print("\n".join(ans))
resolve()

Measured memory_bytes: 48880
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define reps(i,n) for(int i=1;i<(int)(n);i++)

typedef long long ll;
using namespace std;

ll gcd(ll a, ll b) { //最大公約数
  if (b==0) return a;
  else return gcd(b, a%b);
}

ll lcm(ll a, ll b) { //最小公倍数
  return a * b / gcd(a, b);
}

ll digit_sum(ll a){ //10進桁和
  ll ans=0;
  while(a>0){
    ans+=a%10;
    a/=10;
  }
  return ans;
}



int main()
{
  ll a,b;
  ll ans=0;
  cin>>a>>b;
  for(ll i=a;i<=b;i++){
    ll a,b,c,d,tmp=i;
    a=tmp%10;
    tmp/=10;
    b=tmp%10;
    tmp/=10;
    c=tmp%10;
    tmp/=10;
    d=tmp%10;
    tmp/=10;
    if(tmp==a&&b==d)ans++;
  }

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


Measured memory_bytes: 3596
def C():
    N, K = map(int, input().split())
    h = [int(input()) for i in range(N)]
    h.sort()
    hmin = h[0]
    hmax = h[K - 1]
    ans = 100000000000000
    for i in range(K - 1, N):
        hmin = h[i - K + 1]
        hmax = h[i]
        if ans > hmax - hmin:
            ans = hmax - hmin
    print(ans)
C()

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

using namespace std;

#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define DEBUG_MAT(v) cerr<<#v<<endl;for(int i=0;i<v.size();i++){for(int j=0;j<v[i].size();j++) {cerr<<v[i][j]<<" ";}cerr<<endl;}


typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); }
template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
#define X first
#define Y second
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(n);i>0;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(),c.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; }
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = (ll)1e18 + 1;
const ll MOD = 1000000007;
//const ll MOD = 998244353;
const double pi = 3.14159265358979323846;
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
int dx[4] = { -1,0, 1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
#define fio() cin.tie(0); ios::sync_with_stdio(false);
//#define mp make_pair

int main() {
  int n, m;
  cin >> n >> m;
  vl a(n);
  rep (i, n) {
    cin >> a[i];
  }
  sort(all(a));
  vector<pll> cb(m);
  rep (i, m) {
    cin >> cb[i].second >> cb[i].first;
  }

  sort(all(cb));
  reverse(all(cb));

  ll ans = 0;
  int idx = 0;
  rep (i, m) {
    ll c = cb[i].first, b = cb[i].second;
    rep (j, b) {
      if (idx == n) break;
      if (a[idx] >= c) break;
      ans += c;
      idx++;
    }
  }
  while (idx < n) {
    ans += a[idx];
    idx++;
  }
  cout << ans << endl;
}



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

using namespace std;

int main(){
    int A,B,C,X,Y;
    cin >> A >> B >> C >> X >> Y;

    vector<int> buys(4);
    buys.at(0) = A*X+B*Y;
    buys.at(1) = C*max(X,Y)*2;
    buys.at(2) = C*X*2+B*max(0,Y-X);
    buys.at(3) = C*Y*2+A*max(0,X-Y);

    int ans = *min_element(buys.begin(), buys.end());
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

using namespace std;

typedef long long ll;

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

const int MAX_N = 100000;
const ll MOD = ll(1e9 + 7);

// auto mod int
// ref. https://github.com/atcoder-live/library/blob/master/mint.cpp
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%MOD+MOD)%MOD){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += MOD-a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= MOD;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime MOD
  mint inv() const {
    return pow(MOD-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

vector<mint> pats;

ll solve(const ll N, const ll K) {
    mint ans = 0;

    for (int i = K; i >= 1; i--) {
        mint times = K / i;
        mint ps = times.pow(N);
        for (int j = i; j <= K; j += i) {
            ps -= pats[j];
        }
        pats[i] = ps;
        // printf("i: %d, ps: %lld\n", i, ps.x);
        ans += pats[i] * i;
    }

    return ans.x;
}

int main(void) {
    ll N, K;
    cin >> N >> K;

    pats.resize(K + 1, mint(0));

    cout << solve(N, K) << endl;

    return 0;
}


Measured memory_bytes: 4028
#include <bits/stdc++.h>
#define ls (o << 1)
#define rs (o << 1 | 1)
using namespace std;

const int N = 200005;

struct Seg {
    int l, r;
    int len, cov;
} T[N << 2];

void push_up(int o) {
    if (T[o].cov)
        T[o].len = T[o].r - T[o].l + 1;
    else
        T[o].len = T[ls].len + T[rs].len;
}

void build(int o, int l, int r) {
    T[o].l = l; T[o].r = r;
    T[o].len = T[o].cov = 0;
    if (l == r)
        return;
    int m = (l + r) >> 1;
    build(ls, l, m);
    build(rs, m + 1, r);
}

void ins(int o, int l, int r) {
    if (T[o].l == l && T[o].r == r) {
        ++ T[o].cov;
        T[o].len = r - l + 1;
        return;
    }
    int m = (T[o].l + T[o].r) >> 1;
    if (r <= m)
        ins(ls, l, r);
    else if(l > m)
        ins(rs, l, r);
    else {
        ins(ls, l, m);
        ins(rs, m + 1, r);
    }
    push_up(o);
}

void del(int o, int l, int r) {
    if (T[o].l == l && T[o].r == r) {
        -- T[o].cov;
        if (T[o].cov)
            T[o].len = r - l + 1;
        else
            T[o].len = l == r ? 0 : T[ls].len + T[rs].len;
        return;
    }
    int m = (T[o].l + T[o].r) >> 1;
    if (r <= m)
        del(ls, l, r);
    else if(l > m)
        del(rs, l, r);
    else {
        del(ls, l, m);
        del(rs, m + 1, r);
    }
    push_up(o);
}

int A[N], C[N];

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i) {
        scanf("%d", C + i);
        ++ A[C[i]];
    }
    build(1, 1, n);
    for (int i = 1; i <= n; ++ i) {
        if (A[i] == 0)
            continue;
        ins(1, max(i - A[i] + 1, 1), i);
    }
    while (m --) {
        int x, y;
        scanf("%d%d", &x, &y);
        del(1, max(C[x] - A[C[x]] + 1, 1), C[x]);
        if (-- A[C[x]] > 0)
            ins(1, max(C[x] - A[C[x]] + 1, 1), C[x]);
        C[x] = y;
        if (A[y] > 0)
            del(1, max(y - A[y] + 1, 1), y);
        ++ A[y];
        ins(1, max(y - A[y] + 1, 1), y);
        printf("%d\n", n - T[1].len);
    }
    return 0;
}


Measured memory_bytes: 11648
from collections import deque

H, W = map(int, input().split())

S = [['#'] * (W + 2)]
for _ in range(H):
    tmp = ['#'] + list(input()) + ['#']
    S.append(tmp)
S.append(['#'] * (W + 2))

move = [[1, 0], [-1, 0], [0, 1], [0, -1]]

ans = 0
# スタート位置を変えながら全探索
for X in range(1, H + 1):
    for Y in range(1, W + 1):
        if S[X][Y] == '#':
            continue
        check = [[-1] * (W + 2) for _ in range(H + 2)]
        check[X][Y] = 0
        que = deque()
        que.append([X, Y])
        while que:
            tmp = que.popleft()
            x = tmp[0]
            y = tmp[1]
            flag = True
            for dx, dy in move:
                nx = x + dx
                ny = y + dy
                if S[nx][ny] == '.' and check[nx][ny] == -1:
                    que.append([nx, ny])
                    check[nx][ny] = check[x][y] + 1
                    flag = False
            if flag:
                ans = max(ans, check[x][y])


print (ans)

Measured memory_bytes: 3444