akhauriyash/Code-Regression huggingface dataset:
#!/usr/bin/env python3
import sys
import functools
INF = float("inf")


@functools.lru_cache(None)
def hight(n):
    if n == 0:
        return 1
    else:
        return 2*hight(n-1)+3


@functools.lru_cache(None)
def paty(n):
    if n == 0:
        return 1
    else:
        return 2*paty(n-1)+1


def rec(n, x):
    # print(n, x)
    if n == 0:
        if x == 0:
            return 0
        else:
            return 1

    if x == 0:
        return 0
    elif x == 1:
        return 0
    elif x < hight(n-1)+2:
        return rec(n-1, x-1)
    elif x == hight(n-1)+2:
        return paty(n-1) + 1
    else:
        # print(paty(n-1)+1)
        return paty(n-1)+1 + rec(n-1, x-(hight(n-1)+2))


def solve(N: int, X: int):
    print(rec(N, X))

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    solve(N, X)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3684
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <cmath>
#include <functional>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define endl "\n"
#define fi first
#define se second
typedef long long ll;
#define traceV(v) for(auto x:v)cout<<x<<" ";cout<<endl
#define traceM(mp) for(auto x:mp)cout<<x.first<<" "<<x.second<<endl
#define MOD 1000000007
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;}

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

  ll N,M; cin>>N>>M;
  ll sum = 0;
  ll A;
  rep(i,M) {
    cin>>A; sum+=A;
  }

  if(sum>N) cout<<-1<<endl;
  else cout<<N-sum<<endl;

  return 0;
}


Measured memory_bytes: 3640
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;

int main() {
	int N;
	cin >> N;
	map<string, ll> cnt;
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		sort(s.begin(), s.end());
		cnt[s]++;
	}
	ll ans = 0;
	for (auto p : cnt) {
		ans += p.second*(p.second - 1) / 2;
	}
	cout << ans << endl;
}

Measured memory_bytes: 11136
#include<bits/stdc++.h>
#include<iostream>
#include <iomanip>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
//#define mpr make_pair
#define gap ' '
#define abs(x) ((x)>0?(x):-(x))
#define INF 1e18
#define mod 1000000007
#define inf 1e9
ll powr(ll m,ll n)
{
    if(m==1)
        return 1;
    if(n==0)
        return 1;
    if(n==1)
        return m%mod;
    if(n%2)
    {
        ll te=powr(m,n/2);
        return (((te*te)%mod)*(m%mod))%mod;
    }
    else
    {
        ll te=powr(m,n/2);
        return (te*te)%mod;
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int tc=1;
    //cin>>tc;
    int cs=0;
    while(tc--)
    {
      string s;
      cin>>s;
      ll sum=0LL;
      for(int i=0;i<s.size();i++)
        sum+=(s[i]-'0');
      if(sum%9) cout<<"No";
      else cout<<"Yes";
    }
}


Measured memory_bytes: 3752
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int X = sc.nextInt();
        int Y = sc.nextInt();

        int maxX = -101;
        int minY = 101;

        int currentX = -101;
        int currentY = -101;
        for (int i = 0; i < N; i++) {
            currentX = sc.nextInt();
            if (currentX > maxX) {
                maxX = currentX;
            }
        }
        for (int i = 0; i < M; i++) {
            currentY = sc.nextInt();
            if (currentY < minY) {
                minY = currentY;
            }
        }

        if (maxX < minY && maxX != minY && maxX > X && minY < Y) {
            System.out.println("No War");
        } else {
            System.out.println("War");
        }

        sc.close();
    }
}


Measured memory_bytes: 25172
#include<iostream>
using namespace std;
 
int main(){
  int A, B, C;
  int X, Y;
 
  cin >> A >> B >> C >> X >> Y;
 
  unsigned long long cost;
 
  if(2*C >= A+B){
    cost = A*X + B*Y;
  }
 
  else if (2*C <= A && 2*C <= B ){
    if (X<=Y) cost = 2*C*Y;
    else cost = 2*C*X;
  }

  else if (2*C>A && 2*C>B && 2*C<A+B){
    if(X<Y) cost = 2*C*X + B*(Y-X);
    else cost = 2*C*Y + A*(X-Y);
  }
 
  else if (A<B){
    if(Y>=X) cost = 2*C*Y;
    else cost = 2*C*Y + A*(X-Y);
  }
  else {
    if (X>=Y) cost = 2*C*X;
    else cost = 2*C*X + B*(Y-X);
  }
 
  cout << cost;
 
 
  return 0;
}

Measured memory_bytes: 256
N, M = [int(i) for i in input().split()]

S, G = [False] * N, [False] * N
for _ in range(M):
    a, b = [int(i) for i in input().split()]
    if a == 1:
        S[b - 1] = True
    if b == N:
        G[a - 1] = True

if any(s and g for s, g in zip(S, G)):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Measured memory_bytes: 6132
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_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


S = input()
cnt = 0
before = 1

if S == "RRR":
    print(3)
elif S in ["SSS"]:
    print(0)
elif S in ["SSR", "RSS", "SRS", "RSR"]:
    print(1)
elif S in ["SRR", "RRS"]:
    print(2)


# for s in S:
#     if s == 'R':
#         # cnt += 1
#         if before == 1:
#             cnt += 1
#         before = 1
#     else:
#         cnt += 0
#         before = 0
# print(cnt)
        


Measured memory_bytes: 10464
#include<iostream>
#include<vector>
using namespace std;
int main(){
	int n,a,b,num;
	string str;
	cin >> n >> a >> b;
	cin >> str;
	num = a+b;
	for(int i=0;i<str.size();i++){
		if(str[i]=='a'){
			if(num>0){
				num--;
				cout << "Yes\n";
			}
			else	cout << "No\n";
		}
		else if(str[i]=='b'){
			if(b>0&&num>0){
				b--;
				num--;
				cout << "Yes\n";
			}
			else	cout << "No\n";
		}
		else	cout << "No\n";
	}
}

Measured memory_bytes: 896
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = 1'000'000'007;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

template<class T, class ...Tail>
void tiedSort(vector<T> &a, vector<Tail>&... tail) {
	int n = a.size();
	using S = tuple<T, Tail...>;
	vector<S> s(n);
	for (int i = 0; i < n; i++)
		s[i] = make_tuple(a[i], tail[i]...);
	sort(s.begin(), s.end());
	for (int i = 0; i < n; i++)
		tie(a[i], tail[i]...) = s[i];
}

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

	vector<int> a(N), b(N); rep(i, 0, N) {
		cin >> a[i] >> b[i];
	}

	using T = tuple<int, int, int>;
	vector<T> v;
	rep(i, 0, N) {
		v.emplace_back(a[i], 0, i);
		v.emplace_back(b[i], 1, i);
	}

	tiedSort(v);

	int ans = INF;
	chmin(ans, accumulate(all(a), 0LL));
	chmin(ans, accumulate(all(b), 0LL));

	int tmp = 0;
	vector<int> Y(N);
	bool flag = false;
	rep(i, 0, N) {
		int x, y, z;
		tie(x, y, z) = v[i];
		if (Y[z])flag = true;
		Y[z] = y;
		tmp += x;
	}
	if (flag) {
		chmin(ans, tmp);
	}
	else {
		rep(i, 0, N) {
			int tmp2 = tmp;
			if (Y[i] == 0) {
				tmp2 -= a[i];
			}
			else {
				tmp2 -= b[i];
			}
			int x, y, z; tie(x, y, z) = v[N];
			if (z == i) {
				tie(x, y, z) = v[N + 1];
				tmp2 += x;
			}
			else {
				tmp2 += x;
			}
			chmin(ans, tmp2);
		}
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 12780
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<(n);++i)
int n,p[25]={},ans=0;
signed main(){
  cin >> n;
  rep(i,n) cin >> p[i];
  for(int i=1;i<=n-2;i++){
    if((p[i-1]<p[i] && p[i]<p[i+1]) || (p[i-1]>p[i] && p[i]>p[i+1])) ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define pb emplace_back
#define mp make_pair
#define mt make_tuple
#define all(v) v.begin(),v.end()
#define rep(i,start,lim) for(long long (i)=(start);i<(lim);i++)
#define revrep(i,n) for(long long i=n-1;i>=0;i--)
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define osit ostream_iterator<int> output (cout," ")
#define endl '\n'
#define f first
#define s second
#define PI 3.141592653589793
#define MOD 1000000007
#define set0(x) memset(x,0,sizeof(x))
#define set1(x) memset(x,1,sizeof(x))
using namespace std;
typedef vector<int> vi;
typedef list<int> li;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef tuple<int, int, int> iii;
template<typename T> T gcd(T a,T b){if(a==0) return b; return gcd(b%a,a);}
template<typename P> P dectobin(P a){if(a==0)return 0; else return(a%2 + 10*dectobin(a/2));}
template<typename Y> Y bintodec(Y a){int ans=0,b=1,t=a; while (t){int ld=t%10; t/=10;ans+=ld* b;b=b*2;} return ans; }
template<typename H> H modExp(H x, H n){ int r=1; while(n>0){if(n%2==1){r=(r*x)%MOD;}x=(x*x)%MOD;n/=2;}return r;}
template<typename T> T isPowerOfTwo(T x){return x && (!(x & (x - 1)));}	
template<typename T> T lcm(T a,T b) {return a*b/gcd(a,b);}
//template<typename T> T extendedEuclid(T A,T B){if(B==0){d=A; x=1;y=0;}else{ extendedEuclid(B,A%B);int temp=x; x=y; y=temp-(A
//B)*y;}}

int32_t main(){
	boost;osit;
	int n;
    cin>>n;
    double arr[n];
    double sum=0;
    rep(i,0,n){
        cin>>arr[i];
    }
    sort(arr,arr+n);
    sum=arr[0];
    rep(i,1,n){
        sum+=arr[i];
        sum/=2;
    }
    cout<<sum;
	return 0;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
b = [0] * n
mid = n//2

for i in range(mid, n):
    b[i] = a[i]

for i in range(mid-1, -1, -1):
    s = 0
    for j in range(i,n,i+1):
        s += b[j]
    if s%2 != a[i]:
        b[i] += 1


print(b.count(1))
for i in range(n):
    if b[i] == 1:
        print(i+1, end = ' ')


Measured memory_bytes: 64220
// {{{ by shik
#include <bits/stdc++.h>
#include <unistd.h>
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x),end(x)
#define REP(i,n) for ( int i=0; i<int(n); i++ )
#define REP1(i,a,b) for ( int i=(a); i<=int(b); i++ )
#define FOR(it,c) for ( auto it=(c).begin(); it!=(c).end(); it++ )
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;

#ifdef SHIK
template<typename T>
void _dump( const char* s, T&& head ) { cerr<<s<<"="<<head<<endl; }

template<typename T, typename... Args>
void _dump( const char* s, T&& head, Args&&... tail ) {
    int c=0;
    while ( *s!=',' || c!=0 ) {
        if ( *s=='(' || *s=='[' || *s=='{' ) c++;
        if ( *s==')' || *s==']' || *s=='}' ) c--;
        cerr<<*s++;
    }
    cerr<<"="<<head<<", ";
    _dump(s+1,tail...);
}

#define dump(...) do { \
    fprintf(stderr, "%s:%d - ", __PRETTY_FUNCTION__, __LINE__); \
    _dump(#__VA_ARGS__, __VA_ARGS__); \
} while (0)

template<typename Iter>
ostream& _out( ostream &s, Iter b, Iter e ) {
    s<<"[";
    for ( auto it=b; it!=e; it++ ) s<<(it==b?"":" ")<<*it;
    s<<"]";
    return s;
}

template<typename A, typename B>
ostream& operator <<( ostream &s, const pair<A,B> &p ) { return s<<"("<<p.first<<","<<p.second<<")"; }
template<typename T>
ostream& operator <<( ostream &s, const vector<T> &c ) { return _out(s,ALL(c)); }
template<typename T, size_t N>
ostream& operator <<( ostream &s, const array<T,N> &c ) { return _out(s,ALL(c)); }
template<typename T>
ostream& operator <<( ostream &s, const set<T> &c ) { return _out(s,ALL(c)); }
template<typename A, typename B>
ostream& operator <<( ostream &s, const map<A,B> &c ) { return _out(s,ALL(c)); }
#else
#define dump(...)
#endif

template<typename T>
void _R( T &x ) { cin>>x; }
void _R( int &x ) { scanf("%d",&x); }
void _R( long long &x ) { scanf("%" PRId64,&x); }
void _R( double &x ) { scanf("%lf",&x); }
void _R( char &x ) { scanf(" %c",&x); }
void _R( char *x ) { scanf("%s",x); }

void R() {}
template<typename T, typename... U>
void R( T& head, U&... tail ) {
    _R(head);
    R(tail...);
}

template<typename T>
void _W( const T &x ) { cout<<x; }
void _W( const int &x ) { printf("%d",x); }
template<typename T>
void _W( const vector<T> &x ) {
    for ( auto i=x.cbegin(); i!=x.cend(); i++ ) {
        if ( i!=x.cbegin() ) putchar(' ');
        _W(*i);
    }
}

void W() {}
template<typename T, typename... U>
void W( const T& head, const U&... tail ) {
    _W(head);
    putchar(sizeof...(tail)?' ':'\n');
    W(tail...);
}

#ifdef SHIK
#define FILEIO(...)
#else
#define FILEIO(name) do {\
    freopen(name ".in","r",stdin); \
    freopen(name ".out","w",stdout); \
} while (0)
#endif

// }}}

int main() {
    char s[110];
    R(s);
    int c=0;
    for ( int i=0; s[i]; i++ ) if ( s[i]=="CF"[c] ) c++;
    W(c==2?"Yes":"No");
    return 0;
}


Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
typedef pair<int,int> P; typedef pair<Int,Int> Pl;
const int mod = 1e9+7;
#define END {cout<<ans<<'\n'; return 0;}
#define ALL(v) v.begin(),v.end()
#define Pr(type) priority_queue<type>
#define gPr(type) priority_queue<type,vector<type>,greater<type>>
#define V(type) vector<type>
#define rep(i,n) for(int i=0; i<n; i++)
#define rer(i,st,en) for(int i=st; i<=en; i++)
#define eb emplace_back
#define pri1(a) cout<<a<<'\n'
#define pri2(a,n) rep(i,n)cout<<a[i]<<'\n'
#define pri3(a,n) rep(i,n)cout<<a[i]<<(i!=n-1?' ':'\n')
template<class T> inline bool cmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool cmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

template<typename T>
bool is_prime(T x) {
  for(T i = 2; i * i <= x; i++) {
    if(!(x%i)) return false;
  }
  return true;
}

int n,m,_,x,y,q;
string s;

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

  cin>>n; int ans=0;
  rep(i,n){
    cin>>m; ans+=is_prime(m);
  }
  END
}


Measured memory_bytes: 3176
#include <stdio.h>
#include <vector>
#include <iostream>
#include <queue>
#include <bits/stdc++.h>
 
#define rep(i,n) for (int i=0;i<(n);++i)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef pair<int, int> pi;


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

  ll ans = 0;
  ans += min(a, k);
  if (k > (a + b)){
    ans -= min(c, k-(a+b));
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,e) for(int i = s; i < e; i++)
 
int main()
{
    int n, d;
	cin >> n >> d;
	int x[n][d];
	rep(i,1,n+1)
	{
		rep(j,1,d+1)
		{
			cin >> x[i][j];
		}
	}
	int ans = 0;
	int dst = 0;

	rep(i,1,n)
	{
		rep(j,i+1,n+1)
		{
			rep(k,1,d+1)
			{
				int t = x[j][k]-x[i][k];
				dst += t*t;
				
			}
			int x = sqrt(dst);
			if(x*x == dst)
				ans++;
			dst = 0;
		}
	}
    cout << ans << endl;
    return 0;
}

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

int main() {
  int64_t r, d, x;
  cin >> r >> d >> x;
  
  for (int64_t i = 1; i <= 10; i++) {
    x = r * x - d;
    cout << x << endl;
  }
  
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>

using namespace std;

double l[10],v1, v2;

int main()
{
    loop:
    while ( scanf("%lf,%lf,%lf,%lf,%lf,%lf,%lf,%lf,%lf,%lf,%lf,%lf\n", &l[0], &l[1], &l[2], &l[3], &l[4], &l[5], &l[6], &l[7], &l[8], &l[9], &v1, &v2 ) != EOF )
    {
        v2 += v1;
        for( int i = 0; i < 10; i++ )
        {
            l[i] += ( ( i == 0 ) ? 0 : l[i - 1] );
        }
        double t = l[9] / v2;
        double dis = v1 * t;
        for( int i = 0; i < 10; i++ )
        {
            if( dis == l[i] )
            {
                printf( "%d\n", i + 1 );
                goto loop;
            }
            else if( dis < l[i] )
            {
                printf( "%d\n", i + 1 );
                goto loop;
            }
        }
        /* for( int i = 0; i < 10; i++ )
        {
            if( l[i] <= dis && dis <= l[i + 1] )
            {
                printf( "%d\n", i + 2 );
                return 0;
            }
        } */
    }
    return 0;
}


Measured memory_bytes: 2676
#include"iostream"
#include"string"
#include"algorithm"
using namespace std;

int ans,a[3],k;

int main()
{
	for (int i = 0; i < 3; i++) {
		cin >> a[i];
	}
	cin >> k;
	sort(a, a + 3);
	while (k--) {
		a[2] *= 2;
	}

	ans = a[0] + a[1] + a[2];
	cout << ans;

	system("pause");
    return 0;
}

Measured memory_bytes: 504
n=int(input())
x,y=map(int,input().split())

import math
for i in range(n-1):
  t,a=map(int,input().split())
  tbai=(x-1)//t+1
  abai=(y-1)//a+1
  bai=max(tbai,abai)
  x=t*bai
  y=a*bai
  #print(x,y)
print(x+y)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define gc getchar
inline ll read(){
    char ch=gc();
    while (!isdigit(ch)) ch=gc();
    return ch-'0';
}
ll a[1111111],n,b[1111111];
signed main(){
	cin>>n;
	for (int i=1;i<=n;i++) a[i]=read(); 
	n--;
	for (int i=1;i<=n;i++) b[i]=abs(a[i+1]-a[i]);
	for (int i=1;i<=n;i++) a[i]=b[i];
	ll _=0;
	bool flag1=0;
	for (int i=1;i<=n;i++){
		_=(_+((((n-1)&(i-1))==i-1)?a[i]:0))&1;
		flag1|=(a[i]==1);
	}
	if (_==1) puts("1");
	else{
		if (flag1) puts("0"); 
		else{
			_=0;
			for (int i=1;i<=n;i++){
				_=(_+((((n-1)&(i-1))==i-1)?a[i]/2:0))&1;
			}
			puts(_==0?"0":"2");
		}
	}
    return 0;
}


Measured memory_bytes: 16768
import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
K = int(input()) 
a=0
for i in range(1,K+1):
  for j in range(1,K+1):
    for l in range(1,K+1):
      a=a+gcd(i,j,l)
print(a)

Measured memory_bytes: 69952
#include <cstdio>
#include <cmath>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)

int isPrime(int m){
    if(m == 2) return true;
    if(m <= 1) return false;
    if(m % 2 == 0) return false;

    int i = 3;
    while(i <= sqrt(m)){
        if(m % i == 0) return false;
        i++;
    }
    return true;
}

int main(){
    int n;
    scanf("%d",&n);
    int ans = 0;
    rep(i,n){
        int m;
        scanf("%d",&m);
        if(isPrime(m)) ans++;
    }

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

}


Measured memory_bytes: 2752
#include <cstdio>

typedef long long LL;
const int Mod = 998244353;
const int MN = 200005;

inline int qPow(int b, int e) {
	int a = 1;
	for (; e; e >>= 1, b = (LL)b * b % Mod)
		if (e & 1) a = (LL)a * b % Mod;
	return a;
}

bool ip[MN];
int p[MN], pc;
int mu[MN];

inline void Sieve(int N) {
	mu[1] = 1;
	for (int i = 2; i <= N; ++i) {
		if (!ip[i]) p[++pc] = i, mu[i] = -1;
		for (int j = 1, k; j <= pc; ++j) {
			if ((k = p[j] * i) > N) break;
			ip[k] = 1;
			if (i % p[j]) mu[k] = -mu[i];
			else break;
		}
	}
}

int N, A[MN], B[MN], Ans;

inline int Calc(int x) {
	static int C[MN];
	int Cnt = 0;
	for (int i = 1; i <= x; ++i) C[i] = A[i], Cnt = (2ll * Cnt + C[i]) % Mod;
	for (int j = 2; j <= N / x; ++j)
		for (int i = 1; i <= x; ++i)
			C[(j - 1) * x + i] = C[i] ^ (~j & 1);
	int ok = 1;
	for (int i = 1; i <= N; ++i) {
		if (C[i] == A[i]) continue;
		if (C[i] > A[i]) { ok = 0; break; }
		if (C[i] < A[i]) break;
	}
	if (ok) Cnt = (Cnt + 1) % Mod;
	return Cnt;
}

int stk[MN], tp;

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i) scanf("%1d", &A[i]);
	Sieve(N);
	for (int i = 1; i <= N; ++i) {
		if (N % i != 0 || N / i % 2 == 0) continue;
		stk[++tp] = i;
		B[i] = Calc(i);
	}
	for (int i = tp; i >= 1; --i) {
		int x = stk[i], Sum = 0;
		for (int j = 1; j <= tp; ++j) {
			int y = stk[j];
			if (x % y != 0 || !mu[x / y]) continue;
			Sum = ((LL)Sum + mu[x / y] * B[y] + Mod) % Mod;
		}
		B[x] = Sum;
	}
	for (int i = 1; i <= tp; ++i) Ans = (Ans + (LL)B[stk[i]] * stk[i]) % Mod;
	printf("%lld\n", 2ll * Ans % Mod);
	return 0;
}

Measured memory_bytes: 3584
#114_C
#桁dp
N=int(input())

def dfs(s):
    if int(s)>N:
        return 0
    else:
        res=1 if all(s.count(c)>0 for c in '753') else 0
        for c in '753':
            res+=dfs(s+c)
        return res

print(dfs('0'))

Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i < (n);++i)
typedef long long ll;
using namespace std;
 
int main(){
  int d;
  cin >> d;
  
  if(d == 25) cout << "Christmas" << endl;
  else if(d == 24) cout << "Christmas Eve" << endl;
  else if(d == 23) cout << "Christmas Eve Eve" << endl;
  else if(d == 22) cout << "Christmas Eve Eve Eve" << endl;
  
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
int main() {
  int A;
  cin >> A;
  int AAA;
  vector<int> vec(A);
  rep(i, A) {
    cin >> AAA;
    vec.at(i) = AAA;
  }
  sort(vec.begin(), vec.end());
  reverse(vec.begin(), vec.end());
  int X = 0;
  for(int i = 0; i < vec.size(); i += 2) {
    X += vec.at(i);
  }
  int Y = 0;
  rep(i, vec.size()) {
    Y += vec.at(i);
  }
  cout << X - (Y - X) << endl;
}

Measured memory_bytes: 3588
import java.util.*;

class GCD
{
    int gcd; int temp;
    public int HCF(int a, int b)
    {
        if(a!=0&&b!=0)
        {
            if(a>b)return HCF(b, a%b);
            else return HCF(a, b%a);   
        }
        else 
        {
            if(a>0) return a;
            else return b;
        }
    }
}
class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int f = sc.nextInt();
        int s = sc.nextInt();
        GCD g = new GCD();
        System.out.println(g.HCF(f, s));
    }
}   





Measured memory_bytes: 26204
N = int(input())

ans = {"AC": 0, "WA": 0, "TLE": 0, "RE": 0}

for i in range(0, N): 
    a = input()
    ans[a] += 1

print("AC x {}".format(ans["AC"]))
print("WA x {}".format(ans["WA"]))
print("TLE x {}".format(ans["TLE"]))
print("RE x {}".format(ans["RE"]))

Measured memory_bytes: 9148
#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<utility>
#include<queue>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
/************************************************/
#define rep(i,n) for(int i=0;i<n;i++)
#define m_p make_pair
#define pb push_back
#define fr first
#define se second
#define forn(i,a,n) for(int i=a;i<n;i++)
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define sz(s) s.size()
#define all(s) s.begin(),s.end()
#define zero(x) memset(x,0,sizeof(x))
#define vii vector<pair<int,int> >
#define mpis map<int,string>
#define mpii map<int,int>
#define mpsi map<string,int>
#define re return
#define mod 1000000007
/************************************************/
using namespace std;

long long get(){
	char c=getchar();
	long long x=0LL;
	while(c<'0'||c>'9')
	c=getchar();
	while(c>='0'&&c<='9'){
		x*=10LL;
		x+=(c-'0');
		c=getchar();
	}
	return x;
}
ll x,k,d;
int main(){
	ios::sync_with_stdio(0);
	cin>>x>>k>>d;
	if(abs(x)/d>=k){
		x=abs(x)-d*k;
		cout<<x;
		re 0;
	}
	x=abs(x);
	if((k-x/d)%2==0){
		x%=d;
		cout<<min(x,2*d-x);
	}else{
		x%=d;
		x+=d;
		cout<<min(x,2*d-x);
	}
	
	re 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag,
             tree_order_statistics_node_update>
    indexed_set;
typedef long long ll;
const int N = 1e4 + 10, OO = 0x3f3f3f3f, mod = 1e9 + 7;

#define PI acos(-1)
#define clr(arr, val) memset(arr, val, sizeof(arr))
#define loop(i, n) for (int i = 0; i < int(n); i++)
#define rloop(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define xloop(i, a, b) for (int i = int(a); i <= int(b); i++)
#define range(vec)    \
  for (auto &x : vec) \
    cin >> x;
#define ALL(v) ((v).begin()), ((v).end())
#define SZ(v) ((int)((v).size()))
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1}; //4 Direction
//int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
//int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
//int dx[6]={2,1,-1,-2,-1,1};int dy[6]={0,1,1,0,-1,-1}; //Hexagonal Direction

int n, m, x;

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

  scanf("%d %d %d", &n, &m, &x);
  vector<int> cost(n);
  vector<int> a[n];
  for (int i = 0; i < n; ++i)
  {
    scanf("%d", &cost[i]);
    for (int j = 0; j < m; ++j)
    {
      int s;
      scanf("%d", &s);
      a[i].push_back(s);
    }
  }
  int ans = OO;
  for (int mskN = 0; mskN < (1 << n); ++mskN)
  {
    int costNow = 0;
    vector<int> algo(m);
    for (int i = 0; i < n; ++i)
    {
      if (mskN & (1 << i))
      {
        costNow += cost[i];
        for (int k = 0; k < m; ++k)
        {
          algo[k] += a[i][k];
        }
      }
    }
    bool ok = 1;
    for (int i = 0; i < m; ++i)
    {
      if (algo[i] < x)
      {
        ok = 0;
        break;
      }
    }
    if (ok)
      ans = min(ans, costNow);
  }
  if (ans == OO)
    ans = -1;
  printf("%d\n", ans);

  return 0;
}

Measured memory_bytes: 3768
#include <iostream>
using namespace std;
int main(void){
    int a, b;
    cin >> a >> b;
    
    char s[13];
    cin >> s;
    
    int i;
    for(i = 0; i < a; i++){
        if(!isdigit(s[i])){
            cout << "No" << endl;
            return 0;
        }
    }
    
    if(s[i] != '-'){
        cout << "No" << endl;
        return 0;
    }
    
    for(i = a + 1; i < a + b + 1; i++){
        if(!isdigit(s[i])){
            cout << "No" << endl;
            return 0;
        }
    }
    
    cout << "Yes" << endl;
    
    return 0;
}


Measured memory_bytes: 256
n = int(input())

s =str(input())


left_save = 0
dept=0

for i in range(len(s)):
    if s[i] ==')':
        if left_save == 0:
            dept +=1
        else:
            left_save-=1
            
    else:
        left_save+=1

ans = '('*dept + s + ')'*left_save

print(ans)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
    string s;
    cin>>s;
    if(s=="Sunny")
    {
        cout<<"Cloudy\n";
    }
    else if(s=="Cloudy")
    {
        cout<<"Rainy\n";
    }
    else if(s=="Rainy")
    {
        cout<<"Sunny\n";
    }

}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long ll;

const int mod = 1e9 + 7;

int add(int i, int j) {
    if((i += j) >= mod) i -= mod;
    return i;
}

int mult(int i, int j) {
    return (ll) i * j % mod;
}

int n;
int dp[4][100000];
string line;

int f(int i, int j) {
    if(i == 4) return 0;
    if(j == n) return i == 3;
    if(dp[i][j] > -1) return dp[i][j];
    if(line[j] == '?') return dp[i][j] = add(f(i + 1, j + 1), mult(3, f(i, j + 1)));
    int mx = f(i, j + 1);
    if(i == line[j] - 'A') mx = add(mx, f(i + 1, j + 1));
    return dp[i][j] = mx;
}

int main() {
    cin >> line;
    n = line.size();
    memset(dp, -1, sizeof dp);
    cout << f(0, 0);
    
    return 0;
}

Measured memory_bytes: 6656
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int N,K;
  cin >> N >> K;
  vector<int> h(N);
  for(int i=0;i<N;i++){cin >> h[i];}
  sort(h.begin(),h.end());
  int H=2147483647;
  for(int i=0;i<N-K+1;i++){
    H=min(H,abs(h[i]-h[i+K-1]));
  }
  cout << H << endl;
}

Measured memory_bytes: 768
#include <stdio.h>

using namespace std;

int main(){
	int n,x;
	scanf("%d",&n);

	for(int i = 1; i<= n; i++)
	{
		if(i%3 == 0){
			printf(" %d",i);
		}else{
			x = i;
			do{
				if(x%10 == 3){
					printf(" %d",i);
					break;
				}
				x /=10;
			}while(x);
		}
	}
	printf("\n");
}



Measured memory_bytes: 2684
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sct(tc) scanf("%lld",&tc)
#define scl(n) scanf("%lld",&n)
#define scll(n,m) scanf("%lld%lld",&n,&m)
#define scs(ch) scanf("%s", ch)
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
int main()
{
	ll k,i;
	scanf("%lld",&k);
	string s;
	cin >>s;
	ll len=s.length();
	for(i=0;i<len;i++)
	{
		if(i==k)
		{
			cout << "...";
			break;
		}
		else
		cout<< s[i];
	}
	cout <<"\n";
}

Measured memory_bytes: 3692
#include <stdio.h>

int calc_area(int length,int width)
{
    int area;

    area = length*width;
    return (area);
}

int calc_around(int length,int width){
    int around;

    around = (length*2) + (width*2);
    return (around);
}

int main(void){
    int length,width;
    int area,around;

    scanf("%d %d",&length,&width);

    area = calc_area(length,width);
    around = calc_around(length,width);

    printf("%d %d",area,around);
    printf("\n");
    return (0);
}

Measured memory_bytes: 1760
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
using namespace std;

vector<vector<int> > rot = {
	{0,1,2,3,4,5}, {0,2,4,1,3,5}, {0,4,3,2,1,5}, {0,3,1,4,2,5},
	{1,5,2,3,0,4}, {1,2,0,5,3,4}, {1,0,3,2,5,4}, {1,3,5,0,2,4},
	{2,5,4,1,0,3}, {2,4,0,5,1,3}, {2,0,1,4,5,3}, {2,1,5,0,4,3},
	{3,4,5,0,1,2}, {3,5,1,4,0,2}, {3,1,0,5,4,2}, {3,0,4,1,5,2},
	{4,0,2,3,5,1}, {4,2,5,0,3,1}, {4,5,3,2,0,1}, {4,3,0,5,2,1},
	{5,4,2,3,1,0}, {5,2,1,4,3,0}, {5,1,3,2,4,0}, {5,3,4,1,2,0}
};

vector<vector<vector<int> > > cond = {
	{},
	{{3,0,2}},
	{{1,1,4}},
	{{1,0,4},{2,2,3}},
	{{0,3,5}},
	{{0,2,5},{3,4,2}},
	{{0,1,5},{4,5,1}},
	{{0,0,5},{2,6,3},{4,4,1}}
};

struct State { int id, r; };
State pz[8];

string dice[8];
bool used[8];

inline char toggleCase(char c) {
	if (islower(c)) return toupper(c);
	return tolower(c);
}

string solve(int x) {
	if (x == 8) return "YES";
	for (int i=1; i<8; ++i) {
		if (used[i]) continue;
		for (int j=0; j<24; ++j) {
			pz[x].id = i;
			pz[x].r = j;
			bool ok = true;
			for (int k=0; k<(int)cond[x].size(); ++k) {
				int bloc1 = x;
				int face1 = rot[pz[bloc1].r][cond[x][k][0]];
				int bloc2 = cond[x][k][1];
				int face2 = rot[pz[bloc2].r][cond[x][k][2]];
				if (toggleCase(dice[pz[bloc1].id][face1]) != dice[pz[bloc2].id][face2]) {
					ok = false; break;
				}
			}
			if (ok) {
				used[i] = true;
				if (solve(x+1) == "YES") return "YES";
				used[i] = false;
			}
		}
	}
	return "NO";
}

int main() {
	while (cin >> dice[0], dice[0] != "0") {
		for (int i=1; i<8; ++i) {
			cin >> dice[i];
		}
		memset(used, false, sizeof used);
		used[0] = true;
		pz[0].id = 0;
		string res = "NO";
		for (int i=0; i<24; ++i) {
			pz[0].r = i;
			if (solve(1) == "YES") {
				res = "YES"; break;
			}
		}
		cout << res << endl;
	}
	return 0;
}

Measured memory_bytes: 1208
import std.stdio, std.string, std.conv, std.algorithm, std.numeric;
import std.range, std.array, std.math, std.typecons, std.container, core.bitop;


void main() {
    int L;
    string s, t;

    scan(L);
    scan(s);
    scan(t);

    if (s > t) {
        swap(s, t);
    }

    if (s == t[0 .. s.length]) {
        string ss;
        string tt = t ~ t;

        while (ss.length < t.length) {
            ss ~= s;
        }

        if (ss > tt) {
            swap(s, t);
        }
    }

    int n = s.length.to!int;
    int m = t.length.to!int;

    int k = 0;
    int kk = 0;

    while (n * kk <=  L) {
        if ((L - n*kk) % m == 0) {
            k = kk;
        }
        kk++;
    }

    string ans;

    foreach (i ; 0 .. k) {
        ans ~= s;
    }

    foreach (i ; 0 .. (L - n*k) / m) {
        ans ~= t;
    }

    writeln(ans);
}


void scan(T...)(ref T args) {
    string[] line = readln.split;
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}


void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

Measured memory_bytes: 3324
//|a-k|==|b-k|か判断
//(a+b)/2で偶数、奇数で
//統一されていれば解答できる

#include<stdio.h>

int main(){
  int a,b,k;
  scanf("%d %d",&a,&b);

  if(a%2==b%2){
    k=(a+b)/2;
    printf("%d\n",k);
  }else{
    printf("IMPOSSIBLE\n");
  }


  return 0;
}


Measured memory_bytes: 128
import java.util.Scanner

object Main extends App {
  val in = new java.util.Scanner(System.in)
  val N, M, Q = in.nextInt
  val Qs = Array.fill(Q)((1 to 4).map(_ => in.nextInt).toArray)

  def enumerate(ar: Array[Array[Int]]): Array[Array[Int]] =
    if (ar.head.size == N) ar
    else enumerate(ar.flatMap(a => (a.last to M).map(a.appended(_))))

  val seqs = enumerate((1 to M).map(i => Array(i)).toArray)

  println(seqs.map{s =>
    Qs.map{case Array(a, b, c, d) => if (s(b - 1) - s(a - 1) == c) d else 0}.sum
  }.max)
}

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


struct TreeNode {
    int count;
    vector<int> children;
    TreeNode() : count(0) {};
};

void sumar(TreeNode arr[], vector<int>& children, int que[], int amtosum) {
    int sum = 0;

    for(int i = 0; i < children.size(); i++) {
        arr[children[i]].count += amtosum + que[children[i]];
        if (arr[children[i]].children.size() > 0)
            sumar(arr, arr[children[i]].children, que, amtosum + que[children[i]]);
    }
}

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

    TreeNode arr[n];
    int node1, node2;
    for(int i = 0; i < n-1; i++) {
        cin >> node1 >> node2;

        arr[node1-1].children.push_back(node2-1);
    }

    int parent = 0, amtosum = 0;
    int que[n] = {0};
    for(int i = 0; i < q; i++) {
        cin >> parent >> amtosum;
        que[parent-1] += amtosum;
        //arr[parent-1].count += amtosum;
        //sumar(arr, arr[parent-1].children, amtosum);
        //for(int i = 0; i < arr[parent-1].children.size(); i++) {
        //    arr[arr[parent-1].children[i]].count += amtosum;
        //}
    }
    arr[0].count += que[0];
    sumar(arr, arr[0].children, que, que[0]);
    for(int i = 0; i < n; i++) {
        if (i != 0) cout << " ";
        cout << arr[i].count;
    }
    cout << endl;

    return 0;
}


Measured memory_bytes: 25088
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    int n;
    cin >> n;
    vector<ll> a(n);
    ll sum = 0;
    for(ll i = 0; i < n; i++){
        cin >> a[i];
        sum += a[i];
    }
    vector<ll> b;
    for(ll i = 0; i < n; i++){
        if(a[i] % 10 != 0)
        b.emplace_back(a[i]);
    }
    sort(b.begin(),b.end());
    if(b.size()== 0){
        cout << 0 << endl;
        return 0;
    }
    else
    {
        if(sum % 10 == 0){
            cout << sum - b[0] << endl;
            return 0;
        }
        else
        {
            cout << sum << endl;
            return 0;
        }
        
    }
    
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    vector<long long> x(n);
    vector<long long> y(n);
    vector<long long> z(n);

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

    vector<int> sign = {1, -1};

    long long ret = 0;

    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                vector<long long> p(n);
                for (int l = 0; l < n; l++) {
                    p[l] = sign[i]*x[l] + sign[j]*y[l] + sign[k]*z[l];
                }
                sort(p.rbegin(), p.rend());
                long long ans = 0;
                for (int l = 0; l < m; l++) {
                    ans += p[l];
                }
                ret = max(ans, ret);
            }
        }
    }

    cout << ret << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> h(n), dp(n);
    for(int i=0; i<n; i++) cin >> h[i];
    for(int i=1; i<n; i++) {
        dp[i] = dp[i-1] + abs(h[i-1]-h[i]);
        for(int j=2; j<=k; j++) {
            if(i-j>=0) dp[i] = min(dp[i], dp[i-j]+abs(h[i-j]-h[i])); 
        }
    }
    cout << dp[n-1] << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <array>
#include <bitset>
#include <cstring>
#include <deque>
#include <math.h>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <queue>
#include <vector>

#define FOR(i, a, b) for(int (i) = (a); (i) < (b); ++(i))
#define rFOR(i, a, b) for(int (i) = (b); (i) >= (a); --(i))
#define REP(i, n) FOR(i, 0, n)
#define rREP(i, n) rFOR(i, 0, (n-1))
#define SORT(A) std::sort((A).begin(), (A).end())
#define ALL(A) (A).begin(), (A).end()
// 座標圧縮 (for vector) : ソートしてから使うのが一般的 ; SORT(A) => COORDINATE_COMPRESSION(A)
#define COORDINATE_COMPRESSION(A) (A).erase(unique((A).begin(),(A).end()),(A).end())

using lli = long long int;
using pii = std::pair<int, int>;

template <typename T>
bool chmin(T& a, T b){
    if(b < a){ a = b; return true;}
    return false;
}

template <typename T>
bool chmax(T& a, T b){
    if(a < b){ a = b; return true;}
    return false;
}


// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


std::bitset<4> A;

int main(void){
    int a, b; scanf("%d%d", &a, &b);
    A[a] = true; A[b] = true;
    for(int i = 1; i <= 3; ++i){
        if(not A[i]){
            printf("%d\n", i);
            return 0;
        }
    }


    return 0;
}

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

bool linearSearch(int s[], int n, int v) {
    for (int i = 0; i < n; i++) {
        if (s[i] == v) {
            return true;
        }
    }
    return false;
}

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

    int q;
    cin >> q;
    int t[q];
    for (int i = 0; i < n; i++) cin >> t[i];

    int cnt = 0;
    for (int i = 0; i < q; i++) {
        if (linearSearch(s, n, t[i])) {
            cnt++;
        }
    }

    cout << cnt << endl;
}

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

int main()
{
	int n;
	long long m;
	cin >> n >> m;
	vector<pair<long long, long long> > vp(n);
	for(auto&& i : vp)
	{
		cin >> i.first >> i.second;
	}
	sort(begin(vp), end(vp));
	long long ans = 0, p = 0;
	while(m > 0)
	{
		ans += min(m, vp[p].second) * vp[p].first;
		m -= min(m, vp[p].second);
		p++;
	}
	cout << ans << "\n";
}


Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for(;;) {
            int n=sc.nextInt();
            if(n==0) {
                break;
            }
            int count=0;
            while(n!=1) {
                n=n%2==0?n/2:n*3+1;
                count++;
            }
            System.out.println(count);
        }
    }
}


Measured memory_bytes: 25848
#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<ctime>
#include<set>
#include<map>
#include<queue>
#include<stack>
#define sqr(x) ((x)*(x))
#define fz1(i,n) for ((i)=1;(i)<=(n);(i)++)
#define fd1(i,n) for ((i)=(n);(i)>=1;(i)--)
#define fz0g(i,n) for ((i)=0;(i)<=(n);(i)++)
#define fd0g(i,n) for ((i)=(n);(i)>=0;(i)--)
#define fz0k(i,n) for ((i)=0;(i)<(n);(i)++)
#define fd0k(i,n) for ((i)=(long long)((n)-1);(i)>=0;(i)--)
#define fz(i,x,y) for ((i)=(x);(i)<=(y);(i)++)
#define fd(i,y,x) for ((i)=(y);(i)>=(x);(i)--)
#define fzin fz1(i,n)
#define fzim fz1(i,m)
#define fzjn fz1(j,n)
#define fzjm fz1(j,m)
#define ff(c,itr) for (__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
#define rdst(st,len){static char ss[len];scanf(" %s",ss);(st)=ss;}
#define inc(x,y) {x+=(y);if(x>=mod)x-=mod;}
#define dec(x,y) {x-=(y);if(x<0)x+=mod;}
using namespace std;
int n;
double x,d,ans,c;
int main()
{
	scanf("%d%lf%lf",&n,&d,&x);
	c=n+n;
	while(n--){
		ans+=d+x*(c-1)/2;
		double nd=d+(2*d+5*x)/c;
		double nx=x+4*x/c;
		c-=2;d=nd;x=nx;
	}
	printf("%.18f\n",ans);
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ALL(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using lld = long double;
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
const int IINF = 1 << 30;
const ll INF = 1ll << 60;
const ll MOD = 998244353;
VI v;
int n, s;
int main()
{
    cin >> n >> s;
    v.resize(n);
    rep(i, n)
    {
        cin >> v[i];
    }
    VVI dp(n + 1, VI(s + 1, 0));
    dp[0][0] = 1;
    rep(i, 1, n + 1)
    {
        rep(j, s + 1)
        {
            dp[i][j] += dp[i - 1][j];
            if (j - v[i - 1] == 0)
            {
                dp[i][v[i - 1]] += i;
            }
            else if (j - v[i - 1] >= 1)
            {
                dp[i][j] += dp[i - 1][j - v[i - 1]];
                dp[i][j] %= MOD;
            }
        }
    }
    ll ans = 0;

    rep(i, 1, n + 1)
    {
        cerr << dp[i][s] << endl;
        ans += dp[i][s];
        ans %= MOD;
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
    long long n,k;
    cin>>n>>k;
    if(n%k==0){
        cout<<0<<endl;
        return 0;
    }
    long long ans=n%k;
    ans = min(abs(ans-k),ans);
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>

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;
}

using namespace std;
#define int long long
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repr(i,n) for(ll i=n;i>=0;i--)
#define P pair<ll, ll>
#define sz(x) (ll)x.size()
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define VE vector<ll>
#define COUT(x) cout<<(x)<<endl
#define MA map<ll,ll>
#define SE set<ll>
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,VE,greater<ll>>
#define COUT(x) cout<<(x)<<endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define EPS (1e-10)
#define pb push_back

const long long MOD = 1000000007;
//const long long MOD = 998244353;
const long long INF = 1LL << 60;


long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	unsigned r;
	while ((r = a % b)) {
		a = b;
		b = r;
	}
	return b;
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a * g / b;
}
bool prime(ll n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}




const long double PI = 3.14159265359;
const int MAX_N = 100010;



signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n; cin >> n;
	if (n == 0) {
		cout << 0 << endl; return 0;
	}
	int i = 1;
	string s = "";
	while (n != 0) {
		if (n % (i * (-2)) != 0) {
			s += '1';
			n -= i;
		}
		else s += '0';
		i *= -2;
		//cout << n << endl;
	}
	reverse(ALL(s));
	cout << s << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

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

int main(){
	int n;
	cin >> n;
	cout << n*(n+1)/2 << '\n';
	
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
int main() {
    ll N, K;
    cin >> N >> K;
    vector<ll> a(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> a[i];
    }
    vector<vector<ll>> dp(N + 1, vector<ll>(101000, 0));
    vector<vector<ll>> sum(N + 1, vector<ll>(101000, 0));
    dp[0][0] = 1;
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= K; j++) {
            if (i != 0) {
                dp[i][j] = sum[i - 1][j] -
                           (j - a[i] - 1 >= 0 ? sum[i - 1][j - a[i] - 1] : 0LL);
            }
            if (i == 0) {
                sum[i][j] = 1;
            } else {
                sum[i][j] += (j > 0 ? sum[i][j - 1] : 0) + dp[i][j];
            }

            dp[i][j] %= mod;
            sum[i][j] %= mod;
        }
    }
    cout << (dp[N][K] % mod + mod) % mod << endl;
}

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

#define int long long
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rep1(i,n) for(int i=1;i<=(int)(n);++i)
#define rep11(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define repm(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end())
#define vdelete(v) (v).erase(unique(all(v)), (v).end())
#define pb(n) push_back(n)
#define mp make_pair
#define MOD 1000000007
#define INF 9223372036854775807

struct hoge{
    int a;
    string s;
};

int n,p;
string s;
map<string,vector<pair<int,int>>> m;

signed main() {
    cin >> n;
    rep(i,n) cin >> s >> p,m[s].pb(mp(p,i+1));
    for(auto i : m) {
        sort(rall(i.se));
        rep(j,i.se.size()) cout << i.se[j].se << endl;
    }
}


Measured memory_bytes: 256
N,T=map(int,input().split())
tlist=list(map(int,input().split()))

dlist=[]
for i in range(1,N):
  dlist.append(tlist[i]-tlist[i-1])
#print(dlist)

answer=0
for d in dlist:
  answer+=min(d,T)

print(answer+T)

Measured memory_bytes: 26836