akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<string>
#include<functional>

int main(){
    constexpr long long mod = 1e9+7;
    std::function<long long(long long,long long)>
    mpow = [&](long long a,long long N){
        long long res=1;
        while(N){
            if(N&1) res=res*a%mod;
            a=a*a%mod;
            N>>=1;
        }
        return res;
    };
    std::string s;std::cin>>s;
    int k;std::cin>>k;
    int n=s.size();
    std::vector<long long> fac(n+1,1),ifac(n+1,1);
    for(int i=0;i<n;++i) fac[i+1]=fac[i]*(i+1)%mod;
    ifac[n]=mpow(fac[n],mod-2);
    for(int i=n;i>0;--i) ifac[i-1]=ifac[i]*i%mod;
    std::function<long long(int,int)>
    comb = [&](int N,int r){
        if(N<r||N<0||r<0) return 0LL;
        return fac[N]*ifac[N-r]%mod*ifac[r]%mod;
    };
    long long ans=0;
    int r=0;
    while(k&&n){
        ans+=mpow(9,k)*comb(n-1,k)%mod+(s[r]-'1')*mpow(9,k-1)*comb(n-1,k-1)%mod;
        ans%=mod;
        r++;
        while(r<s.size()&&s[r]=='0'){
            r++;
        }
        k--;n=s.size()-r;
    }
    if(k==0) ans++;
    std::cout<<ans%mod<<std::endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

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

  int a = scan.nextInt();
  int b = scan.nextInt();

  if (a < b) {
   System.out.println("a < b");
  } else if (a > b) {
   System.out.println("a > b");
  } else {
   System.out.println("a == b");
  }
 }
}

Measured memory_bytes: 17172
# -*- coding: utf-8 -*-

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

val_wei = [list(map(int, input().split())) for i in range(N)]

dp = [[0] * (W+1) for i in range(N+1)]

for n in range(N):
    for w in range(W+1):
        if w >= val_wei[n][1]:
            dp[n+1][w] = max(dp[n][w-val_wei[n][1]] + val_wei[n][0], dp[n][w])
        else:
            dp[n+1][w] = dp[n][w]

print(dp[N][W])


Measured memory_bytes: 41892
import java.util.Scanner;

public class Main {
	public static void main(String[] args)
	{
		Scanner stdIn = new Scanner(System.in);
		
		while(true)
		{
			int H = stdIn.nextInt();
			int W = stdIn.nextInt();
			
			if(H==0 && W==0)
			{
				break;
			}
			
			for(int i=0;i<H;i++)
			{
				for(int j=0;j<W;j++)
				{
					System.out.print('#');
				}
				System.out.println();
			}
			System.out.println();
		}
	}

}

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


int N;
void solve(){
    map<char,char>M;
    while(N--){
        char from,to;
        scanf(" %c %c",&from,&to);
        M[from]=to;
    }

    int K;
    scanf("%d",&K);
    while(K--){
        char c;
        scanf(" %c",&c);
        if(M.find(c)!=M.end())printf("%c",M[c]);
        else printf("%c",c);
    }
    puts("");
}

int main(){
    while(scanf("%d",&N),N)solve();
    return 0;
}

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

#define dump(...) cout<<"# "<<#__VA_ARGS__<<'='<<(__VA_ARGS__)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;

constexpr int INF=1e9;
constexpr int MOD=1e9+7;
constexpr double EPS=1e-9;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename Ostream,typename Container>
Ostream& operator<<(Ostream& os,const Container& c){
	os<<'[';
	for(auto i=begin(c);i!=end(c);++i)
		os<<(i==begin(c)?"":" ")<<*i;
	return os<<']';
}

bool GaussJordan(const vvd& _a,const vd& b,vd& x)
{
	int n=_a.size();
	vvd a(n,vd(n+1));
	rep(i,n){
		copy(all(_a[i]),begin(a[i]));
		a[i][n]=b[i];
	}
	
	rep(i,n){
		int p=i;
		repi(j,i+1,n) if(abs(a[p][i])<abs(a[j][i])) p=j;
		if(abs(a[p][i])<EPS) return false;
		swap(a[i],a[p]);
		peri(j,i,n+1) a[i][j]/=a[i][i];
		rep(j,n) if(j!=i) peri(k,i,n+1) a[j][k]-=a[j][i]*a[i][k];
	}
	
	rep(i,n) x[i]=a[i][n];
	return true;
}

struct Point{
	double x,y,z;
	Point(){}
	Point(double x,double y,double z):x(x),y(y),z(z){}
	Point& operator+=(Point p){x+=p.x,y+=p.y,z+=p.z; return *this;}
	Point& operator-=(Point p){x-=p.x,y-=p.y,z-=p.z; return *this;}
	Point& operator*=(double c){x*=c,y*=c,z*=c; return *this;}
	Point& operator/=(double c){x/=c,y/=c,z/=c; return *this;}
};
Point operator+(Point a,Point b){return a+=b;}
Point operator-(Point a,Point b){return a-=b;}
Point operator*(Point a,double c){return a*=c;}
Point operator*(double c,Point a){return a*=c;}
Point operator/(Point a,double c){return a/=c;}
ostream& operator<<(ostream& os,const Point& p){
	return os<<'('<<p.x<<','<<p.y<<','<<p.z<<')';
}

int main()
{
	Point me; cin>>me.x>>me.y>>me.z;
	Point enemy; cin>>enemy.x>>enemy.y>>enemy.z;
	vector<Point> barriers(3);
	for(auto& b:barriers) cin>>b.x>>b.y>>b.z;
	
	// ビーム: p+dt (位置ベクトルp, 方向ベクトルd, 媒介変数t)
	// バリア: q+eu+fv (位置ベクトルq, 方向ベクトルe,f, 媒介変数u,v)
	Point p=me,d=enemy-me;
	Point q=barriers[0],e=barriers[1]-barriers[0],f=barriers[2]-barriers[0];
	
	// p+dt=q+eu+fvをt,u,vについて解く(x=(t,u,v))
	vvd a={{d.x,-e.x,-f.x},
				 {d.y,-e.y,-f.y},
				 {d.z,-e.z,-f.z}};
	vd b={q.x-p.x,
				q.y-p.y,
				q.z-p.z};
	vd x(3);
	GaussJordan(a,b,x);
	double t=x[0],u=x[1],v=x[2];
	
	// バリアが自分と敵の間にある
	if(EPS<t && t<1+EPS){
		// バリアを含む平面上の点q+eu+fvを二次元平面上の点(u,v)に射影する．
		// すると，バリアを構成する3点はそれぞれ(0,0),(1,0),(0,1)に射影されているので，
		// (u,v)がこの三角形の内側にあるか判定すればよい．
		if(-EPS<u && -EPS<v && u+v<1+EPS)
			cout<<"MISS"<<endl;
		else
			cout<<"HIT"<<endl;
	}
	else
		cout<<"HIT"<<endl;
}

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

int main() {
	int r, c;
	cin >> r >> c;
	vector<vector<int> > V(r + 1, vector<int>(c + 1, 0));
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> V.at(i).at(j);
		}
	}
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			V[i][c] += V[i][j];
			V[r][j] += V[i][j];
			V[r][c] += V[i][j];
		}
	}
	for (int i = 0; i < r + 1; i++) {
		for (int j = 0; j < c + 1; j++) {
			cout << V[i][j];
			if (j != 0 && j % c == 0)
				cout << endl;
			else
				cout << " ";
		}
	}
}



Measured memory_bytes: 3180
A=input()
a,b=int(A.split()[0]),int(A.split()[1])
c,d="",""
for i in range(b):
  c+=str(a)
for i in range(a):
  d+=str(b)

if(int(c)<int(d)):
  nu=c
else:
  nu=d
for i in range(len(nu)):
  if(int(c[i])<int(d[i])):
    print(c)
    break
  elif(int(c[i])>int(d[i])):
    print(d)
    break
  elif(c==d):
    print(c)
    break

Measured memory_bytes: 3064
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cstring>
#include <queue>
#include <ctime>
#include <cassert>
#include <cstdio>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <bitset>

using namespace std;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define epr(...) fprintf(stderr, __VA_ARGS__)
#define db(x) cerr << #x << " = " << x << endl
#define db2(x, y) cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")\n"; 
#define db3(x, y, z) cerr << "(" << #x << ", " << #y << ", " << #z << ") = (" << x << ", " << y << ", " << z << ")\n"
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)a.size()

#define equal equalll
#define less lesss
const int N = -1;
const long long INF = 1e9 + 19;
typedef long long ll;

string s = "CODEFESTIVAL2016";
void read() {
    string t;
    cin >> t;
    int cnt = 0;
    for (int i = 0; i < (int)s.size(); i++)
        cnt += s[i] != t[i];
    cout << cnt << endl;

}

void solve() {

}

void stress() {

}

int main(){
#ifdef MY_DEBUG
    freopen("in", "r", stdin);
    //freopen("out", "w", stdout);
#endif
    if (1) {
        int k = 1;
        for (int tt = 0; tt < k; tt++) {
            read();
            solve();
        }
    }
    else {
        stress();
    }

    return 0;
}


Measured memory_bytes: 256
s = input()

if s[0] == s[1]:
    print(1, 2)
    exit()

ans = [-1, -1]
for i in range(2, len(s)):
    if s[i] == s[i - 2]:
        ans = [i - 1, i + 1]
        break
    elif s[i] == s[i - 1]:
        ans = [i, i + 1]
        break
print(*ans)

Measured memory_bytes: 9156
get_number(Number) :-
    get_string(String),
    number_string(Number, String).

get_number(A, B) :-
    get_number(A),
    get_number(B).

get_number(A, B, C) :-
    get_number(A, B),
    get_number(C).

get_string(String) :-
    current_input(Input),
    read_string(Input, ' \n\r\t', '', _, String).

get_chars(Xs) :-
    get_string(S),
    string_chars(S, Xs).

get_numbers(0, []).
get_numbers(N, [X|Xs]) :- 
    get_number(X), 
    N2 is N - 1, 
    get_numbers(N2, Xs).

put_numbers([]).
put_numbers([X|Xs]) :-
    writeln(X),
    put_numbers(Xs).

/* memo
    code(int)
    string_code(1, S, C), (C: code)
    char_code(X, Y) (X: char, Y: code)
    string_chars(S, S2) (S: string, S2: [char])
    to_lower(C, C2) (C: char? C2: code?)
    length(S, L),
    sub_string

    f(0, [], []).
    f(Z, [X|Xs], [Y|Ys]) :- X = Y, f(Z1, Xs, Ys), Z is Z1 + 1.
    f(Z, [_|Xs], [_|Ys]) :- f(Z, Xs, Ys).

    match: =, \=

    numeric: <,=<, >, >= (eval)
    lexicographically: @<. @=<, @>, @>=
    value?: =:=, =\= (eval)
    identical: ==, \==

    between(L,U,X): L <= X <= U
    nth0(I, Xs, Y), nth1(I, Xs, Y): (Xs,Y) -> I, (I, Xs) -> Y 

    sort(Key, Order, List, Sorted): Keyは通常0?, Orderは=なしが重複削除，=は重複保持
    \+ P(X) : not P(X)

    sum_list(Xs, Sum)

    orは!忘れに注意(末尾再帰なら直前)
*/

f([], _, S, S).
f([X|Xs], K, S, Z) :- g(X, K, S, S2), f(Xs, K, S2, Z).

g(X, K, S, S2) :- X >= K, !, S2 is S + 1.
g(_, _, S, S).

main :-
    get_number(N, K),
    get_numbers(N, Xs),
    f(Xs, K, 0, Z),
    writeln(Z).

    % statistics(inferences, IC), writeln(IC).


Measured memory_bytes: 12268
#include <iostream>
using namespace std;
int main(){
	int n,i;
	int w,x,l;
	int sum=0;
	string aim;
	while(1){
		int dice[3]={1,2,3};
		cin>>n;
		if(n==0){
			break;
		}
		for(i=0;i<n;i++){
			cin>>aim;
			if(aim=="North"){
				w=0;
				x=1;
			}
			else if(aim=="South"){
				w=1;
				x=0;
			}
			else if(aim=="West"){
				w=0;
				x=2;

			}
			else if(aim=="East"){
               w=2;
               x=0;
			}
			else if(aim=="Right"){
              w=1;
              x=2;
			}
			else if(aim=="Left"){
              w=2;
              x=1;
			}
			l=7-dice[w];
			dice[w]=dice[x];
			dice[x]=l;
			sum+=dice[0];
		}
		cout<<sum+1<<endl;
		sum=0;
	}
	return 0;
}

Measured memory_bytes: 1208
#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 <climits>
#include <cassert>
using namespace std;

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 int INF = INT_MAX/10;

bool ok(int M, int t) {
    return (t<=M);
}

int main() {
	int T;
    while(cin >> T, T) {
        vi ti(T);
        REP(i, T) {
            cin >> ti[i];
	    }

        int N;
        cin >> N;
        vvi data(N, vi(2));
        REP(i, N) {
            cin >> data[i][0] >> data[i][1];
	    }
        sort(ALL(data));
        int tmpN = N;
        FOR(i,1,N) {
            if(data[i][0] == data[i-1][0]) {
                data[i-1][1] = min(data[i-1][1], data[i][1]);
                data.erase(data.begin()+i);
                i--;
                N--;
			}
		}

        int dmax = data[N-1][0];
    
        vvi dp(dmax+1, vi(T+1, INF));
        dp[1][1] = 0;

        int dpos = 0;
        if(data[0][0] == 1) {
            dpos++;
	    }

        FOR(dd, 2, dmax+1) {
            FOR(tt, 1, T) {
                dp[dd][1] = min(dp[dd][1], dp[dd-1][tt]+1);
		    }
            dp[dd][1] = min(dp[dd][1], dp[dd-1][T]);

            FOR(tt, 2, T+1) {
                if(data[dpos][0] == dd) {
                    if(ok(data[dpos][1], ti[tt-1])) {
                        dp[dd][tt] = dp[dd-1][tt-1];
				    } else {
                        dp[dd][tt] = INF;
				    }
                } else {
                    dp[dd][tt] = dp[dd-1][tt-1];
			    }
		    }

            if(data[dpos][0] == dd) {
                dpos++;
			}

            if(dpos == N) {
                break;
		    }
	    }

        int ans = INF;
        REP(t, T+1) {
            ans = min(ans, dp[dmax][t]);
	    }
        cout << ans << endl;
    }
}

Measured memory_bytes: 1232
#include <bits/stdc++.h>
using namespace std;
#define ll long long  
#define pb push_back
#define mk make_pair
#define mod 998244353
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define all(x) x.begin(),x.end()
int main()
{
    ios::sync_with_stdio(0) ;
    cin.tie(0); 
    ll x,y,a,b,c;
    cin>>x>>y>>a>>b>>c;
    ll red[a];
    ll gre[b];
    ll crl[c];
    for(ll i=0;i<a;i++)
    cin>>red[i];
     for(ll i=0;i<b;i++)
    cin>>gre[i];
     for(ll i=0;i<c;i++)
    cin>>crl[i];
    sort(red,red+a,greater<ll>());
    sort(gre,gre+b,greater<ll>());
    sort(crl,crl+c,greater<ll>());
    ll ans=0;
    ll p1=x-1;ll p2=y-1;int flag=0;
    for(ll i=0;i<c;i++)
    {
        if(flag==0)
       { if(red[p1]>=gre[p2])
        {
            if(gre[p2]<=crl[i])
            {
                gre[p2]=crl[i];
                p2--;
                if(p2<0)
                flag+=2;
            }
            else
            {
                break;
            }
        }
        else
        {
            if(red[p1]<=crl[i])
            {
                red[p1]=crl[i];
                p1--;
                 if(p1<0)
                 flag+=1;
            }
            else
            {
                break;
            }
        }
       }
        else if(flag==1)
        {
             if(gre[p2]<=crl[i])
            {
                gre[p2]=crl[i];
                p2--;
                if(p2<0)
                flag+=2;
            }
            else
            {
                break;
            }
        }
        else if(flag==2)
        {
             if(red[p1]<=crl[i])
            {
                red[p1]=crl[i];
                p1--;
                 if(p1<0)
                 flag+=1;
            }
            else
            {
                break;
            }
        }
        else if(flag==3)
        {
            break;
        }
        
    }
    for(ll i=0;i<x;i++)
    ans+=red[i];
    for(ll i=0;i<y;i++)
    ans+=gre[i];
    cout<<ans;
    return 0;
}
//make all values ll



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

int main() {
    int n, h, w, res = 0;
    cin >> n >> h >> w;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        if (h <= a && w <= b) {
            res++;
        }
    }
    cout << res << endl;
}


Measured memory_bytes: 256
import java.math.BigInteger;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int p = sc.nextInt();
    int odd = 0;
    for (int i = 0; i < n; i++) {
      if (sc.nextInt() % 2 == 1) {
        odd++;
      }
    }
    int even = n - odd;
//    System.out.println("o: " + odd);
//    System.out.println("e: " + even);
    BigInteger res;
    BigInteger en = BigInteger.ZERO;
    BigInteger on = BigInteger.ZERO;
    for (int i = 0; i <= even; i++) {
      en = en.add(choose(BigInteger.valueOf(even), BigInteger.valueOf(i)));
    }
    if (p == 0) {
      for (int i = 0; i <= odd; i += 2) {
        on = on.add(choose(new BigInteger("" + odd), new BigInteger("" + i)));
      }
    } else {
      for (int i = 1; i <= odd; i += 2) {
        on = on.add(choose(new BigInteger("" + odd), new BigInteger("" + i)));
      }
    }
    res = on.multiply(en);
//    System.out.println("on: " + on);
//    System.out.println("en: " + en);
    System.out.println(res.toString());
  }

  public static BigInteger[][] memo = new BigInteger[101][101];

  static BigInteger choose(BigInteger n, BigInteger k) {

    if (n.intValue() == 0 && k.intValue() > 0) {
      return BigInteger.ZERO;
    } else if (k.intValue() == 0 && n.intValue() >= 0) {
      return BigInteger.ONE;
    } else if (memo[n.intValue()][k.intValue()] != null) {
      return memo[n.intValue()][k.intValue()];
    } else {
      memo[n.intValue()][k.intValue()] = choose(n.subtract(BigInteger.ONE), k.subtract(BigInteger.ONE)).add(choose(n.subtract(BigInteger.ONE), k));
    }
    return memo[n.intValue()][k.intValue()];

  }

  // mod combination
  static long modComb(long a, long b, long mod) {
    long res = 1;
    for (long i = a; i > a - b; i--) {
      res = (res * i) % mod;
    }
    for (long i = b; i > 1; i--) {
      res = (res * inv(i, mod)) % mod;
    }
    return res;
  }

  static long inv(long a, long mod) {
    return powMod(a, mod - 2, mod);
  }

  // a ^ b (mod p)
  static long powMod(long a, long b, long p) {
    if (b == 0) {
      return 1;
    }
    if (b % 2 == 0) {
      long d = powMod(a, b / 2, p);
      return d * d % p;
    }
    return a * powMod(a, b - 1, p) % p;
  }
  static long N;

  static BigInteger factorial(int n) {
    if (n < 2) {
      return BigInteger.ONE;
    }
    BigInteger p = BigInteger.ONE, r = BigInteger.ONE;
    N = 1;
    int log2n = 31 - Integer.numberOfLeadingZeros(n);
    int h = 0, shift = 0, high = 1;
    while (h != n) {
      shift += h;
      h = n >>> log2n--;
      int len = high;
      high = (h & 1) == 1 ? h : h - 1;
      len = (high - len) >> 1;
      if (len > 0) {
        r = r.multiply((p = p.multiply(bp(len))));
      }
    }
    return r.shiftLeft(shift);
  }

  static BigInteger bp(int n) {
    int m = n >> 1;
    if (m == 0) {
      return BigInteger.valueOf(N += 2);
    } else if (n == 2) {
      return BigInteger.valueOf(N += 2).multiply(BigInteger.valueOf(N += 2));
    }
    return bp(n - m).multiply(bp(m));
  }
}

Measured memory_bytes: 21716
'use strict';
const main = input => {
  const n = parseInt(input[0].split(' ')[0], 10);
  const k = parseInt(input[0].split(' ')[1], 10);
  const q = parseInt(input[0].split(' ')[2], 10);
  let a = input.map(val => parseInt(val, 10));
  a.shift();
  a.pop();
  let arr = new Array(n);
  arr.fill(k-q);
  a.map(val => arr[val-1]++)
  arr.map(val => console.log(val>0?'Yes':'No'));
}
main(require("fs").readFileSync("/dev/stdin", "utf8").split('\n'));

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

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

  if(k < a){
    a -= k;
  }

  else if(k > a + b){
    a = 0;
    b = 0;
  }

  else{
    b = a + b - k;
    a = 0;
  }
  
  cout << a << " " << b << endl;

}


Measured memory_bytes: 256
/*
 * atcoder/abc112/d.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>
#include <map>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> ostream & operator << (ostream & out, vector<T> const & v) {
  for (auto &&a: v) out << a << " "; out << endl; return out;
}
template <class T> void dump(T &a) { cout << a << endl; }
template <class T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template <class T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }

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

int N; ll M;
void solve() {
  cin >> N >> M;
  vector<ll> D;
  for (ll i=1; i*i<=M; i++) {
    if (M%i==0) {
      D.push_back(i);
      if (i*i != M) D.push_back(M / i);
    }
  }

  ll max_ = 0;
  for (auto&& d: D) {
    if (N * d <= M) chmax(max_, d);
  }
  cout << max_ << endl;
}
int main() {
  // cout.precision(15); cout << fixed;

  solve();

  return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i,n) for(ll i=0;i<n;i++)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define fi first
#define se second
#define endl "\n"

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){int len=d.size();rep(i,len){s<<d[i];if(i<len-1) s<<" ";}return s;}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){int len=d.size();rep(i,len){s<<d[i]<<endl;}return s;}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T> ostream& operator<<(ostream& s,const multiset<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){s<<"{"<<endl;for(auto itr=m.begin();itr!=m.end();++itr){s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;}s<<"}"<<endl;return s;}

const ll mod=1e9+7;
const ll inf=1e17;
const int INF=1e9;
const double EPS=1e-10;
const double PI=acos(-1);

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    string s;
    cin>>s;
    if(s=="Sunny") cout<<"Cloudy"<<endl;
    else if(s=="Cloudy") cout<<"Rainy"<<endl;
    else cout<<"Sunny"<<endl;
}

Measured memory_bytes: 256
using System;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var s = Console.ReadLine();

            long r_num = s.Length - s.Replace("R", "").Length;
            long g_num = s.Length - s.Replace("G", "").Length;
            long b_num = s.Length - s.Replace("B", "").Length;

            long sum = r_num * g_num * b_num;

            for (var ri = 2; ri < n; ri++)
            {
                var a = s[ri];

                for (var ce = (ri + 1) >> 1; ce < ri; ce++)
                {
                    var b = s[ce];
                    var c = s[ce - (ri - ce)];
                    if (a != b && b != c && c != a) sum--;
                }
            }

            Console.WriteLine(sum);
        }
    }
}

Measured memory_bytes: 18520
import math
from functools import reduce
 
def gcd(ns):
    return reduce(math.gcd, ns)
 
N, X = map(int, input().split())
L = list(map(int, input().split()))
 
diff = [abs(x - X) for x in L]
 
if len(diff) == 1:
    print(diff[0])
else:
    print(gcd(diff))

Measured memory_bytes: 20612
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Stack;


public class Main {

	/**
	 * @param args
	 */
	
	
	public static void main(String[] args) {
		
		
		
		Scanner sc= new Scanner(System.in);
	
	
		
		int n=sc.nextInt();
		
		int cnt=0;
			
		for(int i=0;i<n;i++)
		{	
		int s=sc.nextInt();
		if(s%2!=0)
			cnt++;
		}
		
		
	if(cnt%2!=0)	
	{
	System.out.println("NO");	
	}
	else 
		System.out.println("YES");
	}
	
}



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

#define all(a) a.begin(), a.end()
#define allr(a) a.rbegin(), a.rend()
#define rev(v) reverse(v.begin(), v.end());
#define io() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); srand(time(NULL));

using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

signed main(){
    io();
    int n; cin >> n;
    string s; cin >> s;
    int cnt = 0;
    for(int i = 0; i < n - 2; ++i)
        cnt += (s[i] == 'A' && s[i + 1] == 'B' && s[i + 2] == 'C');
    cout << cnt << '\n';
    return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;

void Main() {
  ll n,h,w;
  cin >> n >> h >> w;
  pr((n-h+1)*(n-w+1));
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 256
#include<cstdio>
int main() {
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	if (a==b) printf("%d\n",c);
	if (b==c) printf("%d\n",a);
	if (a==c) printf("%d\n",b);
	return 0;
}

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

// Template START
#define endl "\n"
#define async ios_base::sync_with_stdio(false); cin.tie(NULL);
#define int long long int
#define all(y) y.begin(), y.end()
#define present( x, y ) (x.find( y ) != x.end())
const int mod = (int)1e9 + 7 ;
#define vv(T) vector<vector<T>>
#define vvv(T) vector<vector<vector<T>>>
template<class T>
auto matrix( int r, int c, T v ){
    return vector<vector<T>>( r, vector<T>( c, v ) ) ;
}
template<class T>
auto matrix( int o1, int o2, int o3, T v ){ 
    return vector<vector<vector<T>>>( o1, vector<vector<T>>( o2, vector<T>( o3, v ) ) ) ;
}
// Template END

int power( int x, int n ){
    if( n == 0 ) return 1 ;
    else if( n & 1 ) return ( x * power( (x*x) % mod, n / 2 ) ) % mod ;
    return power( (x*x) % mod, n / 2 ) % mod ;
}
void absorb( int &x, int n ){
    x = ( x * n ) % mod ;
    if( x < 0 ) x += mod ;
}



signed main(){
    int a, b, c, d ;
    cin >> a >> b >> c >> d ;
    int x1 = a * c, x2 = a * d, x3 = b * c, x4 = b * d ;
    cout << max( {x1, x2, x3, x4} ) ;
    return 0 ;   
}


Measured memory_bytes: 3604
S = input()

T_count = 0
S_count = 0
ans = 0
for i in range(len(S)):
    if S[i] == "S":
        S_count += 1
    else:
        if S_count > T_count:
            T_count += 1
        else:
            ans += 2
            
print(ans)

Measured memory_bytes: 9108
'use strict'

function main(s) {

  s = s.split('\n');
  const N = Number(s[0]);
  const blue = s.slice(1, 1 + N);
  const red  = s.slice(N + 2, -1);
  const points = [];

  blue.forEach((x, i, self) => {
    if(self.indexOf(x) === i) {
      points.push({key: x, count: 1});
    } else {
      points.forEach(y => {
        if (x === y.key) y.count += 1
      });
    }
  });

  red.forEach((x) => {
    points.forEach(y => {
      if (x === y.key) y.count -= 1
    });
  });

  points.sort((a, b) => b.count - a.count);

  const ans = (points[0].count >= 0) ? points[0].count : 0;
  console.log(ans);
}

main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7500
#include <iostream>

using namespace std;

int main()
{
    long long p25,p50,p1,p2,n,profit,minlit2;
    cin>>p25>>p50>>p1>>p2>>n;
    long long minlit=400000001;
    if(minlit>p25*4)
    {
        minlit=p25*4;
        profit=p25;
    }
    if(minlit>p50*2)
    {
        minlit=p50*2;
        profit=p50;
    }
    if(minlit>p1)
    {
        minlit=p1;
        profit=p1;
    }
    if(n==1)
    cout<<minlit;
    else
    {
        if(minlit*2>p2)
        {
            cout<<(n/2)*p2+minlit*(n%2);
        }
        else
        cout<<minlit*n;
    }
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>

#define pb push_back
#define mp make_pair

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef unsigned long long ull;
typedef long long ll;

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

  vi B;
  for (int i = 0; i < n; ++i) {
    int k;
    cin >> k;

    B.pb(k);
  }

  int sum = 0;

  sum += B.at(0);
  for (int i = 0; i < n-1; ++i) {
    sum += min(B.at(i), B.at(i+1));
  }
  sum += B.at(n-1);

  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 256
// ░░░░░░░░( •̪●)░░░░░░░░░░░░░░░░░░░░░░░░
// ░░░░░░███████ ]▄▄▄▄▄▄▄▄▃░░░▃░░░░ ▃░
// ▂▄▅█████████▅▄▃▂░░░░░░░░░░░░░░░░░
// [███████████████████].░░░░░░░░░░░░░░
// ◥⊙▲⊙▲⊙▲⊙▲⊙▲⊙▲⊙◤...░░░░░░░░░░░░

//PointBlank's code (⌐■_■)
 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
#define repp(i, a, b) for(ll i = a; i <= b; i++)
#define rep(i, a, b) for(ll i = a; i < b; i++)
#define rrep(i, b, a) for(ll i = b; i >= a; i--)
#define pb emplace_back
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define mem(a, b) memset(a, b, sizeof(a));
#define mem0(a) memset(a, 0, sizeof(a));
#define quickio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define in_edges(m) repp(i, 1, m){ll a, b; cin >> a >> b; v[a].pb(b), v[b].pb(a);}
#define debug(this) cerr<<"> "<<#this<<" : "<<this<<"\n"
#define endl "\n"
ll power(ll x, ll y); 

const ll MOD = 1000000007;
ll dp[102][100005], w, v;

int main() //PointBlank's code ¯\_(ツ)_/¯
{
    quickio
    ll n, W;
    cin >> n >> W;
    ll w[n], v[n];
    rep(i, 0, n) cin >> w[i] >> v[i];

    repp(i, 1, n)
        repp(ww, 1, W)
            if(w[i - 1] <= ww) dp[i][ww] = max(v[i - 1] + dp[i - 1][ww - w[i - 1]], dp[i - 1][ww]);
            else dp[i][ww] = dp[i - 1][ww];

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

ll power(ll x, ll y)
{ 
    ll res = 1; x %= MOD;
    while(y > 0){if(y & 1) res = (res*x) % MOD; y = y>>1, x = (x*x) % MOD;} 
    return res; 
}

Measured memory_bytes: 78336
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long int ll;
typedef vector<pair<ll,ll> > Q;
typedef pair<int,int> P;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
const ll inf=1e9+7;
ll gcd(ll a, ll b) { return (b ? gcd(b, a % b) : a); }
ll lcm(ll a, ll b) { return a / (gcd(a, b)) * b; }

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

  int ans=max(a+b,max(a-b,a*b));
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
ll a,b,c,d;
ll n;
int main(void){
    cin>>a>>b>>c>>d>>n;
    a=a*8; b=b*4; c=c*2;
    ll t=min({a,b,c,d});
    if(t==d){
        if(n%2==0){
            cout<<t*n/2<<endl;
        }else{
            ll u=min({a,b,c});
            cout<<t*(n-1)/2+u/2<<endl;
        }
    }else{
        cout<<t/2*n<<endl;
    }

}



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

const int INF = 100100100;
const int MOD = (int)1e9 + 7;
typedef long long ll;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)


int main() {
  int n,d;
  cin >> n >> d;
  d = 2*d + 1;
  int ans = n/d;
  if (n%d!=0) ans++;
  cout << ans << endl;
}

Measured memory_bytes: 3616
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;

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


int n;
double dat[20];

typedef pair<double,double> mp;


const double eps = 1e-4;



double ragra(vector<mp>& nv,double in){
	double res = 0;
	rep(i,nv.size()){
		double nb = nv[i].first;
		rep(j,nv.size()){
			if(i==j)continue;
			double p = nv[j].second;
			nb *= ((in-p)/(nv[i].second-p));
		}
		res += nb;
	}

	return res;
}



int main(void){

	while(1){
		scanf("%d",&n);
		if(n==0)break;
		rep(i,n+3)scanf("%lf",&dat[i]);
	

		rep(i,n+3){
			for(int j=i+1;j<n+3;j++){
				vector<mp> nv;
				rep(k,n+3){
					if(i==k || j==k)continue;
					nv.push_back(mp(dat[k],k));
				}
				if(abs(dat[i]-ragra(nv,i))>eps){
					if(abs(dat[j]-ragra(nv,j))>eps)continue;
					else{
						printf("%d\n",i);
						goto nextn;
					}
				}
				else{
					printf("%d\n",j);
					goto nextn;
				}
			}
		}
nextn:;
	}


	return 0;
}

Measured memory_bytes: 1076
using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
class Program
{
	static void Main()
	{
    
    string[] input = Console.ReadLine().Split(' ');
		long a = long.Parse(input[0]);
		long b = long.Parse(input[1]);

    Console.WriteLine(Convert.ToString(a&b, 2).PadLeft(32, '0'));

    Console.WriteLine(Convert.ToString(a|b, 2).PadLeft(32, '0'));

    Console.WriteLine(Convert.ToString(a^b, 2).PadLeft(32, '0'));
	}
}


Measured memory_bytes: 17976
N = int(input())
S = input()
if N % 2 != 0:
    print("No")
else:
    yes = True
    for i in range(N // 2):
        if S[i] != S[i + N // 2]:
            yes = False
            break
    if yes:
        print("Yes")
    else:
        print("No")

Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
 
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ld;
 
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;
 
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int MAXN = 1e6 + 3;
 
#define _  %  MOD
#define __ %= MOD
 
#define      each(it,s)        for(auto it = s.begin(); it != s.end(); ++it)
#define      sortA(v)          sort(v.begin(), v.end())
#define      sortD(v)          sort(v.begin(), v.end(), greater<auto>())
#define      fill(a)           memset(a, 0, sizeof (a))
 
#define      swap(a,b)        {a=a+b;b=a-b;a=a-b;}
#define      rep(i, n)         for(ll i = 0; i < (n); ++i)
#define      repA(i, a, n)     for(ll i = a; i <= (n); ++i)
#define      repD(i, a, n)     for(ll i = a; i >= (n); --i)
#define watch(x) cout << (#x) << " is " << (x) <<endl
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
#define fbo find_by_order
#define ook order_of_key
 
ll gcd(ll a,ll b){if(b==0) return a; else return gcd(b,a%b);}
ll power(ll x,ll y){ll res=1; while(y>0){if(y&1) res=(res*x)%INF;y=y>>1;x=(x*x)%INF;}return res%INF;} // modular exponent
const int maxn=1e6+1;
ll inv(ll x)
{
	return power(x,INF-2);
}
ll fact[maxn],invfact[maxn];
void work()
{
	fact[0]=1;
	invfact[0]=1;
	for(ll i=1;i<maxn;i++)
	{
		fact[i]=(i*fact[i-1])%INF;
		invfact[i]=inv(fact[i]);
	}
}
ll C(ll n,ll r)
{
	if(r>n) return 0;
	ll ans=1ll;
	ans=fact[n];
	ans*=invfact[r];
	ans%=INF;
	ans*=invfact[n-r];
	ans%=INF;
	return ans;
}
int main()
{
    ios_base::sync_with_stdio(false); // don't use printf and scanf
    cin.tie(NULL); // cout<<fixed<<setprecision
	ll x,y;
	cin>>x>>y;
	if((x+y)%3==0 && 2*x>=y && 2*y>=x)
	{
		work();
		ll i=2*x-y;
		i/=3;
		ll j=2*y-x;
		j/=3;
		ll ans=C(i+j,i);
		cout<<ans<<'\n';
	}
	else cout<<0<<'\n';
	return 0;
}
// JUST ASK YOURSELF DID YOU GIVE YOUR BEST ? ISSE ZYADA
// KUCH KAR BHI NAHI SAKTE !! ENJOY AND GIVE YOUR BEST!!



Measured memory_bytes: 19288
#include<stdio.h>

int gcd(int,int);

int main(void){
  int x,y;
  int i;

  scanf(" %d %d",&x,&y);

  printf("%d\n",gcd(x,y));
  
  return 0;
}

int gcd(int x, int y){
  
  if(x < y){
    if(y%x == 0) return x;
    else return gcd(x,y%x);
  }
  else if(y < x){
    if(x%y == 0) return y;
    else return gcd(y,x%y);
  }
  else return x;
  
}



Measured memory_bytes: 2128
#include<iostream>
#include<string>
#include<algorithm>
#include<bits/stdc++.h>
#include<vector>
 
using namespace std;
int MOD=1000000007;

int main(){
	int N,M; cin >> N >> M;
	long long ans=0;
	vector<int> X(M);
	vector<long long> go;
	if(N>=M){
		cout << 0 << endl;
		return 0;
	}
	for(int i=0; i<M; i++)
	cin >> X[i];
	sort(X.begin(),X.end());
	for(int i=0; i<M-1; i++){
		go.push_back(X[i+1]-X[i]);
	}sort(go.begin(),go.end());
	for(int i=0; i<go.size()-N+1; i++) ans+=go[i];
	cout << ans << endl;
	}

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

#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define MIN(a) *min_element(all(a))
#define MAX(a) *max_element(all(a))
#define SUM(a) accumulate(all(a), 0LL)
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define RREP(i, n) for(int (i)=(n)-1; (i)>=0; (i)--)
#define FOR(i, m, n) for(int (i)=(m); (i)<(n); i++)
#define FORR(i, m, n) for(int (i)=(n)-1; (i)>=(m); i--)
#define debug(x) cerr << #x << " = " << x << endl
//#define int long long

typedef long long ll;
//ll const MOD = 998244353;
ll const MOD = 1e9+7;
int const inf = 1e9;
ll const INF = 1e18;

inline void ios_(){cin.tie(0); ios::sync_with_stdio(false);}
template<typename T> int size(const T& a){return (int)a.size();}
template<typename T> T Div(T a, T b){return (a + b - 1) / b;}
template<typename T> bool chmin(T& a, const T& b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, const T& b){if(a < b){a = b; return true;} return false;}



signed main(){
    int n;
    cin >> n;
    vector<ll> v(n);
    for(auto& i : v) cin >> i;
    bool ans = true;
    v[0]--;
    REP(i, n-1){
        if(v[i] < v[i+1]){
            v[i+1]--;
        }else if(v[i] > v[i+1]){
            ans = false;
            break;
        }
    }
    cout << (ans ? "Yes" : "No") << endl;
    return 0;
}


Measured memory_bytes: 1024
//#pragma GCC optimize "trapv"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand rng
#define fios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define M_PI 3.14159265358979323846
typedef long long ll;



int main() {
	//fios;
	string t;
	cin >> t;
	for(char ch: t) {
		if(ch == '?') cout << 'D';
		else cout << ch;
	}
	cout << endl;

}

Measured memory_bytes: 3756
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1 for _ in range(n+1)]

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    
def main():
    N, M = [int(_) for _ in input().split()]
    bridge = [tuple(map(int, input().split())) for _ in range(M)]
    #print(bridge[M-1][0])
    #print(bridge)
    last = []
    last.append(int(N * (N-1) * 0.5))
    #last = last
    ins = UnionFind(N)
    last_temp = 0
    #print(last)
    ##print(ins.par)
    for i in range(M-1):
        #print(ins.par)
        if ins.same_check(bridge[M-1-i][0],bridge[M-1-i][1]):
            last.append(last[-1])
            #ins.union(bridge[M-1-i][0],bridge[M-1-i][1])
        else:
            last_temp = last[-1] - (ins.size[ins.find(bridge[M-1-i][0])]) * (ins.size[ins.find(bridge[M-1-i][1])])
            #print(ins.size,i)
            last.append(last_temp)
            ins.union(bridge[M-1-i][0],bridge[M-1-i][1])
    
    [print(last[M-i-1]) for i in range(M)]
    exit()
    
main()

Measured memory_bytes: 24932
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())
d, x = map(int, input().split())

a = list(int(input()) for i in range(n))

ans = x
for i in range(n):
    ans += 1
    ans += (d-1)//a[i]
print(ans)


Measured memory_bytes: 3060
#pragma GCC optimize ("O2")
#pragma GCC target ("avx2")
//#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int CM = 1 << 17, CL = 18;
char C[CM + CL], * ci = C + CL, * owa = C + CM, c;

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


	fread(ci, 1, CM, stdin);
	int N = 0;
	while ((c = *ci++) >= '0') N = N * 10 + c - '0';

	ll p[20][20] = {};
	rep(i, N) {
		if (ci - owa > 0) {
			memcpy(C, owa, CL);
			ci -= CM;
			fread(C + CL, 1, CM, stdin);
		}

		ll kari = 0;
		while ((c = *ci++) >= '0') kari = kari * 10 + c - '0';
		int d = 9;
		if (*(ci - 1) == '.') {
			while ((c = *ci++) >= '0') {
				kari = kari * 10 + c - '0';
				d--;
			}
		}

		int a = __builtin_ctzll(kari) + d;
		if (a > 18) a = 18;
		int b = d;
		while (kari % 5 == 0) {
			b++;
			kari /= 5;
		}
		p[a][b]++;
	}
	ll kotae = 0;
	rep(a, 19) rep(b, 19) if (p[a][b]) {
		ll P = p[a][b];
		for (int x = 18 - a; x <= 18; x++) {
			for (int y = 18 - b; y <= 18; y++) {
				kotae += P * p[x][y];
			}
		}
	}
	for (int a = 9; a <= 18; a++) {
		for (int b = 9; b <= 18; b++) {
			kotae -= p[a][b];
		}
	}

	printf("%lld\n", kotae / 2);

	Would you please return 0;
}

Measured memory_bytes: 3224
#include <cstdio>
#include <algorithm>

using namespace std;

long long dp[2][2001][2];

int main() {
    int n, k, m = 924844033, c = 0, i, j, l, r;
    
    scanf("%d %d", &n, &k);
    
    dp[0][0][0] = 1;
    
    for (i = 0; i < k * 2; i++) {
        if (i >= k) {
            for (j = 0; j <= n; j++) {
                if (j + c > 0) {
                    dp[1][j][1] += (dp[0][j][0] + dp[0][j][1]) * (j + c) % m;
                    if (dp[1][j][1] >= m) dp[1][j][1] -= m;
                }
                
                dp[1][j + 1][0] += (dp[0][j][0] + dp[0][j][1]) % m;
                if (dp[1][j + 1][0] >= m) dp[1][j + 1][0] -= m;
            }
            
            c--;
        } else {
            for (j = 0; j <= n; j++) {
                dp[1][j][1] = dp[0][j][0] + dp[0][j][1];
                if (dp[1][j][1] >= m) dp[1][j][1] -= m;
            }
        }
        
        for (j = 0; j <= n; j++) {
            for (l = 0; l < 2; l++) {
                dp[0][j][l] = dp[1][j][l];
                dp[1][j][l] = 0;
            }
        }
        
        for (j = i; j < n; j += k * 2) {
            if (j + k >= n) {
                for (l = 0; l <= n; l++) {
                    for (r = 0; r < 2; r++) {
                        if (dp[0][l][r] == 0) continue;
                        
                        dp[1][l][r] += dp[0][l][r];
                        if (dp[1][l][r] >= m) dp[1][l][r] -= m;
                        
                        if (l > 0) {
                            dp[1][l - 1][0] += dp[0][l][r] * (l - (1 - r)) % m;
                            if (dp[1][l - 1][0] >= m) dp[1][l - 1][0] -= m;
                        }
                    }
                }
                
                c++;
            } else {
                for (l = 0; l <= n; l++) {
                    for (r = 0; r < 2; r++) {
                        if (dp[0][l][r] == 0) continue;
                        
                        dp[1][l + 1][0] += dp[0][l][r];
                        if (dp[1][l + 1][0] >= m) dp[1][l + 1][0] -= m;
                        
                        if (l > 0) {
                            dp[1][l][0] += dp[0][l][r] * (l - (1 - r)) % m;
                            if (dp[1][l][0] >= m) dp[1][l][0] -= m;
                        }
                        
                        if (l + c > 0) {
                            dp[1][l][1] += dp[0][l][r] * (l + c) % m;
                            if (dp[1][l][1] >= m) dp[1][l][1] -= m;
                        }
                        
                        if (l > 0 && l + c > 0) {
                            dp[1][l - 1][1] += dp[0][l][r] * (l - (1 - r)) % m * (l + c) % m;
                            if (dp[1][l - 1][1] >= m) dp[1][l - 1][1] -= m;
                        }
                    }
                }
            }
            
            for (l = 0; l <= n; l++) {
                for (r = 0; r < 2; r++) {
                    dp[0][l][r] = dp[1][l][r];
                    dp[1][l][r] = 0;
                }
            }
        }
    }
    
    printf("%lld\n", (dp[0][0][0] + dp[0][0][1]) % m);
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> iint;
typedef pair<ll,ll> llll;
#define ALL(x) (x).begin(),(x).end()
const ll zero = 0;
const ll INF = 3000000000000000000; //10^18
const int inINF = 1000000000; //10^9
const ll MOD = 1000000007; //10^9+7
const ll MOD2 = 998244353;

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

    if(N>=M/2){
        printf("%lld\n", M/2);
    }
    else{
        printf("%lld\n", (2*N+M)/4);
    }

}


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

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

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

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

#define IN(l, r, x) ((l) <= (x) && (x) < (r))

class UnionFind
{
public:
    vs32 p;
    UnionFind(int size)
    : p(vs32(size, -1))
    {}

    void unite(int x, int y)
    {
        int rx = find(x);
        int ry = find(y);
        if (rx == ry) return;
        if (p[rx] > p[ry]) swap(rx, ry);
        p[rx] += p[ry];
        p[ry] = rx;
    }

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

    int find(int x)
    {
        if (p[x] < 0) return x;
        else return p[x] = find(p[x]);
    }
};

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

    int n, m;
    cin >> n >> m;
    UnionFind uf(n);

    rep (i, m)
    {
        int a, b;
        cin >> a >> b;
        --a, --b;
        uf.unite(a, b);
    }

    int ans = 0;
    rep (i, n)
    {
        int r = uf.find(i);
        ans = max(ans, -uf.p[r]);
    }
    cout << ans << "\n";
    return 0;
}



Measured memory_bytes: 3996
#include <iostream>
#include <cmath>
using namespace std;
 
int N, K, cost[100005], memo[500005];
 
int minCost(int v) {
  if (memo[v] != -1) return memo[v];
  if (v <= 0) return 0;
  
  int currMin = 1000000000;
  for (int i = 1; i <= K; i++) {
    if (v - i >= 0) {
      currMin = min(currMin, minCost(v - i) + abs(cost[v] - cost[v - i]));
    }
  }
  
  memo[v] = currMin;
  
  return currMin;
}
 
int main() {
  cin >> N >> K;
  for (int i = 0; i < N; i++) cin >> cost[i];
  
  for (int i = 0; i < 500005; i++) memo[i] = -1;
  
  cout << minCost(N - 1) << "\n";
  return 0;
}


Measured memory_bytes: 7296
N,M = map(int,input().split())
info = [list(map(int,input().split())) for _ in range(N)]
info.sort()
money = 0
need = M
for a,b in info:
    if need <= b:
        money += a*need
        need = 0
        break
    else:
        money += a*b
        need -= b
print(money)

Measured memory_bytes: 27760