akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string.h>

using namespace std;

int n, x;
int p[200010];

int main() {
    scanf("%d%d", &n, &x);
    memset(p, 0, sizeof(p));
    if (x == 1 || x == 2 * n - 1) {
        printf("No\n");
    } else {
        for (int i = 1; i <= 2 * n - 1; i++) {
            p[i] = i;
        }
        if (x > n) {
            int move = x - n;
            for (int i = n, j = n + move; i < 2 * n - move; i++, j++) {
                p[i] = j;
            }
            for (int i = 2 * n - move, j = n; i < 2 * n; i++, j++) {
                p[i] = j;
            }
        } else if (x < n) {
            int move = n - x;
            for (int i = 1, j = n; i <= move ; i++, j--) {
                p[i] = j;
            }
            for (int i = move + 1, j = 1; i <= n; i++, j++) {
                p[i] = j;
            }
        }
        printf("Yes\n");
        for (int i = 1; i < 2 * n; i++) {
            printf("%d\n", p[i]);
        }
    }
}

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

//mint
#pragma region 
const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

ll sum(ll l, ll r) {
  return (l+r)*(r-l+1)/2;
}
 
int main() {
  int n, k;
  cin >> n >> k;
  mint ans;
  //10^100 = Bとする
  //Bは限りなく大きな数なので、選ぶ個数が異なればかぶる事はない
  for (int i = k; i <= n+1; ++i) {
    //和(S) = 0 + 1 + 2 + .....i  最小値
    //S = 1 + 2 + 3 +........i+1　一つずらした時
    //S = x + x+1 + x+2 ......x+i　x個ずらした時
    //S = n-i+1 + n-i +2.......n  最大値
    //i個選ぶうち最小の和をl 最大の和をrとする
    ll l = sum(0,i-1), r = sum(n-i+1,n);
    //0 1 2 3　から2つ選ぶ時
    //(0,1) (0,2) (0,3) (1,2) (1,3) (2,3)　の6通り考えられる
    //(0,3)と(1,2)は被るので実際は5通り
    //和のパターンは S = 2,3,4,5,6....(n-1 + n)まである
    //すなわち S = l, l +1 ,l+2, .....rに置き換えられる
    //よってパターン数は r -l + 1個となる
    ans += r-l+1;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int n, m;
int constexpr maxn = 100009;
vector<vector<int>> G;

array<int, maxn> dp;

void read_input()
{
    cin >> n >> m;
    G.resize(n + 1);
    for(int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        G[x].push_back(y);
    }
}

int go(int v) {
    if(dp[v] != -1) return dp[v];
    dp[v] = 0;
    for(int adj : G[v]) dp[v] = max(dp[v], 1 + go(adj));
    return dp[v];
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    read_input();
    dp.fill(-1);

    for(int i = 1; i <= n; i++) go(i);

    cout << *max_element(begin(dp) + 1, begin(dp) + n + 1) << endl;

}


Measured memory_bytes: 7424
import java.util.Scanner;

public class Main {

	public static void main (String[] args)  {

		Scanner sc = new Scanner(System.in);
		long h = sc.nextLong();
		long w = sc.nextLong();
		long n = sc.nextLong();
		
		for(int i=0;i<=n;i++) {
			for(int j=0;j<=i;j++) {
				if (h*w-(h-i+j)*(w-j)>=n) {
					System.out.println(i);
					return;
				}
			}
		}
	}

}


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

int main() {
	
	/*
	int a, b, c, d, e;
	cin >> a >> b >> c >> d >> e;

	int answer;
	if (a < 0) {
		answer = -a * c + d + b * e;
	}
	if (a > 0) {
		answer = (b - a)*e;
	}

	cout << answer << endl;
	*/

	/*
	int a, b, c, d, e;
	cin >> a >> b >> c >> d >> e;
	int answer;
	if (a < 40) {
		a = 40;
	}
	if (b < 40) {
		b = 40;
	}
	if (c < 40) {
		c = 40;
	}
	if (d < 40) {
		d = 40;
	}
	if (e < 40) {
		e = 40;
	}
	answer = (a + b + c + d + e) / 5;
	cout << answer << endl;
	*/

	int a, b, c, d, e, f, answer;
	cin >> a >> b >> c >> d >> e >> f;
	if (a <= b&&a <= c&&a <= d) {
		answer = b + c + d;
	}
	if (b <= a&&b <= c&&b <= d) {
		answer = a + c + d;
	}
	if (c <= a && c <= b && c <= d) {
		answer = a + b + d;
	}
	if (d <= a && d <= b && d <= c) {
		answer = a + b + c;
	}
	if (e <= f) {
		answer = answer + f;
	}
	if (e > f) {
		answer = answer + e;
	}
	cout<<answer<< endl;



	return 0;
}


Measured memory_bytes: 3104
#include <cstdio>
#include <cassert>

struct Tree {
    struct Node {
        int value;
        Node *left, *right;
    } *root;
    Node *parse_tree(const char str[], size_t &i) {
        assert(str[i] == '(');

        Node *node=new Node;
        node->left = parse_node(str, i);
        assert(str[i] == '[');
        node->value = parse_int(str, ++i);
        assert(str[i] == ']');
        ++i;
        assert(str[i] == '(');
        node->right = parse_node(str, i);

        return node;
    }
    Node *parse_node(const char str[], size_t &i) {
        assert(str[i] == '(');
        Node *node=(str[++i]==')'? nullptr:parse_tree(str, i));
        assert(str[i] == ')');
        ++i;

        return node;
    }
    int parse_int(const char str[], size_t &i) {
        int res=0;
        while (str[i] <= '9')
            res = res*10 + str[i++]-'0';

        return res;
    }
    void clear(Node *node) {
        if (!node) return;

        clear(node->left);
        clear(node->right);
        delete node;
    }
    Tree(const char str[], size_t &i): root(parse_tree(str, i)) {}
    ~Tree() {
        clear(root);
    }
};

using Node=Tree::Node;

void dfs(const Node *s, const Node *t) {
    if (s->left && t->left) {
        printf("(");
        dfs(s->left, t->left);
        printf(")");
    } else {
        printf("()");
    }

    printf("[%d]", s->value+t->value);

    if (s->right && t->right) {
        printf("(");
        dfs(s->right, t->right);
        printf(")");
    } else {
        printf("()");
    }
}

int main() {
    char A[1024], B[1024];
    scanf("%s %s", A, B);

    size_t i=0, j=0;
    Tree a(A, i), b(B, j);

    dfs(a.root, b.root);
    printf("\n");
    return 0;
}

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

int main(){

string s, t;
  cin >> s >> t;
int S[s.size()] = {27};
int T[t.size()] = {27};  
int mi = min(s.size(), t.size()); 
bool a = false;  
    
  for(int i = 0;i < s.size();i++) S[i] = s.at(i) - '0' - 49;
  for(int i = 0;i < t.size();i++) T[i] = t.at(i) - '0' - 49;
  
  sort(S, S + s.size());
  sort(T, T + t.size());
  
  for(int i = 0;i < mi;i++){
  if(S[i] < T[t.size() - (i + 1)]){
  a = true;
  break;  
  }
  else if(S[i] > T[t.size() - (i + 1)]){
  a = false;
  break;   
  }
  else if((i == mi - 1) && (s.size() < t.size()) && (S[mi - 1] <= T[t.size() - (i + mi)])){
  a = true;
  break;  
  }  
  }

  if(a) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
  
}

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

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

#define pb push_back
#define rep(i, n) for(int i = 0; i < (n); i++)
#define dep(i, a, n) for(int i = a; i >= (n); i--)
#define FOR(i, a, n) for(int i = a; i < (n); i++)
#define mod (ll)(1e9+7)
#define int ll
#define INF 100000000

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

signed main() {
	ll w;
  cin >> w;
  cout << w * 32 << endl;
	return 0;
}


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

int main() {
	int n;
	string str;
	cin >> str >> n;

	int ans = 0;
	for(int i = 0; i < n; ++i) {
		string ring;
		cin >> ring;
		ring += ring;
		if(ring.find(str) != str.npos)
			++ans;
	}

	cout << ans << endl;

	return EXIT_SUCCESS;
}

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

int main()
{
	string str;
	while (cin >> str, str != "#") {
		int hand = -1, res = -1;
		for (int i = 0; i < str.length(); i++) {
			if (str[i] == 'y' || str[i] == 'u' || str[i] == 'i' || str[i] == 'o' || str[i] == 'p'
				|| str[i] == 'h' || str[i] == 'j' || str[i] == 'k' || str[i] == 'l' || str[i] == 'n' || str[i] == 'm') {
				if (hand != 0) {
					hand = 0;
					res++;
				}
			}
			else {
				if (hand != 1) {
					hand = 1;
					res++;
				}
			}
		}
		cout << res << endl;
	}
	return 0;
}

Measured memory_bytes: 1184
#include <stdio.h>
#include <limits.h>
 
#define MAX 5000
 
int main(void) {
    int n, d[MAX];
    int sum, max;
    int i, j;
 
    while (scanf("%d", &n) != EOF) {
        if (n == 0) break;
 
        for (i = 0; i < n; i++)
            scanf("%d", &d[i]);
 
        max = INT_MIN;
        for (i = 0; i < n; i++) {
            sum = 0;
            for (j = i; j < n; j++) {
                sum += d[j];
                if (max < sum) max = sum;
            }
        }
        printf("%d\n", max);
    }
    return 0;
}


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

int main() {
    int A[5] = {};int k;
    for (int i = 0;i < 5;i++){
        cin >> A[i];
    }
    cin >> k;
    if ((A[4] - A[0]) > k) cout << ":(" << endl;
    else cout << "Yay!" << endl;
}

Measured memory_bytes: 256
n,k=map(int,input().split())
p=[]
p=list(map(int,input().split()))

ans=sum(p[0:k])
aa=sum(p[0:k])
for i in range(1,n-k+1):
    aa=aa-p[i-1]+p[i+k-1]
    ans=max(ans,aa)

aaaa=(ans+k)/2
print(aaaa)

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

int main(){
	string str;
	getline(cin,str);
	for(int i= 0;i<str.size();i++){
		str[i] = toupper(str[i]);
	}
	cout << str << endl;
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <cmath>
#include <complex>
using namespace std;

using vec = complex<double>;
using line = pair<vec,vec>;
const double eps = 0.0000001;

double inner_product(vec u,vec v){
    return real(u*conj(v));
}
double cross_product(vec u,vec v){
    return imag(conj(u)*v);
}

double norm(vec& u){
    return abs(u);
}

vec projection(line l,vec p){//p???l???????°???±
    vec s=l.first, t=l.second;
    double k = inner_product(t-s,p-s)/inner_product(t-s,t-s);
    return (1.0-k)*s+k*t;
}

vec reflection(line l,vec p){
    return 2.0*projection(l,p)-p;
}

int ccw(vec& a, vec& b, vec& c){
    vec ab = b-a, ac = c-a;
    double o = cross_product(ab,ac);
    if(o>0) return 1; //CCW
    if(o<0) return -1; //CW
    if(inner_product(ab,ac)<0){
        return 2; //C-A-B
    }else{
        if(inner_product(ab,ab)<inner_product(ac,ac)){
            return -2; //A-B-C
        }else{
            return 0; //A-C-B
        }
    }
}

//???????????§???????????????

bool isIntersect(line l0, line l1){
    int s = ccw(l0.first,l0.second,l1.first)*ccw(l0.first,l0.second,l1.second);
    if(s!=0&&s!=-1&&s!=-4) return false;
    s=ccw(l1.first,l1.second,l0.first)*ccw(l1.first,l1.second,l0.second);
    if(s!=0&&s!=-1&&s!=-4) return false;
    else return true;
}

int main(void){
    int q;
    cin >> q;
    while(q--){
        int x,y;
        cin>>x>>y;
        vec p0(x,y);
        cin>>x>>y;
        vec p1(x,y);
        cin>>x>>y;
        vec p2(x,y);
        cin>>x>>y;
        vec p3(x,y);
        if(isIntersect(line(p0,p1),line(p2,p3))) cout << 1 << endl;
        else cout << 0 << endl;
    }
    return 0;
}

Measured memory_bytes: 3088
#include <iostream>
#include <vector>
#include <utility>

using std::cout;
using std::endl;
using std::cin;
using std::vector;
using std::pair;
using std::make_pair;

const int INF = 1 << 30;

// G[src]=p(dest,distance)
vector<vector<pair<int,int>>> G(100'010);

bool dfs(int s, vector<bool> &visited, vector<int> &x) {
	visited[s] = true;
	for(auto u: G[s]) {
		int dest = u.first;
		int dist = u.second;
		if(visited[dest]) {
			if(x[dest] != x[s] + dist) return false;
		} else {
			x[dest] = x[s] + dist;
			if(!dfs(dest, visited, x)) return 0;
		}
	}
	return true;
}

int main() {
	// Input
	int N, M;
	cin >> N >> M;
	for(int i = 0; i < M; ++i) {
		int l, r, d;
		cin >> l >> r >> d;
		G[l].push_back(make_pair(r,d));
		G[r].push_back(make_pair(l,-d));
	}
	// Calculation
	bool satisfiable = true;
	vector<bool> visited(N+1);
	vector<int> x(N+1);
	for(int i = 1; i <= N; ++i) {
		if(visited[i]) continue;
		if(!dfs(i, visited, x)) { satisfiable = false; break; }
	}
	// Output
	if(satisfiable) cout << "Yes" << endl;
	else            cout << "No" << endl;
	return 0;
}



Measured memory_bytes: 12928
#include <bits/stdc++.h>
#define ALL(v) v.begin(), v.end()
#define MOD 1000000007
#define INF 1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define req(i, j, n) for(int i = j; i <= (int)(n); i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
 
int main() {
    int n,m;
    cin>>n>>m;
    cout<<n*m<<endl;
    return 0;}


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

int main()
{
	// std::ios::sync_with_stdio(false);
    int N, K;
    cin >> N >> K;

    double ans;
    // double count
    int n, score;
    int num_loop = min(K, N);
    for (int i=1; i<=N; i++)
    {
        if (i >= K)
        {
            ans += (double) 1/N;
            continue;
        }
        score = i;
        n = 1;
        while (score < K)
            n++, score <<= 1;
        n--;
        // cout << n << endl;
        ans += (double) 1 / ((1 << n) * N);
    }
    printf("%.15lf\n", ans);
   	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    int a, b;
    cin >> a >> b;
    if (a == b) cout << "Draw";
    else
    {
        if (a == 1) cout << "Alice";
        else if (b == 1) cout << "Bob";
        else
        {
            if (a > b) cout << "Alice";
            else cout << "Bob";
        }
    }
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
// #define che
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define fi first
#define se second
#define MK make_pair
#define PB push_back
using namespace std;

typedef long long LL;
typedef pair<int ,int> PII;
const int N=110;

string s[N];
int t[N];
int n;
int main(){
	#ifdef che
	freopen("input.txt","rt",stdin);
	freopen("output.txt","wt",stdout);
	#endif
	cin>>n;
	for (int i=0; i<n; ++i)cin>>s[i]>>t[i];
	string tar;cin>>tar;
	int res=0,flag=0;
	for (int i=0; i<n;++i){
		res += flag*t[i];
		if ( s[i]==tar) flag=1;
	}
	printf("%d\n", res);
	return 0;
}

Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <cassert>
using namespace std;
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
const double EPS = 1e-9;
const double PI  = acos(-1.0);

vvi mul(vvi &m,vvi &n,int mod){
	int sz=m.size();
	vvi ret(sz,vi(sz));
	REP(i,sz){
		REP(j,sz){
			REP(k,sz){
				ret[i][j]+=m[i][k]*n[k][j];
				ret[i][j]=ret[i][j]%mod;
			}
		}
	}
	return ret;
}
vvi pow(vvi m,int t,int mod){
	int sz=m.size();
	vvi ret(sz,vi(sz,0));
	REP(i,sz){
		ret[i][i]=1;
	}
	while(t){
		if(t&1){
			ret=mul(ret,m,mod);
		}
		m=mul(m,m,mod);
		t>>=1;
	}
	return ret;
}
int main(){
	int n,m,a,b,c,t;
	while(cin>>n>>m>>a>>b>>c>>t,n|m|a|b|c|t){
		vi s(n);
		REP(i,n){
			cin>>s[i];
		}
		vvi matrix(n,vi(n));
		REP(i,n){
			FOR(j,i-1,i+1+1){
				if(j>=0&&j<n){
					int abc[3]={a,b,c};
					matrix[i][j]=abc[j-(i-1)];
				}
			}
		}
		vvi powed_matrix=pow(matrix,t,m);
		vvi ans(n,vi(n,0));
		REP(i,n){
			ans[i][0]=s[i];
		}
		ans=mul(powed_matrix,ans,m);
		REP(i,n){
			cout<<(i!=0?" ":"")<<ans[i][0];
		}
		cout<<endl;
	}
}

Measured memory_bytes: 1284
N=int(input())
p=list(map(int,input().split()))

M=0
for i in range(N-1):
    if p[i]==i+1:
        p[i],p[i+1]=p[i+1],p[i]
        M+=1
if p[N-1]==N:
    M+=1
print(M) 

Measured memory_bytes: 14008
import sys
def I(): return int(sys.stdin.readline().rstrip())
N = I()
dp = [float('INF')]*(N+1) #1_indexed
dp[0] = 0
for i in range(N+1):
    if i+1<=N:
        dp[i+1] = min(dp[i+1],dp[i+1],dp[i]+1)
    num6,num9 = 6,9
    while i+num6<=N:
        dp[i+num6] = min(dp[i+num6],dp[i]+1)
        num6 *= 6
    while i+num9<=N:
        dp[i+num9] = min(dp[i+num9],dp[i]+1)
        num9 *= 9
print(dp[-1])


Measured memory_bytes: 3828
#include <bits/stdc++.h>
#define int long long
#define mod (int)(1e9+7)
#define inf (int)(3e18+7)
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define P pair<int,int>
#define all(v) v.begin(),v.end()
#define mkp make_pair
#define mkt make_tuple
#define prique(T) priority_queue<T,vector<T>,greater<T>>
#define vecunique(vec) sort(vec.begin(), vec.end());decltype(vec)::iterator result = std::unique(vec.begin(), vec.end());vec.erase(result, vec.end())
using namespace std;
 
bool prime(int x) {
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0)return false;
	}
	return x > 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int kai(int x) {
	if (x == 0)return 1;
	return kai(x - 1) * x % mod;
}
int mod_pow(int x, int y, int mod_) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % mod_;
		}
		x = x * x % mod_;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	return kai(x)* mod_pow(kai(x - y), mod - 2, mod) % mod * mod_pow(kai(y), mod - 2, mod) % mod;
}
/*--------Library Zone!--------*/

signed main(){
	int a,b,k;cin>>a>>b>>b>>b>>b>>k;
	if(b-a>k)cout<<":("<<endl;
	else cout<<"Yay!"<<endl;
}


Measured memory_bytes: 256
import sys
input=sys.stdin.readline
n=int(input())

def bin(start):
    ok=0
    ng=n
    while abs(ng-ok)>1:
        mid=(ok+ng)//2
        print(mid)
        sys.stdout.flush()
        s=input()
        if s=='Vacant':exit()
        if mid%2==0 and start==s:
            ok=mid
        elif mid%2!=0 and start!=s:
            ok=mid
        else:
            ng=mid
print(0)
sys.stdout.flush()
start=input()
if start=='Vacant':exit()
bin(start)


Measured memory_bytes: 3660
a,b,c,k = map(int, input().split())

ans = 0
if a <= k:
    ans += a
    k -= a
elif k <= a:
    ans += k
    print(ans)
    exit()
if b <= k:
    k -= b
elif k <= b:
    print(ans)
    exit()
ans -= k
print(ans) 

Measured memory_bytes: 8912
import java.util.*;
import java.io.*;
import static java.lang.Math.*;

public class Main {
    public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		// 入力
		int n = sc.nextInt();
		int m = sc.nextInt();
		UnionFind uf = new UnionFind(n);
		for(int i = 0; i < m; i++){
		    int a = sc.nextInt()-1;
		    int b = sc.nextInt()-1;
		    uf.union(a, b);
		}
		
		// 計算
		int result = 0;
		result = uf.groups().size()-1;
		
		// 出力
		System.out.println(result);
	}
	
	public static class Scanner {
		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());}
	}
}

class UnionFind {
	int[] parent;
	int[] rank;
	int[] cnt;
	
	UnionFind(int n){
		this.parent = new int[n];
		this.rank = new int[n];
		this.cnt = new int[n];
		for(int i = 0; i < n; i++){
			parent[i] = i;
			rank[i] = 0;
			cnt[i] = 1;
		}
	}
	
	public int find(int i){
		if(i == parent[i]) return i;
		parent[i] = find(parent[i]);
		return parent[i];
	}
	
	public boolean union(int x, int y){
		int xRoot = find(x);
		int yRoot = find(y);
		if(xRoot == yRoot) return false;
		if(rank[xRoot] < rank[yRoot]){
			parent[xRoot] = yRoot;
			cnt[yRoot] += cnt[xRoot];
		}else if(rank[xRoot] > rank[yRoot]){
			parent[yRoot] = xRoot;
			cnt[xRoot] += cnt[yRoot];
		}else{
			parent[yRoot] = xRoot;
			rank[xRoot]++;
			cnt[xRoot] += cnt[yRoot];
		}
		return true;
	}
	
	public boolean same(int x, int y){
		return find(x) == find(y);
	}

	public int cnt(int x){
		return cnt[find(x)];
	}

	public ArrayList<ArrayList<Integer>> groups(){
		HashMap<Integer, ArrayList<Integer>> hm = new HashMap<Integer, ArrayList<Integer>>();
		for(int i = 0; i < this.parent.length; i++){
			ArrayList<Integer> list = hm.getOrDefault(find(i), new ArrayList<Integer>());
			list.add(i);
			hm.put(find(i), list);
		}
		ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
		for(ArrayList<Integer> list : hm.values()){
			res.add(list);
		}
		return res;
	}
}

Measured memory_bytes: 56528
import java.util.*;

class Main{
  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    char[] arr = scan.next().toCharArray();
    int result = arr.length;
    int scount = 0;
    for(char c : arr) {
      if(c=='S') scount++;
      else {
        if(scount>0) {
          scount--;
          result-=2;
        }
      }
    }
    System.out.println(result);
  }
}


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

// int/long:		-2,147,483,648 - 2,147,483,647 (-2^31 <= int < 2^31)
// long/long long:	-9,223,372,036,854,775,808 - 9,223,372,036,854,775,807 (-2^63 <= long < 2^63)

// lower_bound(A.begin(), A.end(), N)
// upper_bound(...

// A.erase(unique(A.begin(), A.end()), A.end())

// bit: &/and, |/or, ^/xor, ~/not

// getline(cin, String)
// while (getline(cin, S)) {}

// #include <cstdio>
// int a;
// scanf("%d", &a);
// printf("%d\n", a);
//
// for (int i=0; i<n; ++i)
// 	scanf("%d", &a[i]);
//
// char c;
// scanf(" %c", &c);
//
// cout << "\n";

// cout <<fixed <<setprecision(10)

// priority_queue<int> q;
// priority_queue<int, vector<int>, less<int>> q; // Default: vector, less
// priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> q;

// Graph
// Warshall-Floyd: Distance between each node, N^3
// Dijkstra: Distance from the start node, N^2
// DFS(Depth-First Search)

//
// Notes
//
// When specified less than N, try full scan.
// RE: empty vector
// Check Qs
// long/int
// xor -> count each bit
// Check values
// 	1,000,000 -> Loop
// 	100,000	-> vector(int:400KB, long:800KB) 

#define	INF (1<<30)
//1,073,741,824
//= 536,870,912 *2

#define	MOD 1000000007

/*
ll	myPow(ll x, ll n) {
	if (0==n)
		return 1;
	if (0==n%2)
		return myPow(x*x%MOD, n/2);
	else
		return x*myPow(x, n-1)%MOD;
}
*/
ll	myPow(ll x, ll n) {
	ll r=1;
	while(n>0)
		if (0==n%2) {
			x *=x;
			x %=MOD;
			n /=2;
		} else {
			r *=x;
			r %=MOD;
			n--;
		}
	return r;
}

#define	Rep0(i, n)	for (int i=0; i<n; i++)
#define	Rep1(i, n)	for (int i=1; i<=n; i++)
#define Sort(P)	sort(P.begin(), P.end())
#define Rev(P)	reverse(P.begin(), P.end())

int	main() {
	int H, W;
	cin >>H >>W;
	vector<vector<int>> s(H+2, vector<int> (W+2, 0));
	Rep1(i, H)
		Rep1(j, W) {
			char ss;
			cin >>ss;
			if ('#'==ss)
				s.at(i).at(j)=1;
		}
	vector<vector<int>> DP(H+2, vector<int> (W+2, INF));
	DP.at(1).at(1)=s.at(1).at(1);
	Rep1(i, H)
		Rep1(j, W) {
			int D=DP.at(i).at(j);
			if ((0==s.at(i).at(j))&&(1==s.at(i).at(j+1)))
				DP.at(i).at(j+1)=min(DP.at(i).at(j+1), D+1);
			else
				DP.at(i).at(j+1)=min(DP.at(i).at(j+1), D);
			if ((0==s.at(i).at(j))&&(1==s.at(i+1).at(j)))
				DP.at(i+1).at(j)=min(DP.at(i+1).at(j), D+1);
			else
				DP.at(i+1).at(j)=min(DP.at(i+1).at(j), D);
		}
	cout <<DP.at(H).at(W) <<endl;
	return 0;
}



Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using ull = unsigned long long;

ull f(ull H)
{
	if (H == 1)
	{
		return 1ull;
	}
	else
	{
		return f(H / 2) * 2 + 1;
	}
}

int main()
{
	ull H;
	std::cin >> H;

	std::cout << f(H);
}


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

int main(){
    int_fast32_t N, K;
    cin >> N >> K;
    vector<int_fast32_t> h(N);
    for(int i = 0; i < N; ++i)cin >> h[i];
    sort(h.begin(), h.end());
    int_fast64_t ans = numeric_limits<int_fast64_t>::max() / 5;
    for(int i = K - 1; i < N; ++i){
        ans = min<int_fast64_t>(ans, h[i] - h[i - K + 1]);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define Rint register int
using namespace std;
typedef long long LL;
const int N = 1 << 14, mod = 998244353, G = 3, Gi = 332748118;
inline void qmo(int &x){x += (x >> 31) & mod;}
template<typename T>
inline void read(T &x){
	int ch = getchar(); x = 0;
	while(ch < '0' || ch > '9') ch = getchar();
	while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0'; ch = getchar();}
}
inline int ksm(int a, int b){
	int res = 1;
	while(b){
		if(b & 1) res = (LL) res * a % mod;
		a = (LL) a * a % mod; b >>= 1;
	}
	return res;
}
int n, m, ans, rev[N], lim, fac[N], inv[N], f[N], g[N], tmp[N];
inline void calrev(int len){
	int L = -1; lim = 1;
	while(lim <= len){lim <<= 1; ++ L;}
	for(Rint i = 0;i < lim;++ i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << L);
}
inline void NTT(int *a, int type){
	for(Rint i = 0;i < lim;++ i)
		if(i < rev[i]) swap(a[i], a[rev[i]]);
	for(Rint mid = 1;mid < lim;mid <<= 1){
		int Wn = ksm(type == 1 ? G : Gi, (mod - 1) / (mid << 1));
		for(Rint j = 0;j < lim;j += mid << 1){
			int w = 1;
			for(Rint k = 0;k < mid;++ k, w = (LL) w * Wn % mod){
				int x = a[j + k], y = (LL) w * a[j + k + mid] % mod;
				qmo(a[j + k] = x + y - mod); qmo(a[j + k + mid] = x - y); 
			}
		}
	}
	if(type == -1){
		int inv = ksm(lim, mod - 2);
		for(Rint i = 0;i < lim;++ i) a[i] = (LL) a[i] * inv % mod;
	}
}
inline void init(int n){
	fac[0] = 1;
	for(Rint i = 1;i <= n;++ i) fac[i] = (LL) fac[i - 1] * i % mod;
	inv[n] = ksm(fac[n], mod - 2);
	for(Rint i = n;i;-- i) inv[i - 1] = (LL) inv[i] * i % mod; 
}
int main(){
	read(n); read(m); init(n + 2);
	for(Rint i = 1;i <= n;++ i) g[i] = inv[i + 2]; calrev(n << 1); NTT(g, 1);
	f[0] = tmp[0] = 1;
	for(Rint i = 1;i <= m;++ i){
		NTT(tmp, 1);
		for(Rint j = 0;j < lim;++ j) tmp[j] = (LL) tmp[j] * g[j] % mod;
		NTT(tmp, -1);
		for(Rint j = 0;j <= n;++ j){
			f[j] = ((LL) tmp[j] * fac[j + 2] + (LL) f[j] * (1 + (j * (j + 1ll) >> 1))) % mod;
			tmp[j] = (LL) f[j] * inv[j] % mod;
		}
		memset(tmp + n + 1, 0, lim - n - 1 << 2);
	}
	for(Rint i = 0;i <= n;++ i) ans = (ans + (LL) inv[i] * inv[n - i] % mod * f[i]) % mod;
	printf("%d\n", (LL) fac[n] * ans % mod);
}

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

class Main {

	public static void main(String[] args) throws Exception {
		final Scanner sc = new Scanner(System.in);
		int K = sc.nextInt();

		int[] a = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51
		};
		System.out.println(a[K - 1]);
	}


}


Measured memory_bytes: 21204
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <cassert>
#include <unordered_map>

#define _(x) { cout << #x << " = " << x << " "; }

const double E = 1e-8;
const double PI = acos(-1);

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string n;
    cin >> n; 
    if (n[0] - '0' == 7 || n[1] - '0' == 7 || n[2] - '0' == 7) cout << "Yes\n";
    else cout << "No\n";
    return 0;
}



Measured memory_bytes: 3636
#include<stdio.h>
#include<ctype.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
int main(void){
    char a[201];
    char b[201];
    char d[201];
    int i,j,c,alen,blen,h;
    while(1){
        scanf("%s",a);
        if(a[0] == '-' ) break;
        scanf("%d",&h);
        for(j=0;j<h;j++){
            scanf("%d",&c);
            alen = strlen(a);
            for(i = 0;i<c;i++){
                d[i] = a[i];
            }
            for(i = 0;i<(alen -c);i++){
                a[i] = a[i+c];
            }
            for(i=0;i<c;i++){
                a[i + (alen -c)] = d[i];
            }
        }
        printf("%s\n",a);


    }
    return 0;
}

Measured memory_bytes: 584
q = int(input())
S = set([])

for i in range(q):
    query, x = list(map(int, input().split()))

    # insert
    if query == 0:
        S.add(x)
        print(len(S))

    # find
    elif query == 1:
        if x in S:
            print(1)
        else:
            print(0)

    # delete
    else:
        if x in S:
            S.remove(x)



Measured memory_bytes: 23356
//temp##############################################

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void strInit(char str[]);//str[]を0で初期化
void extIntStr(char str[],int data[]);//str[]から数値(int)を抽出しdata[]に順次格納
void incsort(int data[],int len);//data[]を昇順ソート
void decsort(int data[],int len);//data[]を降順ソート
void printIntArray(int data[],int len);//data[]をprint
int* inputArray(int n);//文字列を受け取り数値を抽出、n個の数値(int)を格納した配列のポインタをreturn
int* cpyArray(int data[],int len);//配列(int)を複製した配列のポインタをreturn

void strInit(char str[]){
    int len=strlen(str);
    for(int i=0;i<len;i++){
        str[i]=0;
    }
}

void extIntStr(char str[],int data[]){
    int length=strlen(str);
    str[length-1]=' ';
    char buff[12];
    int j,index;
    index=j=0;
    for(int i=0;i<length;i++){
        if(str[i]!=' '){
            buff[j++]=str[i];
        }else{
            data[index++]=atoi(buff);
            strInit(buff);
            j=0;
        }
    }
}

void incsort(int data[],int len){
    for(int i=0;i<len-1;i++){
        for(int j=i+1;j<len;j++){
            if(data[i]>data[j]){
                int tmp=data[i];
                data[i]=data[j];
                data[j]=tmp;
            }
        }
    }
}

void decsort(int data[],int len){
    for(int i=0;i<len-1;i++){
        for(int j=i+1;j<len;j++){
            if(data[i]<data[j]){
                int tmp=data[i];
                data[i]=data[j];
                data[j]=tmp;
            }
        }
    }
}

void printIntArray(int data[],int len){
    for(int i=0;i<len;i++){
        printf("%d\n",data[i]);
    }
}

int* inputArray(int n){
    int *data;
    data=(int*)malloc(sizeof(int)*n);
    char *get;
    get=(char*)malloc(sizeof(char)*11*n+1);
    fgets(get,11*n+1,stdin);
    extIntStr(get,data);
    free(get);
    return data;
}

int* cpyArray(int data[],int len){
    int *cp;
    cp=(int*)malloc(sizeof(int)*len);
    for(int i=0;i<len;i++){
        cp[i]=data[i];
    }
    return cp;
}

//temp##############################################

//don't forget free(data);

int main(){
    int n;
    scanf("%d ",&n);
    int *data;
    int *cpy;
    data=inputArray(n);
    cpy=cpyArray(data,n);
    int q=0;
    int i,j;
    int min=0;
    incsort(cpy,n);
    for(int i=0;i<n;i++){
        if(cpy[i]!=data[i])q++;
    }
    if(q>2)printf("NO");
    else printf("YES");
    return 0;
}

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

int main() {
	int a, b;
	cin >> a >> b;
	if (a <= 8 && b <= 8) cout << "Yay!" << endl;
	else cout << ":(" << endl;

	return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long X = sc.nextLong();
		long N = X-1;
		Map<Long, Long> fact = new HashMap<>();
		long ans = 1;
		for(int i = 2; i <= Math.sqrt(N); i ++) {
			if(N % i == 0) {
				long n = 0;
				while(N % i == 0) {
					N /= i;
					n++;
				}
				fact.put((long)i, n);
			}
		}
		if(N > 1)
			fact.put(N, 1L);
		for(long x : fact.values())
			ans *= x+1;
		ans--;
		Set<Long> cd = new HashSet<>();
		for(int i = 1; i <= Math.sqrt(X); i++) {
			if(X % i == 0) {
				cd.add((long)i);
				cd.add(X/i);
			}
		}
		cd.remove(1L);
		for(long i : cd) {
			long Y = X;
			while(true) {
				if(Y % i == 0)
					Y /= i;
				else {
					Y %= i;
					break;
				}
				if(Y == 1)
					break;
			}
			if(Y == 1)
				ans++;
		}
		System.out.println(ans);
	}

}


Measured memory_bytes: 24532
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<list>
#include<string>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<ctime>
using namespace std;

typedef long long ll;

bool debug = false;
const int NIL = -1;
const int INF = 1000000000;
const int NUM = 100010;
clock_t START, END;

int X, Y, E;

struct Edge {
	int from, to, cap, flow;
	Edge(int u, int v, int c, int f) :from(u), to(v), cap(c), flow(f) {}
};

struct Graph {
	int n, m;
	vector<Edge> edges;
	vector<int> G[NUM];
	int a[NUM];
	int p[NUM];

	void init(int n) {
		for (int i = 0; i < n; i++)
			G[i].clear();
		edges.clear();
	}

	void AddEdge(int from, int to, int cap) {
		edges.push_back(Edge(from, to, cap, 0));
		edges.push_back(Edge(to, from, 0, 0));
		m = edges.size();
		G[from].push_back(m - 2);
		G[to].push_back(m - 1);
	}

	int Maxflow(int s, int t) {
		int flow = 0;
		for (;;) {
			memset(a, 0, sizeof(a));
			queue<int> Q;
			Q.push(s);
			a[s] = INF;
			while (!Q.empty()) {
				int x = Q.front();
				Q.pop();
				for (int i = 0; i < G[x].size(); i++) {
					Edge& e = edges[G[x][i]];
					if (!a[e.to] && e.cap > e.flow) {
						p[e.to] = G[x][i];
						a[e.to] = min(a[x], e.cap - e.flow);
						Q.push(e.to);
					}
				}
				if (a[t])
					break;
			}
			if (!a[t])
				break;
			for (int u = t; u != s; u = edges[p[u]].from) {
				edges[p[u]].flow += a[t];
				edges[p[u] ^ 1].flow -= a[t];
			}
			flow += a[t];
		}
		return flow;
	}

};

Graph solve;

int main(void)
{
	if (debug) {
		START = clock();
		freopen("in29.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	}
	int x, y;
	cin >> X >> Y >> E;
	solve.init(X + Y + 2);
	for (int i = 0; i < X; i++)
		solve.AddEdge(0, i + 1, 1);
	for (int i = 0; i < Y; i++)
		solve.AddEdge(X + i + 1, X + Y + 1, 1);
	for (int i = 0; i < E; i++) {
		scanf("%d%d", &x, &y);
		solve.AddEdge(x + 1, X + 1 + y, 1);
	}
	cout << solve.Maxflow(0, X + Y + 1) << endl;
	if (debug) {
		END = clock();
		double endtime = (double)(END - START) / 1000;
		printf("total time = %lf s", endtime);
	}
	return 0;
}


Measured memory_bytes: 6116
#include<stdio.h>
int main(void){
    int n;
    int b,f,r,v;
    int i,j,k,l;
    int room[5][4][11]={0};
    scanf("%d",&n);
    for(l=0;l<n;l++){
        scanf("%d %d %d %d",&b,&f,&r,&v);
        for(i=1;i<=4;i++){
            for(j=1;j<=3;j++){
                for(k=1;k<=10;k++){
                    if(i==b)
                        if(j==f)
                            if(k==r){
                                room[i][j][k]+=v;
                                if(room[i][j][k]>9)
                                    room[i][j][k]=9;
                                if(room[i][j][k]<0)
                                    room[i][j][k]=0;
                            }
                }
            }
        }
    }
    for(i=1;i<=4;i++){
        for(j=1;j<=3;j++){
            for(k=1;k<=10;k++){
                printf(" %d",room[i][j][k]);
            }
        printf("\n");
        }
    if(i<=3)
        printf("####################\n");
    }
    return 0;
}

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

using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef pair<int,int> pii;

#define FASTIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define ff it->first
#define ss it->second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(auto i=0;i<n;++i)
#define LOOP_IT(it,s) for(auto it=(s).begin();it!=(s).end();++it)


#ifdef LOCAL
#define cerr cout
#else
#endif

#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif


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


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




int main(int argv, char* argc[])
{
    FASTIO

    ll n;
    cin>>n;
    ll sum = 100;
    ll cnt=0;
    while(sum<n)
    {
        sum+=(sum/100);
        ++cnt;
    }
    cout<<cnt;
    return 0;
}


Measured memory_bytes: 3664
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {n: usize, p: [usize; n]};

    let mut count = 1;
    let mut min = p[0];

    for i in 1..n {
        if min >= p[i] {
            count += 1;
            min = p[i];
        }
    }

    println!("{}", count)
}


Measured memory_bytes: 4748
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<utility>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<queue>
#include<set>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define prin(arg) cout<<arg<<"\n"
#define prin2(arg1,arg2) cout<<arg1<<" "<<arg2<<"\n"
#define fill(arg,n) memset(arg,n,sizeof(arg))
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef set<int> si;
typedef string str;
const int INF=1e+9;
const ll INFLL=1e+17;
const ll MOD=1e+9+7;
ll A,B,C,D;
ll gcd(ll a,ll b){
  if(b==0) return a;
  else return gcd(b,a%b);
}
ll lcm(ll a,ll b){
  return a*b/gcd(a,b);
}
int main(){
  cin>>A>>B>>C>>D;
  ll ca=(A-1)/C,cb=B/C,da=(A-1)/D,db=B/D;
  ll l=lcm(C,D);
  ll xa=(A-1)/l,xb=B/l;
  ll res=cb+db-xb-(ca+da-xa);
  prin(B-A+1-res);

  
  return 0;
}


Measured memory_bytes: 256
local mce, mfl, msq, mmi, mma = math.ceil, math.floor, math.sqrt, math.min, math.max
local n, k = io.read("*n", "*n")
local t = {}
local colored = {}
for i = 1, n do
  t[i] = {}
  colored[i] = false
end
for i = 1, n - 1 do
  local a, b = io.read("*n", "*n")
  table.insert(t[a], b)
  table.insert(t[b], a)
end

local tasks = {}
local tasknum = 0
local done = 0

local function addtask(idx)
  if(not colored[idx]) then
    colored[idx] = true
    tasknum = tasknum + 1
    tasks[tasknum] = idx
  end
end

addtask(1)
local mod = 1000000007
local ret = k
while(done < tasknum) do
  done = done + 1
  local taskidx = done
  local idx = tasks[taskidx]
  local cnt = 0
  for i = 1, #t[idx] do
    local dstidx = t[idx][i]
    if not colored[dstidx] then
      cnt = cnt + 1
      addtask(dstidx)
    end
  end
  local col = k - 2
  if idx == 1 then
    col = k - 1
  end
  for i = 1, cnt do
    ret = (ret * col) % mod
    col = col - 1
  end
end
print(ret)


Measured memory_bytes: 11516
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
const ld eps = 1e-9;

long long int gcd(long long int l, long long int r) {
	if (l > r)return gcd(r, l);
	else {
		if (r%l) {
			return gcd(l, r%l);

		}
		else {
			return l;
		}
	}
}

int main() {
	while (true) {
		long long int a,b,c;cin>>a>>b>>c;
		if(!a&&!b&&!c)break;
		long long int num=b*b-4*a*c;
		bool ok=true;
		if (num < 0) {
			ok=false;
		}
		else {
			long long int anum=sqrt(num);
			if (num != anum*anum) {
				ok=false;
			}
			else {
				vector<long long int>si{ -b + anum,-b - anum };
				long long int bo=2*a;

				vector<pair<long long int,long long int>>anss;
				for (int i = 0; i < 2; ++i) {
					if (si[i] == 0) {
						anss.emplace_back(1,0);
						continue;
						
					}
					long long int x=gcd(abs(si[i]),bo);
					anss.emplace_back(bo/x,-si[i]/x);
				}
				sort(anss.begin(),anss.end());
				reverse(anss.begin(),anss.end());
				cout<<anss[0].first<<" "<<anss[0].second<<" "<<
					anss[1].first<<" "<<anss[1].second<<endl;
			}
		}

		if (ok) {

		}
		else {

			cout << "Impossible" << endl;
		}
	}
	return 0;
}

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

typedef long long ll;

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

#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define ANS(n) cout << (n) << endl

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FORR(i,a,b) for(int i=(a);i>=(b);i--)

#define ALL(obj) (obj).begin(),(obj).end()

#define pii pair<int,int>

#define pb(a) push_back(a)
#define mp make_pair

ll mypow(ll n)
{
	ll retval = 1;
	FOR(i,0,n)retval *= 2;
	return retval;
}

int main()
{
	int n,p;
	cin >> n >> p;
	int oddCnt,evenCnt;
	oddCnt = evenCnt = 0;
	FOR(i,0,n){
		int a;
		cin >> a;
		if(a % 2 == 1){
			oddCnt++;
		}else{
			evenCnt++;
		}
	}
	if(oddCnt == 0){
		if(p == 0){
			ANS(mypow(n));
		}else{
			ANS(0);
		}
	}else{
		ANS(mypow(n-1));
	}
	return 0;
}


Measured memory_bytes: 256
///Bismillahir Rahmanir Rahim
#include<bits/stdc++.h>
#define        u64             uint64_t
#define        ll              long long
#define        endl            "\n"
#define        PI              acos(-1)
#define        fi              first
#define        si              second
#define        mkp             make_pair
#define        pb              push_back
#define        set0(arr)       memset(arr, 0, sizeof(arr))
#define        setinf(arr)     memset(arr, 126, sizeof(arr))
#define        all(x)          (x).begin(),(x).end()
#define        sz(v)           ((int)(v).size())
#define        IOS             ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
using          pll        =      pair<ll, ll> ;
using          vl         =      vector<ll> ;
using          vpll       =      vector<pll> ;
using          mll        =      map<ll, ll> ;
using          mcl        =      map<char, ll> ;
using          msl        =      map<string,ll> ;
using          sl         =      set<ll> ;
using          sc         =      set<char> ;
using          dl         =      deque<ll> ;
const int N = 1e6+5 ;

ll      mod = 1e9+7 ;
vl      adj[N] ;
vpll    adjc[N] ;
ll      vis[N] ;
ll      arr[N] ;



int main()
{
    IOS;
    ll a, b, c, d, n, m, p, x, y, z, i, j, k, f = 0, tc, cnt = 0, sum = 0, mul = 1, mi = 1e18, ma = -1e18;
    string   str ;
    char     ch ;
    double   db ;
    ll       l, r ;
    //code

        cin>>n;
        for(i=0;i<n;i++)
        {
            cin>>arr[i];
        }
        sum=0;
        ll ans=0;
       for(i=n-1;i>0;i--)
       {
             sum+=arr[i];
             x=((sum%mod)*(arr[i-1]%mod))%mod;
             ans=(ans+x)%mod;
       }
       cout<<ans<<endl;


    //code
    return 0;
}




Measured memory_bytes: 52084
def examA():
    N = I()
    X = [LI()for _ in range(N)]
    l = 0; r = inf
    for _ in range(100):
        now = (l+r)/2
        x_l = -inf; x_r = inf
        y_l = -inf; y_r = inf
        for x,y,c in X:
            move = now / c
            x_l = max(x_l,x-move)
            x_r = min(x_r,x+move)
            y_l = max(y_l,y-move)
            y_r = min(y_r,y+move)
        if x_l<x_r and y_l<y_r:
            r = now
        else:
            l = now
    ans = r
    print(ans)
    return

def examB():
    N = I()
    C = LI()
    C.sort()
    base = pow(2,2*N-1,mod)
    inv = pow(2,mod-2,mod)
    ans = 0
    for i in range(N):
        cur = C[i]*base*(1+(N-1-i)*inv)
        ans += cur
        ans %= mod
    print(ans)
    return

def examC():
    N = I()
    Ag,As,Ab = LI()
    Bg,Bs,Bb = LI()
    dp = [i for i in range(N+1)]
    for i in range(N):
        if dp[i+1]<dp[i]:
            dp[i+1] = dp[i]
        if i+Ag<=N and dp[i+Ag]<dp[i]+Bg:
            dp[i+Ag] = dp[i]+Bg
        if i+As<=N and dp[i+As]<dp[i]+Bs:
            dp[i+As] = dp[i]+Bs
        if i+Ab<=N and dp[i+Ab]<dp[i]+Bb:
            dp[i+Ab] = dp[i]+Bb
    ne_N = dp[-1]
    #print(dp)
    dp2 = [i for i in range(ne_N+1)]
    for i in range(ne_N):
        if dp2[i+1]<dp2[i]:
            dp2[i+1] = dp2[i]
        if i+Bg<=ne_N and dp2[i+Bg]<dp2[i]+Ag:
            dp2[i+Bg] = dp2[i]+Ag
        if i+Bs<=ne_N and dp2[i+Bs]<dp2[i]+As:
            dp2[i+Bs] = dp2[i]+As
        if i+Bb<=ne_N and dp2[i+Bb]<dp2[i]+Ab:
            dp2[i+Bb] = dp2[i]+Ab
    ans = dp2[-1]
    print(ans)
    return


import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-7)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examC()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Measured memory_bytes: 424504
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,a,b,ans;
int main()
{
	cin>>n>>a>>b;
	if(n<a+b && n>=a)
		cout<<a<<endl;
	else if(n<a)
		cout<<n<<endl;
	else if(!a && !b)
		cout<<0<<endl;
	else
	{
		ans+=n/(a+b)*a;
		n-=n/(a+b)*(a+b);
		if(n<a)
			ans+=n;
		else
			ans+=a;
		cout<<ans<<endl;
	}
	return 0;
}


Measured memory_bytes: 256
n, m = gets.split.map(&:to_i)
d = []
h = []
n.times{ d << gets.to_i }
m.times{ h << gets.to_i }
dp = Array.new(n){ Array.new(m, 1 << 31) }
table = Array.new(n){ Array.new(m) }
n.times do |i|
  m.times do |j|
    table[i][j] = d[i] * h[j]
  end
end
m.times{ |i| dp[0][i] = table[0][i] }
(1...n).each do |i|
  (i...m).each do |j|
    (j...m).each do |k|
      if dp[i][k] > dp[i-1][j-1] + table[i][k]
        dp[i][k] = dp[i-1][j-1] + table[i][k]
      end
    end
  end
end
p dp[n-1].min

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define  mx 10000
using namespace std;


int main()
{
    ll a,b,c,d,k,p,i,j,n;
    cin>>n;
    if(n>=1 && n<=999)cout<<"ABC"<<endl;
    else
      cout<<"ABD"<<endl;
    return 0;
}


Measured memory_bytes: 256