akhauriyash/Code-Regression huggingface dataset:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    x,y=map(int, readline().rstrip().split())

    for a in range(101):
        for b in range(101):
            if ((a+b)==x) and ((a*2 + b*4)==y):
                print("Yes")
                return
    print("No")
    #arr=list(map(int, readline().rstrip().split()))
    #n=int(readline())
    #ss=readline().rstrip()
    #yn(1)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Measured memory_bytes: 16212
'''二分探索'''
#import bisect
'''デック'''
#from collections import deque
'''順列,組み合わせ,累積和,直積・forネスト'''
#from itertools import permutations, combinations, accumulate, product
'''小数点以下切り捨て,小数点以下切り上げ,平方根,階乗,最大公約数'''
#from math import floor, ceil, sqrt, factorial, gcd
'''input 文字列は最後に\nを含む'''
#import sys
#input = sys.stdin.readline


def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))

    ans = n-sum(a)
    if ans < 0:
        ans = -1
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 68120
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <fstream>
#include <complex>
#include <stack>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> P;
static const double EPS = 1e-5;

#define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
vector<int> manip(vector<int> seq){
  vector<int> ret;
  int put;
  for(int i=0; i<seq.size(); i++){
    for(int j=i; j<seq.size(); j++){
      if(j==seq.size()-1&&seq[j]==seq[i]){
        put = j-i+1;
        ret.push_back(put%10);
        put/=10;
        while(put){
          vector<int>::iterator it = ret.end();
          it--;
          ret.insert(it,put%10);
          put/=10;
        }
        ret.push_back(seq[i]);
        i = j;
        break;
      }
      if(seq[j]!=seq[i]){
        put = j-i;
        ret.push_back(put%10);
        put/=10;
        while(put){
          vector<int>::iterator it = ret.end();
          it--;
          ret.insert(it,put%10);
          put/=10;
        }
        ret.push_back(seq[i]);
        i = j-1;
        break;
      }
    }
  }
  return ret;
}  

int main(void){
  int n;
  while(cin>>n){
    if(n==0) break;
    string line;
    cin>>line;
    vector<int> seq;
    REP(i,line.size()){
      seq.push_back(line[i]-'0');
    }
    REP(i,n){
      seq = manip(seq);  
    }
    REP(i,seq.size()){
      cout<<seq[i];
    }
    cout<<endl;
  }
  return 0;
}

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

struct Benri { Benri() { std::cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(12);}} benri;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vll = vector<long long>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using ull = unsigned long long;

template <typename T> using PQ = priority_queue<T>;
template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define mp make_pair
#define F first
#define S second

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

constexpr long long MOD = 1000000007;
//constexpr long long MOD = 998244353;
//constexpr int INF = 1001001001;
constexpr ll INF = 1001001001001001001ll;
constexpr double EPS = 1e-10;
using number = long long;

vi prime;
vector<bool> is_prime;

void sieve(number n) {
    is_prime.assign(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (number i = 2; i < n; ++i) {
        if (is_prime[i]) {
            prime.pb(i);
            for (number j = i + i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
}

int main() {
    int n; 
    sieve(1010101);
    while(cin >> n){
        int t = upper_bound(all(prime),n) - prime.begin();
        cout << t << endl;
    }
}


Measured memory_bytes: 3428
#include<bits/stdc++.h>
using namespace std;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n; cin >> n;
    int a[n];

    for(int i = 0; i < n; ++i) {
        cin >> a[i];
        a[i] -= i + 1;
    }
    sort(a, a + n);

    long long mid = (n%2 ? a[n/2] : (a[n/2] + a[n/2]) / 2);

    long long sum = 0;
    for(int i = 0; i < n; ++i) sum += abs(a[i] - mid);
    cout << sum;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

#define int long long

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    
    int a;
    cin >> a;
    vector<int> v(a), s(a);
    
    for(int i = 0;i < a; ++i)
    {
        cin >> v[i];
        s[i] = v[i];
    }
    
    sort(s.begin(), s.end());
 
    int r = s[a / 2], l = s[ (a / 2) - 1];
    
    double mid = ((double)r + l) / 2;
    
    for(int i = 0;i < a; ++i)
    {
        if(v[i] < mid)
        {
            cout << r << "\n";
        }
        else
        {
            cout << l << "\n";
        }
    }
    
    return 0;
}



Measured memory_bytes: 5376
#include <algorithm>
#include <bitset>
#include <cctype>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <iostream>
#include <map>
#include <random>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
/*---------------------------------------*/

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  int n; cin >> n;
  vector<int> a(n);
  int sum = 0;
  REP(i, n) {
    cin >> a[i];
    sum += a[i];
  }
  int minimum = INF;
  int ans;
  REP(i, n) {
    if (abs(sum-a[i]*n) < minimum) {
      minimum = abs(sum-a[i]*n);
      ans = i;
    }
  }
  cout << ans << "\n";
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using std::cerr;
using std::cin;
using std::cout;
using std::endl;

int main(void){
  cout << std::fixed << std::setprecision(10);
  cin.tie(0);
  std::ios::sync_with_stdio(false);
  int n,m;
  cin>>n>>m;
  std::vector<int64_t> x(n),y(n),z(n);
  for(int i=0;i<n;i++){
    cin>>x[i]>>y[i]>>z[i];
  }

  int64_t result=0;
  for(int xi=0;xi<=1;xi++){
    for(int yi = 0; yi < 2; ++yi){
      for(int zi = 0; zi < 2; ++zi){
        std::vector<int64_t> sweets(n);
        for(int si=0;si<n;si++){
          if(xi==0){
            sweets[si]+=x[si];
          }else{
            sweets[si]-=x[si];
          }
          if(yi==0){
            sweets[si]+=y[si];
          }else{
            sweets[si]-=y[si];
          }
          if(zi==0){
            sweets[si]+=z[si];
          }else{
            sweets[si]-=z[si];
          }
        }
        std::sort(sweets.begin(), sweets.end(), std::greater<>());

        int64_t tmp_result=0;
        for(int i=0;i<m;i++){
          tmp_result+=sweets[i];
        }
        result=std::max(result,tmp_result);

      }
    }
  }
  cout<<result<<endl;
  
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int k,n,a[1000000],b[1000000],ans,mx=-100;
int main()
{
    scanf("%d%d",&k,&n);
    for(int i=0;i<n;i++) {
            scanf("%d",&a[i]);
    }
    b[0]=k-a[n-1]+a[0];
    for(int i=1;i<n;i++){
        b[i]=a[i]-a[i-1];
    }
    for(int i=0;i<n;i++) mx=max(mx,b[i]);
    ans=k-mx;
    printf("%d",ans);
}


Measured memory_bytes: 5120
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <queue>
#include <map>
using namespace std;
typedef long long int ll;

struct Edge{
	int to; ll dist;
	Edge(){}
	Edge(int to,ll dist):to(to),dist(dist){}
};

template <class E>
using Graph = vector<vector<E>>;
 
template<class D, D INF>
struct Dijkstra {
    vector<D> res; //res[i] = sからiまでの最短距離
    
    template<class E>
    Dijkstra(const Graph<E> &g, int s) {
        int V = (int)g.size();
        res = vector<D>(V, INF);
        
        using P = pair<D, int>;
        priority_queue<P, vector<P>, greater<P>> q;
        q.push(P(0, s));
        res[s] = 0;
        while (!q.empty()) {
            P p = q.top(); q.pop();
            if (res[p.second] < p.first) continue;
            for (E e: g[p.second]) {
                if (p.first+e.dist < res[e.to]) {
                    res[e.to] = p.first+e.dist;
                    q.push(P(res[e.to], e.to));
                }
            }
        }
    }
};

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n,m; cin >> n >> m;
	Graph<Edge> g(n);
	for(int i=0;i<m;i++){
		int l,r,c; cin >> l >> r >> c;
		l--; r--;
		g[l].push_back(Edge(r,c));
	}
	for(int i=0;i<n-1;i++){
		g[i+1].push_back(Edge(i,0));
	}
	Dijkstra<ll,(ll)1e15> di(g,0);
	if(di.res[n-1]==1e15){
		cout << -1 << endl;
	}
	else{
		cout << di.res[n-1] << endl;
	}
	return 0;
}

Measured memory_bytes: 9336
import collections

n = int(input())

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

c = collections.Counter(prime_factorize(n))

s = 0

def check(x):
    k = 1
    l = 0
    while x >= l + k:
        l += k
        k += 1
    return k-1


for v in c.values():
    s += check(v)



print(s)


Measured memory_bytes: 9484
# 解説を参考に作成
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
#
#
# @stop_watch
def solve(N, Ai, Bi):
    Ci = [0] * (N + 1)
    Di = [0] * (N + 1)
    j = 0
    k = 0
    for i in range(1, N + 1):
        while j < N and Ai[j] <= i:
            j += 1
        Ci[i] = j
        while k < N and Bi[k] <= i:
            k += 1
        Di[i] = k
    # print(Ci)
    # print(Di)
    for i in range(1, N + 1):
        if Ci[i] - Ci[i - 1] + Di[i] - Di[i - 1] > N:
            print('No')
            return
    x = 0
    for i in range(1, N + 1):
        x = max(x, Ci[i] - Di[i - 1])
    print('Yes')
    # print(x)
    # print(' '.join([str(a) for a in Ai]))
    print(' '.join([str(Bi[(N - x + i) % N]) for i in range(N)]))


if __name__ == '__main__':
    # S = input()
    N = int(input())
    # N, M = map(int, input().split())
    Ai = [int(i) for i in input().split()]
    Bi = [int(i) for i in input().split()]
    # ABi = [[int(i) for i in input().split()] for _ in range(N)]
    solve(N, Ai, Bi)

    # # test
    # from random import randint
    # from func import random_str
    # solve()


Measured memory_bytes: 57080
#include<iostream>
#include<cmath>
using namespace std;
static const int mod = 1000000007;
long long mod_pow(long long m, int n, int mod ) {
unsigned long long res = 1;
 	while( n > 0 ) {
 		if( n & 1 ) res = res * m % mod;
 		m = m * m % mod;
 		n >>= 1;
 	}

	return res;
}

int main(int argc, char const *argv[])
{
	int m, n;
	cin >> m >> n;
	cout << mod_pow(m, n, mod) << endl;
	return 0;
}


Measured memory_bytes: 3072
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << endl
#define debug cout << "hi" << endl

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const ll MOD = 1e9 + 7;
const int INF32 = 1<<30;
const ll INF64 = 1LL<<60;
const int N = 1e6 + 10;
const ll mod = 1e9 + 7;

ll fac[N];

ll binpow(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

void init() {
    fac[0] = 1;
    for (ll i = 1; i < N; i++)
        fac[i] = fac[i - 1] * i % mod;
}

ll inv(ll a) {
	return binpow(a, mod - 2);
}

ll A(ll n, ll m) {
	return fac[n] * inv(fac[n - m]) % mod;
}

ll C(ll n, ll m) {
    return fac[n] * inv(fac[m]) % mod * inv(fac[n - m]) % mod;
}

void solve(){
    ll x,y;cin >> x >> y;
    if(y>x) swap(x,y);
    ll j = x - y;
    if((y-j)%3||y - j<0){
        cout << 0;
        return;
    }
    ll k = (y-j)/3;
    ll k2 = k+j;
    init();
    cout << A(k+k2,k+k2)*inv(A(k,k)*A(k2,k2)%mod)%mod;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

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

int main() {
  int a,b,c;
  cin>>a>>b;
  if(b==100)
    c=a*1000+b;
  else if(10<=b)
    c=a*100+b;
  else c=10*a+b;
  bool num=false;
  for(int i=4;pow(i,2)<=c;i++){
    if(pow(i,2)==c)
      num=true;
  }
  if(num) cout<<"Yes";
  else cout<<"No";
  
}


Measured memory_bytes: 256
n = int(raw_input())
ls = {}
for i in range(n):
    inp = raw_input()
    if inp[0] == "i":
        ls[inp[7:]] = 1
    else:
        try:
        	if ls[inp[5:]] == 1: print "yes"
        except:
        	print "no"
            

Measured memory_bytes: 62708
n = int(input())
l = map(int,input().split())
d = {}
ans = 0
for i in l:
  if i not in d:
    d[i] = 1
  else:
    d[i] += 1
for k,v in d.items():
  if k != v:
    if k < v:
      ans += v - k
    else:
      ans += v
print(ans)

Measured memory_bytes: 23284
#include <array>
#include <cstdint>
#include <iostream>
#include <tuple>
#include <vector>

using namespace std;

array<array<int64_t, 100000>, 3> dp;

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

    vector<int64_t> as(n), bs(n), cs(n);

    for (int i = 0; i < n; i++)
    {
        cin >> as[i] >> bs[i] >> cs[i];
    }

    dp[0][0] = as[0];
    dp[1][0] = bs[0];
    dp[2][0] = cs[0];

    for (int i = 1; i < n; i++)
    {
        dp[0][i] = max(dp[1][i - 1], dp[2][i - 1]) + as[i];
        dp[1][i] = max(dp[0][i - 1], dp[2][i - 1]) + bs[i];
        dp[2][i] = max(dp[0][i - 1], dp[1][i - 1]) + cs[i];
    }

    cout << max(dp[0][n - 1], max(dp[1][n - 1], dp[2][n - 1])) << endl;
}

Measured memory_bytes: 4992
parseInt(x) = parse(Int, x)
parseBigInt(x) = parse(BigInt, x)
parseFloat(x) = parse(Float64, x)
parseBigFloat(x) = parse(BigFloat, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
    n,m=parseMap(split(readline()))
    data=[parseMap(split(readline())) for i in 1:m]
    p=parseMap(split(readline()))
    ans=0
    for i in 0:(1<<n)-1
        pat=Vector{Int}()
        for j in 0:n-1
            if i & (1<<j) == 0
                # jは0-startだがJuliaの配列は1-indexedなので
                push!(pat,j+1)
            end
        end
        flg=true
        for j in 1:m
            res=0
            for k in 1:data[j][1]
                if data[j][1+k] in pat
                    res+=1
                end
            end
            if res%2!=p[j]
                flg=false
            end
        end
        if flg
            ans+=1
        end
    end
    println(ans)
end
main()

Measured memory_bytes: 169288
#include<iostream>
#include<string.h>
#include<ctype.h>
#include<string>
#include<math.h>
#define pi 3.141592653589
#include<iomanip>
using namespace std;
#include<algorithm>
#define rep(i,a,n) for(int i=a;i<n;i++)
#define INF 1e9
#define LINF 1e17
#define ll long long


 
int main(){
    
    ll n;
    
    cin>>n;
    if((n-1)%11<=5)cout<<2*(n-1)/11+1<<endl;
    else cout<<2*((n-1)/11)+2<<endl;
    
    return 0;
    
}

Measured memory_bytes: 256
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
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 Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

const int dm = 1 << 20;
char dn[dm], * di = dn;
inline void putint(int X) {
	if (X == 0) {
		*di++ = '0';
		*di++ = '\n';
		return;
	}
	int keta = 0;
	char C[10];
	while (X) {
		*(C + keta) = '0' + X % 10;
		X /= 10;
		keta++;
	}
	for (int i = keta - 1; i >= 0; i--)* di++ = (*(C + i));
	*di++ = '\n';
}


pair<int, int> E[200001];
int H[100001];
int kotae[100001];
char Vis[100001];
void sagasu(int P, int D, int C) {
	if (D == 0) {
		if (kotae[P] == 0) kotae[P] = C;
	}
	else if (Vis[P] < D) {
		Vis[P] = D;
		if (kotae[P] == 0) kotae[P] = C;
		for (int p = H[P]; p; p = E[p].second) {
			sagasu(E[p].first, D - 1, C);
		}
	}
}

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


	int N, M, Q;
	N = getint();
	M = getint();
	for (int i = 1; i < 2 * M; i += 2) {
		int a = getint(), b = getint();
		E[i] = mp(a, H[b]);
		H[b] = i;
		E[i + 1] = mp(b, H[a]);
		H[a] = i + 1;
	}
	Q = getint();
	int v[100000], d[100000], c[100000];
	rep(i, Q) {
		v[i] = getint();
		d[i] = getint();
		c[i] = getint();
	}
	for (int i = Q - 1; i >= 0; i--) {
		sagasu(v[i], d[i], c[i]);
	}
	rep1(i, N) {
		putint(kotae[i]);
	}

	fwrite_unlocked(dn, di - dn, 1, stdout);

	Would you please return 0;
}

Measured memory_bytes: 4736
#include<iostream>
using namespace std;
int main()
{
    int a[3][3][2],n,b,i,j,k,cnt;
    for(i=0;i<3;i++)for(j=0;j<3;j++){
        cin >> a[j][i][0];
        a[j][i][1]=0;
    }
    cin >> n;
    for(k=0;k<n;k++){
        cin >> b;
    for(i=0;i<3;i++)for(j=0;j<3;j++)if(b==a[j][i][0]) a[j][i][1]=1;
    }
    
    for(i=0;i<3;i++){
        cnt=0;
        for(j=0;j<3;j++)if(a[j][i][1]==1)cnt++;
        if(cnt!=3) continue;
        cout << "Yes";
        return 0;
    }
    for(j=0;j<3;j++){
        cnt=0;
        for(i=0;i<3;i++)if(a[j][i][1]==1)cnt++;
        if(cnt!=3) continue;
        cout << "Yes";
        return 0;
    }
    cnt=0;
    for(i=0;i<3;i++)if(a[i][i][1]==1)cnt++;
    if(cnt==3){
        cout << "Yes";
        return 0;
    }
    cnt=0;
    for(i=0;i<3;i++)if(a[2-i][i][1]==1)cnt++;
    if(cnt==3){
        cout << "Yes";
        return 0;
    }
    cout << "No";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n)   for(int i=0;i<(n);++i)
#define ALL(v)     (v).begin(),(v).end()
#define debug(x)   cerr<<#x<<": "<<(x)<<endl
using namespace std;
using llong = long long;
using vi    = vector<int>;
using vvi   = vector<vi >;
using vvvi  = vector<vvi >;
using pii   = pair<int,int>;
constexpr int    INF=1e9;
constexpr double EPS=1e-9;
constexpr int    MOD=1e9+7;
template<class Type>
void line(const Type &a){int cnt=0;for(const auto &elem:a){cerr<<(cnt++?' ':'>');cerr<<elem;}cerr<<endl;}

/*二部マッチング*/
struct BipartiteMatching{
	int vn;				//vn:=(ノード数).
	vvi g;				//g[i]:=(ノードiの隣接リスト).
	vi match;			//match[i]:=(ノードiのペア).
	vector<bool> used;	//used[i]:=(ノードiをDFSで既に調べたかのフラグ).
	
	/*constructor.*/
	BipartiteMatching(unsigned int vn_):vn(vn_),g(vn_),match(vn_),used(vn_){}
	
	void add_edge(int u,int v){//uとvを結ぶ辺をグラフに追加する.
		g[u].push_back(v);
		g[v].push_back(u);
	}
	bool dfs(int v){//増加パスを探す.
		used[v]=true;
		REP(i,g[v].size()){
			int u=g[v][i], w=match[u];
			if(w<0 or !used[w] and dfs(w)){
				match[v]=u;
				match[u]=v;
				return true;
			}
		}
		return false;
	}
	int bipartite_matching(){//二部グラフの最大マッチングを求める.
		int res=0;
		fill(ALL(match),-1);
		REP(i,vn){
			if(match[i]<0){
				fill(ALL(used),false);
				if(dfs(i)) res++;
			}
		}
		return res;
	}
};

int main(){
	int n;
	cin>>n;
	
	vi a(n),b(n),c(n),d(n);
	REP(i,n) cin>>a[i]>>b[i];
	REP(i,n) cin>>c[i]>>d[i];
	
	BipartiteMatching ob(2*n);
	REP(i,n)REP(j,n){
		if(a[i]<c[j] and b[i]<d[j]) ob.add_edge(i,j+n);
	}
	
	cout<<ob.bipartite_matching()<<endl;
	return 0;
}

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

#pragma warning(disable:4996)
using namespace std;



const int mod = 998244353;
struct Mod {
public:
	int num;
	Mod() : Mod(0) { ; }
	Mod(long long int n) : num((n % mod + mod) % mod) {
		static_assert(mod<INT_MAX / 2, "mod is too big, please make num 'long long int' from 'int'");
	}
	Mod(int n) : Mod(static_cast<long long int>(n)) { ; }
	operator int() { return num; }
};

Mod operator+(const Mod a, const Mod b) { return Mod((a.num + b.num) % mod); }
Mod operator+(const long long int a, const Mod b) { return Mod(a) + b; }
Mod operator+(const Mod a, const long long int  b) { return b + a; }
Mod operator++(Mod &a) { return a + Mod(1); }
Mod operator-(const Mod a, const Mod b) { return Mod((mod + a.num - b.num) % mod); }
Mod operator-(const long long int a, const Mod b) { return Mod(a) - b; }
Mod operator--(Mod &a) { return a - Mod(1); }
Mod operator*(const Mod a, const Mod b) { return Mod(((long long)a.num * b.num) % mod); }
Mod operator*(const long long int a, const Mod b) { return Mod(a)*b; }
Mod operator*(const Mod a, const long long int b) { return Mod(b)*a; }
Mod operator*(const Mod a, const int b) { return Mod(b)*a; }
Mod operator+=(Mod &a, const Mod b) { return a = a + b; }
Mod operator+=(long long int &a, const Mod b) { return a = a + b; }
Mod operator-=(Mod &a, const Mod b) { return a = a - b; }
Mod operator-=(long long int &a, const Mod b) { return a = a - b; }
Mod operator*=(Mod &a, const Mod b) { return a = a * b; }
Mod operator*=(long long int &a, const Mod b) { return a = a * b; }
Mod operator*=(Mod& a, const long long int &b) { return a = a * b; }
Mod operator^(const Mod a, const int n) {
	if (n == 0) return Mod(1);
	Mod res = (a * a) ^ (n / 2);
	if (n % 2) res = res * a;
	return res;
}
Mod mod_pow(const Mod a, const long long  int n) {
	if (n == 0) return Mod(1);
	Mod res = mod_pow((a * a), (n / 2));
	if (n % 2) res = res * a;
	return res;
}

//mod が素数の場合のみ　違う場合はextend euclid を用いる。
Mod inv(const Mod a) { return a ^ (mod - 2); }
Mod operator/(const Mod a, const Mod b) {
	assert(b.num != 0);
	return a * inv(b);
}
Mod operator/(const long long int a, const Mod b) {
	return Mod(a) / b;
}
Mod operator/=(Mod &a, const Mod b) {
	return a = a / b;
}

#define MAX_MOD_N 1024000

Mod fact[MAX_MOD_N], factinv[MAX_MOD_N];
void init(const int amax = MAX_MOD_N) {
	fact[0] = Mod(1); factinv[0] = 1;
	for (int i = 0; i < amax - 1; ++i) {
		fact[i + 1] = fact[i] * Mod(i + 1);
		factinv[i + 1] = factinv[i] / Mod(i + 1);
	}
}
Mod comb(const int a, const int b) {
	return fact[a] * factinv[b] * factinv[a - b];
}

int main() {
	string st;cin>>st;

	int N=st.size();

	vector<vector<Mod>>dp(2*N+1,vector<Mod>(2*N+1));
	dp[0][0]=1;

	int b_sum=0;
	int a_sum=0;
	for (int i = 0; i < 2 * N; ++i) {
		if (i < N) {
			b_sum+=st[i]-'0';
			a_sum+='2'-st[i];
		}
		int r=b_sum;
		int l=max(0,i+1-a_sum);
		for (int cnt = 0; cnt <= 2 * N; ++cnt) {
			for (int n_cnt = cnt; n_cnt < cnt + 2; ++n_cnt) {
				if (l <= n_cnt&&n_cnt <= r) {
					dp[i+1][n_cnt]+=dp[i][cnt];
				}
			}
		}
	}
	auto answer=dp[2*N][b_sum].num;
	cout<<answer<<endl;
	return 0;
}

Measured memory_bytes: 70912
def scc(E):
    n = len(E)
    iE = [[] for _ in range(n)]
    for i, e in enumerate(E):
        for v in e:
            iE[v].append(i)
    T = []
    done = [0] * n # 0 -> 1 -> 2
    ct = 0
    for i0 in range(n):
        if done[i0]: continue
        Q = [~i0, i0]
        while Q:
            i = Q.pop()
            if i < 0:
                if done[~i] == 2: continue
                done[~i] = 2
                T.append(~i)
                ct += 1
                continue
            if i >= 0:
                if done[i]: continue
                done[i] = 1
            for j in E[i]:
                if done[j]: continue
                Q.append(~j)
                Q.append(j)
    
    done = [0] * n
    SCC = []
    ### ID が必要なとき
    I = [0] * n
    ###
    for i0 in T[::-1]:
        if done[i0]: continue
        L = []
        Q = [~i0, i0]
        while Q:
            i = Q.pop()
            if i < 0:
                if done[~i] == 2: continue
                done[~i] = 2
                L.append(~i)
                ###
                I[~i] = len(SCC)
                ###
                continue
            if i >= 0:
                if done[i]: continue
                done[i] = 1
            for j in iE[i]:
                if done[j]: continue
                Q.append(~j)
                Q.append(j)
        SCC.append(L)
    return SCC, I

    ### ↓ Edge が必要なとき （上の return を消す）
    nE = [set() for _ in range(len(SCC))]
    for i, e in enumerate(E):
        for j in e:
            if I[i] == I[j]: continue
            # print("i, j, I[i], I[j] =", i, j, I[i], I[j])
            nE[I[i]].add(I[j])
    nE = [list(e) for e in nE]
    return SCC, I, nE

class twosat():
    def __init__(self, n):
        self.n = n
        self.E = [[] for _ in range(n * 2)]
    def add_clause(self, i, f, j, g):
        assert 0 <= i < self.n
        assert f == 0 or f == 1
        assert 0 <= j < self.n
        assert g == 0 or g == 1
        self.E[i * 2 + (f ^ 1)].append(j * 2 + g)
        self.E[j * 2 + (g ^ 1)].append(i * 2 + f)
    
    def satisfiable(self):
        SCC, I = scc(self.E)
        re = [0] * self.n
        for i in range(self.n):
            if I[2*i] == I[2*i+1]: return (0, [])
            if I[2*i] < I[2*i+1]: re[i] = 1
        return (1, re)

N, D = map(int, input().split())
ts = twosat(N)
X = []
for _ in range(N):
    x, y = map(int, input().split())
    X.append((x, y))

for i, (x1, y1) in enumerate(X):
    for j, (x2, y2) in enumerate(X[:i]):
        if abs(x1 - x2) < D:
            ts.add_clause(i, 1, j, 1)
        if abs(x1 - y2) < D:
            ts.add_clause(i, 1, j, 0)
        if abs(y1 - x2) < D:
            ts.add_clause(i, 0, j, 1)
        if abs(y1 - y2) < D:
            ts.add_clause(i, 0, j, 0)

a, sa = ts.satisfiable()
if a == 0:
    print("No")
else:
    print("Yes")
    print(*[x[r] for x, r in zip(X, sa)], sep = "\n")


Measured memory_bytes: 70040
#include <stdio.h>

int main(void){
    int K;
    int X;
    int minimum = -1000000;
    int maximum = 1000000;
    scanf("%d %d", &K, &X);
    if(X-K+1> -1000000){
        minimum = X-K+1;
    }
    if(X+K-1< 1000000){
        maximum = X+K-1;
    }
    for(int i = minimum; i <= maximum; i++){
        printf("%d ",i);
    }
}

Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef pair<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-8;
const int inf=1e8;
int main(){
	vi in(6);
	rep(i,6)cin>>in[i];
	sort(in.begin(),in.begin()+4);
	int out=0;
	rep(i,3)out+=in[i+1];
	cout<<out+max(in[4],in[5])<<endl;
}

Measured memory_bytes: 1208
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MOD 100000
#define FMAX 10946
#define NMMAX 20
using namespace std;

int main(void)
{
  int i, j, k, m, n, fcheck, mask, ans = 1, res = 0, fcount = 0;
  int k2b[FMAX], b2k[1<<19], dp[2][FMAX][2];
  char field[NMMAX][NMMAX+1];
  scanf("%d %d%*c", &m, &n);
  for (i = 0; i < m; i++) {
    for (j = 0; j < n; j++) {
      field[i][j] = getchar();
      if (field[i][j] == '?') ans = (ans * 3) % MOD;
    }
    getchar();
  }
  for (i = 0; i < (1 << (n - 1)); i++) {
    fcheck = 1;
    for (j = 0; j < n - 2; j++) {
      if (((i >> j) & 1) & ((i >> (j + 1)) & 1)) {
        fcheck = 0;
        break;
      }
    }
    if (fcheck) {
      k2b[fcount] = i;
      b2k[i] = fcount++;
    }
  }
  mask = (1 << (n - 1)) - 1;
  fcheck = 1;
  auto &src = dp[0];
  auto &dst = dp[1];
  src[0][0] = 1;
  for (i = 0; i < m; i++) {
    for (j = 0; j < n; j++) {
      memset(dst, 0, sizeof(dst));
      for (k = 0; k < fcount; k++) {
         int nk, jflag;
        if (field[i][j] == 'J' || field[i][j] == '?') {
          nk = b2k[(k2b[k] << 1) & mask];
          jflag = (j < n - 1);
          dst[nk][jflag] = ((dst[nk][jflag]) + (src[k][0]) + (src[k][1]))% MOD;
        }
        if (field[i][j] == 'O' || field[i][j] == '?') {
          nk = b2k[((k2b[k] << 1) & mask) | 0];
          jflag = 0;
          dst[nk][jflag] = ((dst[nk][jflag]) + (src[k][0]))% MOD;
          nk = b2k[((k2b[k] << 1) & mask) | 1];
          dst[nk][jflag] = ((dst[nk][jflag]) + (src[k][1]))% MOD;
        }
        if (field[i][j] == 'I' || field[i][j] == '?') {
          if (((~k2b[k]) >> (n - 2)) & 1) {
            nk = b2k[(k2b[k] << 1) & mask];
            jflag = 0;
            dst[nk][jflag] = ((dst[nk][jflag]) + (src[k][0]) + (src[k][1]))% MOD;
          }
        }
      }
      swap(src, dst);
      fcheck ^= 1;
    }
  }
  for (i = 0; i < fcount; i++) res = (res + (src[i][0]) + (src[i][1])) % MOD;
  printf("%d\n", (ans - res + MOD) % MOD);
}



Measured memory_bytes: 3916
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define IFOR(i, m, n) for (ll i = n - 1; i >= m; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
#define FOREACH(x, a) for (auto&(x) : (a))
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) ll(x.size())

int main() {
  ll x;
  cin >> x;
  FOR(i, 1, 10000) {
    if ((i * x) % 360 == 0) {
      cout << i << endl;
      return 0;
    }
  }
}

Measured memory_bytes: 3620
#include<bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	int r;
	cin>>r;
	cout<<3*r*r;
	return 0;
}

Measured memory_bytes: 256
{-# LANGUAGE BangPatterns #-}
import Control.Monad
import Data.Maybe
import Debug.Trace
import Data.List
import qualified Data.Map.Strict as Map
import qualified Data.IntMap.Strict as IntMap
import qualified Data.Set as Set
import qualified Data.IntSet as IntSet
import Data.Functor
-- import Data.Array
import Data.Array.Unboxed
import Control.Monad.ST
import Data.Array.ST

main :: IO ()
main = do
  (n:k:q:_) <- map read . words <$> getLine :: IO [Int]
  as <- replicateM q $ readLn :: IO [Int]
  putStr . unlines  $ solve n k q as

solve n k q as = map (\p -> if k - q + p > 0 then "Yes" else "No") $ elems ans
  where

    ans :: UArray Int Int 
    ans = runSTUArray $ do
      c <- newArray (1, n) 0 :: ST s (STUArray s Int Int)
      forM_ as $ \a -> do
        prev <- readArray c a
        writeArray c a $ prev + 1
      return c


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

int main() {
    int N, M;
    cin >> N >> M;
    if (N == M) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <list>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>

typedef long long ll;

using namespace std;

string addString(string source, string s, int num) {
	for (int i = 0; i < num; i++) {
		source += s;
	}

	return source;
}

int main(){
    int sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;

    int moveCount = (tx - sx + 1) * 2 + (ty - sy + 1) * 2;
    string moveString = "";
    moveString = addString(moveString, "U", ty - sy + 1);
    moveString = addString(moveString, "R", tx - sx + 1);
    moveString = addString(moveString, "D", ty - sy + 1);
    moveString = addString(moveString, "L", tx - sx + 1);
    string firstMoveString = moveString.substr(1, moveCount - 1) + "U";
    string secondMoveString = "L" + moveString.substr(0, moveCount - 1);

    cout << firstMoveString + secondMoveString;

}


Measured memory_bytes: 256
import itertools
S = input()

ans = 0
for v in itertools.product([1,0], repeat=len(S)-1):
    idx = 0
    sum = 0
    for i in range(1,len(S)):
        if v[i-1] == 1:
            sum += int(S[idx:i])
            idx = i
    ans += int(S[idx:])
    ans += sum
print(ans)

Measured memory_bytes: 9076
#include<bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define debug(x) cerr<<#x<<" = "<<(x)<<endl
#define eps 1e-8
#define pi acos(-1.0)
using namespace std;
void test(){cerr<<"\n";}
template<typename T,typename... Args>void test(T x,Args... args){cerr<<x<<" ";test(args...);}
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int MAXN=(int)1e5+5;
const int MOD=(int)1e9+7;
int b[MAXN];
int a[MAXN];
int main()
{
    int n,m,c;
    cin>>n>>m>>c;
    int ans=0;
    for(int i=1;i<=m;i++)cin>>b[i];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[j];
        }
        ll tmp=c;
        for(int j=1;j<=m;j++){
            tmp+=a[j]*b[j];
        }
        if(tmp>0)ans++;
    }
    cout<<ans<<"\n";
    return 0;
}


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

int main(){
    int64_t N;
    cin >> N;

    int64_t ans = 0;
    for(int64_t i=1; i*i<=N; i++){
        if(N%i) continue;
        vector<int64_t> d = {i};
        if(i < N/i) d.push_back(N/i);
        for(int64_t r : d){
            int64_t m = N/r-1;
            if(r < m) ans += m;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Tasks
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] s = Console.ReadLine().Split(' ');
            int a = int.Parse(s[0]);
            int b = int.Parse(s[1]);
            Console.WriteLine("{0} {1}", a * b, 2 * (a + b));
            
        }
    }
}



Measured memory_bytes: 9124
#include <stdio.h>
#include <stdlib.h>
int main()
{
    int n,a[101];
    int i=0,j=0,q=0;
    int p=0,t;
    scanf("%d",&n);
        for(q=0;q<n;q++)
        {
            scanf("%d",&a[q]);
        }
        for(i=0;i<n-1;i++)
        {
            for(j=0;j<n-i-1;j++)
            {
                if(a[j]>a[j+1])
                {
                    t=a[j];
                    a[j]=a[j+1];
                    a[j+1]=t;
                    p=p+1;
                }
            }
        }
        for(int i = 0;i<n;i++)
             {
               if(i<n-1)
                 printf("%d ",a[i]);
               else printf("%d",a[i]);
             }
        printf("\n");
        printf("%d\n",p);
    return 0;
}



Measured memory_bytes: 2052
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i,a,b) for(inti=a;i<=b;i++)

#define MOD 1000000009
typedef long long int ll;
typedef vector<int>vi;
typedef pair<int,int>pi;



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

if(a%3==0||b%3==0||(a+b)%3==0)
    cout<<"Possible"<<endl;
else
    cout<<"Impossible"<<endl;
 return 0;
}


Measured memory_bytes: 3592
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

#include <fstream>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <functional>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <bitset>
#include <numeric>
#include <unordered_set>
#include <bitset>
#include <limits>
#include <random>
#include <complex>
#include <numeric>
#include <cstdlib>
#include <random>
#include <bits/stdc++.h>


using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
//typedef vector<ll> vec;
//typedef vector<vec> mat;

const ll mod=1000000007ll;
const ll inf=1000000000000000ll;

ll N;

int main(){
  cin>>N;
  if(N<1200)cout<<"ABC"<<endl;
  else if(1200<=N && N<2800)cout<<"ARC"<<endl;
  else cout<<"AGC"<<endl;
  return 0;
}


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

#define maxsize 300*300 + 5

int px[maxsize],py[maxsize],d[maxsize];
int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int H,W,D;
	cin >> H >> W >> D;
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			int A;
			cin >> A;
			px[A]=i;
			py[A]=j;
		}
	}
	for(int i=D+1;i<=H*W;i++){
		d[i] = d[i-D]+abs(px[i]-px[i-D])+abs(py[i]-py[i-D]);
	}
	int Q;
	cin >> Q;
	vector<int> ans;
	for(int i=0;i<Q;i++){
		int L,R;
		cin >> L >> R;
		ans.push_back(d[R]-d[L]);
	}
	for(auto x:ans)cout << x << endl;
}

Measured memory_bytes: 2680
H, W = map(int, input().split())
atlas = [[False for _ in range(W + 2)] for _ in range(H + 2)]

for h in range(1, H + 1):
    line = input()
    for w in range(1, W + 1):
        if line[w - 1] == '#':
            atlas[h][w] = True

for h in range(1, H + 1):
    for w in range(1, W + 1):
        if atlas[h][w]:
            if atlas[h - 1][w] or atlas[h + 1][w] or atlas[h][w - 1] or atlas[h][w + 1]:
                continue
            print('No')
            exit(0)
print('Yes')

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

using ll = long long;

ll calc(ll a, ll N) {
    ll last = N / a * a;
    return (a + last) * (N / a) / 2;
}

int main() {
    ll N;  cin >> N;
    ll ans = 0;
    for (int i = 1; i <= N; ++i) {
        ans += calc(i, N);
    }
    cout << ans << endl;
}


Measured memory_bytes: 3632
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.IO;

class _Class
{
	void _Do()
	{
		//
		var _s = _stringArray();
		var n_ = int.Parse(_s[0]);
		var a_ = _intArray();
		//var n_ = 100000;
		//var a_ = new int[100000];

		//
		var l = new int[n_];

		if(n_%2==0) {

			for (int i =0;i<n_/2;i++) {
				l[i] = a_[a_.Length-1-i*2];	
			}

			for (int i = 0; i < n_/2; i++) {
				l[i+n_/2] = a_[i*2];
			}

		}	else{

			for (int i = 0; i < n_ / 2+1; i++)
			{
				l[i] = a_[a_.Length - 1 - i * 2];
			}

			for (int i = 0; i < n_ / 2; i++)
			{
				l[i + n_ / 2+1] = a_[i* 2+1];
			}
		}


		//
		for (int i = 0; i < n_; i++)
		{
			if (i >= 1)
				Console.Write(" ");
			Console.Write(l[i]);
		}
		Console.WriteLine();
	}

	static void Main(string[] args)
	{
		new _Class()._Do();
	}


	// 1
	string[] _stringArray()
	{
		return Console.ReadLine().Split();
	}

	// 2.1 -2,147,483,648 ~ +2,147,483,647
	int[] _intArray()
	{
		var _s = Console.ReadLine().Split();

		var x = new int[_s.Length];
		for (var i = 0; i < _s.Length; i++)
			x[i] = int.Parse(_s[i]);

		return x;
	}

	// 2.2 -9,223,372,036,854,775,808 ~ +9,223,372,036,854,775,807
	long[] _longArray()
	{
		var _s = Console.ReadLine().Split();

		var x = new long[_s.Length];
		for (var i = 0; i < _s.Length; i++)
			x[i] = long.Parse(_s[i]);

		return x;
	}
}

Measured memory_bytes: 37560
#include<bits/stdc++.h>
#define lld long long
#define pb push_back
#define mk make_pair
#define MAX (lld)1e18+7
#define lim (lld)1e9+7
#define MAX2 (lld)2e5+9
#define ff first
#define ss second
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

const lld mod=lim;

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


lld extend_gcd(lld a, lld b, lld& x, lld& y) {
    if (b == 0) { x = 1;y = 0;return a;}
    lld x1, y1;
    lld d = extend_gcd(b, a % b, x1, y1);
    x = y1; y = x1 - y1 * (a / b);return d;	}

lld rowNum[]={-1,0,0,1};
lld colNum[]={0,-1,1,0};

int main()
{
	fastio
	string s,t;
	cin>>s>>t;

	int n=s.size();
	int m=t.size();

	int ans=lim;
	for(int i=0;i<=n-m;i++)
	{
		string c="";
		for(int j=0;j<m;j++)
		{
			c+=s[i+j];
		}

		int cost=0;
		for(int j=0;j<m;j++)
		{
			if(c[j]!=t[j])
				cost++;
		}

		ans=min(ans,cost);
	}

	cout<<ans<<endl;
}

Measured memory_bytes: 3648
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sa = br.readLine().split(" ");
		int n = Integer.parseInt(sa[0]);
		int m = Integer.parseInt(sa[1]);
		List<Node> list = new ArrayList<>(n);
		for (int i = 0; i < n; i++) {
			list.add(new Node(i));
		}
		for (int i = 0; i < m; i++) {
			sa = br.readLine().split(" ");
			int s = Integer.parseInt(sa[0]) - 1;
			int t = Integer.parseInt(sa[1]) - 1;
			list.get(s).list.add(new Hen(t));
		}
		br.close();

		for (int i = n - 2; i >= 0; i--) {
			Node node = list.get(i);
			double sum = 0;
			for (Hen h : node.list) {
				Node next = list.get(h.v);
				h.c = next.exp + 1;
				sum += h.c;
			}
			node.exp = sum / node.list.size();
		}
		double ans = list.get(0).exp;

		for (int i = 0; i < n - 1; i++) {
			Collections.sort(list.get(i).list);
		}

		for (int i = 0; i < n - 1; i++) {
			for (int j = n - 2; j >= 0; j--) {
				Node node = list.get(j);
				int start = 0;
				if (node.v == i) {
					if (node.list.size() <= 1) {
						continue;
					}
					start++;
				}
				double sum = 0;
				for (int k = start; k < node.list.size(); k++) {
					Hen h = node.list.get(k);
					Node next = list.get(h.v);
					h.c = next.exp + 1;
					sum += h.c;
				}
				node.exp = sum / (node.list.size() - start);
			}
			ans = Math.min(ans, list.get(0).exp);
		}
		System.out.println(ans);
	}

	static class Hen implements Comparable<Hen> {
		int v;
		double c;

		public Hen(int v) {
			this.v = v;
		}
		public int compareTo(Hen o) {
			return Double.compare(o.c, c);
		}
	}

	static class Node {
		int v;
		double exp;
		List<Hen> list = new ArrayList<>();

		public Node(int v) {
			this.v = v;
		}
	}
}


Measured memory_bytes: 64908
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
using namespace std;
#define MOD 1000000007
#define f(i,n) for(int i=0;i<int(n);i++)
#define N 200000


int main(){
	long long n, m, ans;
	scanf("%lld %lld", &n,&m);

	if (n == 1){
		if (m == 1)ans = 1;
		else ans = m - 2;
	}
	else if (m == 1){
		ans = n - 2;
	}

	else{
		ans = (n - 2)*(m - 2);
	}

	printf("%lld\n", ans);


	return 0;
}

Measured memory_bytes: 128
n, m = [ int(v) for v in input().split() ]
shop_data = sorted([ tuple( int(v) for v in input().split() ) for i in range(n) ])


cost = 0
for i in shop_data:
	cost += ( i[0] * min(m,i[1]) )
	m -= min(m,i[1])

print(cost)


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

int powi(int x, int n){
	int res = 1;
	rep(i,n){
		res *= x;
	}
	return res;
}

int main(){
	int d,n;
	cin >> d >> n;
	if(n==100){
		cout << powi(100,d+1) + powi(100,d) << endl;
	}else{
		cout << powi(100,d) * n << endl;
	}
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;

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

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int r;
    cin >> r;
    cout <<3*r*r<< "\n";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n) ; i++)
#define rrep(i,n) for(int i = n-1; i >= 0 ; i--)
typedef long long ll;
constexpr auto INFI = 2147483647;
const ll INFL = 9223372036854775807;

int main(){
    int n;
    cin >> n;
    int totalXor = 0;
    vector<int> otherXor(n,0);
    rep (i, n) {
        cin >> otherXor[i];
        totalXor = totalXor xor otherXor[i];
    }
    rep (i, n) {
        cout << (otherXor[i] xor totalXor) << endl;
    }
  return 0;
}

Measured memory_bytes: 4040
// Best practice

#include<bits/stdc++.h>

#define int         long long
#define pb          push_back
#define pf          emplace_front
#define all(a)      (a).begin(),(a).end()
#define rall(a)     (a).rbegin(),(a).rend()
#define pii 		pair<int,int>
#define psi 		pair<string,int>
#define vi 			vector<int>
#define vpii  		vector<pii>
#define vvi 		vector<vi>
#define sz(x)	    (int)(x).size()
#define x           first
#define y           second
#define endl        '\n'
#define tezz        ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define MOD         1000000007
#define hell        998244353
#define output(x)   cout << (x ? "YES" : "NO")<<endl;
using namespace std;


// Code from Here -------------------------------------------------------------------------------

vi vis;
vi c;
int sz, put=1, extra;
void dfs(int k){
	if(vis[k]!=0){
		sz = put-vis[k];
		extra = vis[k]-1;
		return;
	}
	vis[k] = put++;
	dfs(c[k]);
}

void bfs(int k, int timer){
	if(timer<=0){
		cout << k << endl;
		exit(0);
	}
	bfs(c[k], timer-1);
}

signed main() {
	tezz

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	int n, k;
	cin >> n >> k;
	c = vi (n+1);
	for(int i=1; i<=n; i++){
		cin >> c[i];
	}
	vis = vector<int> (n+1, 0);
	dfs(1);
	int count=0;
	for(int i=1; i<=n; i++)if(vis[i])count++;
	if(k>extra){
		k = (k - extra)%sz+extra;
	}
	// cout << extra << " " << sz << endl;
	bfs(1, k);

	return 0;
}  


Measured memory_bytes: 11264
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
const int inf = 1e9 + 7;
const ll INF = 1e18;
// int mod = 998244353;
int mod = 1000000007;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b); }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll pow(ll a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
ll modpow(ll a, ll b, ll _mod) { return b ? modpow(a * a % _mod, b / 2, _mod) * (b % 2 ? a : 1) % _mod : 1; }
template<class T> ostream& operator << (ostream& os, const vector<T>& vec) { rep(i, sz(vec)) { if (i) os << " "; os << vec[i]; } return os; }
template<class T, class U> ostream& operator << (ostream& os, const pair<T, U>& p) { os << p.F << " " << p.S; return os; }
template<typename T> inline istream& operator >> (istream& is, vector<T>& v) { rep(j, sz(v)) is >> v[j]; return is; }
template<class T, class T2> inline void add(T &a, T2 b) { a += b; if (a >= mod) a -= mod; }


void solve();

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout << fixed << setprecision(10);

  int T;
  // cin >> T;
  T = 1;

  while (T--) {
    solve();
  }
}

void solve() {
  int n, k;
  cin >> n >> k;
  ll sum = 0;
  vector<ll> g(k + 1);
  for (int i = k; i >= 2; --i) {
    ll tmp = modpow(k / i, n, mod);
    rep3(j, 2, inf) {
      if (i * j > k) break;
      (tmp += mod - g[i * j]) %= mod;
    }
    (sum += tmp) %= mod;

    g[i] = tmp;
  }
  // cout << g << endl;
  sum = (modpow(k, n, mod) - sum + mod) % mod;
  ll ans = sum;

  rep3(i, 2, k + 1) (ans += 1LL * i * g[i]) %= mod;
  cout << ans << endl;
}


Measured memory_bytes: 3992