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

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

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


int main(void)
{
    int a,b,i;
    string s;

    cin >> s;
    
    a=0;

    if(s[0] == 'R'){
        a++;
        if(s[1] == 'R'){
            a++;
            if(s[2] == 'R')a++;
        }
    }else{
        if(s[1] == 'R'){
            a++;
            if(s[2] == 'R')a++;
        }else if(s[2] == 'R')a++;
    }

    cout << a;
}

Measured memory_bytes: 3604
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <algorithm>
#include <utility>
#include <functional>
#include <fstream>
#define debug(x) cout << #x << " = " << x << endl
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,n) for(int i = 0; i < (n); i++)
#define repr(i,n) for(int i = (n); i > -1; i--)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const double EPS = 1e-9;


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

  string s,t;
  cin>>s>>t;
  bool done = false;
  for(int i = s.size() - 1; i >= 0; i--) {
    bool flag = true;
    rep(j, t.size()) {
      if(i + j > s.size() - 1 || (s[i + j] != t[j] && s[i + j] != '?')) {
        flag = false;
        break;
      }
    }
    if(flag) {
      s.replace(i, t.size(), t);
      done = true;
      break;
    }
  }
  if(!done) {
    cout << "UNRESTORABLE" << endl;
  } else {
    rep(i, s.size()) {
      if(s[i] == '?') {
        cout << 'a';
      } else {
        cout << s[i];
      }
    }
    cout << endl;
  }

  

  return 0;
}


Measured memory_bytes: 256
data = []
ans = 0
n, k = map(int,input().split())
  
for i in range(n):
  if(i+1 >= k):
    data.append(1.0/n)
  elif((i+1)%2==0):
    data.append(data[(i+1)//2-1]*2.0)
  else:
    j = 0
    while True:
      j+=1
      if(k<=(i+1)*2**j):
        break
    data.append(1.0/(n*2**j))
  
for i in range(n):
  ans += data[i]

print(ans)

Measured memory_bytes: 6296
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <set>
#include <utility>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <cstdio>
#include <map>
#include <list>

using namespace std;

typedef long long Int;
typedef pair<Int,Int> P;

#define rep(i,x) for(Int i = 0; i < (Int)(x); i++)
#define rrep(i,x) for(Int i = ((Int)(x) - 1); i >= 0; i--)
#define _upgrade ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define pb push_back
#define MX 100010


template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

//ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
//ll lcm(ll x, ll y) {return x / gcd(x, y) * y;}

Int dx[4] = {1,0,-1,0};
Int dy[4] = {0,1,0,-1};
const Int INF = 1001002003004005006ll;
const Int mod = 1e9 + 7;
const double PI = 3.14159265358979323846;


// ****************************************CODE***************************************//










Int n;
Int a[300010];

int main(){
        cin >> n;
        for(Int i = 0; i < 3*n; i++) cin >> a[i];
        sort(a,a+3*n);

        Int ans = 0;
        int cnt = 0;
        for(Int i = 3*n-2; i >= 0; i -= 2){
                if(cnt == n) break;
                ans += a[i];
                cnt++;
        }

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











Measured memory_bytes: 2560
#include <stdio.h>
#include <algorithm>
#include <math.h>

using namespace std;

int table[15][15],n;

void func(int row,int col,int num){
	if(num > n*n)return;

	if(col < 0){
		func(row,n-1,num);
	}else if(col >= n){
		func(row,0,num);
	}else if(row >=  n){
		func(0,col,num);
	}else if(table[row][col] != 0){
		func(row+1,col-1,num);
	}else{
		table[row][col] = num;
		func(row+1,col+1,num+1);
	}
}

int main(){

	while(true){
		scanf("%d",&n);
		if(n == 0)break;

		for(int i=0; i < n; i++){
			for(int k=0; k < n; k++)table[i][k] = 0;
		}

		table[(n+1)/2][(n-1)/2] = 1;
		func((n+1)/2+1,(n-1)/2+1,2);

		for(int i = 0; i < n; i++){
			for(int k=0; k < n; k++){
				printf("%4d",table[i][k]);
			}
			printf("\n");
		}
	}

	return 0;
}

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

int main() {
	vector<int> cost(3);
  for(int i = 0;i < 3;i++){
    cin >> cost.at(i) ;
  }
  sort(cost.begin(),cost.end());
  int ans = 0;
  ans = (cost.at(2) - cost.at(1)) + (cost.at(1) - cost.at(0));
	cout << ans << endl;
}

Measured memory_bytes: 256
N = map(int, input())
S = input()
S_list = list(S) #これで一文字ずつの配列にする
S_list_process = []

#10
#aabbbbaacaならabacaになる。

checkchar = ""
for char in S_list:
    if checkchar != char:
        S_list_process.append(char)
        checkchar = char

print(len(S_list_process))

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

#define int long long
#define pb push_back
#define f first
#define s second
#define all(container) container.begin(),container.end()

#define fast ios::sync_with_stdio(0); cin.tie(0)

int32_t main(){
  
    fast;
    int n; cin >> n;
    cout << (n*(n+1))/2;
 
 
    return 0;
} 

Measured memory_bytes: 256
#include<iostream>

using namespace std;

void print(int h,int w)
{
    for(int i=0;i<h;i++){
        if(i==0 || i==h-1){
            for(int j=0;j<w;j++){
                cout<<'#';
            }       
            cout<<'\n';
        }
        else{
            cout<<'#';
            for(int j=1;j<w-1;j++)  cout<<'.';
            cout<<"#\n";
        }
    }
}

int main()
{
    int H[1000],W[1000];

    for(int i=0;;i++){
        cin>>H[i]>>W[i];
        if(H[i]==0 && W[i]==0)  break;
    }

    for(int i=0;;i++){
        if(H[i]==0 && W[i]==0)  break;
        print(H[i],W[i]);
        cout<<'\n';
    }
}


Measured memory_bytes: 3076
#include <stdio.h>
#include <math.h>

int main( void ) {
	int i, e, ee, x, y, z, min;

	while ( scanf( "%d", &e ), e ) {
		min = e;
		for ( z = 0; z * z * z <= e; z++ ) {
			ee = e - z * z * z;
			y = sqrt( ee );
			x = ee - y * y;
			
			if ( x + y + z < min )
				min = x + y + z;
		}

		printf( "%d\n", min );
	}

	return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
#define ll long long
#define MODV 1000000007
#define INFLL LLONG_MAX // 9223372036854775807
#define EPS 1e-9
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
#define Init() std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout<<fixed<<setprecision(15);
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; }
using namespace std;

int main(){
    Init();
    ll a, b, c, d, e, f;
    cin >> a >> b >> c >> d >> e >> f;
    ll anss = 0, anst = (min(a,b)*100 <= f) ? min(a,b)*100 : 0;
    double cons = 0.0;
    
    for(ll i=0; i<= 30; i++){
        if(100*a*i > f) break;
        for(ll j=0; j<= 30; j++){
            if(100*a*i + 100*b*j > f) break;
            for(ll k=0;; k++){
                if(100*a*i + 100*b*j + c*k > f || (a+b)*e < c*k) break;
                for(ll l=0;; l++){
                    if(100*a*i + 100*b*j + c*k + d*l > f || (a*i+b*j)*e < c*k + d*l) break;
                    double tmp = (i == 0 && j==0 && k==0 && l== 0) ? 0.0 : (100.0*(c*k + d*l))/(100.0*a*i + 100.0*b*j + c*k + d*l);
                    if(cons < tmp){
                        cons = tmp;
                        anss = c*k + d*l;
                        anst = 100*a*i + 100*b*j + anss;
                    }
                }
            }
        }
    }
    cout << anst << " " << anss << endl;
}

Measured memory_bytes: 3592
#include <iostream>
#include<string>
#include<map>
#include<queue>
using namespace std;
int main()
{
	int n, m; priority_queue<int>s;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		int k;
		scanf("%d", &k);
		s.push(k);
	}
	while (m--)
	{
		int q = s.top();
		s.pop();
		s.push(q / 2);
	}
	long long sum = 0;
	while (!s.empty())
	{
		sum += s.top();
		s.pop();
	}
	cout << sum << endl;
	return 0;
}


Measured memory_bytes: 892
#coding:utf-8
import math
n, d = map(int, input().split())

grid = []
for i in range(n):
    array = list(map(int, input().strip().split()))
    grid.append(array)

#print(grid)
counter = 0

for i in range(n):
    for j in range(i+1,n):
        tmp = 0
        for k in range(d):
            tmp += (grid[i][k] - grid[j][k])**2

        #y^2がkと等しければ整数があることになる
        if int(round(math.sqrt(float(tmp)))**2) == tmp:
            counter += 1


print(counter)

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

#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define intll int long long
const int INF = 1e9;
const int MOD = 1e9 + 7;

int main() {
 int x , y , z ;
  cin >> x >> y >> z ;
  
  cout << z <<" "  <<  x << " " << y ;


}


Measured memory_bytes: 256
#include <cstdio>
#include <cmath>

double thirdRoot(int q)
{
    if (q == 1) {
        return 1.;
    }

    double xn = q / 2;
    double xn2 = xn;
    double limit = q * 0.00001;
    while (true) {
        xn2 = xn - (xn*xn*xn - q) / (3*xn*xn);
        if (fabs(xn2*xn2*xn2 - q) < limit) {
            break;
        }
        xn = xn2;
    }

    return xn2;
}

int main()
{
    int q;
    while (true) {
        scanf("%d", &q);
        if (q < 0) {
            break;
        }
        printf("%6lf\n", thirdRoot(q));
    }

    return 0;
}


Measured memory_bytes: 2564
N = int(input())
H = list(map(int, input().split()))
H.append(0)
ans = []
start = 0
prev = 0
for i in H:
  if prev > i and prev != start:
    ans.append(prev - start)
    start = i
  elif start > i:
    start = i
  prev = i

print(sum(ans))

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

void solve(std::string S)
{
    cout << ((S == "ABC") ? "ARC" : "ABC") << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main()
{
    std::string S;
    std::cin >> S;
    solve(S);
    return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include <stdio.h>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <iomanip>

#define ll long long
#define ld long double
#define ull unsigned long long
#define endl "\n"
#define MohamedMotaz ios::sync_with_stdio(0); cin.tie(0); ios_base::sync_with_stdio(0);
#define f(a, b, c) for(int a = b; a < c; a++)
using namespace std;


//ll fact[1000001]; ll inv[1000001];
//ll primes[100007];
//ll arr[1000007];
//ll modPower(ll b, ll p) {
//	if (p == 0)
//		return 1;
//
//	ll halfpow = modPower(b, p / 2);
//	ll toReturn = (halfpow * halfpow) % mod;
//	if (p % 2)
//		toReturn = (toReturn * b) % mod;
//
//	return toReturn;
//}
//
//ll fastPower(ll b, ll p) {
//	if (p == 0)
//		return 1;
//	ll ans = fastPower(b, p / 2);
//	ans = (ans * ans);
//	if (p % 2 != 0)
//		ans = (ans * b);
//	return ans;
//}
//ll GcdRecursive(ll a, ll b) {
//	if (b == 0) return a;
//	return GcdRecursive(b, a % b);
//}
//ll modLCM(ll a, ll b) {
//	ll val = GcdRecursive(a, b);
//	ll tmp = ((a % mod) * (b % mod)) % mod;
//	ll finalVal = ((tmp % mod) * (arr[val] % mod)) % mod;
//	return finalVal;
//
//}
//ll LCM(ll a, ll b) {
//	return (a * b) / GcdRecursive(a, b);
//}
//void move1step(ll& a, ll& b, ll q) { // a and b by reference
//	ll c = a - q * b;
//	a = b;
//	b = c;
//}
//ll GcdIterative(ll a, ll b) {
//	while (b) move1step(a, b, a / b);
//	return a;
//}
//
//void pre(ll n) {
//
//	fact[0] = 1;
//	inv[0] = 1;
//
//	for (ll i = 1; i <= n; i++) {
//		fact[i] = (i * fact[i - 1]) % mod;
//		inv[i] = modPower(fact[i], mod - 2);
//		arr[i] = modPower(i, mod - 2);
//	}
//}
//
//ll npr(ll n, ll r) {
//	return ((fact[n] * inv[n - r]) % mod);
//}
//
//ll ncr(ll n, ll r) {
//	return ((((fact[n] * inv[n - r]) % mod) * inv[r]) % mod);
//}
//
//void sieve(ll val) {
//	memset(primes, 1, sizeof primes);
//	primes[0] = primes[1] = false;
//	for (int i = 2; i <= val; i++) {
//		if (primes[i]) {
//			for (int j = i * i; j <= val; j += i) {
//				primes[j] = 0;
//			}
//		}
//	}
//
//}

const ll mod = 1e9 + 7;
const ll N = 1e5 + 7;

ll n, w;
ll val[107] = {}, weight[107] = {};
ll dp[107][N];
int main()
{
    MohamedMotaz;
    cin >> n >> w;
    f(i,1,n + 1) cin >> val[i] >> weight[i];
    //f(i,1 , n + 1) cout << val[i] << " " << weight[i] << endl;
    f(i, 1, n + 1){
        f(j, 1, w + 1){
            //cout << "now at i and j: " << i << " " << j << endl;
            //two options
            ll op1 = 0, op2 = 0;
            //take
            op1 = dp[i - 1][j];
            //cout << "op1 is now: " << op1 << endl;
            //leave
            if (j >= val[i]) op2 = weight[i] +  dp[i - 1][j - val[i]];//, cout << "yayayyay";
            //cout << "op2 is now: " << op2 << endl;
            dp[i][j] = max(op1, op2);
        }
    }


    cout << dp[n][w];
}



Measured memory_bytes: 79360
import math
N, M, X = map(int, input().split())
C = []
A = []
for i in range(N):
  l = list(map(int, input().split()))
  C.append(l[0])
  A.append(l[1:])
  
ans = math.inf
for i in range(2**N):
  a = [0]*M
  c = 0
  flag = True
  for j in range(N):
    if ((i >> j) & 1):
      a = list(map(sum, zip(a, A[j-1])))
      c += C[j-1]
  for x in a:
    if x < X:
      flag = False
      break
  if flag:
    ans = min(ans, c)
    
if ans == math.inf:
  ans = -1
print(ans)

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

double a;

string b;

long double ans;

int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		cin>>a>>b;
		if(b=="JPY") ans+=a;
		else ans+=380000.0*a;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <stdlib.h>
#include <functional>
#include <string>
#include <list>
#include <fstream>
#include <iomanip>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <nmmintrin.h>
#include <chrono>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) <= (b))
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define MODU 1000000007
#define bitcheck(a,b)   ((a >> b) & 1)
#define bitset(a,b)      ( a |= (1 << b))
#define bitunset(a,b)    (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
	std::fill((T*)array, (T*)(array + N), val);
}

struct Edge {
	int from, to;
};

signed main()
{

	int n;
	cin >> n;
	vector<ll> x(n);

	REP(i, n) {
		scanf("%lld", &x[i]);
	}

	ll m, k;
	cin >> m >> k;
	vector<int> w(m);
	REP(i, m) {
		scanf("%d", &w[i]);
		w[i]--;
	}

	vector<vector<int>> sw(65, vector<int>(n-1));
	REP(i, n - 1) {
		sw[0][i] = i;
	}
	REP(i, m) {
		swap(sw[0][w[i] - 1], sw[0][w[i]]);
	}
	rep(cc,1,65){
		REP(i, n-1) {
			sw[cc][i] = sw[cc-1][sw[cc-1][i]];
		}
	}
	vector<int> fn(n - 1);
	REP(i, n - 1) {
		fn[i] = i;
	}
	ll cc = 0;
	ll cl = 1;
	int bai = 0;
	while (cc < k) {
		if (cc + cl <= k) {
			vector<int> nfn(fn);
			REP(i, n - 1) {
				nfn[i] = fn[sw[bai][i]];
			}
			cc += cl;
			cl *= 2;
			bai++;
			fn.swap(nfn);
		}
		else {
			cl /= 2;
			bai--;
		}
	}

	ll cs = x[0];

	cout << x[0] << endl;
	REP(i, n-1) {
		cs = cs + x[fn[i] + 1] - x[fn[i]];
		printf("%lld\n",cs);
	}

	return 0;
}

Measured memory_bytes: 28664
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static ArrayList<Integer>[] adj;
	static long dp[][];
	static int m = 1000000007;
	// dp[i][j] number of ways to print the i rooted tree with or without
	// constraints
	// there can be only two possibilities that parent of i is black than we have to
	// print i with W otherwise we have no constraints

	public static long Solve(int u, int constraint, int parent) {

		if (dp[u][constraint] != -1)
			return dp[u][constraint];

		long ans = 0;
		// we will always colour white whether parent is white or black
		long w1 = 1;
		for (int v : adj[u]) {
			if (v != parent) {
				w1 = (w1 % m * Solve(v, 0, u) % m) % m;
			}
		}
		ans = (ans % m + w1 % m) % m;

		// we can print black only when parent is white
		if (constraint == 0) {
			long w2 = 1;
			for (int v : adj[u]) {
				if (v != parent) {
					w2 = (w2 % m * Solve(v, 1, u) % m) % m;
				}
			}
			ans = (ans % m + w2 % m) % m;
		}

		dp[u][constraint] = ans;
		return dp[u][constraint];

	}

	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		int n = sc.nextInt();
		adj = new ArrayList[n + 1];
		for (int i = 0; i <= n; i++)
			adj[i] = new ArrayList<>();

		for (int i = 0; i < n - 1; i++) {
			int x = sc.nextInt(), y = sc.nextInt();
			adj[x].add(y);
			adj[y].add(x);
		}

		dp = new long[100005][2];
		for (int i = 0; i < 100005; i++)
			Arrays.fill(dp[i], -1);

		long ans = Solve(1, 0, -1);
		System.out.println(ans);

	}

	static class FastScanner {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");

		String next() {
			while (!st.hasMoreTokens())
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		int[] readArray(int n) {
			int a[] = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

	}

}


Measured memory_bytes: 87552
//09
#include<iostream>

using namespace std;

int main(){
  int i;
  char c;
  while(cin>>i>>c){
    if(i==0&&c=='U'){
      cout<<"nn";
    }else{
      const char *v[]={"w","","k","s","t","n","h","m","y","r"};
      cout<<v[i]<<((c=='T')?'a'
		   :(c=='L')?'i'
		   :(c=='U')?'u'
		   :(c=='R')?'e'
		   :'o');
    }
  }
  cout<<endl;
}

Measured memory_bytes: 1156
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4e2+20;
int n,m,a[N][N],cnt[N],vis[N];
bool check(int x)
{
	memset(vis,0,sizeof(vis));
	while(true)
	{
		memset(cnt,0,sizeof(cnt));
		int num=0;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				if(!vis[a[i][j]])
				{
					cnt[a[i][j]]++;
					num++;
					break;
				}
			}
		}
		bool flag=true;
		for(int i=1;i<=m;i++)
		{
			if(cnt[i]>x)
			{
				vis[i]=1;
				flag=false;
			}	
		}
		if(num<n)
			return false;
		if(num==n&&flag)
			return true;	
	}
} 
int main()
{
	while(cin>>n>>m)
	{
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				scanf("%d",&a[i][j]);
		int l=1,r=n;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(check(mid))
				r=mid-1;
			else
				l=mid+1;
		}
		cout<<r+1<<endl;
	}
	return 0;
}


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


int main(){
    int n, tmp, cnt = 0;
    cin >> n;
    rep(i,n){
        cin >> tmp;
        if(tmp != i+1) cnt++;
    }
    if(cnt == 2 || cnt == 0) cout << "YES\n";
    else cout << "NO\n";

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using i64 = long long;

int main() {
    i64 n, k;
    std::cin >> n >> k;
    if (k > (n + 1) / 2) {
        std::cout << -1 << std::endl;
        return 0;
    }

    std::set<std::tuple<i64, i64, i64>, std::greater<>> v;
    for (int i = 0, j = n - k; i < n; i++) {
        i64 a = i, b = n + (j + i) % n;
        v.emplace(a + b, a, b);
    }

    auto it = v.begin();
    for (int i = 3 * n - 1; i >= 2 * n; i--) {
        auto a = std::get<1>(*it), b = std::get<2>(*it);
        it++;
        std::cout << a + k << ' ' << b + k << ' ' << i + k << '\n';
    }

    std::cout << std::flush;

    return 0;
}


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

int main(){

    //データ定義
    int width;
    int height;

    //入力されたデータを取得
    cin >> width >> height;

    //面積と周の長さを出力
    cout << width * height << " " << 2 * width + 2 * height << endl;

    return 0;
}


Measured memory_bytes: 3084
A = int(input())  # 500
B = int(input())  # 100
C = int(input())  # 50
X = int(input())  # 合計

c = 0
for i in range(C+1):
    for j in range(B+1):
        for k in range(A+1):
            if (50 * i) + (100 * j) + (500 * k) == X:
                c += 1
print(c)

Measured memory_bytes: 3060
module Main where
import Debug.Trace
import Data.List
import Data.Maybe
import Data.Ord
import Control.Monad

solve :: [[Int]] -> [String]
solve [] = []
solve ([h,w]:xs) = iter 1 where
    iter row
        | row == 1  = [replicate w '#'] ++  iter (row+1)
        | row == h  = [replicate w '#' ++ "\n"] ++ solve xs
        | otherwise = ['#':(replicate (w-2) '.')++"#"] ++  iter (row+1)

readLine:: IO [Int]
readLine = fmap (map read . words) getLine

readUntil :: ([Int] -> Bool) -> IO [[Int]]
readUntil eof = iter where
    iter = readLine >>=
            (\a -> if eof a then return [] else fmap (a:) iter)

eof :: [Int] -> Bool
eof (x0:x1:xs) = [x0, x1] == [0, 0]

main :: IO() 
main = do
    l <- readUntil eof
    mapM_  putStrLn (solve l)
    


Measured memory_bytes: 4072
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
#include <stack>
#include <deque>
#include <cmath>
#include <map>
using namespace std;
using ll = long long;
#define rep(i, n) for (ll i = 0; i < n; i++)
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

int main() {
    ll n;
    cin >> n;
    ll cntodd = 1, total = 1;
    rep(i, n) {
        ll a;
        cin >> a;
        if (a % 2 == 0) cntodd *= 2;
        total *= 3;
    }
    cout << total - cntodd << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main (void) {
	int N, K;
	cin >> N>> K;
	vector<int> hoge(N);
	for(int i= 0; i < N; i++){
      cin >> hoge[i];
    }
  	sort(hoge.begin(), hoge.end());
  	int sum = 0;
  	for(int i = N-1; i > N-K-1; i--){
    	sum += hoge[i];
    }
  	cout << sum << endl;
	return 0; 
}

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

using namespace std;

int main()
{
	int A, B, C;
	cin >> A >> B >> C;
	int mi = min(A, B);
	int ma = max(A, B);
	if (mi <= C && C <= ma) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
	return 0;
}


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

using namespace std;

typedef long long ll;

int n, k;
double calc(int x){
	double ret = 1.0;
	ret /= 1.0 * n;

	int score = x;
	while(score < k){
		score *= 2;
		ret /= 1.0 * 2;
	}

	return ret;
}

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

	cin >> n >> k;

	double ans = 0.0;
	for(int i = 1; i <= n; i++){
		ans += calc(i);
	}

	cout << fixed << setprecision(11) << ans << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    private static final int MAX_N = 44;
    private static int[] d = new int[MAX_N+1];

    private static int n;

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();

        System.out.println(fibonacchi(n));
    }

    private static int fibonacchi(int n) {

        if (n <= 1)
            return 1;

        if (d[n] > 0)
            return d[n];

        d[n] = fibonacchi(n-1) + fibonacchi(n-2);

        return d[n];
    }
}

Measured memory_bytes: 26120
#include <iostream>

using namespace std;

int main(void){
    int N;
    cin >> N;
    int V[N];
    int C[N];
    int sum =0;
    for(int i = 0;i<N;i++) {
          cin >> V[i];
    }
    for(int i = 0;i<N;i++) {
          cin >> C[i];
          if(V[i]-C[i]>0){
            sum += V[i]-C[i];
          }
    }
   cout << sum;
    return 0;
}


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

//using Graph = vector<vector<edge>>;
using dou =long double;
string yes="yes";
string Yes="Yes";
string YES="YES";
string no="no";
string No="No";
string NO="NO";

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; }
#define rep(i, n)         for(int i = 0; i < (int)(n); i++)
#define brep(n)           for(int bit=0;bit<(1<<n);bit++)
#define erep(i,container) for (auto i : container)
#define irep(i, n)        for(int i = n-1; i >= (int)0; i--)
#define rrep(i,m,n) for(ll i = m; i < (ll)(n); i++)
#define reprep(i,j,h,w) rep(i,h)rep(j,w)
#define all(x) (x).begin(),(x).end()
#define VEC(type,name,n) std::vector<type> name(n);rep(i,n)std::cin >> name[i];
#define pb push_back
#define pf push_front
#define query int qq;std::cin >> qq;rep(qqq,qq)
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define itn int
#define mp make_pair
#define sum(a) accumulate(all(a),0ll)
#define keta fixed<<setprecision
#define vvector(name,typ,m,n,a)vector<vector<typ> > name(m,vector<typ> (n,a))
#define vvvector(name,t,l,m,n,a) vector<vector<vector<t> > > name(l, vector<vector<t> >(m, vector<t>(n,a)));
#define vvvvector(name,t,k,l,m,n,a) vector<vector<vector<vector<t> > > > name(k,vector<vector<vector<t> > >(l, vector<vector<t> >(m, vector<t>(n,a)) ));
#define case std::cout <<"Case #" <<qqq+1<<": "
#define res resize
#define as assign
#define ffor for(;;)
#define ppri(a,b) std::cout << a<<" "<<b << std::endl
#define pppri(a,b,c) std::cout << a<<" "<<b <<" "<< c<<std::endl
#define aall(x,n) (x).begin(),(x).begin()+(n)
#define ssum(a) accumulate(a,0ll) 

typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
//typedef long long T;
const int INF = 1000000000;
const ll INF64 = 922337203685477580ll;
const ll MOD = 1000000007ll;
const dou pi=3.141592653589793;

int main(){
    std::set<string> se;
    int n;
    std::cin >> n;
    rep(i,n){
        string d;
        std::cin >> d;
        se.insert(d);
    }
    std::cout << se.size() << std::endl;
}

Measured memory_bytes: 19176
#include<stdio.h>
#include<algorithm>
#include<functional>
#include<cmath>
using namespace std;
long long  mod = 1000000007;

long long gcd(long long  a, long long b)
{
	if (a < b) swap(a, b);
	if (b == 0) return a;
	return gcd(b, a % b);
}

long long  lcm(long long a, long long b)
{
	return a * (b / gcd(a, b));
}

int main()
{
	int N;
	long long T[100];
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%lld", &T[i]);
	}
	long long an = T[0];
	for (int i = 1; i < N; i++) {
		an = lcm(an, T[i]);
	}
	printf("%lld", an);
	return 0;
}

Measured memory_bytes: 128
import java.io.*;
import java.util.*;



public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str;
                    
        str = br.readLine();
        String[] line = str.split("\\s");
        int x = Integer.parseInt(line[0]);
        int y = Integer.parseInt(line[1]);
     
        int temp = 0;
        if(x > y){
            temp = y;
            y = x;
            x = temp;
        }

        temp = run(x,y);

        System.out.println(temp);
       
        br.close();
    }

    public static int run(int x,int y){
        if(x == 0){
            return y;
        }else{
            int m = y % x;
            return run(m,x);
        }
    }
}



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

using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

using Pi = pair<int, int>;
using Ti = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  string a;
  cin >> a;
  int n = a.size();
  int sum = n*(n+1)/2;
  int cnt[26] = {};
  rep(i, n) cnt[a[i]-'a']++;
  rep(i, 26) sum -= cnt[i]*(cnt[i]+1)/2;
  cout << sum+1 << endl;

  return 0;
}


Measured memory_bytes: 720
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main(){
    int s; cin >> s;
    vector<int> a={s};
    int i=1;
    a[0]=s;
    bool flag=true;
    while(flag){
        if (a[i-1]%2==0) a.push_back(a[i-1]/2);
        else a.push_back(3*a[i-1]+1);
        for (int j=0;j<a.size()-1;j++){
            if (a[i]==a[j]) {
                cout << i+1 << endl;
                flag = false;
                break;
            }
        }
        i++;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>

using namespace std;

int main(void)
{
	string S;
	long long K;
	cin >> S;
	cin >> K;
	for (int i = 0; i < S.size(); i++){
		if (S[i] != '1'){
			cout << S[i] << endl;
			return 0;
		}
		else if (K == 1){
			cout << S[i] << endl;
			return 0;
		}
		else{
			K--;
		}
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
///////////////////////////////////////////
const long long int INF = 1LL<<60;
const long long int Mod = 1000000007;
using ll = long long int; using ci = const int;
using vi = vector<int>;  using Vi = vector<long long int>;
using P = pair<int, int>;  using PLL = pair<ll, ll>;
using matrix = vector<vector<ll>>;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define rp(i,N) for(ll i = 0; i < (ll)N; i++)
#define repi(i,a,b) for(ll i = ll(a); i < ll(b); ++i)
template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
#define p_queue(v) priority_queue<v, vector<v>, greater<v> >
template<class T> inline void princ(T x){cout<<x<<" ";}; 
template<class T> inline void print(T x){cout<<x<<"\n";};
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
///////////////////////////////////////////////////////////////////////////////////

void solve(){
    int a,b;
    cin >> a >> b;
    if((a-b)%2==0){
        print((a+b)/2);
    }
    else print("IMPOSSIBLE");
    return;
}
int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    std::cout<<std::fixed<<std::setprecision(30);
    solve();
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define newl "\n"
using namespace std;
using lli = long long int;
using vvint = vector <vector <int>>;
const int mod = 1e9 + 7;

const int N = 2e5 + 1;

void solve(){
	string s;
	cin >> s;
	cout << s.substr(0,3) << newl;

	return;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout << fixed << setprecision(10);
	#ifdef EXECUTE_LOCALLY
		   freopen("in.txt","r",stdin);
	#endif
	int t = 1;
	//cin >> t;
	while(t--) solve();
	#ifdef EXECUTE_LOCALLY
    	cout << setprecision(3) << "program time: " << (double)clock() / CLOCKS_PER_SEC << newl;
	#endif
	return 0;
}


Measured memory_bytes: 3564
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;

const ll P = 1000000007;
int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

int main()
{
  cout << fixed << setprecision(10);
  int N;
  cin >> N;
  vector<int> a(N);
  ll sum = 0;
  rep(i,N) cin >> a[i];
  rep(i,N)
  {
    sum += a[i] - 1;
  }
  cout << sum << endl;
  return 0;
}


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

typedef long long int ll;
typedef pair<ll, ll> p_ll;
typedef vector<pair<ll, ll>> vec_p; //vector<pair<ll, ll>> pairs(n) ,pairs.at(i) = make_pair(i*i, i)

#define ture ture
#define flase false
#define falg flag

#define REP(i, x) for (ll i = 0; i < (ll)(x); i++)
#define REPS(i, x) for (ll i = 1; i <= (ll)(x); i++)
#define RREP(i, x) for (ll i = ((ll)(x)-1); i >= 0; i--)
#define RREPS(i, x) for (ll i = ((ll)(x)); i > 0; i--)
#define all(x) (x).begin(), (x).end()

const ll MOD = pow(10, 9) + 7;
const ll LLINF = pow(2, 61) - 1;//llの最大9*10^18
const int INF = pow(2, 30) - 1;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }



long long modpow(long long a, long long n, long long mod)
{
    long long res = 1;
    while (n > 0)
    {
        if (n & 1)
            res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

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

    ll N;
    string S;
    cin >> N;

    vector<ll> A(N);

    REP(i,N){
        cin >> A.at(i);
    }

    /*Bint sum = 0;

    REP(i, N)
    {
        sum += (Bint)A.at(i);
        //sum %= MOD;
    }

    Bint tmp = sum * sum;

    Bint sum_d = 0;
    REP(i, N)
    {
        sum_d = (Bint)(A.at(i) * A.at(i) );
    }*/

    ll sum=0;
    REP(i, N)
    {
        sum += A.at(i);
        sum %= MOD;
    }

    ll tmp = sum * sum % MOD;
    sum = tmp;

    //cout << "sum" << sum << endl;

    ll sum_d = 0;
    REP(i, N)
    {
        sum_d += (A.at(i) * A.at(i));
        sum_d %= MOD;
    }
    //cout << "sum_d" << sum_d << endl;

    ll tmp1 = (sum - sum_d+MOD)%MOD;

    ll tmp2 = modpow(2, 1000000005, MOD);

    cout << tmp1 * tmp2 % MOD << endl;

}


Measured memory_bytes: 4752
#include <iostream>
 
using namespace std;
  int a[100001];
int main() {
  
int n;
cin >> n;
   for (int i = 0; i < n; ++i) {
 int d;
cin >> d;
++a[d];
}
 
 int max = 0;
 
 for (int i = 0; i < 100000-2; ++i) {
 int q = a[i] + a[i+1] + a[i+2];
if (q>max) max=q;
}
cout << max;
}

Measured memory_bytes: 640
import Control.Arrow
import Control.Monad
import Data.List
import qualified Data.ByteString.Char8 as B

main :: IO ()
main = getLine >>= print . solve

solve :: String -> Int
solve ss = count . map ((,) <$> head <*> length) $ group ss 
    where
        n = length ss
        count xs = check n xs
        check acc (('S', xl) : ('T', yl) : zs)
            | xl > yl = check (acc - 2 * yl) $ ('S', xl - yl) : zs
            | otherwise = check (acc - 2 * xl) zs
        check acc (('S', xl) : ('S', yl) : zs) = check acc $ ('S', xl + yl) : zs
        check acc ((_, _) : zs) = check acc zs
        check acc _ = acc

readLine :: IO [Int]
readLine = unfoldr (fmap (second (maybe B.empty snd . B.uncons)) . B.readInt) <$> B.getLine

readContents :: Int -> IO [[Int]]
readContents = flip replicateM readLine

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

int main() {
  int a;
  cin >> a; 
  vector<int> vec(a);
  int count=0;
  for(int i=0;i<a;i++){
    cin >> vec.at(i);
    //cout<<vec.at(i)<<endl;
    int n=0;
    while (vec.at(i-n)<=vec.at(i)){
      //cout<<i-n<<endl;
      n++;
      if(i-n==-1){
      count++;
      break;
      }
    }
  }
  cout<<count<<endl;
  
  
}

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

// types
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;

// macros
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

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

  ll n;
  cin >> n;

  vll a(n);
  vector<vector<pll>> say(n);
  REP(i, n){
    cin >> a[i];
    pll xy;
    REP(j, a[i]){
      cin >> xy.FI >> xy.SE;
      xy.FI--;
      say[i].push_back(xy);
    }
  }

  ll ans = 0;
  for(ll i = 0; i < (1<<n); i++){
    vll cas(n, 0);
    ll num = 0;
    REP(j, n){
      if((i>>j) & 1){
        cas[j] = 1;
        num++;
      }
    }

    //check
    bool sflag = true;
    REP(j, n){
      if(cas[j] != 1)
        continue;
      REP(k, a[j]){
        ll target = say[j][k].FI;
        if(cas[target] != say[j][k].SE)
          sflag = false;
      }
    }

    if(sflag)
      ans = max(ans, num);
  }

  cout << ans << endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define max(x, y) ((x) > (y) ? (x) : (y))
#define min(x, y) ((x) < (y) ? (x) : (y))
#define rep(i,a,m) for((i) = (a) ; (i) < (m) ; ++(i))
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define rall(x) x.end(),x.begin()
#define sz(x) ((int)x.size())
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pi;
int a, b, c, i, j, k;
long long ans = 0LL;
int main ()
{
	int t,T;
	scanf("%d",&T);

    if (T%2){
        cout << (T/2) + 1 << endl;
    } else {
        cout << T/2 << endl;
    }
	return 0;
}

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

using namespace std;

#define debug(n) cerr << #n << ':' << n << endl;
#define dline    cerr << __LINE__ << endl;

using ll = long long;
using ull = unsigned long long;
template<class T, class U> using P = pair<T,U>;
template<class T> using Heap = priority_queue<T>;
template<class T> using heaP = priority_queue<T,vector<T>,greater<T>>;
template<class T,class U> using umap = unordered_map<T,U>;
template<class T> using uset = unordered_set<T>;

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

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

template<class T, size_t N, class U>
void Fill(T (&a)[N], const U&v){
    fill((U*)a,(U*)(a+N),v);
}

template<class T>
istream& operator >> (istream&is, vector<T>&v){
  for(auto&e:v)is >> e;
  return is;
}

int Sum(const string&s){
  int n = (int)s.size();
  int sum = 0;
  for(int i = 0; i < n; ++i)sum += s[i] - '0';
  return sum;
}

int main(){
  string s; cin >> s;
  int n = 0;
  for(int i = 0; i < 3; ++i)n += s[i] == 'o';
  cout << 700 + n * 100 << endl;
}


Measured memory_bytes: 3564
N, M = map(int, input().split())
from collections import*
c = Counter(map(int, input().split()))
for _ in range(M):
    B, C = map(int, input().split())
    c[C] = c[C] + B if C in c else B
c = sorted(c.items(), reverse=True)
s = 0
for i in c:
    s += i[0] * min(i[1],N)
    N -= min(i[1],N)
print(s)


Measured memory_bytes: 112184
import java.io.*;

class Main{
  public static void main(String[] args) {

    InputStreamReader sr = new InputStreamReader(System.in);
    BufferedReader br = new BufferedReader(sr);
    try{
      String str = br.readLine();
      int a = Integer.parseInt(str);
      int h = a / 3600;
      int m = a % 3600 / 60;
      int s = a % 3600 % 60;

      System.out.println(h+":"+m+":"+s);
    }
    catch(IOException e) {
            e.printStackTrace();
    }
  }
}

Measured memory_bytes: 24428
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define reps(i, s, n) for(int i = (int)s; i < (int)n; i++)
#define in(i) std::cin >> i;
#define print(i) std::cout << i;
#define println(i) std::cout << i << std::endl;
using namespace std;

int main() {
    long x, m = 100, i;
    
    cin >> x;
    
    for(i = 0; m < x; i++) {
       m = m + (long)(m * 0.01);
    }
    
    
    cout << i << endl;
    
    return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
const int INF=1e9;
//const int MOD=998244353;
const long long LINF=1e18;
#define int long long
//template
int black[2005][2005],ver[2005][2005],wid[2005][2005];
//main
signed main(){
  int N,M,Q;cin>>N>>M>>Q;
  std::vector<string> s(N+1);
  for(int i=0;i<N;i++)cin>>s[i];
  s[N]=(string(M,'#'));
  for(int i=0;i<=N;i++)s[i]+="#";
  for(int i=0;i<N;i++){
    for(int j=0;j<M;j++){
      if(s[i][j]=='1')black[i+1][j+1]++;
      if(s[i][j]=='1'&&s[i][j+1]=='1')ver[i+1][j+1]++;
      if(s[i][j]=='1'&&s[i+1][j]=='1')wid[i+1][j+1]++;
    }
  }
  for(int i=0;i<=N;i++){
    for(int j=0;j<=M;j++){
      black[i][j+1]+=black[i][j];
      ver[i][j+1]+=ver[i][j];
      wid[i][j+1]+=wid[i][j];
    }
  }
  for(int i=0;i<=N;i++){
    for(int j=0;j<=M;j++){
      black[i+1][j]+=black[i][j];
      ver[i+1][j]+=ver[i][j];
      wid[i+1][j]+=wid[i][j];
    }
  }
  std::vector<int> ans(Q);
  for(int i=0;i<Q;i++){
    int x1,x2,y1,y2;cin>>x1>>y1>>x2>>y2;
    int B=black[x2][y2]+black[x1-1][y1-1]-black[x2][y1-1]-black[x1-1][y2];
    int E1=ver[x2][y2-1]+ver[x1-1][y1-1]-ver[x2][y1-1]-ver[x1-1][y2-1];
    int E2=wid[x2-1][y2]+wid[x1-1][y1-1]-wid[x2-1][y1-1]-wid[x1-1][y2];
    ans[i]=B-E1-E2;
  }
  for(int i=0;i<Q;i++)cout<<ans[i]<<endl;
}
 

Measured memory_bytes: 101632
mod = 10**9 + 7
from collections import deque

def main():
    N = iip(False)
    A = iip(True)

    result = [0] * (N+2)
    ans = []

    for i in range(N, 0, -1):
        #s = sum(result[i::i])
        s = 0
        for j in range(1000000):
            if i*j > N+1:
                break
            s += result[i*j]

        if s % 2 != A[i-1]:
            result[i] = 1


    print(sum(result))

    #print(result)
    for i, res in enumerate(result):
        if res == 1:
            ans.append(i)
    split_print_space(ans)


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))

def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        #print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r-l > 1:
        x = (l+r)//2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <=0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n-r+1, n+1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r+1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        #print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod-2)

def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p//2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p-1)) % mod


if __name__ == "__main__":
    main()

Measured memory_bytes: 20252
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define INF INT_MAX;
using namespace std;

int main(){
  int N; cin >> N;
  map<string,int> money;
  rep(i,N){
    string s; cin >> s;
    money[s]++;
  }

  int M; cin >> M;
  rep(i,M){
    string s; cin >> s;
    money[s]--;
  }

  int ans = 0;
  for(auto m:money){
    ans = max(m.second,ans);
  }

  cout << ans <<endl;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define i_7 (ll)(1E9+7)
#define i_5 (ll)(1E9+5)
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    else return c+i_7;
}
typedef pair<int,int> i_i;
typedef pair<ll,ll> l_l;
ll inf=(ll)1E12;//10^12
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
const double EPS=1E-8;
////////////////////////////////////////


int main() {
    ios::sync_with_stdio(false);cin.tie(0);
    
    int n,m;cin>>n>>m;
    vector<int>v[n+1];
    int a,b;
    rep(i,0,m-1){
        cin>>a>>b;
        v[a].pb(b);v[b].pb(a);
    }
    list<int>l;
    l.push_front(a);l.pb(b);
    int s=a,t=b;
    bool res[n+1];memset(res,true,sizeof(res));
    res[a]=false;res[b]=false;
    while(1){
        bool flag=true;
        for(int x:v[s]){
            if(res[x]){
                l.push_front(x);
                res[x]=false;
                s=x;
                flag=false;
                break;
            }
        }
        if(flag)break;
    }
    while(1){
        bool flag=true;
        for(int x:v[t]){
            if(res[x]){
                l.push_back(x);
                res[x]=false;
                t=x;
                flag=false;
                break;
            }
        }
        if(flag)break;
    }
    cout<<l.size()<<endl;
    for(auto ite=l.begin();ite!=l.end();ite++){
        cout<<*ite<<" ";
    }
    
    
    return 0;
}

Measured memory_bytes: 9472
#coding:utf-8
N = int(input())
A = list(map(int,input().split()))
A.append(0)
A.insert(0,0)
ans = 0
for n in range(N+1):
    ans+=abs(A[n]-A[n+1])
for n in range(N):
    if (min(A[n],A[n+2])<=A[n+1] and A[n+1]<=max(A[n],A[n+2])):
        print (ans)
    else:
        print (ans - 2 * min(abs(A[n+1]-A[n]),abs(A[n+1]-A[n+2])))


Measured memory_bytes: 14172