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

#define INF 1001001001
#define LINF 1001001001001001001
#define MOD 1000000007
#define MOD2 998244353

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

#define rep(i,n) for(int i=0,_i=(n);i<_i;++i)
#define rep1(i,a,b) for(int a_=(a),b_=(b),i=a_;i<b_;++i)
#define repr(i,n) for(int _i=(n),i=_i;i>0;--i)

#define db(x) cerr<<#x<<" = "<<x<<" ";
#define db2(x,y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<") ";
#define db3(x,y,z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = ("<<x<<", "<<y<<", "<<z<<") ";
#define ln cout<<endl;

#define all(a)  (a).begin(),(a).end()
#define dig(n)  to_string(n).length()

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

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii,pii> ppii;

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

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

int main(){

    bool flag=false;
    ll ans=0,sum=0;

    ll q,h,s,d,n;
    cin>>q>>h>>s>>d>>n;

    ll OneL = min(q*4,min(h*2,s));
    ll TwoL = min(2*OneL,d);

    ans = TwoL*(n/2) + OneL*(n%2);
    cout<<ans<<endl;

    //cout <<fixed<<setprecision(16)<< << endl;

    //if(flag)cout << "Yes" <<endl;
    //else cout << "No" <<endl;

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int i,j,k;
  int d;	//365
  int c[26];
  int score[9490];
  int t[365] = {0};
  int day1[26] = {0};
  double x = 0.36787944117;
  int tmp1=-999999,tmp2=-999999;
  int tmpi = 0;
  
  scanf("%d",&d);
  for(i=0;i<26;i++){
      scanf("%d ",&c[i]);
  }
  for(i=0;i<d*26;i++){
      scanf("%d ",&score[i]);
  }
  //st
  
  for(i=0;i<26;i++){
    if(c[i]>tmp1){
     tmp1 = c[i];
    }
    tmpi = i;
  }
  tmp1 = -999999;/*
  for(i=0;i<d;i++){
    for(j=0;j<26;j++){
      if(score[i*26+j]-c[j]*(1+day1[j])>tmp1){
       	t[i] = j;
      }
    }
  }
  */
  //en
  int p1[26]={0};
    int p2 = 0;
  for(i=0;i<d;i++){
    if(i%26==0){
     for(j=0;j<26;j++){
      p1[j]=0; 
     }
    }
    int tp = -9999999;
    int tp2 = 0;
    int xx;
    for(xx=0;xx<26;xx++){
     if(p1[xx]==0){
      tp2 = xx;
       xx=999;
     }
    }
    
    
    for(j=0;j<26;j++){
      for(k=0;k<26;k++){
     if(p1[j]==0&&score[i*26+k]>tp){
       tp = score[i*26+k];
       tp2 = k;
     }
    }}
    
    
    //p2 = (tmpi+i+tp2)%26+1;
    p2 =tp2+1;
    
    
    printf("%d\n",p2);
    
    
    
  }
 return 0; 
}











/*
#include<stdio.h>
int main(){
  int i,j,k;
  int d;	//365
  int c[26];
  int score[9490];
  int t[365] = {0};
  int day1[26] = {0};
  double x = 0.36787944117;
  int tmp1=-999999,tmp2=-999999;
  
  scanf("%d",&d);
  for(i=0;i<26;i++){
      scanf("%d ",&c[i]);
  }
  for(i=0;i<d*26;i++){
      scanf("%d ",&score[i]);
  }
  //st
  
  for(i=0;i<d;i++){
    for(j=0;j<26;j++){
      if(score[i*26+j]-c[j]*(1+day1[j])>tmp1){
       	tmp1 =  score[i*26+j]-c[j]*(1+day1[j]);
        t[i] = j;
      }
      for(k=0;k<26;k++){
        day1[k] += 1; 
      }
      day1[t[j]] = 0;
    }
  }
  
  //en
  for(i=0;i<d;i++){
      printf("%d\n",t[i]+1);
  }
 return 0; 
}
*/




Measured memory_bytes: 2192
var lines = [];
var reader = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});
reader.on('line', (line) => {
  lines.push(line);
});
reader.on('close', () => {
  const N = Number.parseInt(lines[0]);
  const cards = lines[1].split(' ');

  let resultBubble = BubbleSort([...cards], N);
  let isBubbleStable = isStable([...cards], [...resultBubble]);
  console.log(resultBubble.join(' '));
  console.log(isBubbleStable);

  let resultSelect = SelectionSort([...cards], N);
  let isSeletStable = isStable([...cards], [...resultSelect]);
  console.log(resultSelect.join(' '));
  console.log(isSeletStable);
});

function isStable(original, target) {
  for (var i = 0; i < original.length; i++) {
    var numOriginal = parseInt(original[i].slice(1, 2));
    for (var j = 0; j < target.length; j++) {
      var numTarget = parseInt(target[j].slice(1, 2));
      if (numOriginal === numTarget) {
        if (original[i].slice(0, 1) === target[j].slice(0, 1)) {
          target.splice(j, 1);
          break;
        } else {
          return 'Not stable';
        }
      }
    }
  }
  return 'Stable';
}

function BubbleSort(C, N) {
  var cnt = 0;
  while (cnt < N) {
    for(var i = N - 1; i > cnt; i--) {
      var num1 = parseInt(C[i-1].slice(1, 2));
      var num2 = parseInt(C[i].slice(1, 2));
      if (num1 > num2) {
        var tmp = C[i-1];
        C[i-1] = C[i];
        C[i] = tmp;
      }
    }
    cnt++;
  }
  return C;
}

function SelectionSort(C, N) {
  for (var i = 0; i < N - 1; i++) {
    var minj = parseInt(C[i].slice(1, 3));
    var minArrayNumber = i;
    for (var j = i + 1; j < N; j++) {
      var val = parseInt(C[j].slice(1, 3));
      if (minj > val) {
        minj = val;
        minArrayNumber = j;
      }
    }
    var tmp = C[i];
    C[i] = C[minArrayNumber];
    C[minArrayNumber] = tmp;
  }
  return C;
}



Measured memory_bytes: 16388
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int c = sc.nextInt();
		int[] b = new int[m];
		int[][] a = new int[n][m];
		for (int i = 0; i < m; i++) {
			b[i] = sc.nextInt();
		}
		for (int i = 0; i < n; i++) {
			for (int i2 = 0; i2 < m; i2++) {
				a[i][i2] = sc.nextInt();
			}
		}
		Solver s = new Solver(b, c);
		int ans = 0;
		for (int[] ai : a) {
			if (s.canSolve(ai)) {
				ans++;
			}
		}
		System.out.println(ans);
	}
	
}

class Solver {
	int[] b;
	int c;
	public Solver(int[] b, int c) {
		this.b = b;
		this.c = c;
	}
	boolean canSolve(int... a) {
		int value = c;
		for (int i = 0; i < b.length; i++) {
			value += a[i] * b[i];
		}
		return value > 0;
	}
}


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

int main() {
  int64_t N;
  cin>>N;
  int64_t Z=2;
  for(int64_t i=2;i<=sqrt(N);i++){
    int64_t a=N;
    if((N-1)%i==0){
      Z++;
    }
    while(a>0){
      if(a%i==0){
        a/=i;
      }
      else if(a%i==1){
        Z++;
        break;
      }
      else{
        break;
      }
    }
    if(i*i==N-1){
      Z--;
    }
  }
  if(N==2){
    Z=1;
  }
  cout<<Z<<endl;
            
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		
		boolean a=true;
		
		if(A>8 || B>8){
			a=false;
		}
		
		if(a){
			System.out.println("Yay!");
		}else{
			System.out.println(":(");
		}
	}
}

Measured memory_bytes: 20948
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <utility>
#include <set>
#include <stack>
#include <climits>
#include <cmath>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define rep1(i,n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
#define reps(i,s,n) for(int i=s, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define MEMSET(v, h) memset((v), h, sizeof(v))
typedef long long ll;
const char sp = ' ';


using namespace std;

int main(void){
    ll H, W;
    cin>>H>>W;
    rep(i, W+2) cout<<"#";
    cout<<endl;
    rep(i, H){
        cout<<"#";
        string a;
        cin>>a;
        cout<<a;
        cout<<"#";
        cout<<endl;
    }
    rep(i, W+2) cout<<"#";
    cout<<endl;
    return 0;
}


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

int main(){

    while(1){
        int n, a, b, c, x; cin >> n >> a >> b >> c >> x;
        if(n == 0) break;
        vector<int> y(n);
        for(int i = 0; i < n; i++){
            cin >> y[i];
        }

        int idx = 0;
        for(int i = 0; i <= 10000; i++){

            if(x == y[idx]) idx++;
            if(idx == n){
                cout << i << endl;
                break;
            }
            x = (a * x + b) % c;
            
        }

        if(idx != n) cout << -1 << endl;

    }

    return 0;
}


Measured memory_bytes: 3096
#include<cstdio>
#include<cstring>
#include<algorithm>
using std::max;

int vis[105];
char s[105];
int main()
{
	int n;
	scanf("%d %s",&n,s+1);
	
	int ans=0,cnt=0;
	for(int i=1;i<n;i++)
	{
		memset(vis,0,sizeof(vis));
		cnt=0;
		for(int j=1;j<=i;j++)
			vis[s[j]]=1;
		for(int j=i+1;j<=n;j++)
			if(vis[s[j]])
				cnt++,vis[s[j]]=0;
		ans=max(ans,cnt);
	}
	
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 128
S = input()

over_count_in_my_left = [0] * (len(S)+1)
over_count_in_my_right = [0] * (len(S)+1)

over = 0
for idx, s in enumerate(S):
    over_count_in_my_left[idx] = over
    if s == '<':
        over += 1
    else:
        over = 0
over_count_in_my_left[-1] = over

over = 0
for idx, s in enumerate(S[::-1], 1):
    over_count_in_my_right[-idx] = over
    if s == '>':
        over += 1
    else:
        over = 0
over_count_in_my_right[0] = over

ans = 0
for a, b in zip(over_count_in_my_left, over_count_in_my_right):
    ans += max(a, b)

print(ans)

Measured memory_bytes: 27676
#include<bits/stdc++.h>
   
using namespace std;
  
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define Fixed fixed << setprecision(14)
#define int int64_t
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod1 = 1e9+7; 
constexpr int mod2 = 998244353;
 
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
 
template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;
template <class A,class B> using umap = unordered_map<A,B>;
   
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;}

signed main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;
    vector<int> a(n+1);

    rep(i,n){
        cin >> a[i];
    }
    a[n] = a[n-1] - 1;

    if(a[0] != 0) return cout << "-1\n",0;

    int res = 0;

    for(int i = n-1;i >= 0;--i){
        if(a[i+1] <= a[i]){
            res += a[i];
        }else if(a[i+1] > a[i] + 1){
            return cout << "-1\n",0;
        }
    }

    cout << res << '\n';

    return 0;
}

Measured memory_bytes: 1792
it = input()
it = it.split()
n = int(it[0])
m = int(it[1])
p = [[] for _ in range(n)]
for _ in range(m):
    itf = input()
    itf = itf.split()
    a = int(itf[0])
    b = int(itf[1])
    p[a-1].append(b)
    p[b-1].append(a)
d = [1, ]
con = [0] * n
while d:
    l = d.pop(0)
    for k in p[l-1]:
        if con[k-2]==0:
            d.append(k)
            con[k-2] = l
print('Yes')
for i in range(n-1):
    print(con[i])

Measured memory_bytes: 34076
#include <stdio.h>
int array[100][100];
void DIJK(int);
int main(){
  int num,i,j,id,nextnum,next,weight;
  scanf("%d",&num);
  for(i=0;i<num;i++){
    for(j=0;j<num;j++){
      array[i][j]=110001;
    }
  }
  for(i=0;i<num;i++){
    scanf("%d%d",&id,&nextnum);
    for(j=0;j<nextnum;j++){
      scanf("%d%d",&next,&weight);
      array[id][next]=weight;
    }
  }
  DIJK(num);
  return 0;
}

void DIJK(int num){
  int min,cost[100],col[100];
  int i,j,val;
  for(i=0;i<num;i++){
    cost[i]=110001;
    col[i]=0;
  }
  cost[0]=0;
  while(1){
    min=110001;
    for(i=0;i<num;i++){
      if(col[i]!=2 && min>cost[i]){
	val=i;
	min=cost[i];
      }
    }
    if(min==110001) break;
    col[val]=2;
    for(j=0;j<num;j++){
      if(col[j]!=2 && array[val][j]!=110001){
	if(cost[j]>cost[val]+array[val][j]){
	  cost[j]=cost[val]+array[val][j];
	  col[j]=1;
	}
      }
    }
  }
  for(i=0;i<num;i++){
    if(cost[i]==110001) printf("%d -1\n",i);   /*output*/
    else printf("%d %d\n",i,cost[i]);
  }
}
   
			



Measured memory_bytes: 2052
N,Q=map(int,raw_input().split())
A=map(int,raw_input().split())
maxA=max(A)
T=[0]*(maxA+2)
for i in A:
    T[i]=1
L=[0]*(maxA+2)
num=0
for i in range(maxA+2):
    L[i]=num
    if T[i]==1:
        num=i
for i in range(Q):
    q=input()
    maxv=0
    cur=maxA
    while True:
        p=cur%q
        maxv=max(maxv,p)
        if cur-p<=0: break
        cur=L[cur-p]
    print maxv

Measured memory_bytes: 30444
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define pi acos(-1.0)

int main()
{
    ll n, i, j, half = 0;
    string s;
    cin >> n >> s;
    if(n % 2 != 0)
        cout << "No\n";
    else{
        half = n / 2;
        ll cnt = 0;
        for(i = 0, j = n / 2; j < n; ){
            if(s[i++] == s[j++])
                cnt++;
        }
        if(cnt == n / 2)
            cout << "Yes\n";
        else
            cout << "No\n";
    }
    return 0;
}


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

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

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

	for(int a, b, c, d, e; cin >> a >> b >> c >> d >> e, a;) {
		int na, nb, nc;
		cin >> na >> nb >> nc;

		int ans = a * na + b * nb + c * nc;
		if(nc >= d)
			ans = a * na + b * nb + e * nc;

		else if(nb + nc >= d)
			chmin(ans, a * na + b * (nb + nc - d) + d * e);

		else if(na + nb + nc >= d)
			chmin(ans, a * (na + nb + nc - d) + d * e);

		else
			chmin(ans, d * e);

		cout << ans << endl;
	}

	return EXIT_SUCCESS;
}

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

int main() {

  int t,d;
  cin >> t >> d;
  int ta,tb,da,db;
  cin >> ta >> tb;
  cin >> da >> db;

  double ans = 10000000;
  for(int i=0;i<=d/da;i++)
    for(int j=0;j<=d/db;j++) {
      int va = i*da;
      int vb = j*db;
      if(va+vb < 1 || va + vb > d) continue;
      double ond = 1.0*(ta*va+tb*vb)/(va+vb);  
      ond = t - ond;
      if(ond < 0) ond *= -1;
      if(ond < ans) ans = ond; 
    }

  printf("%.10lf\n",ans);

  return 0 ;
}

Measured memory_bytes: 1196
#ifdef DEBUG_IS_VALID
#define DEB 1 
#define _LIBCPP_DEBUG 0
#else
#define DEB 0
#define NDEBUG
#endif

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

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define pb push_back
#pragma GCC optimize ("-O3")

using namespace std;

#define DUMPOUT cout
#define dump(...) if(DEB) DUMPOUT<<"  "<<#__VA_ARGS__<<" :["<<__LINE__<<":"<<__FUNCTION__<<"]"<<endl<<"    "; if(DEB) dump_func(__VA_ARGS__)
template<typename T1,typename T2>ostream& operator << (ostream& os, pair<T1,T2> p){cout << "(" << p.first << ", " << p.second << ")"; return os;}
template<typename T>ostream& operator << (ostream& os, vector<T>& vec) { os << "{"; for (int i = 0; i<vec.size(); i++) os << vec[i] << (i + 1 == vec.size() ? "" : ", "); os << "}"; return os; }
template<typename T>ostream& operator << (ostream& os, set<T>& st){cout << "{"; for(auto itr = st.begin(); itr != st.end(); itr++) cout << *itr << (next(itr)!=st.end() ? ", " : ""); cout << "}"; return os;}
template<typename T1,typename T2>ostream& operator << (ostream& os, map<T1,T2> mp){cout << "{"; for(auto itr = mp.begin(); itr != mp.end(); itr++) cout << "(" << (itr->first) << ", " << (itr->second) << ")" << (next(itr)!=mp.end() ? "," : ""); cout << "}"; return os; }

void dump_func(){DUMPOUT << endl;}
template <class Head, class... Tail>void dump_func(Head&& head, Tail&&... tail){ DUMPOUT << head; if (sizeof...(Tail) == 0) { DUMPOUT << " "; } else { DUMPOUT << ", "; } dump_func(std::move(tail)...);}
template<class T> inline bool chmax(T& a,T const& b){if(a>=b) return false; a=b; return true;}
template<class T> inline bool chmin(T& a,T const& b){if(a<=b) return false; a=b; return true;}

using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<Pl>;
using vvp = vector<vp>;

const int INF = 1<<29;
const long long LINF=1LL<<59;


void solve(long long N, long long X, std::vector<long long> L){
  ll now = 0;
  ll ans = 1;
  rep(i,N){
    now += L[i];
    if(now>X) break;
    ans++;
  }
  cout << ans << endl;
}

int main(){
  long long N;
  scanf("%lld",&N);
  long long X;
  scanf("%lld",&X);
  std::vector<long long> L(N);
  for(int i = 0 ; i < N ; i++){
    scanf("%lld",&L[i]);
  }
  solve(N, X, std::move(L));
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <numeric>
#include <set>

using namespace std;

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define REPO(i, n) for(int i = 1;i <= n;i++)
#define ll long long
#define INF 999999999
#define MINF -999999999
#define ALL(n) n.begin(),n.end()

int main() {
	int ans = 0;
	string s;
	cin >> s;
	REP(i, s.size() - 1) if (s[i] != s[i + 1]) ans++;
	cout << ans << endl;
}



Measured memory_bytes: 512
#include <iostream>
using namespace std;
int main(){
  int n,i;
  cin>>n;
  int a[n+1];
  for(i=1;i<n+1;i++){
    cin>>a[i];
  }

  i=1;
  for(int cnt=0;cnt<n+1;cnt++){
    if(i==2){
      cout<<cnt<<endl;
      return 0;
    }
    i=a[i];
  }
  cout<<-1<<endl;

  return 0;
}


Measured memory_bytes: 640
def calc_vh(S):
  res = []
  N = len(S)
  pos = 0
  while pos < N:
    if(pos == N-1 or S[pos+1] != S[pos]):
      res.append("v")
      pos += 1
    else:
      res.append("h")
      pos += 2
  return res

N = int(input())
S = input()
S2 = input()

vh = calc_vh(S)
if vh[0]=="v":
  res = 3
else:
  res = 6
length = len(vh)
multiple = {("v", "v"): 2, ("v", "h"): 2, ("h", "v"): 1, ("h", "h"): 3}

for pos in range(1, length):
  v = vh[pos-1], vh[pos]
  res *= multiple[v]

print(res %  1000000007 )



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

using namespace std;
typedef long long ll;
typedef double db;
#define inf 0x3f3f3f3f
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll a[312345];
ll b[312345];
ll c[312345];//输出
ll d[312345];//前缀和
ll n, m;
ll solve(ll t) {	//t 一次的数量
	ll ans = 0, i;
	t = m - t + 1;//从t到m取牌
	ans = d[t - 1];
	ll left = a[t], right = a[m] + ans;
	while (left < right) {
		ll mid = left + right+1 >> 1;//mid 最大次数
		ll* tt = lower_bound(a + t, a + m + 1, mid);
		ll x = tt - a;//坐标值
		ll y = x - t;//不够个数
		ll z = d[x - 1] - d[t - 1];//已有数量
		z = mid * y - z;//缺口
		if (z > ans)right = mid - 1;
		else left = mid;
	}
	return left;
}
signed main() {
	ll i, t;
	cin >> n;
	for (i = 0; i < n; ++i)cin >> b[i];
	sort(b, b + n);
	a[1] = 1;
	ll cnt = 1;
	for (i = 1; i < n; ++i) {
		if (b[i] == b[i - 1])++a[cnt];
		else {
			a[++cnt] = 1;
		}
	}
	m = cnt;
	sort(a + 1, a + m + 1);
	a[m + 1] = inf;
	for (i = 1; i <= m; ++i) {
		d[i] = a[i] + d[i - 1];
	}
	//for (i = 1; i <= m; ++i)cout << d[i] << endl;
	for (i = m + 1; i <= n; ++i)c[i] = 0;
	for (i = 1; i <= m; ++i) {
		c[i] = solve(i);
	}
	for (i = 1; i <= n; ++i)cout << c[i] << " ";
	cout << endl;
}

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

using namespace std;

int main()
{
  int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
  printf("%d %d %d %d\n",
         x2-(y2-y1),
         y2+(x2-x1),
         x1-(y2-y1),
         y1+(x2-x1));
}

Measured memory_bytes: 256
h, w = map(int, input().split())

rows = [] #最初のfor文で、..だけの行を除く行を格納

for i in range(h):
  row = input()
  for c in row:
    if c == '#':
      rows.append(row)
      break
      
columns = []
column = ''
for i in range(w): #各列に対して行う
  for j in range(len(rows)): #行の数、つまり列の長さ
    if rows[j][i:i+1] == '#':
      for k in range(len(rows)):
        column += rows[k][i:i+1]
      columns.append(column)
      column = ''
      break
      
r = len(columns[0]) #最終行の数
ansrows = [''] * r
for i in range(r): #最終行の数だけ
  for j in range(len(columns)): #最終列の数だけ
  	ansrows[i] += columns[j][i]

#解答
for ans in ansrows: print(ans)

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


int main(void){

  double x[4], y[4];
  double vx[2], vy[2];
  double ans[4];
  int i, k;


  while(scanf("%lf,%lf,%lf,%lf,%lf,%lf,%lf,%lf", 
	      &x[0], &y[0], &x[1], &y[1], &x[2], &y[2], &x[3], &y[3])!=EOF){
    
    k=0;
    for(i=0; i<4; i++){
      vx[0]=x[(i+1)%4]-x[i];
      vy[0]=y[(i+1)%4]-y[i];
      vx[1]=x[(i+2)%4]-x[i];
      vy[1]=y[(i+2)%4]-y[i];
    
      ans[k++]=vx[0]*vy[1]-vy[0]*vx[1];
    }

    if(ans[0]>0 && ans[1]>0 && ans[2]>0 && ans[3]>0){
      printf("YES\n");
    }
    else if(ans[0]<0 && ans[1]<0 && ans[2]<0 && ans[3]<0){
      printf("YES\n");
    }
    else{
      printf("NO\n");
    }
  }

  return(0);
}



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

string s;
int main(){
	while(cin >> s){
		int ans = s.size();
		int n = s.size();
		for(int i=0;i<s.size()-1;i++){
			if(s[i] != s[i+1]){
				ans = min(ans,max(i+1,n-i-1));
			}
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 512
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define rg register
#define ll long long 
#define inf 0x3f3f3f3f
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x*f;
}
int n;
int a[305][305],flag[305][305];
int main(){

    n=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            a[i][j]=read();
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
        {
            if(i==k) continue;
            for(int j=1;j<=n;j++)
            {
                if(i==j||k==j) continue;
                if(a[i][j]>a[i][k]+a[k][j])
                {
                    printf("-1\n");
                    return 0;
                }
                if(a[i][j]==a[i][k]+a[k][j])
                {
                    flag[i][j]=flag[j][i]=1;
                }
            }
        }
    ll ans=0;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(!flag[i][j])
                ans+=a[i][j];
    printf("%lld\n",ans);
    return 0;
}


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

using namespace std;

vector<long long> parents;
vector<long long> sizes;

void init(long long n) {
    parents = vector<long long>(n, 0LL);
    sizes = vector<long long>(n, 1LL);
    for (long long i = 0; i < n; ++i) {
        parents[i] = i;
    }
}

long long find(long long x) {
    if (parents[x] == x) {
        return x;
    }
    else {
        parents[x] = find(parents[x]);
        return parents[x];
    }
}

void unite(long long x, long long y) {
    x = find(x);
    y = find(y);
    if (x == y) {
        return;
    }
    long long total = sizes[x] + sizes[y];
    if (sizes[x] > sizes[y]) {
        parents[y] = x;
    }
    else { // (sizes[y] >= sizes[x])
        parents[x] = y;
    }
    sizes[x] = total;
    sizes[y] = total;
}

bool same(long long x, long long y) {
    return find(x) == find(y);
}

void Main() {
    long long N, M;
    cin >> N >> M;
    vector<long long> A(M, 0), B(M, 0);
    for (long long i = 0; i < M; ++i) {
        cin >> A[i] >> B[i];
        A[i] -= 1LL;
        B[i] -= 1LL;
    }
    reverse(A.begin(), A.end());
    reverse(B.begin(), B.end());

    init(N);
    vector<long long> ans(M, -1);
    ans[0] = N * (N - 1LL) / 2LL;
    for (long long i = 0; i < M - 1; ++i) {
        if (ans[i] == 0LL) {
            ans[i + 1] = 0LL;
        }
        else {
            if (!same(A[i], B[i])) {
                long long szA = sizes[find(A[i])];
                long long szB = sizes[find(B[i])];
                ans[i + 1] = ans[i] - szA * szB;
            }
            else {
                ans[i + 1] = ans[i];
            }
            unite(A[i], B[i]);
        }
    }
    reverse(ans.begin(), ans.end());

    for (long long i = 0; i < M; ++i) {
        cout << ans[i] << endl;
    }
}

int main() {
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 7128
#include <bits/stdc++.h>
#define ALL(v) v.begin(), v.end()
#define MOD 1000000007
#define INF 1000000011
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
using namespace std;
typedef long long ll;
 
int main(){
 int n,k;
  cin>>n>>k;

if(k>=2){
  cout<<n-k<<endl;}
  if(k==1){
    cout<<0<<endl;}
 
}

Measured memory_bytes: 256
from fractions import gcd
N = int(input())
A = list(map(int,input().split()))
gcda = [A[0]]
gcdb = [A[-1]]
for i in range(N-2):
    gcda.append(gcd(gcda[-1],A[i+1]))
    gcdb.append(gcd(gcdb[-1],A[-(i+2)]))
gcdb.reverse()
GC = [gcdb[0]]
for i in range(N-2):
    GC.append(gcd(gcda[i],gcdb[i+1]))
else:
    GC.append(gcda[-1])
print(max(GC))

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

using namespace std;

const int N = 100007;
long long D[N];
                              
int main() {
  int n, W, w, v;
  scanf("%d%d", &n, &W);
  for (int i = 0; i < n; i++) {
    scanf("%d%d", &w, &v);
    for (int j = W - w; j >= 0; j--) {
      D[j + w] = max(D[j + w], D[j] + v);
    }
  }
  long long mx = 0;
  for (int i = 0; i <= W; i++) {
    mx = max(mx, D[i]);
  }
  printf("%lld\n", mx);
  return 0;
}

Measured memory_bytes: 1024
#pragma GCC optimize(3)
#include<iostream>
using namespace std;
typedef long long LL;
int cs(LL n){
int res=0;while(n>0){
res+=n%10;n/=10;}
return res;}
main(){
LL n,temp,cnt=1;
cin>>n;
int ans=cs(n);temp=n;
while(temp>=10) {
temp/=10;cnt*=10;}
ans=max(ans,cs(n/cnt*cnt - 1));
cout<<ans<<endl;}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <map>
#include <numeric>
using namespace std;


int main()
{
  int MOD=1000000007;
  int N;
  cin>>N;
  vector<int> C(N+1),right(210000);
  vector<long long> dp(N+1);

  for(int i=0;i<=210000;i++){
    right[i]=-1;
  }
  dp[0]=1;
  cin>>C[0];
  right[C[0]]=0;
  for(int i=1;i<N;i++){
    cin>>C[i];
    if(right[C[i]]!=-1 && right[C[i]]!=i-1){
      dp[i]=dp[right[C[i]]]+dp[i-1];
    }else{
      dp[i]=dp[i-1];
    }
    right[C[i]]=i;
    dp[i]%=MOD;
  }
  cout<<dp[N-1]<<endl;
}



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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define Abs(x)((x) < 0 ? (x) * -1 : (x))
#define rep(x, y) for ((x) = 0; (x) < (y); (x)++)
#define repin(x, y) for ((x) = 0; (x) <= (y); (x)++)
#define nep(x, y) for ((x) = (y) - 1; 0 <= (x); (x)--)
#define nepi(x, y, z) for ((x) = (y) - 1; (z) <= (x); (x)--)
#define repi(x, y, z) for ((x) = (z); (x) < (y); (x)++)
#define repiin(x, y, z) for ((x) = (z); (x) <= (y); (x)++)
#define reps(x, y, z) for ((x) = 0; (x) < (y); (x) += (z))
#define repit(x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define nepit(x) for (__typeof((x).rbegin()) it = (x).rbegin(); it != (x).rend(); it++)
#define All(x) (x).begin(),(x).end()
#define Mem0(x) memset(x, 0, sizeof(x))
#define Mem1(x) memset(x, -1, sizeof(x))
#define End '\n'
#define Out(x) cout<<(x)<<End
template<typename T> inline bool Max(T &x, const T &y) { return x < y ? x = y, 1 : 0; }
template<typename T> inline bool Min(T &x, const T &y) { return x > y ? x = y, 1 : 0; }
template<typename T> using V = vector<T>;
template<typename T> using VV = V<V<T> >;

#define pb push_back
#define mp make_pair
#define X first
#define Y second

static const ll MOD = 1e9 + 7;
static const double PI = 3.141592653589793;

#define LOCAL 0

int main()
{
#if LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("debug.txt", "w", stderr);
#endif

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

    string s, t;

    cin >> s;
    cin >> t;

    map<char, int> a, b;
    V<int> c, d;

    int i, len = s.size();

    rep(i, len) a[s[i]]++;
    rep(i, len) b[t[i]]++;

    repit(a) c.pb(it->Y);
    repit(b) d.pb(it->Y);

    if (c.size() != d.size()) {
        Out("No");

        return 0;
    }

    sort(All(c));
    sort(All(d));

    len = c.size();

    rep(i, len) {
        if (c[i] != d[i]) {
            Out("No");

            return 0;
        }
    }

    Out("Yes");

    return 0;
}


Measured memory_bytes: 916
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

import javax.swing.text.Segment;

public class Main {
	
	public static final long INF = Long.MAX_VALUE / 2 - 1;
	
	public static void main(String[] args) throws IOException {
		try(Scanner sc = new Scanner(System.in)){
			final int A = sc.nextInt();
			final int B = sc.nextInt();
			final int C = sc.nextInt();
			final int D = sc.nextInt();
			
			final int E = sc.nextInt();
			final int F = sc.nextInt();
			
			int max_sweets = 0;
			int max_waters = 0;
			
			for(int a_t = 0; a_t <= 30; a_t++){
				for(int b_t = 0; b_t <= 30; b_t++){
					final int waters = 100 * A * a_t + 100 * B * b_t;
					if(waters > F){ continue; }
					final int limit_sweets = (A * a_t + B * b_t) * E;
					
					for(int c_t = 0; c_t <= 100; c_t++){
						for(int d_t = 0; d_t <= 100; d_t++){
							final int sweets = C * c_t + D * d_t;
							
							if(waters + sweets > F){ continue; }
							if(sweets > limit_sweets){ continue; }
							
							if(max_sweets == 0){
								max_sweets = sweets;
								max_waters = waters;
							}else{
								final int max_sum = max_sweets + max_waters;
								final int max_cur = waters + sweets;
								
								if(sweets * max_sum > max_cur * max_sweets){
									max_sweets = sweets;
									max_waters = waters;
								}
							}
						}
					}
				}
			}
			
			System.out.println((max_waters + max_sweets) + " " + max_sweets);
		}
	}
	
	public static class Scanner implements Closeable {
		private BufferedReader br;
		private StringTokenizer tok;
 
		public Scanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
		}
 
		private void getLine() throws IOException {
			while (!hasNext()) {
				tok = new StringTokenizer(br.readLine());
			}
		}
 
		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}
 
		public String next() throws IOException {
			getLine();
			return tok.nextToken();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
 
		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
		
		public int[] nextIntArray(int n) throws IOException {
			final int[] ret = new int[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextInt();
			}
			return ret;
		}
		
		public long[] nextLongArray(int n) throws IOException {
			final long[] ret = new long[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextLong();
			}
			return ret;
		}
 
		public void close() throws IOException {
			br.close();
		}
	}
}

Measured memory_bytes: 23252
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define double long double
  int n,k;
  vector<int>a;
  vector<int>f;


bool good(int limit )
{
	int sum=0;
	for(int i=0;i<n;i++)
	{
		if(a[i]*f[i]>limit)
		{
			sum+=(a[i]-limit/f[i]);//no of task required to take the maximum time below the limit
		}

	}
	return sum<=k;
}

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

  cin>>n>>k;

  for(int i=0;i<n;i++)
  {
       int x;
  	cin>>x;
  	a.push_back(x);
  }
  sort(a.begin(),a.end());

   for(int i=0;i<n;i++)
  {
     int x;
  	cin>>x;
  	f.push_back(x);
  }
  sort(f.rbegin(),f.rend());
  int lo=1,hi = 1000000000010;
  int best=0;
  while(lo<=hi)
  {
  	int mid=lo+(hi-lo)/2;
  	if(good(mid))
  	{
  		hi=mid-1;
  		best=mid;
  	}
  	else
  		lo=mid+1;
  }
	if (good(min(hi, lo))) {
		cout << min(hi, lo) << endl;
	} else {
		cout << max(hi, lo) << endl;
	}
	
	
   return 0;
}

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

int main() {
	pair<int, int>AB, CD;
	cin >> AB.first >> AB.second >> CD.first >> CD.second;
	
	int ans = (AB.second < CD.second ? AB.second : CD.second);
	if (AB.first < CD.first)ans -= CD.first;
	else ans -= AB.first;
	cout << (ans>0?ans:0) << endl;

	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

using ll = long long;

void max_self(ll& a, ll b) {
    a = max(a, b);
}
void min_self(ll& a, ll b) {
    a = min(a, b);
}

const ll INF = 1e18L + 5;

int main() {
    int n, W;
    scanf("%d%d", &n, &W);
    vector<int> weight(n), value(n);
    for(int i = 0; i < n; ++i) {
        scanf("%d%d", &weight[i], &value[i]);
    }
    int sum_value = 0;
    for(int x : value) {
        sum_value += x;
    }
    vector<ll> dp(sum_value + 1, INF); // 0 ... W
    dp[0] = 0;
    // dp[i] - the minimum total weight of items with total value exactly i
    for(int item = 0; item < n; ++item) {
        for(int value_already = sum_value - value[item]; value_already >= 0; --value_already) {
        //~ for(int weight_already = 0; weight_already <= W - weight; ++weight_already) {
            min_self(dp[value_already+value[item]], dp[value_already] + weight[item]);
        }
    }
    ll answer = 0;
    for(int i = 0; i <= sum_value; ++i) {
        if(dp[i] <= W) {
            answer = max(answer, (ll) i);
        }
        //~ min_self(answer, dp[i]);
    }
    printf("%lld\n", answer);
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main (){
    int c,d,a,b;
    cin>>a>>b>>c>>d;

    if( abs(a-c)<= d ){
            cout<<"Yes";
    }
    else {
        if( abs(a-b)<=d && abs(b-c)<=d)cout<<"Yes";
        else cout<<"No";
    }
   // main();
    return 0;
}

Measured memory_bytes: 3624
#include <stdio.h>

static
const char *src[ ] = { "apple", "peach", "" };

/** Application main entry point. */
int main (
  int     argc,
  char  * argv[ ]
  )
{
  const char  * p = src[ 2 ];
  int           ch, f = 2;

  for ( ; ; )
  {
    ch = getchar ( );

    if ( ch == *p )
    {
      ++p;
      if ( *p == '\0' )
      {
        fputs ( src[ !f ], stdout );
        f = 2; p = src[ f ];
      }
    }
    else
    {
      if ( f < 2 )  fwrite ( src[ f ], sizeof ( char ), p - src[ f ], stdout );
      switch ( ch )
      {
        case 'a':   f = 0; p = src[ f ] + 1; break;
        case 'p':   f = 1; p = src[ f ] + 1; break;
        case EOF:   goto ESCAPE;  break;
        default:    f = 2; p = src[ f ];
          putchar ( ch );
          break;
      }
    }
  }
ESCAPE:

  return ( 0 );
}

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

int main() {
  int A,B,C,X;
  int counter = 0;

  cin >> A >> B >> C >> X;

  for(int i = 0;i <= A;i++){
    for(int j = 0;j <= B;j++){
      for(int k = 0;k <= C;k++){
        if(500*i+100*j+50*k == X)counter++;
      }
    }
  }

  cout << counter << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define maxn 55
#define LL long long
using namespace std;
int n,m,d,V,lim,ans;
LL f[maxn*maxn*maxn];
struct node{
	int v,id; LL w;
	bool operator < (const node &p)const{return v*p.w>w*p.v;}
}a[maxn];
vector<int>G[maxn];
void dfs(int u){for(int v:G[u]) dfs(v),a[u].v+=a[v].v,a[u].w+=a[v].w;}
void ins(LL v,LL w){for(int i=V;i>=v;i--) f[i]=min(f[i],f[i-v]+w);}
int main()
{
	scanf("%d%d%d%d",&n,&m,&d,&a[1].w),a[1].v=a[1].id=1;
	for(int i=2,x;i<=n;i++) scanf("%d%d",&a[i].w,&x),a[i].v=1,G[x].push_back(i);
	dfs(1);
	memset(f,0x3f,sizeof f),f[0]=0;
	V = n*n*n, lim = min(n,d);
	for(int i=1;i<=n;i++){
		int x=lim;
		for(int j=1;j<=x;x-=j,j<<=1) ins(1ll*j*a[i].v,j*a[i].w);
		if(x) ins(1ll*x*a[i].v,x*a[i].w);
	}
	sort(a+1,a+1+n);
	while(a[n].id!=1) n--;
	for(int i=0;i<=V&&f[i]<=m;i++){
		int v=i,w=f[i];
		for(int j=1;j<n;j++){
			int k=min(1ll*d-lim,(m-w)/a[j].w);
			v+=k*a[j].v,w+=k*a[j].w;
		}
		int k=(m-w)/a[n].w;
		ans=max(ans,v+k*a[n].v);
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 5100
#include<bits/stdc++.h>
using namespace std;
#define    for0(i,n) for(int i=0;i<n;i++)
#define    fors(i,s) for(int i=0;i<s.size();i++)
#define    nl     "\n"
#define    End    return 0
#define    gt     greater<int>()
#define    ll     long long int

int main()
{
    bool f=false;
    int n,a,b;
    cin>>n>>a>>b;
    for(int i=a;i<=b;i++){
        if(i%n==0){
            f=true;
            break;
        }
    }
    if(f)cout<<"OK";
    else cout<<"NG";
}


Measured memory_bytes: 3644
//Keep pluggin',this is your only outlet.
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cctype>
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,b,a) for(int i=b;i>=a;i--)
#define fi first
#define mp make_pair
#define se second
using namespace std;
#define int long long

inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int quickmul(int x,int y,int mod){return (x*y-(int)((long double)x/mod*y)*mod+mod)%mod;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x * f;
}

const int MAXN = 1e5 + 100;

int a[MAXN],b[MAXN],c[MAXN<<1],sum[MAXN];
int n,c1 = 0,c2 = 0,ans;
///------------------head------------------
signed main(signed argc, char *argv[]){
    n = read();
    rep(i,1,n) {
        a[i] = read(),c[i] = a[i],c1 += a[i];
        b[i] = read(),c[i+n] = b[i],c2 += b[i];
    }
    ans = min(c1,c2);
    sort(c+1,c+n*2+1);
    rep(i,1,n) sum[i] = sum[i-1] + c[i];
    for (int i = 1; i <= n; ++i) {
        int x = a[i],y = b[i];
        if (x > y) swap(x,y);
        if (lower_bound(c+1,c+2*n+1,x) - c <= n - 2) {
            if (lower_bound(c+1,c+2*n+1,y) - c <= n - 1)
            ans = min(ans,sum[n]);
            else ans = min(ans,sum[n-1] + y);
        }
        else ans = min(ans,sum[n-2] + x + y);
    }
    printf("%lld\n",ans);
    return 0;
}

/* Examples: */
/*

*/

/*

*/


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

using namespace std;

#define ll long long

const int N=1e6+5;

int m,n,k,ans,l,r,u,v,x,tc,y,q,sz,d,a[N];


char s[N];

int main(){ 
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
   
    double sum=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]),sum+=1.0/a[i];
    printf("%.6lf\n",1.0/sum);

}




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;
using P = pair<int, int>;

int main() {

    int N;
    cin >> N;

    for (int i = 1; i < 10; i++)
    {
        for (int j = 1; j < 10; j++)
        {
            if (i*j == N) {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    
    cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 3584
#include <bits/stdc++.h>
#define rep(i,N) for (int i = 0; i < (N); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int inf{int(1e9)};
int main(void){
  string s;
  cin >> s;

  int N = s.length();
  for (int i = 0; i < N; i += 2){
    cout << s[i];
  }
  cout << endl;
}


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

int main() {
  int N, K;
  string S;
  cin >> N >> K >> S;
  
  int cnt = 0;
  for (int i = 0; i < N - 1; i++) {
    if (S[i] != S[i + 1]) cnt++;
  }
  
  int x = (cnt + 1) / 2;
  if (x <= K) {
    cout << N - 1 << endl;
  } else {
    cout << N - cnt - 1 + 2 * K << endl;
  }
  
  return 0;
}

Measured memory_bytes: 512
#pragma gcc optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort(ALL(V)) //小さい方からソート
#define REV(V) reverse(ALL(V)) //リバース
#define RSORT(V) SORT(V);REV(V) //大きい方からソート
#define NPN(V) next_permutation(ALL(V)) //順列
#define pb(n) push_back(n)
#define endl '\n'
#define Endl '\n'
#define DUMP(x)  cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define Yay(n) cout << ((n) ? "Yay!" : ":(") << endl
#define RAPID cin.tie(0);ios::sync_with_stdio(false)
#define IN(n) cin >> n
#define IN2(a,b) cin >> a >> b
#define IN3(a,b,c) cin >> a >> b >> c 
#define VIN(V) for(int i = 0; i < (V).size(); i++) {cin >> (V).at(i);}
#define OUT(n) cout << n << endl
#define VOUT(V) REP(i, (V).size()) {cout << (V)[i] << endl;}
#define VOUT2(V) REP(i, (V).size()) {cout << (V)[i] << " ";} cout<<endl;

// 型マクロ定義
#define int long long
#define P pair<ll,ll>
#define Vi vector<ll>
#define Vd vector<double>
#define Vs vector<string>
#define Vc vector<char>
#define M map<ll,ll>
#define S set<ll>
#define PQ priority_queue<ll>
#define PQG priority_queue<ll,V,greater<ll>
//

const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);

int gcd(int a,int b){return b?gcd(b,a%b):a;} //最小公倍数

// デフォルト変数定義
int n,m,a,b,c,x,y,z;
double d,e,f;
string s,t;
//

signed main() {
  RAPID;
  IN2(a,b);
  if(b%a==0) OUT(a+b);
  else OUT(b-a);
}

Measured memory_bytes: 256
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int n,m;
    for(;;){
        scanf("%d%d",&n,&m);
        if(n==0&&m==0)break;
        vector<int> ns(n+1);
        for(int i=0;i<n;i++){
            scanf("%d",&ns[i]);
        }
        ns[n]=0;
        vector<int> ntwos;
        for(int i=0;i<n+1;i++){
            for(int j=i;j<n+1;j++){
                ntwos.push_back(ns[i]+ns[j]);
            }
        }
        sort(ntwos.begin(),ntwos.end());
        int ma=0;
        for(int i=0;i<ntwos.size();i++){
            vector<int>::iterator it;
            if((it=upper_bound(ntwos.begin(),ntwos.end(),m-ntwos[i]))!=ntwos.begin()){
                ma=max(ma,ntwos[i]+*(it-1));
            }
        }
        printf("%d\n",ma);
    }
}

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

int F[102][102];

void
DFS (int Y, int X, int A)
{
  if (F[Y][X] != A)
    return;

  F[Y][X] = 7;

  DFS (Y - 1, X, A);
  DFS (Y, X + 1, A);
  DFS (Y + 1, X, A);
  DFS (Y, X - 1, A);
}

int
main ()
{
  int w, h;
  int xs, ys;
  int xg, yg;
  int n;
  int c, d, x, y;

  while (true)
    {
      cin >> w >> h;
      if (w == 0 && h == 0)
	break;
      cin >> xs >> ys;
      cin >> xg >> yg;
      cin >> n;

      for (int i = 0; i < n; i++)
	{
	  cin >> c >> d >> x >> y;
	  if (d == 0)
	    {
	      for (int a = 0; a < 4; a++)
		{
		  for (int b = 0; b < 2; b++)
		    {
		      F[y + b][x + a] = c;
		    }
		}

	    }
	  else
	    {
	      for (int a = 0; a < 2; a++)
		{
		  for (int b = 0; b < 4; b++)
		    {
		      F[y + b][x + a] = c;
		    }
		}
	    }

	}


      if (F[ys][xs] == 0 || F[ys][xs] == 1 || F[ys][xs] == 2 || F[ys][xs] == 3
	  || F[ys][xs] == 4 || F[ys][xs] == 5)
	{
	  DFS (ys, xs, F[ys][xs]);
	}

      if (F[yg][xg] == F[ys][xs])
	{
	  cout << "OK" << endl;
	}
      else
	{
	  cout << "NG" << endl;
	}

    /*for (int y = 0; y < h; y++)
	{
	  for (int x = 0; x < w; x++)
	    {
	      cout << F[y][x];
	    }
         cout << endl;
	}*/

    }

  return 0;
}

Measured memory_bytes: 3092
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define VIEW(x) do {cerr << #x << ": "; for(auto i : x) cerr << i << " "; cerr << endl;} while(0)
#define ALL(x) (x).begin(),(x).end()
template<class T>bool umax(T &a, const T &b) {if(a<b){a=b;return 1;}return 0;}
template<class T>bool umin(T &a, const T &b) {if(b<a){a=b;return 1;}return 0;}

template<typename A,size_t N,typename T> void FILL(A (&array)[N],const T &val){fill((T*)array,(T*)(array+N),val);}
template<typename T> void FILL(vector<T> &v, const T &x) {fill(v.begin(), v.end(), x);}
template<typename T> void FILL(vector<vector<T>> &v, const T &x) {for(auto &i:v)fill(i.begin(), i.end(), x);}


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

  vector<int> group[3];
  rep(i,n) rep(j,n) {
    int q; cin >> q;
    group[(i+j+2) % 3].push_back(q-1);
  }

  vector<vector<int>> cost(3, vector<int>(c));
  rep(g, 3)
    rep(to, c)
      for(auto from : group[g])
        cost[g][to] += d[from][to];

  int ans = 1 << 30;
  rep(c0, c) rep(c1, c) rep(c2, c) if(c0 != c1 && c1 != c2 && c0 != c2) 
    umin(ans, cost[0][c0] + cost[1][c1] + cost[2][c2]); 
  cout << ans << endl;
}


Measured memory_bytes: 4436
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
// #include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <stack>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <sstream>
#include <iomanip>
using namespace std;


#define int int64_t
#define vi vector<int>
#define vb vector<bool>
#define vbb vector< vector<bool> >
#define all(x) (x).begin(), (x).end()
#define vii vector< vector<int> >
#define rip(dp, n, m) vector< vector<int> > dp(n, vector<int>(m,0))
#define ff first
#define ss second
#define pii pair<int64_t, int64_t>
#define miv map<int, vector<int> >
#define mp make_pair
#define pb push_back
#define prr(x) cout << (#x) <<'	' << (x) << endl
#define pr(x) cout  << (x) << endl
#define f(i,n) for(i=0;i<n;i++)
#define pqb priority_queue<int>
#define pqs priority_queue<int,vi,greater<int> >
#define setbits(x)  __builtin_popcountll(x)
#define zrobits(x)  __builtin_ctzll(x)
#define mod 1000000007
#define inf 1e18
#define ps(x,y) fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x) int x; cin>>x; while(x--)
#define FIO  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int32_t main()
{
  FIO;
  int i, n, j, m, k, l, t;
  cin >> n >> k;
  vi v(n);
  f(i,n) cin >> v[i];
  vi ans(n,1e18);
  for(i=1;i<=min(k,n-1);i++)
  {
     ans[i] = abs(v[i]-v[0]);
  }

  if(n<k)
  {
    cout << ans[n-1];
  }

  else
  {
    for(i=k+1;i<n;i++)
    {
      for(j=1;j<=k;j++) ans[i] = min(ans[i], ans[i-j] + abs(v[i]-v[i-j]));
    }
    
    cout << ans[n-1];
    // f(i,n) cout << ans[i] << " ";
 }
  

}

Measured memory_bytes: 4784