akhauriyash/Code-Regression huggingface dataset:
// Template {{{
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
using namespace std;
typedef long long LL;

#ifdef LOCAL
#include "contest.h"
#else
#define dump(x) 
#endif

class range {
    struct Iterator {
        int val, inc;
        int operator*() {return val;}
        bool operator!=(Iterator& rhs) {return val < rhs.val;}
        void operator++() {val += inc;}
    };
    Iterator i, n;
    public:
    range(int e) : i({0, 1}), n({e, 1}) {}
    range(int b, int e) : i({b, 1}), n({e, 1}) {}
    range(int b, int e, int inc) : i({b, inc}), n({e, inc}) {}
    Iterator& begin() {return i;}
    Iterator& end() {return n;}
};

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
inline bool valid(int x, int w) { return 0 <= x && x < w; }

void iostream_init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.setf(ios::fixed);
    cout.precision(12);
}
//}}}

typedef vector<int> Node;
typedef vector<Node> Graph;
int dp[202][202];
int size[202];
const int MOD = 1e9 + 7;
int memo[202][202][402];
int ways(int a, int b, int c) {
    assert(a <= c);
    assert(b <= c);
    assert(c <= a+b);
    if(memo[a][b][c] != -1) return memo[a][b][c];
    if(c == 0) return 1;
    int res = 0;
    if(a > 0 && b <= c-1){ res += ways(a-1, b, c-1); res %= MOD; }
    if(b > 0 && a <= c-1){ res += ways(a, b-1, c-1); res %= MOD; }
    if(a > 0 && b > 0 && c-1 <= a-1+b-1){ res += ways(a-1, b-1, c-1); res %= MOD; }
    return memo[a][b][c] = res;
}
void rec(const Graph& G, int u, int p) {
    size[u] = 1;
    for(int v : G[u]) if(v != p) {
        rec(G, v, u);
        size[u] += size[v];
    }
    int cur[202] = {};
    cur[0] = 1;
    for(int v : G[u]) if(v != p) {
        int next[202] = {};
        for(int c = 0; c < size[u]; c++) {
            for(int d = 1; d <= size[v]; d++) {
                for(int e = max(c, d); e <= c + d; e++) {
                    if(cur[c] > 0 && dp[v][d] > 0) {
                        next[e] += (LL)ways(c, d, e) * cur[c] % MOD * dp[v][d] % MOD;
                        next[e] %= MOD;
                    }
                }
            }
        }
        memcpy(cur, next, sizeof(next));
    }
    for(int c = 0; c < size[u]; c++) {
        dump(u);
        dump(c+1);
        dump(cur[c]);
        dp[u][c+1] = cur[c];
    }
}
int main(){
    iostream_init();
    memset(memo, -1, sizeof(memo));
    assert(ways(1, 1, 1) == 1);
    assert(ways(1, 1, 2) == 2);

    int N;
    while(cin >> N) {
        Graph G(N);
        int deg[200] = {};
        REP(i, N-1) {
            int a, b;
            cin >> a >> b;
            G[a].push_back(b);
            deg[b]++;
        }
        int root = -1;
        REP(i, N) if(deg[i] == 0) root = i;
        rec(G, root, -1);

        int ans = 0;
        for(int c = 1; c <= N; c++) {
            ans += dp[root][c];
            ans %= MOD;
        }
        cout << ans << endl;
    }
    return 0;
}

/* vim:set foldmethod=marker: */

Measured memory_bytes: 65484
import bisect
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort()
c.sort()
ans = 0
for i in range(n):
    lower_cnt = bisect.bisect_left(a, b[i])
    upper_cnt = len(b) - bisect.bisect_right(c, b[i])
    ans += lower_cnt * upper_cnt
print(ans)

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

using namespace std;

using ll = long long;

int main(void){
    ll n;
    string s;

    cin >> n >> s;

    ll nR, nG, nB;
    nR = nG = nB = 0;

    for(auto c : s){
        if(c == 'R') nR++;
        if(c == 'G') nG++;
        if(c == 'B') nB++;
    }

    ll ans = nR * nG * nB;

    //cout << ans << endl;

    ll sep = 1;
    vector<char> buf(3);
    for(ll sep=1; sep <= n/2; sep++){
        for(ll i=0; i+sep*2<n; i++){
            buf[0] = s[i + 0];
            buf[1] = s[i + sep];
            buf[2] = s[i + sep*2];
            //cout << i << "," << i+sep << "," << i+sep*2 << endl;
            if(buf[0] != buf[1] && buf[1] != buf[2] && buf[0] != buf[2]){
                ans--;
                //cout << i << "," << i+sep << "," << i+sep*2 << endl;
                //cout << buf[0] << "," << buf[1] << "," << buf[2] << endl;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

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

int main(void){
  int n, m; cin >> n >> m;
  long long sum = 0;
  priority_queue<int> pq;
  
  for(int i = 0; i < n; i++){
    int price; cin >> price;
    pq.push(price);
  }
  
  for(int i = 0; i < m; i++){
    int max_price = pq.top();
    pq.pop();
    pq.push(int(max_price / 2));
  }
  
  for(int i = 0; i < n; i++){
    sum += pq.top();
    pq.pop();
  }
  
  cout << sum;

}

Measured memory_bytes: 892
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long

#define maxN 200011

int n, m, i, j, cover, x, y;
int a[maxN], cnt[maxN], here[maxN];

void rm(int x) {
    if (x - cnt[x] + 1 >= 1)
        if (--here[ x - cnt[x] + 1 ] == 0)
            cover--;
    cnt[x]--;
}

void add(int x) {
    if (x - cnt[x] >= 1)
        if (++here[ x - cnt[x] ] == 1)
            cover++;
    cnt[x]++;
}

int main()
{
   // freopen("test.in","r",stdin);

    scanf("%d%d", &n, &m);
    for (i = 1; i <= n; i++) scanf("%d", &a[i]), add(a[i]);

    for (i = 1; i <= m; i++) {
        scanf("%d%d", &x, &y);
        rm(a[x]);
        add(y);
        a[x] = y;

        printf("%d\n", n - cover);
    }


    return 0;
}


Measured memory_bytes: 3712
#include <iostream>
#include <string>
#include <set>

using namespace std;



int N, M;
string open="Opened by ", clsd="Closed by ", unk = "Unknown ";

int main() {
	cin >> N;
	
	set<string> users;
	for (int i=0; i<N; i++) {
		string user; cin >> user;
		users.insert(user);
	}
	
	cin >> M;
	bool opened = false;
	for (int i=0; i<M; i++) {
		string comes; cin >> comes;
		if (users.find(comes) != users.end()) {
			if (!opened) cout << open << comes << endl;
			else cout << clsd << comes << endl;
			opened = !opened;
		} else {
			cout << unk << comes << endl;
		}
	}
	
	return 0;
}

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

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()

int digit(int n)
{
    if (n < 10)
    {
        return 1;
    }
    return digit(n / 10) + 1;
}

string int_to_string(int n)
{
    string res = "";

    while (n)
    {
        char tmp = (n % 10) + '0';
        res = tmp + res;
        n /= 10;
    }
    return res;
}

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> s(m), c(m);
    rep(i, m) cin >> s[i] >> c[i];

    rep(i, 1000)
    {
        if (n != digit(i))
        {
            continue;
        }

        bool flag = true;
        rep(j, m)
        {
            string st_num = to_string(i);
            if (st_num[s[j] - 1] - '0' != c[j])
            {
                flag = false;
            }
        }
        if (flag)
        {
            cout << i << '\n';
            return 0;
        }
    }

    cout << -1 << '\n';
    return (0);
}


Measured memory_bytes: 3676
import math
PI = math.pi
a, b, h, m = [int(x) for x in input().split()]
min = PI * m / 30
hr = PI * (60 * h + m) / 360
gamma = hr - min
ans = math.sqrt(a ** 2 + b ** 2 - 2 * a * b * math.cos(gamma))
print(ans)

Measured memory_bytes: 9508
#include<bits/stdc++.h>
#define fi first
#define se second

using namespace std;
const int N = 2e5 + 5;

pair<int, int> a[N];
int n;
int ans[N];

int main()
{
  cin >> n;
  for (int i=0; i<n; i++) cin >> a[i].fi, a[i].se = i;
  sort(a,a+n);
  for (int i=0; i<n; i++)
  {
    if (i==n-1)
    {
      ans[a[i].se] = a[i-1].fi;
    }
    else 
    {
      ans[a[i].se] = a[n-1].fi;
    }
  }
  for (int i=0; i<n; i++) cout << ans[i] << '\n';
  return 0;
}


Measured memory_bytes: 3968
var
 c:array[1..8] of integer=(-1,-1,-1,0,0,1,1,1);
 d:array[1..8] of integer=(-1,0,1,-1,1,-1,0,1);
 a:array[0..50,0..50] of char;
 b:array[0..50,0..50] of longint;
 i,j,n,m:longint;
procedure pd(x,y:longint);
 var
  i:longint;
 begin
  if a[x,y]='#' then begin b[x,y]:=-maxlongint;exit; end;
  for i:=1 to 8 do if a[x+c[i],y+d[i]]='#' then inc(b[x,y]);
 end;
begin
 readln(n,m);
 for i:=1 to n do
  begin
   for j:=1 to m do read(a[i,j]);
   readln;
  end;
 for i:=1 to n do
  for j:=1 to m do pd(i,j);
 for i:=1 to n do
  begin
   for j:=1 to m do if b[i,j]=-maxlongint then write('#')
    else write(b[i,j]);
   writeln;
  end;
end.

Measured memory_bytes: 128
N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(len(A)):
  a = A[i]
  if a%2 == 0:
    if a%3 == 0 or a%5 == 0:
      continue
    else:
      ans = 1
if ans == 0:
  print('APPROVED')
else:
  print('DENIED')
    

Measured memory_bytes: 2940
#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>

auto& in = std::cin;
auto& out = std::cout;

uint64_t a,b_raw,b_big, b_rem;

int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);

	in >> a>>b_raw;
	if (a == b_raw) {
		std::cout << 1 << std::endl;
		return 0;
	}

	for (;;)
	{
		for (size_t i = 0; i <= 61; i++) {
			if (b_raw & ((uint64_t)(1) << i)) {
				b_big = ((uint64_t)(1) << i);
			}
		}
		b_rem = b_raw - b_big;

		if (a & b_big) {
			b_raw -= b_big;
			a -= b_big;
			continue;
		}

		//if (b_big <= a) {
		//	std::cout << (b_raw - a + 1) << std::endl;
		//	return 0;
		//}

		break;
	}

	//remを強化？
	if(b_rem!=0){
		uint64_t rem=0;
		for (size_t i = 0; i <= 61; i++) {
			if (b_rem & ((uint64_t)(1) << i)) {
				rem = ((uint64_t)(1) << i);
			}
		}
		rem *= 2;
		b_rem = rem - 1;
	}

	uint64_t count=0;
	count += (b_big - a);
	count += b_big;
	count -= a;
	count += std::min(a,b_rem + 1);
	std::cout << count << std::endl;

	return 0;
}
#endif


Measured memory_bytes: 888
using System;
using System.Linq;

namespace ConsoleApp1
{
	class Program
	{
		static void Main(string[] a_asArgs)
		{
			int[] l_aiABC = Console.ReadLine().Split(' ').Select(a => int.Parse(a)).ToArray();
			Console.WriteLine(l_aiABC[0] + l_aiABC[1] >= l_aiABC[2] ? "Yes" : "No");
		}
	}
}


Measured memory_bytes: 13396
def add(x,y):
    return x + y


a,b = map(int,input().split())
x = b -a
sum = 1
next_x = 2
while True:
    result = add(sum,next_x)
    if result - sum == x:
        print(sum - a)
        break
    sum = result
    next_x += 1


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int N,H;
    cin >> N >> H;
    vector<int> a(N),b(N);
    for(int i = 0; i < N; i++){
        cin >> a[i] >> b[i];
    }
    sort(b.begin(),b.end());
    reverse(b.begin(),b.end());
    sort(a.begin(),a.end());
    int A = a[N-1];
    int Count = 0;
    int i = 0;
    while(H > 0){
        if(A < b[i]){
            H -= b[i];
            i++;
            Count++;
        }
        else{
            if(H % A != 0) Count += H / A + 1;
            else Count += H / A;
            H = 0;
        }
    }
    cout << Count << endl;
}

Measured memory_bytes: 1024
#include<stdio.h>
int main(){
int a,b,c,d,e,f,g;
scanf("%d %d %d %d %d",&a,&b,&c,&d,&e);
if(a%b==0){
f=a/b*c;
}
else{
f=(a/b+1)*c;
}
if(a%d==0){
g=a/d*e;
}
else{
g=(a/d+1)*e;
}
if(f<g){
printf("%d\n",f);
}
else{
printf("%d\n",g);
}
return 0;
}


Measured memory_bytes: 2108
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define rp(i,n) for(int i=1;i<=(int)n;i++)
int main(){
string n;cin>>n;
int a=0;
if(n[0]=='7')a=1;
if(n[1]=='7')a=1;
if(n[2]=='7')a=1;
if(a==1)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}

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

int gcd(int a, int b) 
{ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
}

int main() {
	// your code goes here
	int k;
	cin>>k;
	long long sum=0;
	for(int a=1; a<=k; a++)
	{
		for(int b=1; b<=k; b++)
		{
			for(int c=1; c<=k; c++)
			{
				sum+=gcd(a, gcd(b,c));
			}
		}
	}
	cout<<sum;
	return 0;
}

Measured memory_bytes: 3624
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

n = int(input())
lower = []
upper = []
for _ in range(n):
    a, b = map(int, input().split())
    lower.append(a)
    upper.append(b)

lower.sort()
upper.sort()

if n % 2 == 1:
    l_mid = lower[n // 2]
    u_mid = upper[n // 2]
    print(u_mid - l_mid + 1)
else:
    l_mid = (lower[n // 2] + lower[n // 2 - 1])
    u_mid = (upper[n // 2] + upper[n // 2 - 1])
    ans = u_mid - l_mid + 1
    print(ans)

Measured memory_bytes: 25540
#! env/bin/local python3
# -*- coding: utf-8 -*-

import itertools

n = int(input())
names = []
march = {
    'M': 0,
    'R': 0,
    'A': 0,
    'C': 0,
    'H': 0
}

while True:
    try:
        names.append(input())
    except EOFError:
        break


for name in names:
    try:
        march[name[0]] += 1
    except KeyError:
        continue

patterns = list(itertools.combinations(['M', 'A', 'R', 'C', 'H'], 3))

total = 0
for pattern in patterns:
    total += march[pattern[0]] * march[pattern[1]] * march[pattern[2]]

print(total)

Measured memory_bytes: 16124
#include<stdio.h>


int main( void ) 
{
	int a[101];
	int n;
	int i;
	
	scanf( "%d", &n );
	for( i=0; i<n; i++ ) {
		scanf( "%d", &a[i] );
	}
	for( i=n-1; 0<=i; i-- ) {
		printf( "%d", a[i] );
		if( 0 != i ) {
			printf( " " );
		} else {
			printf( "\n" );
		}
	}
	
	return 0;
}

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

using namespace std;


int main(){
    
    int N;
    cin >> N;
    long int A[N+2];
    long int B[N+1];
    
    A[0] = 0;
    B[0] = 0;
    for (int i = 1; i <= N+1; i++) {
        cin >> A[i];
    }
    for (int i = 1; i <= N; i++) {
        cin >> B[i];
    }
    
    long int ans = 0;
    
    for (int i = N; i >= 1; i--) {
        if (A[i+1] >= B[i]) {
            ans += B[i];
            
        }else{
            B[i] -= A[i+1];
            ans += A[i+1];
            
            if (A[i] >= B[i]) {
                ans += B[i];
                A[i] -= B[i];
            }else{
                ans += A[i];
                A[i] = 0;
                
            }
            
        }
        
        
    }
    
    cout << ans << endl;
    
}



Measured memory_bytes: 1792
N = int(input())
A = []
B = []
for _ in range(N):
  a,b = list(map(int, input().split()))
  A.append(a)
  B.append(b)

A.sort()
B.sort()

if N%2 != 0:
  print(B[(N+1)//2-1]-A[(N+1)//2-1]+1)
else:
  print(int((((B[(N)//2-1]+B[(N)//2])/2)-((A[(N)//2-1]+A[(N)//2])/2))*2+1))



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

int main() {
  while (true) {
    int m, nmin, nmax;
    cin >> m >> nmin >> nmax;
    if (m == 0 && nmin == 0 && nmax == 0) break;
    vector<int> P(m);
    for (int i = 0; i < m; i++) cin >> P.at(i);
    int ans = nmin, maxgap = 0;
    for (int i = nmin - 1; i < nmax; i++) {
      if (maxgap <= P.at(i) - P.at(i + 1)) {
        maxgap = P.at(i) - P.at(i + 1);
        ans = i + 1;
      }
    }
    cout << ans << endl;
  }
}


Measured memory_bytes: 3084
#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
	
using namespace std;
const int MAX_N=1e5;
ll A[MAX_N];
int N;
const ll MOD=1e9+7;
ll mpw(ll n,ll m){
	ll ret=1;
	while(m){
		if (m&1){
			ret*=n;
			ret%=MOD;
		}
		n*=n;
		n%=MOD;
		m>>=1;
	}
	return ret;
}
ll minv(ll n){
	return mpw(n,MOD-2);
}
ll psm[MAX_N];
int main(){
	cin>>N;
	REP(i,N)cin>>A[i];
	psm[0]=1;
	REP(i,N-1){
		psm[i+1]=psm[i]+minv(i+2);
	}
	ll ans=0;
	REP(i,N){
		ans+=A[i]*((psm[i]-psm[0]+psm[N-1-i]+2*MOD)%MOD)%MOD;
		ans%=MOD;
	}
	REP(i,N){
		ans*=(i+1);
		ans%=MOD;
	}
	cout<<ans<<endl;
	return 0;
}

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ll          long long
#define pb          push_back
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define rs(v,n)     v.resize(n)
#define hell        1000000007
#define peak        9123372036854775807
#define pii         acos(-1)
#define clr(a,x)    memset(a,x,sizeof(a))
#define ios         ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ordered_set tree<ll int, null_type,less<ll int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
template<class x,class y> x sum(x a,y b){return a+b;}
template<class x,class y> x mul(x a,y b){return a*b;}
template<class x,class y> x sub(x a,y b){return a-b;}
template<class x,class y> x divi(x a,y b){return a/b;}

template<class x,class y>
istream &operator>>(istream &in,pair<x,y> &p) 
{ 
    in>>p.F>>p.S;
    return in;
}
template<class x>
istream &operator>>(istream &in,vector<x> &v) 
{
    for(auto& i:v)
        in>>i;
    return in;
}
template<class x,class y>
ostream &operator<<(ostream &out,pair<x,y> &p) 
{ 
    out<<"("<<p.F<<","<<p.S<<") ";
    return out; 
}
template<class x>
ostream &operator<<(ostream &out,vector<x> &v) 
{ 
    out<<v.size()<<endl;
    for(auto i:v)
        out<<i<<" ";
    out<<endl;
    return out; 
}
#define N  1000005

int main()
{
    ios;
    ll tt=1;
    // cin>>tt;
    while(tt--)
    {
        ll i,j,k,l,m,n;
        string s,r,t,sma;
        cin>>n>>k;
        cin>>s;
        r=s;
        reverse(all(r));
        sma=s;
        t=s+r;
        reverse(all(t));
        n=s.size();
        for(i=0;i<=n;i++)
        {
            string g;
            for(j=i;j<i+n;j++)
                g.pb(t[j]);
            if(g<sma)
                sma=g;
        }
        // cout<<sma<<endl;
        for(i=1;i<n;i++)
        {
            if(sma[i]!=sma[i-1])
                break;
        }
        if(k>30)
        {
            for(j=0;j<n;j++)
                cout<<sma[0];
            return 0;
        }
        ll x=(1<<(k-1))*i;
        // cout<<x<<endl;
        if(x>=n)
        {
            for(j=0;j<n;j++)
                cout<<sma[0];
            return 0;
        }
        for(j=0;j<x;j++)
            cout<<sma[0];
        for(j=i;j<n-x+i;j++)
            cout<<sma[j];
    }
    return 0;
}

Measured memory_bytes: 384
#include<iostream>
using namespace std;
int main() {
    string s;
    cin >> s;
    for(int i = 1; i < s.length(); ++i) {
        if(s[i] == s[i-1]) {
            printf("%d %d\n",i,i+1);
            return 0;
        }
        if(i >= 2) {
            if(s[i] == s[i-2]) {
                printf("%d %d\n",i-1,i+1);
                return 0;
            }
        }
    }
    printf("-1 -1\n");
return 0;
}

Measured memory_bytes: 3844
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n,i,j,k,l,m,x,y;
    string s1,s2,s3;
    map<string ,int>m1;
    map<string ,int>m2;
    map<string ,int>::iterator it;
    cin>>n;
    cin.ignore();
    for(i=0;i<n;i++)
    {
        cin>>s1;
        m1[s1]++;
    }
    cin>>m;
    cin.ignore();
    for(i=0;i<m;i++)
    {
        cin>>s2;
        m2[s2]++;
    }
    x=-10000;
    for(it=m1.begin();it!=m1.end();it++)
    {
        k=m1[it->first];
        l=m2[it->first];
        y=k-l;
        if(y>x)
        {
            x=y;
        }

    }
    if(x<0)
    {
        x=0;
    }
    cout<<x<<endl;
    return 0;
}


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

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int n,x,t;
    cin>>n>>x>>t;
    int time=0;
    int piece=0;
    while(piece<n){
        piece+=x;
        time+=t;
    }
    cout<<time<<endl;
}


Measured memory_bytes: 3636
N,M,C=gets.chomp.split(" ").map(&:to_i)
@array=gets.chomp.split(" ").map(&:to_i)

@rets = [@array.inject(:+)]
@memo = [] # i番目 精度r の強さ memo[i][r]
(0..(N-1)).each do |i|
    @memo.push([@array[i]])
end

def calc(r)
    max_rl = Array.new(N)
    max_r = Array.new(N)
    max_l = Array.new(N)
    deq_up = []
    deq_down = []
    (0..(N-1)).each do |i|
        if !deq_up.empty?
            deq_up.shift if deq_up[0] < i - r
            up_val = @array[i] + i*C
            while !deq_up.empty? && up_val > @array[deq_up[-1]] + deq_up[-1]*C do
                deq_up.pop
            end
        end
        deq_up.push(i)
        max_l[i] = @array[deq_up[0]] - (i-deq_up[0])*C
    end
    (0..(N-1)).to_a.reverse.each do |i|
        if !deq_down.empty?
            deq_down.shift if deq_down[0] > i + r
            down_val = @array[i] - i*C
            while !deq_down.empty? && down_val > @array[deq_down[-1]] - deq_down[-1]*C do
                deq_down.pop
            end
        end
        deq_down.push(i)
        max_r[i] = @array[deq_down[0]] + (i-deq_down[0])*C
    end
    (0..(N-1)).each do |i|
        max_rl[i] = max_l[i] > max_r[i] ? max_l[i] : max_r[i]
    end
    max_rl.inject(:+)
end

ret = (0..(N-1)).to_a.bsearch { |e| calc(e) >= M }
if ret 
    puts ret
else
    puts "-1"
end



Measured memory_bytes: 56596
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define erep(i,a,b) for(int i=a;i<=(int)(b);++i)
#define per(i,a,b) for(int i=(a);i>(b);--i)
#define eper(i,a,b) for(int i=(a);i>=b;--i)
#define pb push_back
#define mp make_pair
#define INF 100100100100
#define inf 2001001001
#define MOD 1000000007
#define ALL(x) begin(x),end(x)
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using vii = vector<int>;
using vll = vector<ll>;
template<class T>using vv = vector<T>;
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; }
int dy[]={0, 1, -1, 0};
int dx[]={1, 0, 0, -1};
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a, b)*b;}

string s;
ll dp[100005][4];
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
    cin >> s;
    int n = (int)s.size();
    string t = "ABC";
    eper(i, n, 0) {
      eper(j, 3, 0) {
        if (i == n) 
          dp[i][j] = (j == 3 ? 1 : 0);
        else {
          dp[i][j] = dp[i+1][j] * (s[i] == '?' ? 3 : 1);
          if ((j < 3) && (s[i] == '?' || s[i] == t[j])) {
            dp[i][j] += dp[i+1][j+1];
          }
          dp[i][j] %= MOD;
        }
      }
    }
    cout << dp[0][0] << endl;
    return 0;
}



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

using namespace std;

typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = (ll)1e9 + 7;

int main()
{
  int N, LIM; scanf("%d %d", &N, &LIM);
  vector<ll> W(N), V(N);
  for (int i = 0; i < N; ++i) {
    scanf("%lld %lld", &W[i], &V[i]);
  }

  // vector<vector<ll>> dp(N + 5, vector<ll>(305, 0));
  // ll diff_sum = 0;
  // for (int i = 0; i < N; ++i) {
  //   ll diff = W[i] - W[0];
  //   for (int j = i + 1; j > 0; --j) {
  //     for (int k = diff_sum; k >= 0; --k) {
  //       dp[j][k + diff] = max(dp[j][k + diff], dp[j - 1][k] + V[i]);
  //     }
  //   }
  //   diff_sum += diff;
  // }
  vector<vector<vector<ll>>> dp(N + 5, vector<vector<ll>>(N + 5, vector<ll>(305, 0)));
  ll diff_sum = 0;
  for (int i = 0; i < N; ++i) {
    ll diff = W[i] - W[0];
    for (int j = 1; j <= i + 1; ++j) {
      for (int k = 0; k <= 300; ++k) {
        dp[i + 1][j][k] = dp[i][j][k];
        if (k - diff >= 0) {
          dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j - 1][k - diff] + V[i]);
        }
      }
    }
  }
  ll ans = 0;
  for (int i = 1; i <= N; ++i) {
    for (int j = 0; j <= 300; ++j) {
      if (W[0] * i + j <= LIM) {
        ans = max(ans, dp[N][i][j]);
      }
    }
  }

  // ll ans = 0;
  // for (int i = 1; i <= N; ++i) {
  //   for (int j = 0; j <= diff_sum; ++j) {
  //     if (W[0] * i + j <= LIM) {
  //       ans = max(ans, dp[i][j]);
  //     }
  //   }
  // }
  printf("%lld\n", ans);

  return 0;
}


Measured memory_bytes: 27136
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define fs first
#define sc second
typedef pair<ll, ll> l_l;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
 
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
    int N; cin >> N;
    vector<int> V(N), C(N);
    rep(i,N) cin >> V[i];
    rep(i,N) cin >> C[i];
    int pro = 0;
    rep(i,N) if(V[i] - C[i] > 0) pro += V[i] - C[i];
    cout << pro << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int lld;
typedef vector<lld> vll;
#define pb push_back
#define rep(i,a,b) for(i=a;i<b;i++)
#define srt(v) sort(v.begin(),v.end())
#define rev(v) reverse(v.begin(),v.end())
#define mod 1000000007
#define pi 3.1415926535
lld a,b,c,d,e,f,g,h,i,j,k=0,l=0,m=1,n=1,o,q=0,r=0,u,v,w,x,y,z,s,t,p=0;
lld temp=0,ans=0;
double f1,f2,f3,f4,f5,f6;
char c2,c3,c4,c5,c6;
vll v11;
pair<lld,lld>p1,p2,p3;
map<lld,lld>mv;lld a12[200005],a13[200005];
bool b11[500006],c11[500006];lld a11[500006];
lld gcd(lld a, lld b) 
{ 
    if (b == 0) 
        return a; 
    return gcd(b, a % b);  
}
void dfs(lld i,vector<lld>vg[],lld m)
{
    if(b11[i]==true)    return;
    b11[i]=true;
    for(auto x11:vg[i])
    {
        if(b11[x11]==false)
        {
            dfs(x11,vg,m);
        }
    }
}
int main()
{
  ios::sync_with_stdio(false);cin.tie(0);
  t=1;
  //cin>>t;
  while(t--)
  {
    string s3,s1,s2;
    cin>>a>>b>>c>>d;lld bn,a11,p1,n1,c11,cn;
    lld a1[n+1]={0},b1[n],c1[n+1];vector<lld>vg[n+1];
    map<char,lld>m1,m2;queue<lld>q2;vll v1,v2;r=0;temp=0;
    cout<<max(a*c,max(b*d,max(a*d,b*c)));
    cout<<endl;
  }
  return 0;
}

Measured memory_bytes: 3660
def mk_table(n):
    res = [1] * (n + 1)
    res[:2] = [0, 0]

    for i in range(2, n):
        if i ** 2 > n:
            break

        if res[i] == 1:
            j = 2
            while i * j <= n:
                res[i * j] = 0
                j += 1

    return res


tbl = mk_table(999999)
try:
    while 1:
        print(len([x for x in tbl[:int(input())+1] if x == 1]))
except Exception:
    pass

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

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

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

const int maxn = 610;

int n;
int d1, d2;
int dx[4], dy[4];

int col[maxn * maxn];
int ans[maxn][maxn];
int cand[2];

vector<int> x[maxn];

vector<int> g[maxn * maxn];

void dfs(int u, int c){
    for(auto v : g[u]){
        if(col[v] == -1){
            col[v] = c ^ 1;
            dfs(v, c ^ 1);
        }
    }
}

void solve(int d){
    for(int i = 0;i < 2 * n;i++){
        x[i].clear();
        for(int j = 0;j < 2 * n;j++){
            int id = i * 2 * n + j;
            g[id].clear();
            if(i * i + j * j == d){
                x[i].push_back(j);
            }
        }
    }
    for(int i = 0;i < 2 * n;i++){
        for(int j = 0;j < 2 * n;j++){
            int id = i * 2 * n + j; 
            for(int dx = 0;dx < 2 * n;dx++){
                if(x[dx].size() == 0)
                    continue;
                int dy = x[dx][0];
                for(int i1 = -1;i1 <= 1;i1 += 2){
                    for(int j1 = -1;j1 <= 1;j1 += 2){
                        int xx = i + i1 * dx;
                        int yy = j + j1 * dy;
                        if(xx >= 0 and xx < 2 * n and yy >= 0 and yy < 2 * n){
                            int to = xx * 2 * n + yy;
                            g[to].push_back(id);
                            g[id].push_back(to);
                        }
                    }
                }
            }
        }
    } 
    memset(col, -1, sizeof(col));
    for(int i = 0;i < 2 * n;i++){
        for(int j = 0;j < 2 * n;j++){
            int id = i * 2 * n + j;
            if(col[id] == -1){
                col[id] = cand[0];
                dfs(id, 0);
            }
            ans[i][j] += col[id];
        }
    }
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    cin >> d1 >> d2;
    cand[0] = 0, cand[1] = 1;
    solve(d1);
    cand[0] = 0, cand[1] = 2;
    solve(d2);
    for(int c = 0;c < 4;c++){
        int cnt = 0;
        for(int i = 0;i < 2 * n;i++){
            for(int j = 0;j < 2 * n;j++){
                if(ans[i][j] == c){
                    cnt++;
                }
            }
        }
        if(cnt >= n * n){
            cnt = 0;
            for(int i = 0;i < 2 * n;i++){
                for(int j = 0;j < 2 * n;j++){
                    if(ans[i][j] == c){
                        cout << i << " " << j << endl;
                        cnt++;
                        if(cnt == n * n){
                            return 0;
                        }
                    }
                }
            }
        }
    }
    return 0;
}


Measured memory_bytes: 115840
#include <bits/stdc++.h>
#define ll             long long
#define pl             pair <ll,ll>
#define ps             pair <string,string>
#define vi         vector <int>
#define vl             vector <ll>
#define vpi            vector <pi>
#define vpl            vector <pl>
#define f(i,a,b)       for(ll i=(a);i<(b);i++)
#define fd(i,a,b)      for(ll i=(a);i>(b);i--)
#define Max(a,b)       ((a)>(b)?(a):(b))
#define Min(a,b)       ((a)<(b)?(a):(b))
#define x              first
#define y              second
#define si(a)          scanf("%d",&a)
#define sii(a,b)       scanf("%d %d",&a,&b)
#define siii(a,b,c)    scanf("%d %d %d",&a,&b,&c)
#define sl(a)          scanf("%lld",&a)
#define sll(a,b)       scanf("%lld %lld",&a,&b)
#define slll(a,b,c)    scanf("%lld %lld %lld",&a,&b,&c)
#define ss(s)          scanf("%s",s)
#define pf             printf
#define pfi(n)         printf("%d\n",n)
#define pfl(n)         printf("%lld\n",n)
#define pfls(n)        printf("%lld ",n)
#define pfci(n,ans)    printf("Case %lld: %d\n",n,ans)
#define pfcl(n,ans)    printf("Case %lld: %lld\n",n,ans)
#define pfcd(n,ans)    printf("Case %lld: %lf\n",n,ans)
#define pb             push_back
#define all(v)         v.begin(),v.end()
#define mem(a,v)       memset(a,v,sizeof(a))
#define MOD 1000000007
#define LG  16
#define mid ((l+r)/2+1)
#define PI (acos(-1.0))
#define ppl pair<pl,ll>
#define PT pair<double,double>
#define IN(n) (2*n-1)
#define OUT(n) (2*n)

using namespace std;

ll a[200006];
int main(){
    ll N;
    sl(N);
    ll sum=0;
    f(i,0,N){
        sl(a[i]);
        sum+=a[i];
        if(i) a[i]+=a[i-1];
    }
    ll ans=1e18;
    f(i,0,N-1) ans=min(ans,llabs(sum-2*a[i]));
    pfl(ans);
}


Measured memory_bytes: 1792
import java.util.*;
import java.io.PrintWriter;

public class Main{
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		if(n>=30){
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}
	}
}


Measured memory_bytes: 35736
import java.util.*;

public class Main {
	//constant
	public static final String YES = "YES";
	public static final String NO = "NO";
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int age = sc.nextInt(); //整数の入力
		if (age == 7 || age == 5 || age == 3) {
			System.out.println(YES);
		} else {
			System.out.println(NO);
		}
	}
}

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

int main( ) {
  int N;
  cin>>N;
  vector<char>A(N);
  for(int i=0; i<N;i++) {
      cin>>A.at(i);
  }
  bool answer = false;
  for(int i=0; i<N; i++){
    if(A.at(i)=='Y')
      answer = true;
  }
  if(answer)
    cout<<"Four"<<endl;
  else
    cout<<"Three"<<endl;
}
    
      
    
    
  

Measured memory_bytes: 256
function Main(input) {
  const lines = input.split('\n');
  const S = lines[0];
  let answer = 0;
  if (S.match(/RRR/)) {
    answer = 3;
  } else if (S.match(/RR/)) {
    answer = 2;
  } else if (S.match(/R/)) {
    answer = 1;
  }
  console.log(answer);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 29472
#include <iostream>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
typedef long long ll;
const ll INF=100000000000000LL;

int main() {
	int x,t;
	cin>>x>>t;
	cout<<max(0,x-t)<<endl;
		return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) {
	if (a < b) return gcd(b, a);
	long long r;
	while ((r = a % b)) {
		a = b;
		b = r;
	}
	return b;
}
int main() {
	int N;
	cin >> N;
	vector<int> A(N);
	for (size_t i = 0; i < N; i++)
	{
		cin >> A.at(i);
	}
	int t = A.at(0);
	for (size_t i = 0; i < N; i++)
	{
		t = gcd(t, A.at(i));
	}
	cout << t;
}

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




int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int a, cnt1= 0, cnt2= 0;
	for (int i = 0; i < 3; ++i) {
		cin >> a;
		if (a == 7)
			++cnt1;
		if (a == 5)
			++cnt2;
	}
	if (cnt2 == 2 && cnt1 == 1)
		cout << "YES";
	else cout << "NO";

}

Measured memory_bytes: 256
import math

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

#a = list(map(int, input().split()))

m1,d1 = list(map(int, input().split()))
m2,d2 = list(map(int, input().split()))

if(m1!=m2):
    print(1)
else:
    print(0)

Measured memory_bytes: 38384
import sys

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())

sys.setrecursionlimit(10 ** 9)


def main():
    A = INT()
    B = INT()

    if A + B == 5: print(1)
    elif A + B == 4: print(2)
    else: print(3)


if __name__ == '__main__':
    main()

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

using namespace std;

int n,i,j,nxt;
long long l,state;
char s[100005];

int node[2][400005];
bool mark[400005];

void insert(){
	int id = 0;
	int l1 = strlen(s);
	
	for(int ii = 0; ii < l1; ii++){
		if(node[s[ii] - '0'][id] == -1)
		node[s[ii] - '0'][id] = ++nxt;
		
		id = node[s[ii] - '0'][id];
	}
	
	mark[id] = 1;
}

long long grundy(long long lv){
	for(int ii = 0; ii <= 60; ii++){
		if(lv & (1LL << ii))
		return 1LL << ii;
	}
}

void solve(int id, long long lv){
	if(lv == 0LL) return;
	
	if(node[0][id] != -1){
		solve(node[0][id], lv - 1);
		if(mark[node[0][id]])
		state ^= grundy(lv - 1);
		mark[id] |= mark[node[0][id]];
	}
	
	if(node[1][id] != -1){
		solve(node[1][id], lv - 1);
		if(mark[node[1][id]])
		state ^= grundy(lv - 1);
		mark[id] |= mark[node[1][id]];
	}
}

int main(){
	scanf("%d%lld", &n, &l);
	
	memset(node, -1, sizeof(node));
	
	for(i = 0; i < n; i++){
		scanf("%s", s);
		insert();
	}
	
	solve(0, l + 1);
	
	if(state > 0LL)
	printf("Alice\n");
	else
	printf("Bob\n");
}


Measured memory_bytes: 8192
#include<bits/stdc++.h>
#define dd(x) cout<<#x<<" = "<<x<<" "
#define de(x) cout<<#x<<" = "<<x<<"\n"
#define sz(x) int(x.size())
#define All(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef priority_queue<int> BQ;
typedef priority_queue<int,vector<int>,greater<int> > SQ;
const int maxn=3e5+10,mod=1e9+7,INF=0x3f3f3f3f;

int main()
{
	ll a,b,n;
	cin>>a>>b>>n;
	ll r=n%b,q=n/b;
	ll x1=r,x2=q*b-1;
	ll ans=(x1*a)/b-a*(x1/b);
	if (x2>=0)
		ans=max(ans,(x2*a)/b-a*(x2/b));
	cout<<ans;
	return 0;
}


Measured memory_bytes: 3620
#include<bits/stdc++.h>
#include<set>
#define lli long long int
using namespace std;
int main()
{
	lli t,a,n,i;
	cin>>n;
	vector<lli>v;
	for(i=1;i*i<=n;i++)
	{
		if(n%i==0)
		{
			a=i+n/i-2;
			v.push_back(a);
		}
	}
	sort(v.begin(),v.end());
	cout<<v[0];	
	return 0;
}

Measured memory_bytes: 3644
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
using namespace std;
int main(){
  string s;
  cin >> s;
  for(int i=s.size()-1; i>=0; i--){
    cout << s[i];
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 3044
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    n = INT()
    a = LIST()
    b = set(a)
    if len(a) == len(b):
        print('YES')
    else:
        print('NO')

if __name__=='__main__':
    main()


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

#define fo(i,s,t) for(int i = s; i <= t; ++ i)
#define fd(i,s,t) for(int i = s; i >= t; -- i)
const int maxn = 1000050;
const int zqc = 1e9+7;
typedef long long ll;

int n, cnt, fa[maxn];
struct node{int x,y,id;}a[maxn];
struct edge{int u,v,w;}e[maxn];

bool cmp(node a,node b){return a.x<b.x;}
bool cmp2(node a,node b){return a.y<b.y;}
bool cmp3(edge a,edge b){return a.w<b.w;}
int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}

int main()
{
	scanf("%d",&n);
	fo(i,1,n) scanf("%d%d",&a[i].x,&a[i].y),a[i].id=i;
	sort(a+1,a+n+1,cmp);
	fo(i,1,n-1) e[++cnt] = (struct edge){a[i].id,a[i+1].id,a[i+1].x-a[i].x};
	sort(a+1,a+n+1,cmp2);
	fo(i,1,n-1) e[++cnt] = (struct edge){a[i].id,a[i+1].id,a[i+1].y-a[i].y};
	fo(i,1,n) fa[i] = i;
	sort(e+1,e+cnt+1,cmp3);
	int k = n-1, a, b; ll ans = 0;
	fo(i,1,cnt)
	{
		a = getfa(e[i].u); b = getfa(e[i].v);
		if(a != b)
		{
			ans += e[i].w;
			fa[a] = b;
			-- k;
			if(!k) break;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 10496
fun main(args : Array<String>) {
    val N = readLine()!!.toInt()
    val a = readLine()!!.split(" ").map { it.toLong() }.toLongArray()

    val sum = a.reduce { acc, l -> acc xor l }
    if (sum == 0L) {
        println("Yes")
    } else {
        println("No")
    }
}

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

#define int long long
#define double long double
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define RE(i,n) for (int i = 1; i <= n; i++)
#define RED(i,n) for (int i = n; i > 0; i--)
#define REPS(i,n) for(int i = 1; (i*i) <= n; i++)
#define REP(i,n) for (int i = 0; i < n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)
#define remax(a,b) a = max(a,b)
#define remin(a,b) a = min(a,b)
#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define mii map<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define WL(t) while(t --)
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) ((a)*(b))/gcd((a),(b))
#define print(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout << *it << " "; cout << endl;
#define debug(x) cout << x << endl;
#define debug2(x,y) cout << x << " " << y << endl;
#define debug3(x,y,z) cout << x << " " << y << " " << z << endl;
#define rep(i,a,n) for(int i=a; i<n; i++)
#define endl "\n"
#define e "\n"
#define show(arr) REP(i,arr.size()){cout<<arr[i]<<" ";}
const int INF = 1e18+1;
const int MOD = 1e9+7;
const double PI = 3.14159265358979323846264338;

#define N 5010

void solve()
{
    int n,ans=0;
    vi arr;
    cin >> n;
    n *= 2;
    REP(i,n){
        int x;
        cin >> x;
        arr.pb(x);
    }
    sort(arr.begin(),arr.end());
    for (int i=arr.size()-1;i>0;i-=2){
        ans += min(arr[i],arr[i-1]);
    }
    cout<<ans;
}

signed main()
{
    int t=1;
    //cin>>t;
    WL(t)solve();

    return 0;
}




Measured memory_bytes: 3636
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
using namespace std;
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; }
//****************************************
// Graph template
//****************************************

// status of edge
template <typename X>
struct Edge{
  int from;
  int to;
  X cost;

  Edge() = default;

  Edge(int from, int to, X cost) : from(from), to(to), cost(cost) {}
};

// status of node
template <typename X>
struct Node{ 
  int idx;
  vector<Edge<X>> edge;
  
  Node() = default;

  explicit Node(int idx) : idx(idx) {}
};

template <typename X>
class Graph{
private:
  int n; // number of node
  int m; // number of edge
  vector<Node<X>> node; 

  void Init_Node() {
    rep(i,n) node.emplace_back(i);
  }
public:
  explicit Graph(int n) : n(n) {
    Init_Node();
  }

  // edges have no-weight 
  Graph(int n, int m, vector<int> from, vector<int> to) : n(n), m(m) {
    Init_Node();
    rep(i,m) {
      add_edge(from[i], to[i]);
      add_edge(to[i], from[i]);      
    }
  }  

  // edges have weight
  Graph(int n, int m, vector<int> from, vector<int> to, vector<X> cost) : n(n), m(m) {
    Init_Node();
    rep(i,m) {
      add_edge(from[i], to[i], cost[i]);
      add_edge(to[i], from[i], cost[i]);      
    }
  }

  void add_edge(int from, int to, X cost = 1) {
    node[from].edge.emplace_back(from, to, cost);
  }
  vector<bool> f;
  void Dfs(int v) {
    f[v] = false;
    for(auto next: node[v].edge) {
      int w = next.to;
      if(f[w]) Dfs(w);
    }
  }
  
  void Solve() {
    int res = 0;
    f.assign(n, true);
    rep(i,n) {
      if(f[i]) {
	res++;
	Dfs(i);
      }
    }
    cout << res << "\n";
  }
  
};


int main()
{
  int n,m; cin >> n >> m;
  vector<int> x(m),y(m),z(m);
  rep(i,m) {
    cin >> x[i] >> y[i] >> z[i];
    x[i]--; y[i]--;
  }
  Graph<int> gp(n, m, x, y);
  gp.Solve();
  return 0;
}


Measured memory_bytes: 15140
n = int(input())
k = 1
while 2**k < n:
    k += 1

m = 2**k
ans = []
for i in range(m):
    x = []
    for j in range(i+1,m):
        for l in range(k):
            if (i^j) &(1<<l):
                x.append(l+1)
                break
    ans.append(x)

for i in range(n-1):
    for j in range(n-i-1):
        print(ans[i][j],end=" ")
    print()

Measured memory_bytes: 55132
n,k=map(int,input().split())
x=list(map(int,input().split()))
ans=10**18
for i in range(n-k+1):
        a=abs(x[i+k-1]-x[i])
        ans=min(ans,min(abs(x[i+k-1])+a,abs(x[i])+a))
print(ans)

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

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
const int INF = 1e18;

using namespace std;


signed main() {
  int N, M;
  cin >> N >> M;

  vector<vector<int>> A(N*3);
  int u, v;
  REP(i, M){
    cin >> u >> v;
    u--; v--;
    A[u].push_back(v+N);
    A[u+N].push_back(v+2*N);
    A[u+2*N].push_back(v);
  }

  int S, T;
  cin >> S >> T;
  S--; T--;
  vector<int> dist(3*N, -1);
  queue<int> q;
  q.push(S);
  dist[S] = 0;

  while(!q.empty()){
    int v = q.front(); q.pop();
    for(int i : A[v]){
      if(dist[i] == -1){
        dist[i] = dist[v]+1;
        q.push(i);
      }
    }
  }

  if(dist[T]%3 != 0) cout << -1 << endl;
  else cout << dist[T]/3 << endl;

  return 0;
}

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

int main(){
  string s; cin >> s;
  int n = s.size();
  int k; cin >> k;
  vector<string> sv; 
  for(int i = 0; i < n; ++i){
    for(int j = 1; j <= k; ++j){
      if(i+j-1>=n)break;
      sv.push_back(s.substr(i,j));
    }
  }
  sort(sv.begin(),sv.end());
  unique(sv.begin(),sv.end());
  cout << sv[k-1] << endl;
  return 0;
}


Measured memory_bytes: 1660
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define MOD 1000000007
#define INF (1<<30)
#define LINF (1LL<<60)
#define endl "\n"
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
typedef unsigned long long int ull;
typedef long long lint;
 
 int main(void){
     int X,dis=0,ans=0,count=1;
     cin >> X;
     while(dis<X) ans++,dis+=count,count++;
     cout << ans << endl;
 }

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main(){
	string s;
	cin>>s;
	int a=10000000;
	bool b=0;
	for(int i=0;i<s.size();++i){
		if(s[i]=='C') a=i;
		else if(a<=i&&s[i]=='F') b=1;
	}
	if(b) printf("Yes");
	else printf("No");
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
using Graph = vector<vector<int>>;

int main() {
    // 頂点数と辺数
    int N,M;
    cin >> N >> M;
    Graph G(N);
    // グラフ入力受取 (ここでは無向グラフを想定)
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        a--;b--;
        G[a].push_back(b);
    }
    bool a=false;
    for (int i=0;i<G[0].size();++i) { 
        for(int j=0;j<G[G[0][i]].size();++j){
             if(G[G[0][i]][j]==N-1)a=true;
        }
    }
    if(a)cout<<"POSSIBLE"<<endl;
    else cout<<"IMPOSSIBLE"<<endl;
}


Measured memory_bytes: 8576
#include <bits/stdc++.h> 
#define FOR(i,a,b) for(int i=(a);i<=(b);++i) 
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i) 
#define REP(i,n) for(int i=0;i<(n);++i)
#define RREP(i,n) for(int i=(n);i>0;--i)
#define CI cin>> 
#define CO cout<<
#define EN <<endl 
#define all(x) (x).begin(),(x).end() 
#define asn ans
using namespace std;
template <typename T> istream& operator >> (istream& is, vector<T>& vec) { for (T& x : vec) is >> x; 	return is; }
using ll = long long;

int main() {
	int a; CI a;
	CO a / 3 EN;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h>

int main(){
    int n;
    std::cin >> n;
    int m = (int)(std::sqrt((n + 5) / 6) + 0.9);
    
    for (int l = 1; l <= n; l++)
    {   
        int count = 0;
        for (int i = 1; i < m; i++)
        {
            for (int j = i; j < 100; j++)
            {
                for (int k = j; k < 100; k++)
                {
                    if (i * i + j * j + k * k + i * j + j * k + k * i == l)
                    {
                        if (i == j && j == k)
                        {
                            count++;
                        }
                        else if ((i == j && j != k) || (j == k && k != i) || (k == i && i != j))
                        {
                            count += 3;
                        }
                        else
                        {
                            count += 6;
                        }
                    }
                }
            }
        }
        std::cout << count << std::endl;
    }
    
    return 0;
}

Measured memory_bytes: 3576