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

#include <iostream>
//#include <algorithm>
// #include <iomanip>
#define ll long long
#define map unordered_map
#define set unordered_set
#define pll pair<ll, ll>
#define vll vector<ll>
#define mll map<ll, ll>

using namespace std;

const ll MOD = 1000000007LL;
const ll INF = (1LL << 60LL);

int main() {
  // std::cout << std::fixed << std::setprecision(10);
  string s;
  cin >> s;

  bool e1 = s[0] == 'R' && s[0] == s[1];
  bool e2 = s[1] == 'R' && s[1] == s[2];

  if (e1 && e2) {
    cout << (3) << endl;
  } else if (e1 || e2) {
    cout << (2) << endl;
  } else {
    bool r = false;

    for (ll i = 0; i < s.size(); i++) {
      if (s[i] == 'R') {
        r = true;
            }
    }
    if (r) {
      cout << (1) << endl;
    } else {
      cout << (0) << endl;
    }
  }
}


Measured memory_bytes: 3592
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    int n;
    cin>>n;
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        int a,b;
        cin>>a>>b;
        if(a==b)
            cnt++;
        else
            cnt=0;
        if(cnt==3)
        {
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    cout<<"No"<<endl;
  
  
  return 0;
}

Measured memory_bytes: 3632
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define ll long long int

double dist(int x1, int x2, int y1, int y2)
{
  return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}

int next_perm(int *p, int n)
{
  int i, j, k, tmp;

  for (i = n - 1; i > 0 && p[i - 1] >= p[i]; i--)
    ;

  if (i == 0)
    return 0;

  for (j = n - 1; j > i && p[i - 1] >= p[j]; j--)
    ;

  tmp = p[i - 1], p[i - 1] = p[j], p[j] = tmp;

  for (k = 0; k <= ((n - 1) - i) / 2; k++)
    tmp = p[i + k], p[i + k] = p[(n - 1) - k], p[(n - 1) - k] = tmp;

  return 1;
}

int main(void)
{
  float a, b, c;
  int n, *x, *y, *z, i, X, Y;

  scanf("%d", &n);
  x = (int *)malloc((n) * sizeof(int));
  y = (int *)malloc((n) * sizeof(int));
  z = (int *)malloc((n) * sizeof(int));
  for (i = 0; i < n; i++)
  {
    scanf("%d %d", &X, &Y);
    x[i] = X;
    y[i] = Y;
    z[i] = i;
  }

  double distsum = 0; //ある経路における距離の総和
  double distance = 0;
  double pat = 0; //順列の総数
  do
  {
    distsum = 0;
    for (i = 0; i < n - 1; i++)
    {
      distsum += dist(x[z[i]], x[z[i + 1]], y[z[i]], y[z[i + 1]]);
    }
    pat++;
    distance += distsum;
  } while (next_perm(z, n));

  printf("%.10f\n", distance / pat);
  return 0;
}

Measured memory_bytes: 128
import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		ArrayList<Integer> p = new ArrayList<>();
		for(int i=0;i<N;++i){
			p.add(sc.nextInt());
		}
		Collections.sort(p);
		int sum=0;
		for(int i=0;i<K;++i){
			sum += p.get(i);
		}
		System.out.println(sum);
	}
}


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

using namespace std;
typedef long long int ll;
typedef pair<int,int> pi;
typedef vector<int> vi;

void solve() {
    ll n;
    cin>>n;
    ll rem = n%1000;
    if(rem)
        cout<<(1000-rem)<<endl;
    else
        cout<<"0"<<endl;
    return;
}


int main()
{
    int testcases=1;
    // cin>>testcases;
    while(testcases--)
    {
        solve();
    }
    return 0;
}


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

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;

#define REP(i, n, m) for(ll i=n; i<(ll)m; ++i)
#define IREP(i, n, m) for(ll i=n-1; i>=m; --i)
#define rep(i, n) REP(i, 0, n)
#define irep(i, n) IREP(i, n, 0)
#define all(v) v.begin(), v.end()

int main(){
    ll n;    
    cin >> n;
    vll a(n), b(n);
    rep(i, n) cin >> a[i];
    rep(i, n) cin >> b[i];

    vll ta(a), tb(b);
    sort(all(ta), greater<ll>());
    sort(all(tb), greater<ll>());
    ll last = LONG_MAX;
    bool rep = false;
    rep(i, n){
        if(ta[i]>tb[i]){
            cout << "No" << endl;
            return 0;
        }
        if(last<=tb[i]) rep = true;
        last = ta[i];
    }
    if(rep) cout << "Yes" << endl;
    else{
        unordered_map<ll, ll> m;
        unordered_map<ll, ll> om;
        unordered_map<ll, ll> im;
        unordered_map<ll, ll> oim;
        rep(i, n) m.insert({ta[i], tb[i]});
        rep(i, n) im.insert({tb[i], ta[i]});
        rep(i, n) om.insert({a[i], b[i]});
        rep(i, n) oim.insert({b[i], a[i]});
        rep(i, n){
            if(i<n-1 && m[a[i]]==om[a[i]]){
                cout << "Yes" << endl;
                return 0;
            }
            ll a1 = a[i];
            ll b1 = m[a1];
            ll a2 = oim[m[a1]];
            ll b2 = om[a1];
            om[a1] = b1;
            om[a2] = b2;
            oim[b1] = a1;
            oim[b2] = a2;
        }
        cout << "No" << endl;
    }
}


Measured memory_bytes: 20644
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <vector>
using namespace std;
int main(){
  cin.tie(NULL);
  ios::sync_with_stdio(false);
  string s;
  cin>>s;
  if(s[0]=='A'){
    cout<<"T"<<"\n";
  }
  else if(s[0]=='T'){
    cout<<"A"<<"\n";
  }
  else if(s[0]=='C'){
    cout<<"G"<<"\n";
  }
  else{
    cout<<"C"<<"\n";
  }
  return 0;
}

Measured memory_bytes: 3568
#include <algorithm>
#include <cstdio>
#include <climits>
#include <vector>
using namespace std;

int main() {
    while(true) {
        int h,w,n; scanf("%d%d%d", &h, &w, &n);
        if(h==0) break;
        static int dp[1001][1001];
        for(int y = 0; y < h; y++)
            for(int x = 0; x < w; x++)
                dp[y][x] = 0;
        dp[0][0] = n-1;
        for(int y = 0; y < h; y++) {
            for(int x = 0; x < w; x++) {
                int dir; scanf("%d", &dir);
                int cnt = dp[y][x];
                dp[y+dir][x+(dir^1)] += cnt/2;
                dp[y+(dir^1)][x+dir] += (cnt+1)/2;
                dp[y][x] = (dir+cnt)&1;
            }
        }
        int ax=0,ay=0;
        while(ax<w && ay<h) {
            int dir = dp[ay][ax];
            ay += dir^1;
            ax += dir;
        }
        printf("%d %d\n", ay+1, ax+1);
    }
    return 0;
}

Measured memory_bytes: 4672
from collections import deque

N = int(input())
G = dict()

# Graph
for i in range(1, N + 1):
    G[i] = dict()

for _ in range(N - 1):
    u, v, w = map(int, input().split())
    G[u][v] = w
    G[v][u] = w

# start from 1
res = [2]*(N+1)
res[1] = 0
queue = deque([1])

while len(queue) > 0:
    u = queue.popleft()
    for v in G[u].keys():
        if res[v] == 2:
            if G[u][v] % 2 == 1:
                res[v] = 1 - res[u]
            else:
                res[v] = res[u]
            queue.append(v)

for i in range(1, N + 1):
    print(res[i])


Measured memory_bytes: 92260
def edu_dp_d_knapsack1():
    n, c = map(int, input().split())
    w, v = [], []
    for _ in range(n):
        a, b = map(int, input().split())
        w.append(a)
        v.append(b)
    dp = [[0] * (c + 1) for _ in range(n)]
    dp[0][w[0]] = v[0]
    for i in range(1, n):
        for j in range(0, c + 1):
            dp[i][j] = dp[i - 1][j]
            if j >= w[i]:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i])
    print(max(dp[n - 1]))
edu_dp_d_knapsack1()

Measured memory_bytes: 146392
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long int ll;
#define rep(i,n) for(int i=0;i<(int)n;i++)
int Min(int a, int b, int c) {
	if (a <= b) { return std::min(a, c); }
	else return std::min(b, c);
}
int Max(int a, int b, int c) {
	if (a >= b) { return std::max(a, c); }
	else return std::max(b, c);
}
int main(void) {
	int a, b; cin >> a >> b;
	int s, t, d; s = a + b; t = a * b; d = a - b;
	cout << Max(s, t, d) << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ALL(a) (a).begin(), (a).end()
const int64_t BIG_PRIME = 1000000007;

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

    float a1 = a * 12.5;
    float a2 = (a + 1) * 12.5;

    float b1 = b * 10;
    float b2 = (b + 1) * 10;

    // cout << a1 << "," << a2 << endl;
    // cout << b1 << "," << b2 << endl;

    int ans1 = ceil(max(a1, b1));
    int ans2 = min(a2, b2);

    if (ans1 < ans2)
    {
        cout << ans1 << endl;
    }
    else
    {
        cout << -1 << endl;
    }
}

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

int main() {
  string a;
  int b;
  cin >> a;
  b=0;
  if (a.at(0)=='1') {
    b++;
  }
  if (a.at(1)=='1') {
    b++;
  }
  if (a.at(2)=='1') {
    b++;
  }
  cout << b <<endl;
}


Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *

H, W, D = MAP()
A = [LIST() for _ in range(H)]

dic = defaultdict(tuple)

for y in range(H):
	for x in range(W):
		dic[A[y][x]] = (y+1, x+1)

power = [[] for _ in range(D)]
for i in range(1, H*W+1):
	if i <= D:
		power[i%D].append(0)
	else:
		idx = i%D
		tmp = abs(dic[i][0]-dic[i-D][0]) + abs(dic[i][1]-dic[i-D][1])
		power[i%D].append(tmp)

#print(power)
power_acc = []
for x in power:
	power_acc.append(list(accumulate(x)))
#print(power_acc)

Q = INT()
for _ in range(Q):
	L, R = MAP()
	if L%D:
		print(power_acc[R%D][R//D] - power_acc[L%D][L//D])
	else:
		print(power_acc[R%D][R//D-1] - power_acc[L%D][L//D-1])

Measured memory_bytes: 44872
#include<bits/stdc++.h>
using namespace std;
long long int pf(long long int n)
{long long int ans=0;
    while(n%2==0){ans++;n/=2;}
    for(long long int i=3;i<=sqrt(n);i+=2)
    {
        while(n%i==0){ans++;n/=i;}
    }
    if(n>2)
        ans++;
    return ans;
}
int main()
{ios_base::sync_with_stdio(false);
//cin.tie(NULL);
   long long int n,sum=0,curr_sum=0,ans=0,t;
   cin>>n;
   
   while(n!=0)
   {
    if(n%10==7)
        ans=1;
    n/=10;
   }
   if(ans)
    cout<<"Yes";
   else
    cout<<"No";
}


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

#define reps(v, f, l) for (int v = (f), v##_ = (l); v < v##_; ++v)
#define rep(v, n) reps(v, 0, n)
#define lep(v, n) reps(v, 1, n + 1)

using namespace std;

typedef long long int lint;

static inline int in(){ int x; scanf("%d", &x); return x; }
static inline lint inl(){ lint x; scanf("%lld", &x); return x; }
template<typename T> void show(T& a, char del='\n', char last='\n'){ rep(i, a.size() - 1) cout << a[i] << del; cout << a[a.size() - 1] << last; }

int main()
{
  int n;
  while (n = in()){
    vector<int> v;
    vector<int> counter(n + 1, 0);
    lep(i, n - 1) v.push_back(i * i % n);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    rep(i, v.size()){
      rep(j, v.size()){
        if (i == j) continue;
        int x = v[i] - v[j];
        if (x < 0) x += n;
        if (x > (n - 1) / 2) x = n - x;
        counter[x]++;
      }
    }
    lep(i, (n - 1) / 2){
      printf("%d\n", counter[i]);
    }
  }
  return 0;
}

Measured memory_bytes: 1340
while True:
    n = int(input())
    if n==0:break
    d = dict()
    for _ in range(n):
        l = list(map(int, input().split()))
        a, b = divmod((l[2]+l[4]+l[6]+l[8]), 60)
        d[l[0]] = (l[1]+l[3]+l[5]+l[7])*60 + a*60 + b
    for i in [0,1,-2]: print(sorted(d.items(), key=lambda x: x[1])[i][0])

Measured memory_bytes: 8352
#include <bits/stdc++.h>
#include <atcoder/dsu>
using namespace std;
using namespace atcoder;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
#define dame(a) {out(a);return 0;}
#define decimal cout<<fixed<<setprecision(15);
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef tuple<ll,ll,ll,ll> PPP;
typedef multiset<ll> S;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vvvvi=vector<vvvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vb=vector<bool>;
using vvb=vector<vb>;
const ll inf=1001001001001001001;
const ll INF=1001001001;
const ll mod=1000000007;
const double eps=1e-10;
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;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void noyes(T b){if(b)out("no");else out("yes");}
template<class T> void NoYes(T b){if(b)out("No");else out("Yes");}
template<class T> void NOYES(T b){if(b)out("NO");else out("YES");}
void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll modpow(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}

vi parent,rankk;
void init(ll n){
    parent=vi(n);
    rankk=vi(n);
    rep(i,n)parent[i]=i;
}
ll root(ll i){if(parent[i]==i)return i;return root(parent[i]);}
bool same(ll a,ll b){return root(a)==root(b);}
bool heigou(ll x,ll y){
    x=root(x);y=root(y);
    if(x==y)return false;
    if(rankk[x]<rankk[y])parent[x]=y;
    else parent[y]=x;
    if(rankk[x]==rankk[y])rankk[x]++;
    return true;
}

int main() {
    ll n,q;cin>>n>>q;
    init(n);
    rep(i,q){
        ll t,u,v;cin>>t>>u>>v;
        if(!t)heigou(u,v);
        else if(same(u,v))out(1);
        else out(0);
    }
}


Measured memory_bytes: 6308
#include <stdio.h>
void swap(int *a, int *b) 
{
	int temp = *a;
	*a = *b;
	*b = temp;	
}
int max(int a, int b) 
{
	return (a > b) ? a : b;
}
 
int min(int a, int b) 
{
	return (a < b) ? a : b;
}
 
int abs(int a) 
{
	return (a < 0) ? -a : a;
}
int main() {
	int n;
 
	scanf("%d", &n);
	char string[n];
	scanf("%s", string);
 
	int maximum = 0;
	int current = 0;
	for(int i = 0; i < n; i++) 
	{
		if(string[i] == 'D') 
		{
			current--;
		}
		else if(string[i] == 'I')
		{
			current++;
		}
		maximum = max(maximum, current);
	}
 
	printf("%d\n", maximum);
	return 0;
}
 

Measured memory_bytes: 1732
#include <bits/stdc++.h>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <iostream>
#include <numeric>
#define rep(i,n) for (int i = 0;i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define chmax(x,y) x = max(x,y)
int INF = 1e9;


int main(){
	string s,t,u;cin >> s >> t >> u;
	cout << s[0] << t[0] << u[0] << endl;
} 


Measured memory_bytes: 3604
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
#include<set>
#define ll long long
using namespace std;
int main() {
	string s;
	cin >> s;
	ll x = 700;
	for (ll i = 0; i < 3; i++) {
		if (s[i] == 'o') {
			x += 100;
		}
	}

	
	cout << x<< endl;

}

Measured memory_bytes: 256
s = input()
k = int(input())
sub = set([])
L = len(s)
for i in range(L) :
    for j in range(1, k+1) :
        if i + j <= L :
            sub.add(s[i:i+j])

sub = list(sub)
sub.sort()
print(sub[k-1])

Measured memory_bytes: 4464
//27
#include<iostream>

using namespace std;

char s[501];
int i;

bool cls(){
  int ap[128]={};
  bool r=true;
  for(int j=0;j<3;j++){
    int f=1;
    if(s[i]=='~'){
      f=-1;
      i++;
    }
    r&=ap[s[i]]*-1!=f;
    ap[s[i]]=f;
    i+=2;
  }
  i--;
  return r;
}

bool exp(){
  if(s[i]=='\0'){
    return false;
  }else{
    i++;
    if(cls()){
      return true;
    }else{
      i++;
      if(s[i]=='|'){
	i++;
	return exp();
      }else{
	return false;
      }
    }
  }
}

int main(){
  while(cin>>s,s[0]!='#'){
    i=0;
    cout<<(exp()?"yes":"no")<<endl;
  }
  return 0;
}
  
  

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

int main() {
    int n, h, ans=0, am=0;
    cin >> n >> h;
    vector<int> a(n), b(n);

    for(int i=0; i<n; i++) {
        int x, y;
        cin >> x >> y;
        a[i]=x;
        am=max(a[i], am);
        b[i]=y;
    }
    sort(b.begin(), b.end());
    reverse(b.begin(), b.end());
    for(int i=0; i<n; i++) {
        if(b[i]>am) {
            ans++;
            h-=b[i];
            if(h<=0) break;
        }
    }
    if(h>0){
        ans+=(h+am-1)/am;
    }
    cout << ans;
}

Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include<math.h>
#include<list>
#include <algorithm>
#include<set>
#include<vector>
#include<math.h>
#include<map>
#include<string>
#include <numeric>
#include <queue>
#include <sstream>

using namespace std;
using ll = long long;
using vll = vector<long long>;
using sll = set<long long>;

template<typename T>
T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T>
T lcm(T a, T b) { return a / gcd(a, b) * b; }

template<typename T>
map<T, T> primeFactor(T n) {
	map<T, T> res;
	for (T i = 2; i * i <= n; ++i) {
		while (n % i == 0) {
			res[i] ++;
			n /= i;
		}
	}
	if (n != 1) res[n] = 1;
	return res;
}

template<typename T>
bool IsPrimeNumber(T num)
{
	if (num <= 2) return true;
	else if (num % 2 == 0) return false;

	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2)
	{
		if (num % i == 0)
		{
			return false;
		}
	}

	return true;
}


#define in(x) cin >> x
#define out(x) cout << x
#define outn(x) cout << x << '\n'
#define outs(x) cout << x << ' '
#define rep(i,s,e) for(long i=s;i<e;i++)
#define repeq(i,s,e) for(long i=s;i<=e;i++)



int main() {
	ll n;
	in(n);

	for (ll i = sqrt(n); i > 0; i--) {
		if (n % i == 0) {
			outn(i + (n / i) - 2);
			return 0;
		}
	}

	return 0;

}


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

namespace AOJ
{
    class Program
    {
        static void Main(string[] args)
        {
            foreach (var h in Enumerable.Range(0, 10).Select(_ => Console.ReadLine())
                                        .Select(int.Parse)
                                        .OrderByDescending(h => h)
                                        .Take(3))
            {
                Console.WriteLine(h);
            }
        }
    }
}

Measured memory_bytes: 6408
import math

#n = int(input())
#a, b = map(int, input().split())
#a, b, c = map(int, input().split())
#a, b, c, d = map(int, input().split())
#arr - list(map(int, input().split()))
s = input()
if s == 'ABC':
  print('ARC')
else:
  print('ABC')

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

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
# def LIST(): return list(map(str, input().split()))
# def LIST(): return list(input())

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, W = MAP()
L = [LIST() for _ in range(N)]

V = 0
# sum_v = 0
for w, v in L:
    V += v

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

# V = sum(v)
for i in range(1, N+1):
    for j in range(0, V+1):
        # j，1スタートだと16,0スタートだと17になる
        w = L[i-1][0]
        v = L[i-1][1]
        if j - v >= 0:
            dp[i][j] = min(dp[i-1][j - v] + w, dp[i][j])
        dp[i][j] = min(dp[i][j], dp[i-1][j])

# ans = 0
for sum_v in range(V+1):
    # print(dp[N][sum_v])
    # print(dp)
    if dp[N][sum_v] <= W:
        ans = sum_v
print(ans)

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

// -------------------------------
// 関数定義

// 各桁の和を計算する。
int CalcSumOfDigit(int n);


// -------------------------------

int main() {
  int n = 0;
  int d[110];

  memset(d,0,sizeof(d));

  cin >> n;

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

  sort(d , d + n);

  int x = 1;

  for(int i = 0;i<n-1;i++)
  {
    if(d[i] < d[i+1])
    {
      x++;
    }
  }
  
  cout << x;

  return 0;
}



// ********************************************************************************************
// ********************************************************************************************
int CalcSumOfDigit(int n)
{
  int s = 0;
  while(n)
  {
    s += n % 10;
    n = n / 10;
  }
  return s;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    static int count = 0;
    static int n;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = Integer.parseInt(sc.next());
        dfs(0,0);
        System.out.println(count);
        sc.close();
    }

    public static void dfs(long val,int flag){
        if(val > n)return;
        if(flag == 7)count++;

        dfs(val*10+3,flag | 1);
        dfs(val*10+5,flag | 2);
        dfs(val*10+7,flag | 4);
    }


    
}

Measured memory_bytes: 23380
//{{{
#include <bits/stdc++.h>
using namespace std;
#define repX(a,b,c,x,...) x
#define repN(a) repX a
#define rep(...) repN((__VA_ARGS__,rep3,rep2,loop))(__VA_ARGS__)
#define rrep(...) repN((__VA_ARGS__,rrep3,rrep2))(__VA_ARGS__)
#define loop(n) rep2(i_,n)
#define rep2(i,n) rep3(i,0,n)
#define rep3(i,begin,end) for(int i=(int)(begin),i##_end=(int)(end);i<i##_end;++i)
#define rrep2(i,n) rrep3(i,n,0)
#define rrep3(i,begin,end) for(int i=(int)(begin-1),i##_end=(int)(end);i>=i##_end;--i)
#define foreach(x,a) for(auto&x:a)
using ll=long long;
const ll mod=(ll)1e9+7;
//}}}

const int inf = 100000000;

int l[8];
int N, A, B, C;

int g(vector<int> v, int target){
  if(v.size() == 0) return inf;
  int sum = 0;
  rep(i, v.size()){
    sum += v[i];
  }
  return (v.size() - 1) * 10 + abs(sum - target);
}

int f(vector<int> v[4]){
  int res = 0;
  res += g(v[0], A);
  res += g(v[1], B);
  res += g(v[2], C);
  return res;
}

int main(){
  cin >> N >> A >> B >> C;
  rep(i, N) cin >> l[i];
  int ans = inf;
  rep(i, pow(4, N)){
    int id = i;
    vector<int> v[4];
    rep(j, N){
      v[id % 4].push_back(l[j]);
      id /= 4;
    }
    ans = min(ans, f(v));
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	vector<float> arr;
	for(int i =0;i<n;i++)
	{
		float a;
		cin>>a;
		arr.push_back(a);
	}
	sort(arr.begin(),arr.end());
	unordered_map<int, int> cnt;
	for(int i =0;i<arr.size();i++)
	{
		float check = arr[i];
		if(check < 165.0)
			cnt[1]++;
		else if(check >= 165.0 && check <170.0)
			cnt[2]++;
		else if(check >= 170.0 && check < 175.0)
			cnt[3]++;
		else if(check >= 175.0 && check < 180.0)
			cnt[4]++;
		else if(check >= 180.0 && check < 185.0)
			cnt[5]++;
		else
			cnt[6]++;
	}
	for(int i =1;i<=6;i++)
	{
		cout<<i<<":";
		int size = cnt[i];
		for(int j = 0; j < size;j++)
			cout<<"*";
			
		cout<<endl;
	}
	return 0;
}


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

int main() {
  string s, t1, t2;
  cin >> s;
  int N = s.size();
  for (int i = 0; i < N; i++) {
    if (s[i] != 'x') t1 += s[i];
  }
  if (t1 == "") {
    cout << 0 << endl;
    return 0;
  }
  t2 = t1;
  reverse(t2.begin(),t2.end());
  if (t1 != t2) {
    cout << -1 << endl;
    return 0;
  }
  int c = 0;
  int n = t1.size();
  int m = (n+1)/2;
  vector<int> countx(m,0);
  for (int i = 0; i < N; i++) {
    if (s[i] != 'x') c += 1;
    else countx[c] += 1;
    if (c == m) break;
  }
  c = 0;
  for (int i = N-1; i > 0; i--) {
    if (s[i] != 'x') c += 1;
    else countx[c] -= 1;
    if (c == m) break;
  }
  int ans = 0;
  for (int e : countx) ans += abs(e);
  cout << ans << endl;
}

Measured memory_bytes: 3936
package main

import(
	"fmt"
	"math"
	"strconv"
)

func main(){
  var num1, num2 int
  fmt.Scanf("%d %d", &num1, &num2)
  num11 := strconv.Itoa(num1)
  num21 := strconv.Itoa(num2)
  convnum, _ := strconv.Atoi(num11 + num21)
  var ansnum float64 = math.Sqrt(float64(convnum))
  if math.Round(ansnum) == ansnum{
    fmt.Println("Yes")
  }else{
    fmt.Println("No")
  }
}


Measured memory_bytes: 1836
#include "bits/stdc++.h"
using namespace std;
using ll     = long long;
using pii    = pair<int, int>;
using pll    = pair<ll, ll>;
using vi     = vector<int>;
using vl     = vector<ll>;
using vvi    = vector<vi>;
using vvl    = vector<vl>;
const ll INF = 1LL << 60;
const ll MOD = 1000000007;
template <class T>
bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}
template <class C>
void print(const C &c, std::ostream &os = std::cout) {
    std::copy(std::begin(c), std::end(c), std::ostream_iterator<typename C::value_type>(os, " "));
    os << std::endl;
}

int main() {
    int n;
    cin >> n;
    int il(0), ir(n);
    string l, r, curr;
    cout << 0 << endl;
    cin >> curr;
    r = l = curr;
    if (l == "Vacant")
        return 0;
    for (int i = 0; i < 20; ++i) {
        int mid = (il + ir) / 2;
        cout << mid << endl;
        cin >> curr;
        if (curr == "Vacant")
            return 0;

        if ((curr != l && (mid - il) % 2 == 0) || (curr == l && (mid - il) % 2 == 1)) {
            ir = mid;
            r  = curr;
        } else if ((curr != r && (ir - mid) % 2 == 0) || (curr == r && (ir - mid) % 2 == 1)) {
            il = mid;
            l  = curr;
        }
    }
    return 0;
}

Measured memory_bytes: 852
#include <iostream>
#include <cctype>
#include <cstdlib>
#include <string>
#include <algorithm>
#define rep(i, n) for(int i = 0; i < n; ++i)
using namespace std;

int comp(const void* a, const void* b){
	return *(int*)a - *(int*)b;
}

int main() {
	int x, a, b;
	cin >> x >> a >> b;
	if(a-b >= 0){
		cout << "delicious" << endl;
	}else if(x >= b-a){
		cout << "safe" << endl;
	}else{
		cout << "dangerous" << endl;
	}
}

Measured memory_bytes: 256
n=int(input())
*x,=map(int,input().split())
s=sorted(x)
m=(s[n//2]+s[(n//2)-1])/2
for i in x:
	if i<m:
		print(s[n//2])
	elif i==m:
		print(i)
	else: 
		print(s[(n//2)-1])

Measured memory_bytes: 26772
#include <cmath>
#include <cstdio>
#include <vector>
#include <iterator>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <stdio.h>
#include <functional>
#include <chrono>
using namespace std;

#define rep(i,s,n) for(ll i=s;i<(n);++i)
using ll = long long;
using pll = pair<ll, ll>;
constexpr ll INF = (1LL << 60);
constexpr ll MAX_INF = 9223372036854775807;
//constexpr ll MOD = (1e9 + 7);
constexpr ll MOD = (998244353);

using vl = vector<ll>;
using vvl = vector<vector<ll>>;

template<class T>
vector<vector<T>> vvt(T init, ll m, ll n) {
	vector<vector<T>> ans = vector<vector<T>>(m, vector<T>(n, init));
	return move(ans);
}

template<class T>
vector<T> vt(T init,ll n) {
	vector<T> ans = vector<T>(n, init);
	return move(ans);
}

template<class T>
T maxVec(vector<T> &v) {
	T ans = -INF;
	rep(i,0, v.size()) {
		ans = max(ans, v[i]);
	}
	return ans;
}

// 素数判定
bool judge(ll n) {
	for (ll i = 2; i * i <= n; i++) if (n %= i)return false;
	return true;
}


template <class C>
void print(const C& c, std::ostream& os = std::cout)
{
	std::copy(std::begin(c), std::end(c), std::ostream_iterator<typename C::value_type>(os, ", "));
	os << std::endl;
}
/*
ll count(ll n,ll r) {
	ll ans = 0,check = 1;
	rep(i,0, r) {
		if ((n & check) > 0) {
			ans++;
		}
		check = check << 1;
	}
	return ans;
}
*/
bool sortreverse(ll a, ll b) {
	return a > b;
}

bool kansu(pll a, pll b) {
	return a.first < b.first;
}

ll kiriage(ll a, ll b) {
	if (a % b == 0)return a / b;
	return a / b + 1;
}

ll n,m,x,y,t,q;
vl a, b, c, d;
vl h,s,ls,mihon(100000);

vl stack(10);

ll solv(ll idx,ll before) {
	if (idx == n) {
		ll ref = 0;
		rep(i, 0, q) {
			if (stack[b[i] - 1] - stack[a[i] - 1] == c[i]) {
				ref += d[i];
			}
		}
		//print(stack);
		return ref;
	}

	ll ref = 0;
	rep(i, before, m+1) {
		stack[idx] = i;
		ref = max(ref, solv(idx + 1, i));
	}
	return ref;
}

int main() {
	cin >> n >> m >> q;
	a = vl(q); b = vl(q); c = vl(q); d = vl(q);
	rep(i, 0, q) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	}

	printf("%lld\n", solv(0, 1));
}

Measured memory_bytes: 3904
# -*- coding: utf-8 -*-
a,b,n = map(int,input().split())
"""
ans = 0
tmp = min(b, n)
for x in range(int(pow(n, 0.5)) + 1, n+1):
    #print(x)
    tmp1 = (a * x) // b - (a * (x // b))
    if tmp1 >= ans:
        ans = tmp1
print(ans)
"""

x = min(b-1, n)
#print(x)
ans = (a * x) // b - (a * (x // b))
print(ans)

Measured memory_bytes: 61752
using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;
using E = System.Linq.Enumerable;
 
class Program
 {
        static void Main(string[] args)
        {
          //入力を受け取る
          var ABC = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
          int A = ABC[0];
          int B = ABC[1];
          int C = ABC[2];
          
          if(A<B){
            var tmp = A;
            A = B;
            B = tmp;
          }
          if(A<C){
            var tmp = A;
            A = C;
            C = tmp;
          }
          var sa = (A-C)+(A-B);
          
          if(sa%2 == 0){
            Console.WriteLine(sa/2);
          }else{
            Console.WriteLine(sa/2+2);
          }
        }
  
}


Measured memory_bytes: 13396
n = int(input())
A = list(map(int, input().split()))

L = A[0:n]
R = A[2*n:3*n]
import heapq
sl = sum(L)
heapq.heapify(L)
sls = [0]*(n+1)
sls[0] = sl
for i in range(n, 2*n):
    heapq.heappush(L, A[i])
    x = heapq.heappop(L)
    sl += A[i]-x
    sls[i-n+1] = sl
#print(sls)

sr = sum(R)
R = [-c for c in R]
heapq.heapify(R)
srs = [0]*(n+1)
srs[-1] = sr
for i in reversed(range(n, 2*n)):
    heapq.heappush(R, -A[i])
    x = -heapq.heappop(R)
    sr += A[i]-x
    srs[i-n] = sr
#print(srs)
ans = - 10**18
for i in range(n+1):
    ans = max(ans, sls[i]-srs[i])
print(ans)

Measured memory_bytes: 120208
Q, H, S, D = map(int, input().split())
N = int(input())

c_05 = min(2*Q, H)
c_1 = min(2*c_05, S)

if 2*c_1 <= D:
    print(c_1 * N)
else:
    if N % 2 == 0:
        print(D * (N//2))
    else:
        print(D * (N//2) + c_1)

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

int main(){
	double l1, l2, l3, l4, l5, l6, l7, l8, l9, l10;
	double v1, v2;
	char c;
	while(cin >> l1 >> c >> l2 >> c >> l3 >> c >> l4
		>> c >> l5 >> c >> l6 >> c >> l7 >> c >> l8
		>> c >> l9 >> c >> l10 >> c >> v1 >> c >> v2)
	{
		double l[] = {
			0,l1,l2,l3,l4,l5,
			l6,l7,l8,l9,l10
		};
		double max_length = l1 + l2 + l3 + l4 + l5
							+l6 + l7 + l8 + l9 + l10;
		for(int i = 1; i <= 10;i++){
			max_length -= (l[i] + (v2 * l[i] / v1));
			if(max_length <= 0){
				cout << i << endl;
				break;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 0
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception{
		Scanner scn = new Scanner(System.in);
		int[] a = new int[9];
		for(int i=0; i<a.length; ++i){
			a[i] = scn.nextInt();
		}
      	int n = scn.nextInt();
		int[] b = new int[n];
		for(int i=0; i<b.length; ++i){
			b[i] = scn.nextInt();
		}
      	for(int i=0; i<a.length; ++i){
			for(int j=0; j<b.length; ++j){
				if(a[i]==b[j]){
                  a[i]=0;
                }
			}
		}
      	int check = 0;
      	if(a[0]==0 && a[1]==0 && a[2]==0){
          check = 1;
        }
      	if(a[3]==0 && a[4]==0 && a[5]==0){
          check = 1;
        }
      	if(a[6]==0 && a[7]==0 && a[8]==0){
          check = 1;
        }
      	if(a[0]==0 && a[3]==0 && a[6]==0){
          check = 1;
        }
      	if(a[1]==0 && a[4]==0 && a[7]==0){
          check = 1;
        }
      	if(a[2]==0 && a[5]==0 && a[8]==0){
          check = 1;
        }
      	if(a[0]==0 && a[4]==0 && a[8]==0){
          check = 1;
        }
      	if(a[2]==0 && a[4]==0 && a[6]==0){
          check = 1;
        }
      	if(check==0){
          System.out.println("No");
        }else{
          System.out.println("Yes");
        }
	}
}

Measured memory_bytes: 35740
#!/usr/bin/env python3

def fact_of_two(i):
    for j in range(10000):
        if i % (2 ** j) != 0:
            break
    assert j >= 1
    return j - 1

n = int(input())
ai = list(map(int, input().split()))
assert len(ai) == n

mi = 999999
for a in ai:
    mi = min(mi, fact_of_two(a))

print(mi)



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

typedef long long ll;
typedef unsigned long long ull;

template <typename T>
T gcd( T m, T n ){
    if ( ( 0 == m ) || ( 0 == n ) ) return 0;

    while( m != n ){
        if ( m > n ) m %= n;
        else         n %= m;

        if(m == 0) return n;
        if(n == 0) return m;
    }
    return m;
}

template <typename T>
vector<T> PrimeFactorization(T x){
    vector<T> res;
    T v = 2;
    while( v * v <= x){
        if(x%v != 0){
            v++;
        }else{
            res.push_back(v);
            x /= v;
        }
    }
    if(x!=1) res.push_back(x);
    sort(res.begin(), res.end());
    return res;
}

int main()
{
    ll A, B;
    cin >> A >> B;
    auto C = gcd(A, B);
    auto pf = PrimeFactorization(C);
    set<ll> pf_set(pf.begin(), pf.end());
    cout<<pf_set.size()+1<<endl;

    return 0;
}

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

#define ll long long
#define endl "\n"
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define f first
#define s second
#define vecll vector<ll>
#define pairll pair<ll,ll>
#define vecpairll vector<pair<ll,ll>>
#define mapllll map<ll,ll>
#define mapstrll map<string,ll>
#define mapllvecll map<ll,vecll>
#define setll set<ll>
#define fio ios_base::sync_with_stdio (false); cin.tie (NULL); cout.tie(NULL);

using namespace std;

ll const N=1e5+5;
ll const inf=1e18+5;
ll const MOD=1e9+7;

ll t,n,m,x,y,z,w,k;

int main()
{
    fio

    cin>>n;
    
    while(n)
    {
        if((n%10) == 7)
        {
            cout<<"Yes";
            return 0;
        }
        n /= 10;
    }
    cout<<"No";
    return 0;
}



Measured memory_bytes: 3652
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int h = sc.nextInt();
		int w = sc.nextInt();
		char[][] weather = new char[h][w + 1];
		int[][] result = new int[h][w + 1];
		for (int i = 0; i < h; i++) {
			weather[i] = sc.next().toCharArray();
		}
		int cnt;
		for(int i = 0; i < h; i++) {
			cnt = -1;
			for(int k = 0; k < w; k++) {
				if(weather[i][k] == 'c') {
					cnt = 0;
					result[i][k] = cnt;
					cnt = cnt + 1;
				} else if(cnt >= 0) {
					result[i][k] = cnt;
					cnt = cnt + 1;
				} else {
					result[i][k] = cnt;
				}
				
			}
		}
		for(int i = 0; i < h; i++) {
			for(int k = 0; k < w; k++) {
				if(k == w - 1) {
					System.out.println(result[i][k]);
				} else {
					System.out.print(result[i][k] + " ");
				}
			}
		}
	}

}

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

int main(){
    
    // 1. 入力情報.
    char c[55];
    scanf("%s", c);
    int l = strlen(c) - 8; // "FESTIVAL" 分 を マイナス.
    
    // 2. 出力.
    for(int i = 0; i < l; i++) printf("%c", c[i]);
    printf("\n");
    return 0;
    
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner scan = null;
		try{
			scan = new Scanner(System.in);
			while(true){
				 String str = scan.next();
				 if(str.equals("-"))break;
				 int n = scan.nextInt();
				 for(int i = 0 ;i < n;i++){
					 int data = scan.nextInt();
					 str = str.substring(data,str.length()) + str.substring(0,data);
				 }
				 System.out.println(str);
			}
		}finally{
			if(scan!=null)scan.close();
		}
	}
}

Measured memory_bytes: 18296
#include <iostream>
#include <cstdio>
#include <cctype>
#include <queue>
#include <vector>
#define il inline
#define vd void
#define rg register
#define rep(i,x,y) for(rg int i=x;i<=y;++i)
#define drp(i,x,y) for(rg int i=x;i>=y;--i)
using namespace std;
const int Len=2333333;
char buf[Len],*p1=buf,*p2=buf,duf[Len],*q1=duf;
il char gc(); il int rd(); il vd pc(char c); il vd rt(int x); il vd flush();
int n,m,a,b,ans;
vector <int> V[100005];
priority_queue <int> q;
int main(){
	n=rd(),m=rd();
	rep(i,1,n) a=rd(),b=rd(),V[a].push_back(b);
	drp(i,m-1,0){
		for(rg int j=0;j<(int)V[m-i].size();++j) q.push(V[m-i][j]);
		if(!q.empty()) ans+=q.top(),q.pop();
	}
	rt(ans);
	return flush(),0;
}

il char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,Len,stdin),p1==p2)?-1:*p1++;}
il int rd(){char c;
	while(!isdigit(c=gc())&&c!='-');
	int f=c=='-'?c=gc(),1:0,x=c^48;
	while(isdigit(c=gc())) x=((x+(x<<2))<<1)+(c^48);
	return f?-x:x;
}
il vd pc(char c){q1==duf+Len&&fwrite(q1=duf,1,Len,stdout),*q1++=c;}
il vd rt(int x){x<0?pc('-'),x=-x:0,pc((x>=10?rt(x/10),x%10:x)+48);}
il vd flush(){fwrite(duf,1,q1-duf,stdout);}

Measured memory_bytes: 9472
li = list(map(int,input().split()))
la = list(map(int,input().split()))

b = 0

for num in range(0,li[0]):
    b += la[num]

c = b/4/li[1]

d = 0

for i in range(0,li[0]):
    if la[i] >= c:
        d += 1

if d >= li[1]:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3060
#include <iostream>

using namespace std;

int main()
{
    int a{0},b{0};
    while (cin>>a>>b){
        if ((a+b) % 3 == 0 && a && b)cout<<"Possible"<<endl;
        else if (a%3==0 || b%3 == 0)cout<<"Possible"<<endl;
        else cout<<"Impossible"<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
	ll a,b;
	cin>>a>>b;
	ll k = (a+b)/2;
	if(abs(a-k)==abs(b-k))
		cout<<k<<endl;
	else cout<<"IMPOSSIBLE"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <string.h>
#include <vector>
#include <algorithm>
#include <random>
using namespace std;
typedef long long ll;

int main()
{
	int n;
	cin >> n;
	vector<int>v(n);
	for (auto&i : v)cin >> i;
	ll sum = 0;

	for (int i = 1; i < n; i++) 
		if (v[i - 1] > v[i]) {
			sum += v[i - 1] - v[i];
			v[i] = v[i - 1];
		}
	cout << sum;
}


Measured memory_bytes: 3992
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()

MOD = 10 ** 9 + 7
N, M = inm()

t = [1]


def fact(x):
    if x >= len(t):
        for i in range(len(t), x + 1):
            t.append(t[-1] * i % MOD)
    return t[x]


def solve():
    k = 2
    m = M
    fs = []
    while k * k <= m:
        cnt = 0
        while m % k == 0:
            m //= k
            cnt += 1
        if cnt:
            fs.append(cnt)
        k += 1
    if m > 1:
        fs.append(1)

    ni = pow(fact(N - 1), MOD - 2, MOD)
    ans = 1
    for c in fs:
        ans = ans * fact(c + N - 1) % MOD
        ans = ans * ni % MOD
        ans = ans * pow(fact(c), MOD - 2, MOD) % MOD
    return ans


print(solve())


Measured memory_bytes: 44784
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i < (b); i++)
#define rrep(i, a, b) for (int i = a; i >= (b); i--)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <class T>
inline bool chmin(T& a, T b) {
   if (a > b) {
      a = b;
      return true;
   }
   return false;
}
template <class T>
inline bool chmax(T& a, T b) {
   if (a < b) {
      a = b;
      return true;
   }
   return false;
}
void hr() {
   cerr << "--------------" << endl;
}
const int INF = 1001001001;
const int MOD = 1000000007;

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

   int n, m, k;
   cin >> n >> m >> k;
   vector<int> a(n), b(m);
   rep(i, 0, n) cin >> a[i];
   rep(i, 0, m) cin >> b[i];

   ll t = 0;
   rep(i, 0, m) t += b[i];
   int b_i = m;
   int ans = 0;
   rep(i, 0, n + 1) {
      while (b_i > 0 && t > k) {
         b_i--;
         t -= b[b_i];
      }
      if (t > k) break;
      ans = max(ans, i + b_i);
      if (i == n) break;
      t += a[i];
   }
   cout << ans << endl;
   return 0;
}

Measured memory_bytes: 4740
#include <bits/stdc++.h>
using namespace std;
#define null NULL
#define mp make_pair
#define pb(a) push_back(a)
#define sz(a) ((int)(a).size())
#define all(a) a.begin() , a.end()
#define fi first
#define se second
#define relaxMin(a , b) (a) = min((a),(b))
#define relaxMax(a , b) (a) = max((a),(b))
#define SQR(a) ((a)*(a))
#define PI 3.14159265358979323846
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;

void No(){
  printf("No\n");
  exit(0);
}

int n;
vector<pair<int, pii>> nal;

int main(){
  scanf("%d", &n);
  nal.resize(n + 1);

  nal[0] = mp(0, mp(0, 0));
  for(int i = 1;i <= n;++i)
    scanf("%d%d%d", &nal[i].fi, &nal[i].se.fi, &nal[i].se.se);

  for(int i = 1;i <= n;++i){
    int dlt = abs(nal[i].se.fi - nal[i - 1].se.fi) +
              abs(nal[i].se.se - nal[i - 1].se.se);
    int have = nal[i].fi - nal[i - 1].fi;
    if(have < dlt || ((have - dlt) & 1))
      No();
  }

  printf("Yes\n");

  return 0;
}


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

namespace Lsk {
#define _auto_ template <typename T>

// fast io
#define writesp(x) (write(x), putchar(' '))
#define writeln(x) (write(x), putchar('\n'))
_auto_ inline void read(T &x) {
	x = 0; bool sgn = false; char ch = getchar();
	while(!isdigit(ch)) (ch == '-') && (sgn = true), ch = getchar();
	while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
	if(sgn) x = -x;
}
_auto_ inline void write(T x) {
	if(x < 0) putchar('-'), x = -x;
	static char buf[40]; int o = 0;
	for(x; x > 9; x /= 10, ++o) buf[o] = x % 10 + '0'; buf[o] = x + '0';
	for(o; ~o; --o) putchar(buf[o]);
	return;
}

// cmin / cmax / swap
_auto_ inline void cmin(T &u, const T v) { if(u > v) u = v; }
_auto_ inline void cmax(T &u, const T v) { if(u < v) u = v; }
_auto_ inline T min(const T u, const T v) { return u < v ? u : v; }
_auto_ inline T max(const T u, const T v) { return u > v ? u : v; }
_auto_ inline void swap(T &u, T &v) { T tmp(u); u = v, v = tmp; }

// math
const int mod = 998244353, mod_2 = 1996488706;
//const int mod = 1000000007, mod_2 = 2000000014;
//const int mod = 1000000009, mod_2 = 2000000018;
_auto_ inline T abs(T x) { return x > 0 ? x : -x; }
_auto_ inline T gcd(T u, T v) {	return v ? gcd(v, u % v) : u; }
_auto_ inline T Mod(T u) { return u >= mod_2 ? u % mod : (u > mod ? u - mod : u); }
_auto_ inline T inmod(T u) { return u >= mod ? u - mod : (u < 0 ? u + mod : u); }
inline long long fpm(long long base, long long mi) {
	long long res = 1;
	while(mi) {
		if(mi & 1) res = Mod(res * base);
		base = Mod(base * base), mi >>= 1;
	}
	return res;
}

} using namespace Lsk;
#define N 150

int n;
bool f[N];

int main() {
	for(int i = 1; i <= 9; ++i)
		for(int j = 1; j <= 9; ++j)
			f[i * j] = true;	
	read(n);
	puts(f[n] ? "Yes" : "No");
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <utility>
#include <cassert>

using namespace std;
typedef long long ll;

void solve1(ll k, ll x, ll y, vector<pair<ll, ll>>& ans){
    ans.push_back(make_pair(x, - (k - x)));
    ans.push_back(make_pair((k + 3 * x - y) / 2, (x + y - k) / 2));
    ans.push_back(make_pair(x, y));
}

void solve2(ll k, ll x, ll y, ll n, ll d, vector<pair<ll, ll>>& ans){
    ll cx = 0, cy = 0;

    while(cy - k > - d){
        cy -= k;
        ans.push_back(make_pair(cx, cy));
    }

    cx = k - (d + cy);
    cy = -d;
    ans.push_back(make_pair(cx, cy));

    while(cx + k < x){
        cx += k;
        ans.push_back(make_pair(cx, cy));
    }

    cy += k - (x - cx);
    cx = x;
    ans.push_back(make_pair(cx, cy));

    while(cy < y){
        cy = min(y, cy + k);
        ans.push_back(make_pair(cx, cy));
    }
    assert(cx == x && cy == y);
}

void solve(ll k, ll x, ll y, vector<pair<ll, ll>>& ans){
    if(x + y == k){
        ans.push_back(make_pair(x, y));
        return;
    }

    ll n = (x + y) / k + (ll)((x + y) % k > 0);
    if(n <= 1){ n = 2; }
    if((n * k - (x + y)) % 2 != 0){ n++; }
    ll d = (n * k - (x + y)) / 2;

    if(d % k + x < k){
        solve1(k, x, y, ans);
    }else{
        solve2(k, x, y, n, d, ans);
    }
}

int main(){
    ll k, x, y;
    cin >> k >> x >> y;

    bool nx = false, ny = false, txy = false;
    if(x < 0){
        nx = true;
        x *= -1;
    }
    if(y < 0){
        ny = true;
        y *= -1;
    }
    if(x < y){
        txy = true;
        ll tmp = x;
        x = y;
        y = tmp;
    }

    if(k % 2 == 0 && (x + y) % 2 == 1){
        cout << -1 << endl;
        return 0;
    }

    vector<pair<ll, ll>> ans;
    solve(k, x, y, ans);

    cout << ans.size() << endl;
    for(auto p : ans){
        ll u = p.first;
        ll v = p.second;
        if(txy){
            u = p.second;
            v = p.first;
        }
        if(ny){ v *= -1; }
        if(nx){ u *= -1; }
        cout << u << ' ' << v << endl;
    }

    return 0;
}


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

using namespace std;

int main(){
	int n; cin >> n;
	int res=0;
	int g;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			for(int k=1; k<=n; k++){
				g = gcd(i, gcd(j, k));
				res += g;
			}
		}
	}
	cout << res ;
	return 0;
}

Measured memory_bytes: 3664
N = int(input())
A = sorted(map(int, input().split())) 

A_even = [i for i in A if i % 2 == 0]

A_even_35 = [i for i in A_even if i % 3 != 0and i%5!=0]
if len(A_even_35)==0:
  print("APPROVED")
else:
  print("DENIED")

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

using namespace std;
int a, b, c, k;

int main(){
  cin >> a >> b >> c >> k;
  int sum = a+b+c;
  int maxa = max({a, b, c});
  sum -= maxa;
  for(int i = 0; i < k; i++){
    maxa = maxa*2;
  }
  sum += maxa;
  cout << sum << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,k;
    cin>>n>>k;
    vector<int> v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }

    vector<int> dp(n+1,INT_MAX);
    dp[1]=0;
    dp[2]=abs(v[1]-v[0]);

    for(int i=3;i<=n;i++){
        for(int j=i-1;j>=i-k && j>=1;j--){
            dp[i]=min(dp[i],dp[j]+abs(v[j-1]-v[i-1]));
        }
    }
    cout<<dp[n];
    return 0;
}

Measured memory_bytes: 1024