akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define clr(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define PI acos(-1.0)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef long long ll;
typedef unsigned long long ull;
const int INF=0x3f3f3f3f;
const int maxn=1e5+10;
int dp[1<<16],V[maxn],cnt[16];
int n,x,y,a;
inline int Count(int x)
{
	int ans=0;
	for(int i=0;i<=15;++i) if(x&(1<<i)) ans++;
	return ans;
}
int Work(int s)
{
    if(s==0) return 0;
    if(dp[s]!=-1) return dp[s];
    dp[s]=INF;
    for(int i=1;i<16;i++)
    {
    	if(s&(1<<i))
            for(int j=1;j<16;j++)
            {
            	
            	if(s&(1<<j))
                {
                    int cs=s^(1<<i)^(1<<j)^(1<<(i^j));
                    if(Count(cs)<Count(s)) 
					{
						if(((1<<(i^j)) & s) == (1<<(i^j))) dp[s]=min(dp[s], Work(cs) + 2);
						else dp[s]=min(dp[s], Work(cs) + 1 ); 
					}
                }
			}
	}
    return dp[s];
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d%d",&x,&y,&a);
        V[x]^=a; V[y]^=a;
    }
    for(int i=0;i<n;i++) if(V[i]) cnt[V[i]]++;
    int ans=0,s=0;
    for(int i=0;i<16;i++) ans+=cnt[i]/2, s^=(cnt[i]&1)<<i;
    memset(dp,-1,sizeof dp);
    ans+=Work(s);
    printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 896
//#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,no-stack-protector") 
//#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

#define int long long
#define ll long long
#define ull unsigned long long
#define ld long double
#define rep(i, l, r) for (int i = l; i < r; i++)
#define repb(i, r, l) for (int i = r; i > l; i--)
#define sz(a) (int)a.size()
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp(a, b) make_pair(a, b)
#define ret(a) {cout << a; exit(0);}

using namespace std;

mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b,ll mod) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}

typedef pair < int , int > pii ;
typedef pair < long long  , long long > pll ;

const int N = 200 , K = 501;
int n , m , k;
int x[N];
bool was[N] ;
int mt[N];
vector < int > gr[N];
bool pr(int x){
	if(x < 0) x *= -1;
	if(x <= 2)
		return false;
	for(int i = 2 ; i * i <= x; i++)
		if(x % i == 0)	
			return false;
	return true;
}
bool kuhn(int v){
	if(was[v])return false;
	was[v] = 1;
	for(auto to : gr[v])
		if(mt[to] == -1 or kuhn(mt[to])){
			mt[to] = v;
			return true;
		}
	return false;
}
main(){
	ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
	cin >> n;
	for(int i = 1;i <= n; i++){
		cin >> x[i];
	}
	vector < int > v;
	x[0] = -1;
	for(int i = 1 ;i <= n ; i++){
		if(x[i] != x[i - 1] + 1)
			v.pb(x[i]) ;
		if(x[i + 1] != x[i] + 1)
			v.pb(x[i] + 1);			
	}
/*	for(int i = 1; i <= 6 ; i++)
		cout << tmp[i];
	cout << endl;*/
	int cnt0 = 0 , cnt1 = 0;
	for(auto i : v){
		cnt0 += i % 2 == 0,
		cnt1 += i % 2 == 1;		
//		cerr << i << '\n';
	}
//	return 0;
	for(int i = 0 ; i < sz(v); i++){
		for(int j = i + 1 ; j < sz(v); j++){
			if(pr(v[j] - v[i]))
				gr[i].pb(j) , gr[j].pb(i);
		}
	}	
	for(int i = 0 ;i < sz(v); i++)
		mt[i] = -1;
	for(int i = 0 ; i < sz(v) ;i++){
		memset(was , 0, sizeof(was));
		kuhn(i);
	}
	int tot = 0, d0 = 0 , d1 = 0;
	for(int i = 0; i < sz(v) ; i++){
		if(mt[i] != -1){
			tot++,d0 += i % 2 == 0 , d1 += i % 2 == 1;
		}
	}
	tot /= 2;
	cerr << tot << ' ' << cnt1 << ' ' << cnt0 << '\n';
	cout << tot + ((cnt0 - tot)/2 + (cnt1 - tot)/2) * 2 + ((cnt0 - tot)%2) * 3;
    return 0;
}

Measured memory_bytes: 384
#include <iostream>
using namespace std;
struct point
{
    double x,y;
};
point vt(point a,point b)
{
    point vt;
    vt.x=b.x-a.x;
    vt.y=b.y-a.y;
    return vt;
}
double tichcheo(point a,point b)
{
    return a.x*b.y-b.x*a.y;
}
int test1(point a,point b,point c,point d)
{
    if ((a.x==c.x&&a.y==c.y)||(a.x==d.x&&a.y==d.y)||(c.x==b.x&&c.y==b.y)||(d.x==b.x&&d.y==b.y)) return 1;
    else return 0;
}
int test2(double a,double b,double c,double d)
{
    if (a>b) {
        swap(a,b);
    }
    if (c>d)
    {
        swap(c,d);
    }
    if (max(a,c)<=min(b,d)) return 1;
    else return 0;
}
int test(point a,point b,point c,point d)
{
    point ab=vt(a,b);
    point bc=vt(b,c);
    point bd=vt(b,d);
    if ((tichcheo(ab,bc)*tichcheo(ab,bd))<=0&&tichcheo(ab,bc)!=tichcheo(ab,bd)) return 1;
    else if (tichcheo(ab,bd)==0&&tichcheo(ab,bc)==0)
    {
        /*cout<<test2(a.x,b.x,c.x,d.x)<<endl;
        cout<<test2(a.y,b.y,c.y,d.y)<<endl;
        cout<<test2(c.x,d.x,a.x,b.x)<<endl;
        cout<<test2(c.y,d.y,a.y,b.y)<<endl;*/
        if ((test2(a.x,b.x,c.x,d.x)==1)&&(test2(a.y,b.y,c.y,d.y)==1)&&(test2(c.x,d.x,a.x,b.x)==1)&&(test2(c.y,d.y,a.y,b.y)==1)) return 1;
        else return 0;
        /*cout<<(test2(a.x,b.x,c.x,d.x)&&test2(a.y,b.y,c.y,d.y))<<endl;
        cout<<(test2(c.x,d.x,a.x,b.x)&&test2(c.y,d.y,a.y,b.y))<<endl;
        return 1;*/
    }
    else return 0;
}
int q;
int main()
{
    cin>>q;
    while (q--)
    {
        point p0,p1,p2,p3;
        cin>>p0.x>>p0.y>>p1.x>>p1.y>>p2.x>>p2.y>>p3.x>>p3.y;
        if (test1(p0,p1,p2,p3))
        {
            cout<<"1\n";
        }
        else
        if (test(p0,p1,p2,p3)==1&&test(p2,p3,p0,p1)==1) cout<<"1\n";
        else cout<<"0\n";
    }
    return 0;
}



Measured memory_bytes: 3216
#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
#define begin Begin
#define next Next
inline int read(){
	int x;
	char c;
	int f=1;
	while((c=getchar())!='-' && (c>'9' || c<'0'));
	if(c=='-') c=getchar(),f=-1;
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
	return x*f;
}
inline ll readll(){
	ll x;
	char c;
	int f=1;
	while((c=getchar())!='-' && (c>'9' || c<'0'));
	if(c=='-') c=getchar(),f=-1;
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
	return x*f;
}
const int maxn=100+10;
int begin[maxn],next[maxn*maxn],to[maxn*maxn],e;
void add(int x,int y){
	to[++e]=y;
	next[e]=begin[x];
	begin[x]=e;
}
bool p[maxn];
int ma[maxn],ans;
int dfs(int x){
	for(int i=begin[x];i;i=next[i])
		if(!p[to[i]]){
			p[to[i]]=1;
			if(!ma[to[i]] || dfs(ma[to[i]])){
				ma[to[i]]=x;
				return 1;
			}
		}
	return 0;
}
struct point{
	int x,y;
}a[maxn],b[maxn];
int main(){
	int n=read();
	REP(i,1,n) a[i].x=read(),a[i].y=read();
	REP(i,1,n) b[i].x=read(),b[i].y=read();
	REP(i,1,n)
		REP(j,1,n)
			if(a[i].x<b[j].x && a[i].y<b[j].y)
				add(i,j);
	REP(i,1,n){
		memset(p,0,sizeof(p));
		ans+=dfs(i);
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#ifdef __GXX_EXPERIMENTAL_CXX0X__
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
using namespace std;


int main() {
	int count = 0;

	int A, B, C;

	cin >> A >> B >> C;

	if (A == B) {
		count++;
	}
	if (B == C) {
		count++;
	}
	if (A == C) {
		count++;
	}

	if (count == 1) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

}


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

int main(){
	string s, ans = "Yes";
	cin >> s;
	if(s.find('C') == string::npos) ans = "No";
	else if(s.find('F') == string::npos) ans = "No";
	else{
		if(s.find_first_of('C') > s.find_last_of('F')) ans = "No";
	}
	cout << ans << endl;
	return 0;
}

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

using namespace std;
using ll = long long;

int main() {
  ll n; cin >> n;
  ll ans = 0;
  ll m = 1;
  while (n > 0) {
    ans += m;
    m *= 2;
    n /= 2;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<map>
#include<cassert>
#include<cstdlib>
#include<algorithm>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
typedef long long ll;
const int N =7;
const int inf = (1<<29);
int dp1[1<<N];

void precomp1(int n,int *x,int *y){
  int dp[1<<N][N];
  rep(i,(1<<n))rep(j,n)dp[i][j]=inf;
  rep(i,n){
    dp[(1<<i)][i]=abs(x[i])+abs(y[i]);
  }
  rep(i,(1<<n)){
    rep(j,n){//cur
      if (((1<<j)&i) == 0)continue;
      rep(k,n){//next
	if (((1<<k)&i) != 0)continue;
	int next=(1<<k)|i;
	dp[next][k]=min(dp[next][k],dp[i][j]+abs(x[j]-x[k])+abs(y[j]-y[k]));
      }      
    }
  }
  REP(i,1,(1<<n)){
    dp1[i]=inf;
    rep(j,n){
      dp[i][j]+=abs(x[j])+abs(y[j]);
      dp1[i]=min(dp1[i],dp[i][j]);
    }
  }
}

ll dp2[1<<N];
void precomp2(int m,int w,int bit,int *tv,int *weight){
  static ll dp[7][10000+1];
  rep(i,m)rep(j,w+1)dp[i][j]=0;
  rep(i,m){
    rep(j,w+1){
      if (j-weight[i] >= 0)dp[i][j]=dp[i][j-weight[i]]+tv[i];
      if (i)dp[i][j]=max(dp[i][j],dp[i-1][j]);
    }
  }
  dp2[bit]=0;
  rep(i,w+1)dp2[bit]=max(dp2[bit],dp[m-1][i]);
}

ll dp3[1<<N][10001];
ll solve(int n,int t){
  rep(i,(1<<n))rep(j,t+1)dp3[i][j]=0;
  rep(i,(1<<n)){
    rep(j,t+1){
      if (j-dp1[i] >= 0)dp3[i][j]=max(dp3[i][j],dp3[i][j-dp1[i]]+dp2[i]);
      if (i)dp3[i][j]=max(dp3[i][j],dp3[i-1][j]);
    }
  }
  ll ret=0;
  rep(i,t+1)ret=max(ret,dp3[(1<<n)-1][i]);
  return ret;
}

main(){
  int n,m,w,t;
  while(cin>>n>>m>>w>>t){
    map<string,int> M;
    int x[n],y[n],weight[m],value[m];
    rep(i,m){
      string tmp;
      cin>>tmp>>weight[i]>>value[i];
      M[tmp]=i;
    }
    int price[n][m];
    rep(i,n)rep(j,m)price[i][j]=0;
    rep(i,n){
      int l;
      cin>>l>>x[i]>>y[i];
      string tmp;
      rep(j,l){
	int g;
	cin>>tmp>>g;
	price[i][M[tmp]]=value[M[tmp]]-g;
      }
    }
    precomp1(n,x,y);
    REP(i,1,(1<<n)){
      int tv[m];
      rep(j,m)tv[j]=0;
      rep(j,n){
	if (((1<<j)&i) == 0)continue;
	rep(k,m)tv[k]=max(tv[k],price[j][k]);
      }
      precomp2(m,w,i,tv,weight);
      //cout << i <<" " << dp1[i] <<" " << dp2[i] << endl;
    }
    cout << solve(n,t) << endl;
  }
  return false;
}

Measured memory_bytes: 11000
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using P = pair<ll, ll>;
#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 all(x) (x).begin(), (x).end()
const ll INF = ll(1e18)+1;

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

    ll k,a,b;
    cin >> k >> a >> b;

    string result = "NG";
    for(ll i=a;i<=b;i++){
        if(i%k==0){
            result = "OK";
        }
    }
    cout << result;
}

Measured memory_bytes: 3636
using System;

namespace ConsoleApp1
{
    class ABC179C
    {
        // https://atcoder.jp/contests/abc179/tasks/abc179_c
        static void Main(string[] args)
        {
            int N = Int32.Parse(Console.ReadLine());

            long result = 0;

            for (int A = 1; A < N; A++)
            {
                result += (N - 1) / A;
            }

            Console.WriteLine(result);
        }
    }
}


Measured memory_bytes: 27540
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val dp = IntArray(n + 1)

    for (i in 1..n) {
        dp[i] = 1 + dp[i - 1]

        var j = 6
        while (j <= i) {
            dp[i] = Math.min(1 + dp[i - j], dp[i])
            j *= 6
        }

        j = 9
        while (j <= i) {
            dp[i] = Math.min(1 + dp[i - j], dp[i])
            j *= 9
        }
    }

    println(dp[n])
}


Measured memory_bytes: 33692
/*input
3
4 3 5
4 3 6
8 8 8
*/
fn main() {
    let mut input;
    input = format!("");
    std::io::stdin().read_line(&mut input).expect("");
    let iter: u16 = input.trim().parse().expect("");
    let mut v: Vec<u32>;
    let mut max;
    for _ in 0..iter {
        input = format!("");
        std::io::stdin().read_line(&mut input).expect("");
        v = input
            .trim()
            .split_whitespace()
            .map(|x| x.parse().expect(""))
            .collect();
        max = v
            .clone()
            .into_iter()
            .fold(None, |max, x| match max {
                None => Some(x),
                Some(y) => Some(if x > y { x } else { y }),
            })
            .unwrap();
        if v[0].pow(2) + v[1].pow(2) + v[2].pow(2) - max.pow(2) == max.pow(2) {
            println!("YES");
        } else {
            println!("NO");
        }
    }
}



Measured memory_bytes: 5036
s=input()
t=input()
n=len(s)
n1=len(t)  
ans=10**10 
for i in range(n-n1+1):
    diff=0
    for j in range(n1):
        if(t[j]!=s[i+j]):
            diff+=1
    ans=min(ans,diff)
print(ans)

Measured memory_bytes: 72844
/* 163-A.cpp
 *     Created on : Apr 19, 2020 
 *     Time       : 5:57:48 PM
 *     Author     : null_ptr
 */
#include<bits/stdc++.h>

using namespace std;

const double pi=acos(-1);

int main()
{
	int n;
	cin>>n;
	cout<<setprecision(9)<<fixed;
	cout<<(pi*2.0*n);
}


Measured memory_bytes: 3788
#include<iostream>
#include"bits/stdc++.h"
using namespace std;
#define ll long long
#define FOR(i, j, k, in) for (ll i=j ; i<k ; i+=in)
#define RFOR(i, j, k, in) for (int i=j ; i>=k ; i-=in)
#define rep(i, j) FOR(i, 0, j, 1)
#define rrep(i, j) RFOR(i, j, 0, 1)
#define MP make_pair
#define PB push_back
#define INF (int)1e9
#define endl "\n"
#define MOD 1000000007
#define DEB(x) cout<<"##"<<x<<"##"<<endl;
void fastio()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
void solve1()
{
	int r;
	cin>>r;
	cout<<2*((double)(r))*(3.141592653589793238);
}
void solve()
{
	ll n,m;
	cin>>n>>m;
	int ar[m];
	ll sum=0;
	rep(i,m)
	{


		cin>>ar[i];
		sum+=ar[i];
	}
	ll x=-1;
	cout<<max(n-sum,x);
}
int main()
{
	fastio();
	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	#endif
	solve1();


	return 0;

	
}

Measured memory_bytes: 3800
def myAnswer(N:int,M:int,p:list,S:list) -> None:
   ac = 0
   wa = 0
   dic = {}
   for key,value in zip(p,S):
      if(key in dic.keys()):
         dic[key].append(value)
      else:
         dic[key] = [value]
   for values in dic.values():
      if(("AC" in values)):
         for v in values:
            if(v == "AC"):
               ac+=1
               break
            else:
               wa+=1
   print(ac,wa)

def modelAnswer():
   tmp=1
def main():
   N, M = map(int,input().split())
   p =[]
   S = []
   for _ in range(M):
      tmp = list(map(str,input().split()))
      p.append(tmp[0])
      S.append(tmp[1])
   myAnswer(N,M,p[:],S[:])
if __name__ == '__main__':
   main()


Measured memory_bytes: 34740
#include <stdio.h>
#include <math.h>

int main(void) {
	int w, h, n;
	int x, y, a;
	int S[100][100] = {  };
	scanf("%d %d %d", &w, &h, &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d %d %d", &x, &y, &a);
		switch (a)
		{
		case 1:
			for (int j = 0; j < x; ++j) {
				for (int k = 0; k < h; ++k) {
					S[k][j] = 1;
				}
			}break;
		case 2:
			for (int j = x; j < w; ++j) {
				for (int k = 0; k < h; ++k) {
					S[k][j] = 1;
				}
			}break;
		case 3:
			for (int j = 0; j < y; ++j) {
				for (int k = 0; k < w; ++k) {
					S[j][k] = 1;
				}
			}break;
		case 4:
			for (int j = y; j < h; ++j) {
				for (int k = 0; k < w; ++k) {
					S[j][k] = 1;
				}
			}break;
		default:
			break;
		}

	}
	int ans = 0;
	for (int i = 0; i < h; ++i) {
		for (int k = 0; k < w; ++k) {
			ans += 1-S[i][k];
		}
	}
	printf("%d", ans);
	return 0;
}

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

using namespace std;
#define f first
#define s second
#define p pair<int,int>
#define P pair<ll,ll>
#define pb push_back
#define ll long long
#define ull unsigned long long
#define db double
#define zero(a) memset(a,0,sizeof(a))
#define inff(a,n) fill(a,a+n+1,inf)
#define all(a) a.begin(),a.end()
#define sz(a) int((a).size())
#define read(x) scanf("%d",&x)
#define read2(x,y) scanf("%d%d",&x,&y)
#define write(x) printf("%d\n",x)


const ll inf = 1e9;

int n, m, cnt, ans, flag = 1, a[100001];
vector<int>v[100001];

void dfs(int u, int fa)
{
	for (auto i : v[u])
	{
		if (i == fa)continue;
		if (a[i] == -1)
		{
			a[i] = (a[u] ^ 1);
			dfs(i, u);
		}
		else
		{
			if (a[i] == a[u])flag = 0;
		}
	}
}

int main()
{
	cin >> n >> m;
	for (int i = 0; i<m; i++)
	{
		int x, y;
		cin >> x >> y;
		v[x].pb(y);
		v[y].pb(x);
	}
	memset(a, -1, sizeof(a));
	a[1] = 0;
	dfs(1, 0);
	if (flag)
	{
		for (int i = 1; i <= n; i++)if (a[i])cnt++;
		cout << 1ll * cnt*(n - cnt) - m;
	}
	else
	{
		cout << 1ll * n*(n - 1) / 2 - m;
	}
	return 0;
}

Measured memory_bytes: 6912
const Main = (input) => {
    array = input.split('\n')
    N = array.shift()
    array.pop()
    array = array[0].split(' ')
    arrayInt = array.map(item => parseInt(item))
    console.log(F(N, arrayInt[0], arrayInt[1]))
}

const F = (n, min, max) => {
    result = 'NG'
    for (i = min; i <= max; i++) {
        // console.log(i, min, max, i >= n, i % n == 0)
        if (i >= n && i % n == 0) {
            result = 'OK'
            break
        }
    }
    return result
}

//*この行以降は編集しないでください（標準入出力から一度に読み込み、mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 29628
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define rep(i,n) for (int i = (0); i < (n); ++i)
#define rng(x) (x).begin(),(x).end()
#define rrng(x) (x).rbegin(),(x).rend()
#define show(x) cout << #x << " = " << (x) << endl;
#define show2(x,y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define uni(x) x.erase(unique(rng(x)),x.end())
#define SP << " " <<
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const int mod = 1000000007;
const double EPS = 1e-9;
const int INF = 1<<30;
const ll INFLL = 1LL<<60;
//cout << fixed << setprecision(10);

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

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

  if (n%2 == 1) {
    cout << 0 << endl;
    return 0;
  }

  ll a5 = 0;
  for (ll i = 10; i <= n; i *= 5) {
    a5 += n/i;
  }

  ll ans = a5;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<set>

#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)

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;


template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
	for (auto& e : t) fill_v(e, v);
}


#define ARRAY_MAX 100005
const int INF = 1e9;
const ll MOD = 1e9 + 7;

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




/******************************************************************************************/


//繋げる方向を一方向にする
typedef struct union_find{
    
    vector<int> pa;//親
    vector<int> ra;//木の深さ
    vector<int> siz;
    //n要素で初期化
    void init(int n){
        pa.resize(n);
        ra.resize(n);
        siz.resize(n);
        for(int i = 0;i < n;i++){
            pa[i] = i;/*各ノードに番号を振る,この時par[x]=xとなる時は木の根となる*/
            ra[i] = 0LL;/*各ノード自体の高さは0*/
            siz[i] = 1LL;
        }
    }
    //木の根を求める
    int find(int x){
        if(pa[x] == x){
            return x;/*根ならそのノードの番号を返す*/
        }else{
            return pa[x] = find(pa[x]);/*根でないならさらにノードの根を探す*/
        }
    }

    //xとyの属する集合を併合する
    void unite(int x,int y){
        x = find(x);//xの根の番号を探す
        y = find(y);//yの根の番号を探す
        if(x == y){//一致すればつながっている
            return;
        }
        pa[y] = x;
        siz[x] += siz[y];
    }

    //xとyが同じ集合に属するか判定
    bool same(int x,int y){
        return find(x) == find(y);//同じ集合なら1、違うなら0が返る
    }
}UF;



int main(){

	int n, m;
	cin >> n >> m;
	int ans = 0;

	vector<int> x(m), y(m), z(m);
	UF tree;
	tree.init(n + 10);
	
	for (int i = 0; i < m; i++){
		cin >> x[i] >> y[i] >> z[i];
		x[i]--;
		y[i]--;
		tree.unite(x[i], y[i]);
	}

	set<int> st;
	for (int i = 0; i < n; i++)
	{
		st.insert(tree.find(i));
	}
	cout << st.size() << endl;





	
	return 0;
}


Measured memory_bytes: 7296
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(a==b)
printf("%d",c);
else if(b==c)
printf("%d",a);
else
printf("%d",b);
return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
inline void rd(char &c){
  int i;
  for(;;){
    i = getchar_unlocked();
    if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
      break;
    }
  }
  c = i;
}
inline int rd(char c[]){
  int i, sz=0;
  for(;;){
    i = getchar_unlocked();
    if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
      break;
    }
  }
  c[sz++] = i;
  for(;;){
    i = getchar_unlocked();
    if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF){
      break;
    }
    c[sz++] = i;
  }
  c[sz]='\0';
  return sz;
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(const char c[]){
  int i=0;
  for(i=0;c[i]!='\0';i++){
    putchar_unlocked(c[i]);
  }
}
int N;
char S[100002];
int main(){
  N = rd(S);
  if(S[0]==S[N-1]){
    N++;
  }
  if(N%2==0){
    wt_L("Second");
    wt_L('\n');
  }
  else{
    wt_L("First");
    wt_L('\n');
  }
  return 0;
}
// cLay varsion 20190902-1

// --- original code ---
// int N;
// char S[100002];
// {
//   rd(S@N);
//   if(S[0]==S[N-1]) N++;
//   wt( if[N%2==0, "Second", "First"] );
// }


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define pb push_back
#define ff first
#define ss second
#define rep(i,a,n) for(int i=a;i<n;i++)
#define M 1000000007
ll power(ll x, ll y, ll p)
{
    int res = 1;
    x = x % p;
    while (y > 0)
    {   if (y & 1)
        res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}
int main()
{
	IOS;
	int n;
	cin>>n;
	vector<double> dp(n+1);
	dp[0]=1;
	rep(i,0,n)
	{
		 double x;
		cin>>x;
		for(int j=i+1;j>=0;j--)
		{
			dp[j]=(j==0?0:dp[j-1]*x)+dp[j]*(1-x);
		}
	}
	 double ans=0;
	for(int i=0;i<=n;i++)
	{
		int k=n-i;
		if(k<i)
		ans+=dp[i];
	}
	printf("%.10lf\n",ans);
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
#include <map>
#include <string.h>
#include <cstring>
#include <stack>
#include <queue>

typedef long long ll;
#define ALL(obj) (obj).begin(),(obj).end()
#define MOD 1000000007


using namespace std;

long long GCD(long long x, long long y){
   long long r, tmp;
   if(x < y){
       tmp = x;
       x = y;
       y = tmp;
   }
   while(y!=0){
       r = x%y;
       x = y;
       y = r;
   }
   return x;
}
long long LCM(long long x, long long y){
   long long lcm = (x*y)/GCD(x, y);
   return lcm;
}

int bubblesort(int n){
    vector<int> data(n);
    int num=0;
    for(int end = n-1; end>0; end--){
        for(int j=0; j<end; j++){
            if(data[j+1] < data[j]){
                int temp = data[j];
                data[j] = data[j+1];
                data[j+1] = temp;
                num++;
            }
        }
    }
    return num;
}



int main(){
    ll n;
    cin >> n;
    vector<int> x(n), y(n);
    ll ans=0;
    for(int i=0; i<n; i++){
        cin >> x[i] >> y[i];
    }
    for(int i=0; i<n-2; i++){
        if(x[i]==y[i] && x[i+1]==y[i+1] && x[i+2]==y[i+2]){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3624
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>
#include<climits>
#include<iostream>
#include<iterator>
#include<string.h>
#include<algorithm>
#include<unordered_map>
#pragma GCC optimize "trapv"
using namespace std;

#define ld long double
#define ll long long int
#define pb push_back
#define mp make_pair
#define f(i,a,b) for(int i=a;i<b;i++)
#define pp pair<int,pair<int,int>>
#define ppp pair<pair<int,int>,pair<int,int>>

const ll M=998244353,N=1e5+2;

struct hash_pair{
	template <class T1, class T2>
	size_t operator()(const pair<T1, T2>& p) const{
		auto hash1 = hash<T1>{}(p.first);
		auto hash2 = hash<T2>{}(p.second);
		return hash1 ^ hash2;
	}
};

void sieve(){
	bool prime[N+1];
	memset(prime,true,sizeof(prime));
	for(ll p=2;p*p<=N;p++){
		if(prime[p] == true){
			for(ll i=p*p;i<=N;i+=p)
				prime[i] = false;
		}
	}
}

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

int root(int i,int A[]){
	while(A[i] != i){
		A[i] = A[A[i]];
		i = A[i];
	}
	return i;
}

void unite(int a,int b,int A[],int B[]){
	int c = root(a,A);
	int d = root(b,A);
	if(c == d)
		return;
	if(B[c] < B[d]){
		A[c] = d;
		B[d] += B[c];
	}
	else{
		A[d] = c;
		B[c] += B[d];
	}
}

inline ll in()
{
	ll n=0;
	bool check=0;
	register char c=getchar();
	while(c<'0' || c>'9')
	{
		if(c=='-')
			check=1;
		c=getchar();
	}
	while(c>='0' && c<='9')
	{
		n = (n<<1)+(n<<3)+c-'0';
		c=getchar();
	}
	return n-2*n*check;
}

string ip()
{
    string i="";
    int temp=getchar();
    while(temp<'a'||temp>'z')
        temp=getchar();
    while(temp>='a'&&temp<='z')
    {
        i+=(char)temp;
        temp=getchar();
    }
    return i;
}

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

	int n,m;
	cin>>n>>m;
	cout<<(m*(m-1))/2+(n*(n-1))/2;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

int main(){
	int n, cost, cnt, cmin, flag;
	cin >> n;
	vector<pair<int, int>> crd(n);
	pair<long long, long long> dp[n][n];

	if(n ==1){
		cout << 1 << endl;
		return 0;
	}
	for(int i=0; i<n; i++){
		cin >> crd[i].first >> crd[i].second;
	}
	for(int j=0; j<n; j++){
		for(int i=0; i<n; i++){
			dp[j][i].first = crd[j].first - crd[i].first;
			dp[j][i].second = crd[j].second - crd[i].second;
		}
	}
	cost = 0;
	cmin = 50;
	cnt = 0;
	flag = true;
//	for(int j=0; j<n; j++){
//		for(int i=0; i<n; i++){
//			cout << dp[j][i].first << ", " << dp[j][i].second << "  ";
//		}
//		cout << endl;
//	}
	cost = n;
	for(int j=0; j<n; j++){
		for(int i=0; i<n; i++){
//			cout <<"start: " << dp[j][i].first << ", " << dp[j][i].second << "  " << endl;
			if(j==i){
				continue;
			}

			cost = n;
			for(int k=0; k<n; k++){
				for(int l=0; l<n; l++){
					if((dp[j][i] == dp[k][l])){
						cost--;
						break;
					}	
				}
			}
			//cout << cost << endl;
			cmin = min(cmin, cost);
			cost = n;
		}
	}
	cout << max(cmin, 1) << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, a, b) for(int i = a; i < b; i++)
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  FastIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef long long int lli;
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 (a>b) { a=b; return true; } return false; }

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

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

int main(){
    int n;
    cin >> n;
    string s1, s2;
    cin >> s1 >> s2;
    vector<int> tate(n);
    rep(i,n) if (s1[i] == s2[i]) tate[i] = 1;
    mint ans;
    int i = 0;
    while(i < n){
        if (i == 0){
            if (tate[i]){
                ans = 3;
                i++;
            }else{
                ans = 3*2;
                i+=2;
            }

        }
        else{
            if (tate[i]){
                if (tate[i-1]){
                    ans *= 2;
                }
                i++;
            }else{
                if (tate[i-1]){
                    ans *= 2;
                }else{
                    ans *= 3;
                }
                i += 2;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3616
N,M=map(int,input().split())
a=[int(input()) for _ in range(M)]
MOD=10**9+7

dp=[0]*(N+1)
dp[0]=1
dp[1]=1
for i in a:
    dp[i]=-1
for i in range(2,N+1):
    if dp[i]==-1:
        continue
    if dp[i-1]!=-1:
        dp[i] = (dp[i]+dp[i-1])%MOD
    if dp[i-2]!=-1:
        dp[i] = (dp[i]+dp[i-2])%MOD

print(dp[N])


Measured memory_bytes: 50008
#include <bits/stdc++.h>
using namespace std;
int main(void){
    string s,t;
    cin>>s>>t;
    std::deque<char> S;
    std::deque<char> T;
    for (int i=0;i<s.size();i++) {
        S.emplace_back(s.at(i));
    }
    for (int j=0;j<t.size();j++) {
        T.emplace_back(t.at(j));
    }
    sort(S.begin(),S.end());
    sort(T.begin(),T.end(),greater<int>());
    string tmp_s="",tmp_t="";
    for (int k=0;k<S.size();k++) {
        tmp_s+=S[k];
    }
    for (int l=0;l<T.size();l++) {
        tmp_t+=T[l];
    }
    if (tmp_s<tmp_t) {
        cout<<"Yes"<<endl;
    } else {
        cout<<"No"<<endl;
    }
}


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

int main()
{
    string str;
    int t=0;
    getline(cin,str);

    for(int i=0;i<str.size();i++){
        if("peach"==str.substr(i,5)){
            i += 4;
            cout<<"apple";
        }
        else if("apple"==str.substr(i,5)){
            i += 4;
            cout<<"peach";
        }
        else cout<<str[i];
    }
    cout<<endl;
}

Measured memory_bytes: 1180
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
int f[100005],h[100005];

int main()
{
	int n,k;
	scanf("%d%d",&n,&k);
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=n;++i)
	scanf("%d",&h[i]);
	f[1]=0;
	for(int i=2;i<=n;++i)
	for(int j=1;j<=k;++j)
	if(i-j>=1)
	f[i]=min(f[i-j]+abs(h[i]-h[i-j]),f[i]);
	printf("%d",f[n]);
	return 0;
} 


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main() {
  char coffee[6];
  for (int i = 0; i < 6; ++i) cin >> coffee[i];
  cout << (coffee[2] == coffee[3] && coffee[4] == coffee[5] ? "Yes" : "No") << '\n';
  return 0;
}

Measured memory_bytes: 256
N = int(input())
##N, M = map(int, input().split())
D = list(map(int, input().split()))
if sum(D) > 0:
    target = int(sum(D) / N + 0.5)
else:
    target = int(sum(D) / N - 0.5)
ans = 0
for i in D:
    ans += (target - i)*(target - i)

print(ans)

Measured memory_bytes: 3060
#include<stdio.h>

int main(){
	int n,i,j,l[200],ans=0;
	scanf("%d",&n);
	for(i=0;i<2*n;i++)scanf("%d",&l[i]);
	for(i=0;i<2*n;i++){
		for(j=0;j<2*n;j++){
			if(l[i]<l[j]){
				int tmp=l[i];
				l[i]=l[j];
				l[j]=tmp;
			}
		}
	}
	for(i=0;i<2*n;i+=2)ans+=l[i];
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#include <limits.h>
int main()
{
    long a, b, c, d;
    scanf("%ld %ld %ld %ld", &a, &b, &c, &d);
    long long p, q, r, s;
    p = b * d;
    q = a * c;
    r = a * d;
    s = b * c;
    long long max = LLONG_MIN;

    //printf("%ld %ld %ld %ld\n", p, q, r, s);
    max = (max > p) ? max : p;
    max = (max > q) ? max : q;
    max = (max > r) ? max : r;
    max = (max > s) ? max : s;

    printf("%lld", max);
    return 0;
}


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

#define PII pair<int, int>
#define MP make_pair

using namespace std;

int main() {
	int l;
	scanf("%d", &l);
	vector<pair<PII, int>> edge;
	int n, hb = 0;
	for (n = 0; (1 << n) <= l; n++);
	for (int i = 1, k = 1 << (n - 1), kk; i < n; k = kk, i++) {
		kk = k >> 1;
		edge.push_back(MP(MP(i, i + 1), kk));
		edge.push_back(MP(MP(i, i + 1), 0));
		if (l & k) {
			if (i > 1) {
				edge.push_back(MP(MP(1, i), hb));
			}
			hb += k;
		}
	}
	if (hb < l) {
		edge.push_back(MP(MP(1, n), l - 1));
	}
	printf("%d %d\n", n, (int)edge.size());
	for (int i = 0; i < edge.size(); i++) {
		printf("%d %d %d\n", edge[i].first.first,
			edge[i].first.second, edge[i].second);
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
typedef vector<int> vec;
typedef vector<int64> vec64;
#define db(x) cout << "> " << #x << ": " << x << "\n";
#define ss cout << " ";
#define ct(x) cout << x;
#define nn cout << "\n";
#define cts(x) cout << x << " ";
#define ctn(x) cout << x << "\n";
#define qr queries();
void solve();
void YN(bool b){if (b){ctn("YES");}else{ctn ("NO");}};
void yn(bool b){if (b){ctn("Yes");}else{ctn ("No");}};
void queries(){int n;cin >> n;while (n--)solve();}
// // // // // // // // // // // // // // // // // // // // // // 
/*                  TEMPLATE - VANILLA                         */
// // // // // // // // // // // // // // // // // // // // // //
int64 q, n;

void solve(){

    return;
}


int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int64 a,b;
    cin >> a >> b;
    ctn((a * b) / __gcd(a, b));
    return 0;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
 
#define EPS 1e-9
#define INF 1070000000LL
#define mod 1000000007
#define all(x) (x).begin(),(x).end()
#define fir first
#define foreach(it,X) for(auto it=(X).begin();it!=(X).end();it++)
#define ite iterator
#define mp make_pair
#define mt make_tuple
#define rep(i,m,n) for(int i=m;i<(n);i++)
#define rep1(i,m,n) for(int i=m;i<=(n);++i)
#define pb push_back
#define sec second
#define sz(x) ((int)(x).size())
 
using namespace std;
 
typedef istringstream iss;
typedef long long ll;
typedef pair<int,int> pi;
typedef stringstream sst;
typedef vector<int> vi;
typedef vector<ll>vii;
vector<int>a;
  
  ll power(ll base, ll exp) 
{ 
    ll t = 1; 
    while (exp > 0)  
    { 
        if (exp % 2 != 0) 
            t = (t * base) % mod; 
  
        base = (base * base) % mod; 
        exp /= 2; 
    } 
    return t % mod; 
} 
 
 
 
int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
ll n;
cin>>n;
ll ans=power(10LL,n);
ans=(ans-power(9LL,n)+mod)%mod;
ans=(ans-power(9LL,n)+mod)%mod;
ans=(ans+power(8LL,n))%mod;
cout<<ans<<'\n';
	
 
}

Measured memory_bytes: 3616
#include<stdio.h>
#include<stdlib.h>
#define MAX 2000001
#define VM 10000

int main(){
  short *A,*B;
  
  int C[VM+1];
  int n,i,j;
  scanf("%d",&n);
  
  A=malloc(sizeof(short) * n + 1);
  B=malloc(sizeof(short) * n + 1);

  for(i=0;i<=VM;i++)C[i]=0;
  
  for(i=0;i<n;i++){
    scanf("%hu",&A[i+1]);
    C[A[i+1]]++;
  }

  for(i=1;i<=VM;i++)C[i] = C[i] + C[i-1];

  for(j=1;j<=n;j++){
    B[C[A[j]]]=A[j];
    C[A[j]]--;
  }

  for(i=1;i<=n;i++){
    if(i>1)printf(" ");
    printf("%d",B[i]);
  }
  printf("\n");

  return 0;
}

Measured memory_bytes: 8464
#include <iostream>
using namespace std;
int main() {
    int N, M; cin >> N >> M;
    int c[51] = {};
    for(int i = 0, a, b; i < M; i++) {
        cin >> a >> b;
        c[a]++; c[b]++;
    }
    for(int i = 1; i <= N; i++) cout << c[i] << endl;
}

Measured memory_bytes: 256
#include <stdlib.h>
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
using ll=long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
inline constexpr ll gcd(ll a,ll b){if(!a||!b)return 0;while(b){ll c=b;b=a%b;a=c;}return a;}
inline constexpr ll lcm(ll a,ll b){if(!a||!b)return 0;return a*b/gcd(a,b);}

int main() {
  long long a,b;
  cin>>a>>b;
  vector<pair<long long,long long>> vec;
  rep(i,a){
    long long c,d;
    cin>>c>>d;
    auto q=make_pair(c,d);
    vec.push_back(q);
  }
  sort(vec.begin(),vec.end());
  long long ret=0;
  long long count=0;
  bool flag=true;
  for(auto p:vec){
    long long j=p.first;
    long long k=p.second;
    long long cn=min(b,k);
    ret+=j*cn;
    b-=cn;
  }
  cout<<ret<<endl;
  

}


Measured memory_bytes: 2420
#include<iostream>
using namespace std;
int main(){
	
	int n,a[100];
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = n - 1; i >= 0; i--)
	{
                if (i < n - 1)
			cout << " ";
		cout << a[i];
		
	}
        cout <<endl;
	return 0;
}

Measured memory_bytes: 3072
#include <iostream>
#include<string>
#include<vector>
#include<stdio.h>

using namespace std;


int main()
{

	char a, b;

	cin >> a >> b;

	char ans;

	if (a > b) {
		ans = '>';
	}
	else if (a == b) {
		ans = '=';
	}
	else {
		ans = '<';
	}

	cout << ans << endl;






}



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

int main () 
{
    int a[3];
    
    std::cin >> a[0] >> a[1] >> a[2];
    
    sort(a, a+3);
    
    std::cout << a[0] << " " << a[1] << " " << a[2] << std::endl;
    
    return 0;
}


Measured memory_bytes: 3096
#include <iostream>

long long ckc[1000000], ckt[1000000], res;

int main()
{
    long long n;
    std::cin >> n;
    long long a[n + 1];
    for (long long i = 1; i <= n; i++)
    {
        std::cin >> a[i];
        if ((a[i] + i >= 0) && (a[i] + i <= 2 * 100000))
            ckc[a[i] + i]++;
        if ((i - a[i] >= 0) && (i - a[i] <= 2 * 100000))
            ckt[i - a[i]]++;
    }
    for (long long i = 0; i <= 2 * 100000; i++)
    {
        res += ckc[i] * ckt[i];
    }
    std::cout << res;
}

Measured memory_bytes: 8264
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
using namespace std;
const int N=1000000+10;
int n,m,d[N];
vector<int> g[N];
pair<int,int> p[N];
map< pair<int,int>,int > id;
set<int> st;
int col[N],ans[N];
void dfs(int u){
    int cnt=0;
    for(auto v: g[u]) {
        if(st.count(v)) {
            if(col[v]==0){
                col[v]=3-col[u]; 
                ans[id[make_pair(u,v)]] = d[u]; cnt++;
                dfs(v);
            } else if (col[v]+col[u]==3) {
                cnt ++;
            }
            continue;
        }
        if(col[v]==3-col[u]) {
            ans[id[make_pair(u,v)]] = d[u]; cnt++;
        }
    }
    if(cnt==0) {
        printf("-1\n"); exit(0);
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&d[i]),p[i]=make_pair(d[i],i);
    for(int i=1;i<=m;i++){
        int x,y; scanf("%d%d",&x,&y); 
        g[x].push_back(y); g[y].push_back(x);
        id[make_pair(x,y)]=id[make_pair(y,x)]=i;
    }
    sort(p+1,p+1+n);
    for(int i=1,j=1;i<=n;i=j){
        vector<int> tmp; st.clear();
        while(j<=n && p[j].first==p[i].first) {
            tmp.push_back(p[j].second); st.insert(p[j].second); j++;
        }
        //printf("!\n");
        for(auto x: tmp){
            //printf("%d ",x);
            if(col[x]==0){
                for(auto v: g[x]) {
                    if(col[v]) {
                        col[x]=3-col[v];
                    }
                } 
                if(!col[x]) col[x]=1; 
                dfs(x);
            }
        }
        //printf("\n");
    }
    for(int i=1;i<=n;i++){
        printf("%c", col[i]==1?'W':'B');
    }
    printf("\n");
    for(int i=1;i<=m;i++){
        printf("%d\n", ans[i]?ans[i]:(int)1e9);
    }
}


Measured memory_bytes: 68760
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0089
"""
import sys


def solve(data):
    """
    ??????????????????????????????????????§????????????????????????????????????
    (2????????\??????)??????????´????????????????????????????????????????????????????????´???????????????°?????§????????????
    ????????????????????????????????§???????????????????????????????????°?????????????????????????????§???????????????
    ????????????????????§??°???????????°??????????????????????????????
    :param data: ??±??¢?????\????????????
    :return: ?????§???????????£?????????????¨????
    """
    increasing = True           #  ??±??¢????¨????????¢???????????????£??????????????????????????????????????°
    prev_line = data[0]
    for curr_line in data[1:]:
        if len(curr_line) < len(prev_line):
            increasing = False
        for i, ele in enumerate(curr_line):
            if increasing:
                try:
                    up_left = prev_line[max(0, i-1)] #  prev_line[-1]?????¨?????????????????£?????????????????§???index???????????°??????????????????????????????
                except:
                    up_left = 0
                try:
                    up_right = prev_line[i]
                except:
                        up_right = 0
                curr_line[i] += max(up_left, up_right)
            else:               #  ??±??¢????¨???????????????§???????????????????????????[i], [i+1]??????????????¨???????????§?????\??????????????????
                    curr_line[i] += max(prev_line[i], prev_line[i+1])
        prev_line = curr_line
    return data[-1][0]


def main(args):
    data = []
#    data.append([7])
#    data.append([3,8])
#    data.append([8,1,0])
#    data.append([2,7,4,4])
#    data.append([4,5,2,6,5])
#    data.append([2,7,4,4])
#    data.append([8,1,0])
#    data.append([3,8])
#    data.append([7])

    for line in sys.stdin:
        data.append([int(x) for x in line.split(',')])
    result = solve(data)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

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

using namespace std;

int main(){
    long long N ,cnt = 0;
    cin>>N;
    for (int i = 1;i<=N;i++){
        for (int j = 1;i<=N;j++){
            if (i * j < N)
                cnt++;
            else
                break;
        }
    }
    cout<<cnt<<endl;
}


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

#define rep(i, n) for (int i = 0; i < n; i++)
#define rep1(i, n) for (int i = 1; i <= n; i++)
#define show(a, n) rep(i,n) {cout<<a[i]<<' ';} cout<<endl;

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

const int INF = 1 << 30;
const long long INFL = 1LL << 62;
const int MOD = 1000000007;
const int MAX = 100000;
const int N = 100000;

int main() {
	ll a, b;
	cin >> a >> b;
	ll ans = 0;
	rep(i, 50) {
		ll p = 1ll << (i + 1ll);
		ll c = (b + 1) / p * (p / 2) + max((b + 1) % p - p / 2, 0ll);
		c -= a / p * (p / 2) + max(a % p - p / 2, 0ll);
		ans |= (c % 2) << i;
	}
	cout << ans << endl;
}


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

#define ll long long
#define ar array

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

    int k, n;
    cin >> k >> n;
    int a[n];
    for(int i=0; i<n; ++i)
        cin >> a[i];
    int ans=a[n-1]-a[0];
    for(int i=1; i<n; ++i)
        ans=min(a[i-1]+k-a[i], ans);
    cout << ans;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define rep(i,c) for(int i=0;i<c;++i)
#define swap(a,b,type)do{type temp; temp= a;a = b; b= temp;}while(0); 
int main(){
 int a;
 cin >> a;
 float c = 380000.0;
 float d = 0;
 vector< pair< float,string> >b(a);
 rep(i,a){
     cin >> b[i].first >> b[i].second ;
 }
 rep(i,a){
     if(b[i].second=="BTC"){
       d += c*b[i].first;
     }else{
         d+=b[i].first;
     }
 }
 cout << d<< endl;

 return 0; 
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <math.h>

using namespace std;

int main() {
	int N,ans1,ans2;
	double x;
	cin >> N;
	x = (double)N/1.08;
	ans1 = x;
	ans2 = x+1;
	if(int(ans1 * 1.08) == N){
		cout << ans1;
	}
	else if(int(ans2 * 1.08) == N){
		cout << ans2;
	}
	else{
		cout << ":(";
	}
	return 0;
}

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

int main(){
	int a,b,ca[5000],cb[5000],ma = 0;
	cin >> a >> b;
	for(int i = 0;i < a;i++) cin >> ca[i];
	for(int i = 0;i < b;i++) cin >> cb[i];
	for(int i = 0;i < b;i++){
		int bcnt = 0;
		for(int j = 0;j < a;j++){
			if(ca[j] == cb[i + bcnt]) bcnt++;
		}
		ma = max(bcnt,ma);
	}
	cout << ma << endl;
	return 0;	
}

Measured memory_bytes: 3132
#include<cstdio>
long long s[2][100002];
long long const infty=1e15;
long long max(long long a,long long b){
    return (a<b)?b:a;
}
long long min(long long a,long long b){
    return (a<b)?a:b;
}
long long min(long long a,long long b,long long c){
    return min(a,min(b,c));
}
long long min(long long a,long long b,long long c,long long d){
    return min(min(a,b),min(c,d));
}
int main(){
    int a[2],q;
    scanf("%d%d%d",&a[0],&a[1],&q);
    for(int i=0;i<2;i++){
        s[i][0]=-infty;
        for(int j=1;j<=a[i];j++)scanf("%lld",&s[i][j]);
        s[i][a[i]+1]=infty;
    }
    for(int qi=0;qi<q;qi++){
        long long x;
        scanf("%lld",&x);
        int l[2],r[2];
        long long dl[2],dr[2];
        for(int i=0;i<2;i++){
            l[i]=0;
            r[i]=a[i]+1;
            while(r[i]-l[i]>1){
                int m=(r[i]+l[i])/2;
                if(s[i][m]<x)l[i]=m;
                else r[i]=m;
            }
            dl[i]=x-s[i][l[i]];
            dr[i]=s[i][r[i]]-x;
        }
        //左に直進: 左側の遠いほうまでの距離
        //右に直進: 右側の遠いほうまでの距離
        //方向転換: 左右の近いほうまでの距離の和+xまで戻る距離
        printf("%lld\n",min(max(dl[0],dl[1]),max(dr[0],dr[1]),min(dl[0],dr[0])+min(dl[1],dr[1])+min(dl[0],dl[1],dr[0],dr[1])));
    }
    return 0;
}

Measured memory_bytes: 2816