akhauriyash/Code-Regression huggingface dataset:
import Control.Monad
import Data.Array
import qualified Data.ByteString.Char8 as BS
import Data.Char
import Data.List
import Data.Maybe

readInts :: IO [Integer]
readInts = map (fst . fromJust . BS.readInteger) . BS.words <$> BS.getLine

readStrings :: IO [BS.ByteString]
readStrings = BS.words <$> BS.getLine

splitBy :: (a -> Bool) -> [a] -> [[a]]
splitBy p [] = []
splitBy p xs = a : splitBy p (dropWhile p b)
  where
    (a, b) = break p xs

main :: IO ()
main = do
  c <- getChar
  putChar $ succ c
  putStrLn ""

Measured memory_bytes: 380
#include <bits/stdc++.h>
#include <atcoder/all>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
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;
}

const long long INF = 1e18;
//const ll mod = 1000000007;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll T;
    cin >> T;
    while(T--) {
        ll N, M, A, B;
        cin >> N >> M >> A >> B;
        ll ans = atcoder::floor_sum(N, M, A, B);
        cout << ans << endl;
    }
    return 0;
}

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

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define pb(i) push_back(i)
#define INF 100100100
#define EPS 1e-9
#define itn int
typedef long long ll;
typedef vector<int> vi;
typedef map<string, int> msi;


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

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


int in() {int x; cin >> x; return x;}

int main()
{
    int n;

    cin >> n;

    if (n % 4 == 0) {
        cout << "Yes" << endl;
    }
    else if (n % 7 == 0) {
        cout << "Yes" << endl;
    }
    else if (n % 11 == 0) {
        cout << "Yes" << endl;
    }
    else {
        while (n > 0) {
            if ((n - 4) % 7 == 0){
                cout << "Yes" << endl;
                return (0);
            }
            else {
                n -= 4;
            }
        }
        cout << "No" << endl;
    }
    return (0);
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;

LL a[505][505];

int main(){
	ios::sync_with_stdio(false);
	LL n,k;
	cin >> k;
	
	n = min(500LL,k);
	for(LL i = 1;i <= n;i ++){
		for(LL j = 1;j <= n;j ++){
			a[j][i] = i;
		}
	}
	if(k > 500){
		k -= 500;
		for(LL i = 1;i <= k;i ++){
			for(LL j = 2;j <= n;j += 2){
				a[j][i] += n;
			}
		}
	}
	
	cout << n << endl;
	for(LL i = 1;i <= n;i ++){
		for(LL j = i;j <= n;j ++) cout << a[i][j] << ' ';
		for(LL j = 1;j < i;j ++) cout << a[i][j] << ' ';
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 3200
#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"

using namespace std;

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i8 = int8_t;
using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;

using vi = vector<int>;

constexpr char newl = '\n';
constexpr double eps = 1e-10;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define F0R(i,b) FOR(i,0,b)
#define RFO(i,a,b) for (int i = ((b)-1); i >=(a); i--)
#define RF0(i,b) RFO(i,0,b)
#define fi first
#define se second
#define show(x) cout << #x << " = " << x << '\n';
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define sz(x) (int)(x).size()
#define YesNo {cout<<"Yes";}else{cout<<"No";}
#define YESNO {cout<<"YES";}else{cout<<"NO";}
#define v(T) vector<T>
#define vv(T) v(v(T))

template<typename T1, typename T2> inline void chmin(T1& a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
template<class T> bool lcmp(const pair<T, T>& l, const pair<T, T>& r) {
  return l.first < r.first;
}
template<class T> istream& operator>>(istream& i, v(T)& v) {
  F0R(j, sz(v)) i >> v[j];
  return i;
}
template<class T> ostream& operator<<(ostream& o, const vector<T>& v) {
  F0R(i, v.size()) {
    o << v[i] << ' ';
  }
  o << newl;
  return o;
}
template<class T1, class T2> ostream& operator<<(ostream& o, const map<T1, T2>& m) {
  for (auto& p : m) {
    o << p.first << ": " << p.second << newl;
  }
  o << newl;
  return o;
}

#if 1


// INSERT ABOVE HERE
signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int N, M;
  cin >> N >> M;
  vector<vector<pair<int,int>>> as(N+1);
  F0R(i, M) {
    int p, y;
    cin >> p >> y;
    as[p].emplace_back(y, i);
  }
  vector<pair<int, int>> bs(M);
  F0R(i, as.size()) {
    sort(rng(as[i]), lcmp<int>);
    F0R(j, as[i].size()) {
      bs[as[i][j].second] = { i, j };
    }
  }

  cout << setfill('0');
  F0R(i, M) {
    cout << setw(6) << bs[i].first << setw(6) << (bs[i].second + 1) << newl;
  }
}
#endif


Measured memory_bytes: 9524
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<numeric>

#define rep(n) for(int i=0;i<n;i++)
#define repp(j, n) for(int j=0;j<n;j++)
#define reppp(i, m, n) for(int i=m;i<=n;i++)
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define pb(x) push_back(x)
#define eb(x,y) emplace_back(x,y)
#define MOD 1000000007
#define MAX 1000000001
#define INF 1410065408
#define EPS 1e-9
#define DEBUG 0
#define ll long long
#define Pll pair<ll, ll>
#define Pii pair<int, int>
 
using namespace std;
struct edge{int from, to; ll cost;};

signed main(){
    ios::sync_with_stdio(false); cin.tie(0);
    vector<ll> a(7);
    rep(7) cin >> a[i];
    ll ans = a[1], tmp = a[1];
    int v [3] = {0, 3, 4};
    rep(3){
        if(a[v[i]] >= 2) ans += a[v[i]] / 2 * 2;
    }
    if(a[0] == 1 && a[3] == 1 && a[4] == 1) ans += 3;

    if(a[0] > 0 && a[3] > 0 && a[4] > 0) tmp += 3;
    rep(3){
        a[v[i]]--;
        if(a[v[i]] >= 2) tmp += a[v[i]] / 2 * 2;
    }
    cout << max(ans, tmp);
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    int a, b;
    int asum = 0, bsum = 0, cnt = 0;
    while(scanf("%d,%d", &a, &b) != EOF){
        asum += a*b; bsum += b; cnt++;
    }
    printf("%d\n%d\n", asum, (bsum*2+cnt)/(2*cnt));
    return 0;
}


Measured memory_bytes: 3136
/*
    問題をよく読もう！
    論理的に考えよう！
    サンプルを確認しよう!
    絶対に諦めるな！
    工夫をしろ！

    Twitterは終わるまでログアウト！
    （間違えて解法をツイートしてはいけないから）

*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <functional>
using namespace std;
#define rep(i, n) for(int i=0; i<n; ++i)
typedef long long ll;
//必要な宣言

int main() {
  int N;
  int d[100];
  cin >> N;
  rep(i, N) cin >> d[i];
  int now_size;
  int cnt = 0;

  sort(d, d+N, greater<int>());

  now_size = d[0];
  cnt += 1;

  for(int i=1; i<N; ++i) {
    if(d[i] < now_size) {
      now_size = d[i];
      cnt += 1;
    }
  }

  cout << cnt << endl;

  return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>

#define CH(N,A,B) (A<=N&&N<B)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define RREP(i,a,b) for(int i=(b-1);a<=i;i--)

using namespace std;

int N, M;
pair<int,int> p[10005];

int main() {
  while(1){
    cin>>N>>M;
    if(N==0&&M==0) break;
    long long sum = 0;
    REP(i,0,N){
      int a, b;
      cin>>a>>b;
      p[i] = make_pair(b,a);
      sum += a*b;
    }
    //sort(p,p+N);
    sort(p,p+N,greater< pair<int,int> >());

    long long diff = 0;
    //for(int i = N-1; 0<=i; i--){
    REP(i,0,N){
      if(M == 0) break;
      int tmp = min(M, p[i].second);
      diff += p[i].first*tmp;
      M -= tmp;
    }
    cout<<sum - diff<<endl;
  }
  return 0;
}

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

constexpr int Maxn=100000;

inline int Max(const int&x,const int&y)
	{return x>y?x:y;}
inline void chkMax(int&x,const int&y)
	{(x<y)&&(x=y);}

namespace IOManager{
	constexpr int FILESZ(131072);
	unsigned char buf[FILESZ];
	const unsigned char*ibuf=buf,*tbuf=buf;

	struct IOManager{
		inline unsigned char gc()
			{return(ibuf==tbuf)&&(tbuf=(ibuf=buf)+fread(buf,1,FILESZ,stdin),ibuf==tbuf)?EOF:*ibuf++;}

		template<class _Tp>
			inline operator _Tp(){
				_Tp s=0u;unsigned char c=gc();
				for(;c<48;c=gc());
				for(;c>47;c=gc())
					s=(_Tp)(s*10u+c-48u);
				return s;
			}
	};
}IOManager::IOManager io;

int cnt[2][Maxn+1];

int main(){
	const int n=io;
	for(int i=1;i<=n;++i)
		++cnt[i&1][(int)io];

	auto mxp1=std::max_element(cnt[0]+1,cnt[0]+Maxn+1);
	auto mxp2=std::max_element(cnt[1]+1,cnt[1]+Maxn+1);
	int mx1=*mxp1,mx1p=mxp1-cnt[0],mx2=*mxp2,mx2p=mxp2-cnt[1];
	*mxp1=*mxp2=0;
	mxp1=std::max_element(cnt[0]+1,cnt[0]+Maxn+1);
	mxp2=std::max_element(cnt[1]+1,cnt[1]+Maxn+1);

	printf("%d",n-(mx1p==mx2p?Max(mx1+*mxp2,mx2+*mxp1):mx1+mx2));

	return 0;
}


Measured memory_bytes: 1024
n = int(input())
l = list(map(int,input().split()))

def elements(dim):
    ans = []
    cnt = 2
    while cnt <= dim:
        if dim % cnt == 0:
            dim //= cnt
            ans.append(int(cnt))
            cnt = 2
        else:
            cnt += 1
    return ans

l_e = []

for i in l:
    i_e = elements(i)
    for j in i_e:
        if j in l_e:
            l_e.remove(j)
    l_e += i_e

out = 1
for i in l_e:
    out *= i
print(out)


Measured memory_bytes: 5596
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define N1 101
#define INF (1e9)
#define f first
#define s second
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P > P1;
void dijkstra();
int d[N1][N1],N,M,L,A,B,D,E;
P cost[N1][N1];
int main(){
  while(1){
    cin >> N >> M >> L;
    if(N==0&&M==0&&L==0) break;
    for(int i=0;i<N1;i++)
      for(int j=0;j<N1;j++) d[i][j]=INF,cost[i][j].f=cost[i][j].s=-1;
    for(int i=0;i<M;i++) cin >> A >> B >> D >> E,cost[A][B]=cost[B][A]=make_pair(D,E);
    dijkstra();
    int ans=INF;
    for(int i=0;i<=L;i++) ans=min(ans,d[i][N]);
    cout << ans << endl;
  }
  return 0;
}
void dijkstra(){
  priority_queue<P1,vector<P1>,greater<P1> > PQ;
  PQ.push(make_pair(0,make_pair(0,1)));
  d[0][1]=0;
  while(!PQ.empty()){
    P1 t=PQ.top();
    PQ.pop();
    int u=t.s.s,l=t.s.f,cos=t.f;
    if(cos<d[l][u]) continue;
    for(int i=1;i<=N;i++){
      int dd=cost[u][i].f,ee=cost[u][i].s;
      if(dd!=-1&&ee!=-1&&i!=u){
	if(d[l][i]>d[l][u]+ee){
	  d[l][i]=d[l][u]+ee;
	  PQ.push(make_pair(d[l][i],make_pair(l,i)));
	}
	if(L-l>=dd&&d[l+dd][i]>d[l][u]){
	  d[l+dd][i]=d[l][u];
	  PQ.push(make_pair(d[l+dd][i],make_pair(l+dd,i)));
	}
      }
    }
  }
}

Measured memory_bytes: 1700
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n); i >= 0; i--)
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define ALL(obj) begin(obj), end(obj)
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int INF = 2100100100;
const int MOD = 1e9 + 7;

// 多次元 vector 生成
template <class T> vector<T> make_vec(size_t a) { return vector<T>(a); }
template <class T, class... Ts> auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

bool is_prime(long long n) { // is n prime or not
    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}

vector<bool> prime_table(int n) { // table:= false: not prime, true: prime
    vector<bool> prime(n + 1, true);
    if (n >= 0)
        prime[0] = false;
    if (n >= 1)
        prime[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (!prime[i])
            continue;
        for (int j = i + i; j <= n; j += i) {
            prime[j] = false;
        }
    }
    return prime;
}

map<long long, int> prime_factor(long long n) { // prime factorization
    map<long long, int> ret;
    for (long long i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            ret[i]++;
            n /= i;
        }
    }
    if (n != 1)
        ret[n] = 1;
    return ret;
}

vector<long long> divisor(long long n) { // all divisors of n
    vector<long long> ret;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n)
                ret.push_back(n / i);
        }
    }
    sort(ret.begin(), ret.end());
    return ret;
}

int main() {

    int n, m;
    cin >> n >> m;
    auto div = divisor(m);

    sort(ALL(div), greater<ll>());

    for (auto d : div) {
        if (m / d < n) {
            continue;
        } else {
            cout << d << endl;
            return 0;
        }
    }

    return 0;
}


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

#define ll          long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)
using namespace std;
int f[2020];
void solve(){
    string s;
    cin>>s;
    f[0]=1;
    int cur=1,mod=0;
    ll ans=0;
    for(int i=sz(s)-1;i>=0;i--){
        mod=(mod+cur*(s[i]-'0'))%2019;
        cur=cur*10%2019;
        ans+=f[mod];
        f[mod]++;
    }
    cout<<ans<<endl;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}


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

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<(n);i++)
#define loop(i,a,n) for(i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define int ll
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;

signed main(void) {
  int i,j;
  int n;
  cin>>n;
  vi a(n),b(n);
  rep(i,n)cin>>a[i];
  rep(i,n)cin>>b[i];

  int x=0;
  int sum=0;
  rep(i,n){
    int t=b[i]-a[i];
    sum+=b[i]-a[i];
    if(t>=0)
      x+=(t+1)/2;
  }
  if(x<=sum)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#define int long long int
#define endl "\n"
using namespace std;
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int t=1;
    // cin >> t;
    while (t--) {
        int n;;
        cin>>n;
        int a[n];
        int count=0;
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                count+=a[i]*a[j];
            }
        }
        cout<<count<<endl;
    }
    return 0;
}

Measured memory_bytes: 3608
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;
int a[100010],n,M;
ll gao1(){
	ll s;
	int i;
	M=n;
	s=0;
	for(i=3;i<n;i+=2)s+=2*a[M--];
	s+=a[M--];
	if(n&1)
		s+=a[M--];
	else
		s-=a[M--];
	while(M)s-=2*a[M--];
	return s;
}
ll gao2(){
	ll s;
	int i;
	M=n;
	s=0;
	for(i=2;i<n;i+=2)s+=2*a[M--];
	if(n&1)
		s-=a[M--];
	else
		s+=a[M--];
	s-=a[M--];
	while(M)s-=2*a[M--];
	return s;
}
int main(){
	int i;
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",a+i);
	sort(a+1,a+n+1);
	printf("%lld",max(gao1(),gao2()));
}

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

using namespace std;

int main()
{

    string b;
    cin >> b;

    if (b == "A")
    {
        cout << "T" << endl;
    }
    if (b == "T")
    {
        cout << "A" << endl;
    }
    if (b == "G")
    {
        cout << "C" << endl;
    }
    if (b == "C")
    {
        cout << "G" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
N, M, X = map(int, input().split())
C = []
A = []
for i in range(N):
    l = list(map(int, input().split()))
    C.append(l[0])
    A.append(l[1:])

mn = 1e9
for i in range(2 ** N):
    p = [0] * M
    v = 0
    for j in range(N):
        if (1 << j) & i:
            v += C[j]
            for k in range(M):
                p[k] += A[j][k]
    if min(p) >= X:
        mn = min(mn, v)
print(mn if mn != 1e9 else -1)

Measured memory_bytes: 9220
#include <iostream>
#include <array>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <string>
using namespace std;

int main(){
    int N, A, B;
    cin >> N >> A >> B;

    if(A + B - 1 > N){
        cout << -1 << endl;
        return 0;
    }

    vector<int> ans;
    int rest = N - A;
    int now = 0;
    for(int i = 0; i < A; ++i){
        if(rest > 0){
            int temp = min(rest + 1, B);
            for(int j = 0; j < temp; ++j){
                ans.push_back(now + temp - j);
            }
            now += temp;
            rest -= temp - 1;
        } else {
            ans.push_back(now + 1);
            now++;
        }
    } 
    if(ans.size() != N){
        cout << "-1" << endl;
        return 0;
    }
    for(int i = 0; i < N; ++i){
        cout << ans[i];
        if(i != N - 1) cout << " ";
    }
    cout << endl;
}

Measured memory_bytes: 3440
#include<bits/stdc++.h>
using namespace std;
int main()
{

    long a,b,c,d=0,e,g,f,h,i,j,k,l,m,n,x,y,z;
    cin>>a>>b;
    vector<long>vc;
    for(i=0;i<a;i++)
    {

        cin>>c;
        vc.push_back(c);


    }

    sort(vc.begin(),vc.end());
    for(i=0;i<b;i++)
        d+=vc[i];

    cout<<d<<endl;



}


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

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

  for(int i=x-(k-1); i<=x+(k-1); i++){
    cout << i;
    if(i != x+(k-1)) cout << " ";
  }

  cout << endl;

}


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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<ll, pair<ll, ll> > P3;

const ll MOD = ll(1e9 + 7);
const ll LLINF = LLONG_MAX;
const int IINF = INT_MAX;
const int MAX_N = int(1e5) + 5;
const double EPS = 1e-8;
const int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
string dir[] = {"R", "D", "L", "U"};
#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 (ll i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()

struct UF{
    int p[MAX_N], r[MAX_N];
    void init(int N){
        REP(i,N){
            p[i] = i;
            r[i] = 0;
        }
    }
    int find(int x){
        if(p[x] == x)return x;
        else return p[x] = find(p[x]);
    }
    void unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x==y)return;
        if(r[x]<r[y])swap(x,y);
        if(r[x]==r[y])r[x]++;
        p[y] = x;
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
};

P x[MAX_N], y[MAX_N];

int main() {
    int n;
    
    cin >> n;
    REP(i,n){
        cin >> x[i].first >> y[i].first;
        x[i].second = i;
        y[i].second = i;
    }
    sort(x,x+n);
    sort(y,y+n);
    vector<P3> ls;
    REP(i,n){
        ls.push_back({abs(x[i+1].first-x[i].first),{x[i].second,x[i+1].second}});
        ls.push_back({abs(y[i+1].first-y[i].first),{y[i].second,y[i+1].second}});
    }
    sort(ALL(ls));
    int ans = 0;
    UF g;
    g.init(n);
    for(auto i : ls){
        P e = i.second;
        if(!g.same(e.first,e.second)){
            g.unite(e.first,e.second);
            ans += i.first;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 9968
#include<string>
#include<iostream>
#include <algorithm>
#include<vector>
#include<functional>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <numeric>
#define ll long long
#define rep(i,n) for(ll i=0;i<(ll)n;i++)
using namespace std;



int main() {
    ll N, A;
    ll ans;
    cin >> N >> A;
    ans = N * N - A;
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>
#include <cmath>

using namespace std;
typedef long long ll;
ll mod = 1e9+7;
//ll mod = 998244353;
#define rep(i,n) for(int i = 0; i < (n); ++i)

int main() {
    ll N;
    cin >> N;
    for (ll h = 1; h <= 3500; ++h) {
        for (ll n = 1; n <= 3500; ++n) {
            ll a = 4 * h * n;
            ll b = N * n;
            ll c = N * h;
            ll d = N * h * n;
            if (a - b - c >= 1 && d % (a - b - c) == 0) {
                cout << h << " " << n << " " << d / (a - b - c) << endl;
                return 0;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 3652
n=io.read("*n", "*l")
odd=0
four=0
for i=1, n do
    a=io.read("*n")
    if a%2==1 then
        odd=odd+1
    elseif a%4==0 then
        four=four+1
    end
end

if four==odd-1 and four+odd==n then
    print("Yes")
elseif four==odd then
    print("Yes")
elseif four==n then
    print("Yes")
else 
    print("No")
end

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cstdlib>
#define ll long long
#define FOR(i,x,y) for(ll i=(ll)x; i<(ll)y; ++i)
#define MX 100010
using namespace std;

int n,k;
string s;
string ans;
char t;
int main(){
        cin >> n >> s >> k;
        ans = s;
        t = ans[k-1];
        FOR(i,0,n){
                if(s[i] != t) ans.replace(i,1,"*");
        }
        cout << ans << endl;

        return 0;
}


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

int main() {
	int H, W;
	while (1) {
		(void)scanf("%d %d", &H, &W);
		if (!H && !W) break;
		for (int i = 0; i < H; i++) {
			for (int i = 0; i < W; i++) {
				printf("#");
			}
			printf("\n");
		}
		printf("\n");
	}
	return 0;
}


Measured memory_bytes: 2684
#include <iostream>
#include <string>
using namespace std;
int main()
{
    string s;
    int i = 0, num[20] = {0}, z = 0, j = 0, ten = 100, total = 0, d = 1000, d1 = 0;
    cin >> s;
    for(i = 0; i < s.size(); i++)
    {
        s[i] -= 48;
    }

    for(j = 1; j <= s.size() - 2; j++)
    {
        for(i = z; i <= z + 2; i++)
            {
                total = total + int(s[i]) * ten;
                ten /= 10;
            }
            ten = 100;
            z++;
            if(total > 753)
            {
                d1 = total - 753;
            }
            else
            {
                d1 = 753 - total;
            }
            if(d1 <= d)
            {
                d = d1;

            }
            total = 0;
    }
    cout << d;
return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() 
{
	ll N;
	cin>>N;
    bool flag=false;
	ll h=0,n=0,w=0;
	for(ll i=1;i<=3500;i++){
      if(flag) break;
		for(ll j=1;j<=3500;j++){
          ll tmp2=4*i*j-N*(i+j);
          ll tmp1=N*i*j;
          if(tmp2<=0) continue;
          if(tmp1%tmp2==0&&tmp1>=tmp2){
			h=i;
			n=j;
			w=N*i*j/(4*i*j-N*(i+j));
            flag=true;
            break;
          }
        }
	}

	cout<<h<<" "<<n<<" "<<w;

}

Measured memory_bytes: 256
S = input()
S.split()

N = len(S)

for i in range(N//2):
    if (S[i*2] == 'R' or S[i*2] == 'U' or S[i*2] == 'D') and \
            (S[i*2 + 1] == 'L' or S[i*2 + 1] == 'U' or S[i*2 + 1] == 'D'):
        continue
    else:
        print('No')
        exit(0)
if N%2 != 0:
    if S[N-1] == 'R' or S[N-1] == 'U' or S[N-1] == 'D':
        print('Yes')
    else:
        print('No')
        exit(0)
else:
    print('Yes')


Measured memory_bytes: 3064
import sys
readline = sys.stdin.buffer.readline

def func(lst):
    res = 0
    for i in range(1,n):
        if lst[i]==lst[i-1]:
            res += 1
    return res


if __name__ == "__main__":
    n = int(readline())
    lst1 = list(map(int,readline().split()))
    lst1.sort()

    same = func(lst1)

    if same%2 != 0:
        print(n-same-1)
    else:
        print(n-same)


Measured memory_bytes: 52464
#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
// https://atcoder.jp/contests/abc168/tasks/abc168_c
long double getRad(long double th){
	return th * 3.14159265358979323846 / 180;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

	long double ans;
	long double a,b,h,m;
	cin >> a >> b >> h >> m;
	long double temp = a*a + b*b;
	long double h_angle = h * 30;
	long double m_angle = m * 6;
	h_angle += m_angle/12;
	long double th = getRad(abs(h_angle - m_angle));
	ans = temp - 2*a*b*cos(th);
	ans = sqrt(ans);
    cout << fixed;
	cout.precision(20);
	cout << ans << "\n";


    return 0;
}

Measured memory_bytes: 4152
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
const ll INF = 1e+14;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back

void Yes(){
    cout<<"Yes"<<endl;
    exit(0);
}
 
void No(){
    cout<<"No"<<endl;
    exit(0);
}
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;
}

int main() {
   ios::sync_with_stdio(false);
   cin.tie(0);
   int N, W; cin >> N >> W;
   ll w[110], v[110]; rep(i, N) cin >> w[i] >> v[i];
   ll dp[110][100100]; //i-1番目までの品を選んで重さがj以下の時の価値の最大
   rep1(i, N) {
      rep(j, W + 1) {
         chmax(dp[i][j], dp[i - 1][j]);
         if(j - w[i - 1] >= 0) chmax(dp[i][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
      }
   }
   cout << dp[N][W] << endl;
   return 0;
}

Measured memory_bytes: 80384
n = int(input())
a = []
for i in range(n):
    t = int(input())
    a.append(t)
a.sort()
count = 1
ans = 0
for i in range(1,n):
    if a[i] == a[i-1]:
        count+=1
    elif count % 2 == 0:
        count = 1
    else:
        ans += 1
        count = 1
if count%2 == 1:
    ans+=1
print(ans)

Measured memory_bytes: 7388
#include <iostream>

using namespace std;
int d[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int main()
{
    int a, b, cnt(0);
    cin >> a >> b;
    for(int i = 1; i <= a; i++)
        for(int j = 1; j <= ((i == a) ? b : d[i]); j++)
            if(i == j)
            {
                //cout << i << " " << j;
                cnt++;
            }
    cout << cnt;
}


Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main() {
	
	int m, f, r;
	
	while( cin >> m >> f >> r) {
		
		if( m != -1 && f != -1 ){
		if( m + f >= 80 )
		cout << "A\n";
		
		if( m + f >= 65 && m + f < 80 )
		cout << "B\n";
		
		if( m + f >= 50 && m + f < 65 )
		cout << "C\n";
		
		if( m + f >= 30 && m + f < 50 ) {
			
			if(r == -1)
			cout << "D\n";
			
			else if( r >= 50)
			cout << "C\n";
			
			else
			cout << "D\n";
		}
		if( m + f < 30 )
		cout << "F\n";
	}
	if( (m == -1 || f == -1) ) {
	if( m == -1 && f == -1 && r == -1)
	break;
	else
		cout << "F\n";
	}

	}

	return 0;
}


Measured memory_bytes: 3028
#include                        <bits/stdc++.h>
#include                        <ext/pb_ds/assoc_container.hpp>
#define lb                      lower_bound
#define ub                      upper_bound
#define fe(x)                   *(x.begin())
#define le(x)                   *(x.rbegin())
#define pb                      push_back
#define load(node,n)            bool operator < (const node &n) const
#define fbo(x)                  find_by_order(x)
#define ook(x)                  order_of_key(x)
#define all(x)                  (x).begin(),(x).end()
#define FOR(i,n)                for(int i = 1; i<=n; i++)
#define REP(i,n)                for(int i = 0; i<n;  i++)
#define TT                      int TC;  scanf("%d",&TC);  while(TC--)
#define read                    freopen("input.txt","r",stdin)
#define write                   freopen("output.txt","w",stdout)
#define dbg(...)                debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#define set(x)                  tree<x,null_type,less<x>,rb_tree_tag,tree_order_statistics_node_update>
using                           namespace __gnu_pbds;
using                           namespace std;
typedef                         long long ll;
typedef                         pair<ll,ll> pll;
typedef                         pair<int,int> pii;

vector<string> vec_splitter(string s){
    s += ','; vector<string> res;
    while(!s.empty()) res.push_back(s.substr(0,s.find(','))), s = s.substr(s.find(',') + 1);
    return res;
}
void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused))int idx,
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T){
    if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") "; stringstream ss; ss << H;
    cerr << args[idx] << " = " << ss.str(); debug_out(args, idx + 1, LINE_NUM, T...);
}


const ll P = 7+1e9;

ll fn(ll x){
    return x*(x+1)/2;
}

main(){
//read;

ll n,k;
cin>>n>>k;
ll ans = 0;

for(ll i = k-1; i<=n; i++){
    ll a = fn(i),b = fn(n)-fn(n-i-1);
    ans = (b-a+1 + ans)%P;
//    cout<<i<<" "<<a<<" "<<b<<endl;
}

cout<<ans;





return 0;
}


Measured memory_bytes: 3632
a = int(input())
x = list(map(float, input().split()))
m = max(x)
M = m/2
t = 0
s = float("INF")
for i in x:
    #print(s,abs(M-i),i,M)
    if s >= abs(M-i):
        s = min(s,abs(M-i))
        t = i
print(str(int(m))+" "+str(int(t)))

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

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

using namespace std;

int main(){
    cin.tie(0);

    int ans = 0, n; cin >> n;
    int a[n], b[n]; REPI(i, n) cin >> a[i] >> b[i];

    REPI(i, n)
        ans += b[i] - a[i];
    cout << ans + n;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>

int main(void)
{
	char s[1001], order[8], ch[1001];
	int i, j, n, a, b;

	scanf("%s\n%d", s, &n);

	for (i = 0; i < n; i++){
		scanf("%s %d %d", order, &a, &b);

		if (!strcmp(order, "reverse")){
			for (j = a; j <= b; j++)
				ch[b - j] = s[j];
			for (j = a; j <= b; j++)
				s[j] = ch[j - a];
		}

		if (!strcmp(order, "replace")){
			scanf("%s", ch);
			for (j = 0; ch[j] != '\0'; j++)
				s[a + j] = ch[j];
		}

		if (!strcmp(order, "print")){
			for (j = a; j <= b; j++)
				printf("%c", s[j]);
			printf("\n");
		}
	}

	return 0;
}


Measured memory_bytes: 2112
#include <algorithm>
#include <array>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define FOR(i,a,b) for (int i=(a),for_##i##_max=(b);i<=(for_##i##_max);++i)
#define RFOR(i,a,b) for (int i=(a),rfor_##i##_min=(b);i>=(rfor_##i##_min);--i)
#define REP(i,n) for (int i=0,rep_##i##_len=(n);i<(rep_##i##_len);++i)
#define RREP(i,n) for (int i=(n)-1;i>=0;--i)


using namespace std;

constexpr int nmax = 305;
double dp[nmax][nmax][nmax];

void solve(int N, int A, int B, int C) {
  REP(i, nmax) REP(j, nmax) REP(k, nmax) { dp[i][j][k] = 0; }
  REP(c, C+1) REP(b, C+B+1) REP(a, C+B+A+1) {
    if (a + b + c > 0) {
      dp[c][b][a] = (1 + dp[c][b][a]) * N / (a + b + c);
    }
    dp[c][b][a+1] += dp[c][b][a] * (a+1) / N;
    if (a > 0) { dp[c][b+1][a-1] += dp[c][b][a] * (b+1) / N; }
    if (b > 0) { dp[c+1][b-1][a] += dp[c][b][a] * (c+1) / N; }
  }
  cout << dp[C][B][A] << endl;
}

int main() {
  cout << fixed << setprecision(10);
  int N; cin >> N;
  int s[3] = { 0, 0, 0 };
  REP(i, N) {
    int K; cin >> K;
    s[--K]++;
  }
  solve(N, s[0], s[1], s[2]);
  return 0;
}


Measured memory_bytes: 221952
//#pragma GCC optimize("O3", "unroll-loops")
//#pragma GCC target("avx2")
#include<bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define FIXED cout << fixed << setprecision(12)
#define RANDOM srand(94385)
#define all(a) a.begin(), a.end()
#define shuffle(a) \
    for (int i = 0; i < sz(a); ++i) \
        swap(a[i], a[rand() % sz(a)]);
#define enter putchar('\n')
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
using namespace std;

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

void debug_out() { cerr << '\n'; }

template<typename T, typename ...R>
void debug_out(const T &f, const R &...r) {
    cerr << f << " ";
    debug_out(r...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__);

inline ll read() {
    ll x = 0;
    int f = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') f |= (ch == '-'), ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x = f ? -x : x;
}

inline void write(ll x) {
    if (x == 0) {
        putchar('0');
        return;
    }
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    static char s[23];
    int l = 0;
    while (x != 0)s[l++] = x % 10 + 48, x /= 10;
    while (l)putchar(s[--l]);
}

int lowbit(int x) { return x & (-x); }

template<class T>
T big(const T &a1, const T &a2) { return a1 > a2 ? a1 : a2; }

template<typename T, typename ...R>
T big(const T &f, const R &...r) { return big(f, big(r...)); }

template<class T>
T sml(const T &a1, const T &a2) { return a1 < a2 ? a1 : a2; }

template<typename T, typename ...R>
T sml(const T &f, const R &...r) { return sml(f, sml(r...)); }

template<class T, class U>
inline void checkMin(T &x, U y) { if (y < x) x = y; }

template<class T, class U>
inline void checkMax(T &x, U y) { if (y > x) x = y; }

template<class T, class U>
inline bool ifMax(T &x, U y) {
    if (y > x) return x = y, true;
    return false;
}

template<class T, class U>
inline bool ifMin(T &x, U y) {
    if (y < x) return x = y, true;
    return false;
}

const int M = 212345;// 2e5+5
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1000000007;// 1e9+7

// HAVE FREE OPEN IN MAIN FUNCTION

char a[M];
int n;
int dp[M][2];

void init() {
    scanf("%s", a + 2);
    n = strlen(a + 2);
    fill(dp[0],dp[0]+M*2,-inf);
    dp[1][0]=dp[0][1]=0;
    for (int i = 2; i < n + 2; ++i) {
        checkMax(dp[i][0], dp[i - 1][1] + 1);
        if (a[i] != a[i - 1])checkMax(dp[i][0], dp[i - 1][0] + 1);
//        checkMax(dp[i][1], dp[i - 2][1] + 1);
        checkMax(dp[i][1], dp[i - 2][0] + 1);
    }

//    for (int i = 2; i < n + 2; ++i) {
//        printf("%d %d\n", dp[i][0], dp[i][1]);
//    }


    write(big(dp[n + 1][0], dp[n + 1][1]));

}

void solve() {

}

int main() {
//#ifndef ONLINE_JUDGE
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
//#endif
    init();

    solve();

    return 0;
}

Measured memory_bytes: 2048
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(M)]
AB.sort()

ar=N+1
ans=0
for i in reversed(range(M)):
  a,b=AB[i]
  if b<=ar:
    ans+=1
    ar=a
  
print(ans)

Measured memory_bytes: 27872
import sys
from collections import deque
sys.setrecursionlimit(10**7)
n=int(input())
l=[list(input()) for i in range(n)]
colors = [0 for i in range(n)]
es=[[] for i in range(n)]
Edges=es
for i in range(n):
  for j in range(n):
    if l[i][j]=='1':
      es[i].append(j)
def dfs(v,color):
    colors[v] = color
    for to in es[v]:
        if colors[to] == color:
            return False
        if colors[to] == 0 and not dfs(to, -color):
            return False
    return True
 
def is_bipartite():
    return dfs(0,1)
if is_bipartite()==0:
  print(-1)
  sys.exit()


def bfs(v):
    Visited=[False]*n
    q=deque()
    q.append((v,0))
    Visited[v]=True
    ret=(v,0)
    while q:
        fr,dist=q.popleft()
        if ret[1]<dist:
            ret=(fr,dist)
        for to in Edges[fr]:
            if not Visited[to]:
                Visited[to]=True
                q.append((to,dist+1))
    return ret

ans=[]
for i in range(n):
  ans.append(bfs(i)[1])
print(max(ans)+1)

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

int main() {
    int N, M;
    cin >> N >> M;
    Graph G(N);
    rep(i, M) {
        int a, b;
        cin >> a >> b;
        G[a-1].push_back(b);
        G[b-1].push_back(a);
    }
    vector<int> sign(N, -1);
    queue<int> que;

    sign[0] = 0;
    que.push(1);

    while(!que.empty()) {
        int v = que.front();
        que.pop();

        for (auto nv : G[v-1]) {
            if (sign[nv-1] != -1) continue;

            sign[nv-1] = v;
            que.push(nv);
        }
    }
    rep(i, N) {
        if (sign[i] == -1) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    for(int i = 1; i < N; i++) cout << sign[i] << endl;
  	return 0;
}

Measured memory_bytes: 10244
#include<iostream>
using namespace std;
int N[105]; 
int main()
{
	int n,x;
	cin>>n>>x;
	int min1=1000;
	int sum=0;
	for(int i=0;i<n;i++)
	{
		cin>>N[i];
		sum+=N[i];
		if(N[i]<min1) min1=N[i];
	}
	int ans=n+(x-sum)/min1;
	cout<<ans<<endl;
	return 0;
 } 

Measured memory_bytes: 256
n,a,b,c,d = map(int,input().split())
s = input()
if d<c:
    if "##" not in s[a-1:d] and '...' in s[b-2:d+1]:
        print('Yes')
    else:
        print('No')
    
else:
    if "##" not in s[a-1:d]:
        print('Yes')
    else:
        print('No')


Measured memory_bytes: 40560
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner scan = new Scanner(System.in);
		
		long a = scan.nextLong();
		long b = scan.nextLong();
		long c = scan.nextLong();
		long k = scan.nextLong();
		long ans = 0;
		
		if(k <= a) {
			ans = k;
		}
		else if(k <= a + b) {
			ans = a;
		}
		else {
			ans = a - (k - a - b);
		}
		
		
		System.out.println(ans);

	}

}


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

int main(){
	char c;
	for(int i = 0;i < 4;i++){
		cin >> c;
		cout << c;
	}
	cout << " ";
	for(int i = 0;i < 8;i++){
		cin >> c;
		cout << c;
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 256
import heapq

while True:
  N,M = map(int, raw_input().split())
  if N==M==0: break
  q = []
  for _ in xrange(N):
    d,p = map(int, raw_input().split())
    heapq.heappush(q, [p,d])
  q = sorted(q, reverse=True)
  for i in xrange(N):
    if q[i][1] > M:
      q[i][1] -= M
      M = 0
      break
    else:
      M -= q[i][1]
      q[i][1] = 0
  precision = 0
  for i in xrange(N):
    precision += q[i][0] * q[i][1]
  print precision

Measured memory_bytes: 7940
#include <iostream>


using namespace std;

int main()
{
int a,b,c,d,A1,A2;
scanf("%d%d%d%d",&a,&b,&c,&d);
A1=a*b;
A2=c*d;
if(A1>A2)
printf("%d",A1);
else
printf("%d",A2);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mod 1000000007
#define ull unsigned ll
#define ll long long int
#define ld long double
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
#define pi acos(-1)
#define nui 100
#define INF 100000000000
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#define F(i,a,n) for(ll i=a;i<n;i++)
#define B(i,a,n) for(ll i=n-1;i>=a;i--)
#define tc int t;cin>>t;while(t--)
#define tcf int t;cin>>t;for(int w=1;w<=t;w++)



using namespace std;

void dex(int a)
{
    if (a == 1)
    {
        cout << "1\n";
    }
    else if (a == -1)
    {
        cout << "-1\n";
    }
    else if (a == 0)
    {
        cout << "0\n";
    }
    else if (a == 2)
    {
        cout << "YES\n";
    }
    else if (a == 3)
    {
        cout << "NO\n";
    }

}

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




int main()
{

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

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    ll n;
    cin >> n;
    ll a[n];
    ll sum = 0;
    ll csum = 0;
    ll res = 0;
    F(i, 0, n)
    {
        cin >> a[i];
        sum += a[i];
        sum %= mod;
    }
    F(i, 0, n)
    {
        csum += a[i];
        csum %= mod;
        res += (((mod + sum - csum) % mod) * (a[i] % mod)) % mod;
        res %= mod;
    }

    cout << res % mod << "\n";





    return 0;


    return 0;

}

Measured memory_bytes: 5124
#include <bits/stdc++.h>
using namespace std;
#define ll                  long long
#define ld                  long double
#define pb                  push_back
#define mkp                 make_pair
#define f(i,l,h)            for(ll i=l;i<h;i++)
#define fr(i,h,l)           for(ll i=h;i>=l;i--)
#define mem(a,val)          memset(a,val,sizeof(a))
#define all(v)              (v).begin(),(v).end()
#define ff                  first
#define ss                  second
#define spc(x)              cout<<fixed<<setprecision((x));
#define deb(x)              cout<<#x<<" "<<x<<endl;
#define deba(x)             cout<<#x<<": "; for(auto u:x) cout<<u<<" ";  cout<<endl;
#define check               cout<<"hello"<<endl;
#define fastio              ios_base::sync_with_stdio(false);cin.tie(NULL)
const ld pi=3.141592653589793;
const ll mod=998244353;
const ll INF=(ll)(1e9+7);
typedef pair<ll,ll> pll;
typedef vector<ll> vll;

ll power(ll a,ll b){
    ll res=1;
	while(b){
	    if(b&1) res=(res*a);
	    a=(a*a);
	    b>>=1;
	}
	return res;
}


int main()
{
    //cout << "Hello world!" << endl;
    ll n,m;
    cin>>n>>m;
    char a[n][m];
    f(i,0,n){
        f(j,0,m){
            cin>>a[i][j];
        }
    }

    ll dp[n][m];
    dp[0][0]=1;
    for(ll i=1;i<n;i++){
        if(a[i][0]=='#'){
            dp[i][0]=0;
        }else dp[i][0]=dp[i-1][0];
    }
    for(ll i=1;i<m;i++){
        if(a[0][i]=='#'){
            dp[0][i]=0;
        }else dp[0][i]=dp[0][i-1];
    }
    for(ll i=1;i<n;i++){
        for(ll j=1;j<m;j++){
            if(a[i][j]=='#'){
                dp[i][j]=0;
                continue;
            }
            dp[i][j]=(dp[i-1][j]+dp[i][j-1])%INF;
        }
    }
    cout<<dp[n-1][m-1]<<endl;




    return 0;
}


Measured memory_bytes: 12424
//#pragma comment(linker, "/STACK:36777216")
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <sstream>
#include <vector>
#include <complex>
#include <ctime>
#include <stack>

//#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef vector< VI > VVI;
typedef pair<int, int> PII;
typedef vector<PII> VPII;

#define REP(i, n) for(int i = 0; i < (n); ++i)
#define RREP(i, n) for(int i = (n) - 1; i >= 0; --i)
#define FOR(i, x, y) for(int i = (x); i <= (y); ++i)
#define RFOR(i, y, x) for(int i = (x); i >= (y); --i)
#define SZ(a) (int)(a).size()
#define ALL(a) (a).begin(),(a).end()
#define SORT(a) sort(ALL(a)) 
#define CLEAR(x) memset(x, 0, sizeof x);
#define COPY(FROM, TO) memcpy(TO, FROM, sizeof TO);
#define UNIQUE(c) SORT(c),(c).resize(unique(ALL(c))-(c).begin())
#define pb push_back
#define mk make_pair
#define sqr(x) ((x)*(x))
#define X first
#define Y second
//typedef tree<int, null_type, less<int>, 
//  rb_tree_tag, tree_order_statistics_node_update> order_set;

const long double PI = acos(-1.0);
const double EPS = 1E-6;
const int INF = 2 * (1e+9) + 1;
const int MAXN = 3 * 100000001;
const int MOD = (1e+9) + 7;


ll n, m, k;
string s;
int a[100100];
int main() {
    int nn = 0;
    //freopen("a.txt", "r", stdin);
    cin >> n >> m;
    REP(i, m) {
        cin >> a[i];
    }
    sort(a, a + m);
    ll sum = 0;
    int i = 0;
    while (n >= 0 && i < m) {
        if (n - a[i] >= 0) {
            n -= a[i];
            i++;
        }
        else break;
    }
    if (i != m) cout << -1;
    else cout << n;
    return 0;
}

Measured memory_bytes: 3180
#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
#include<cmath>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define MAX 20
using namespace std;
int p,q;
string P[MAX],Q[MAX];
int leading[2][MAX];
 
bool check(int R,int C,int S)
{
  int r,c,s;
  r = c = s = 0;
  rep(i,p)
    {
      //cout << leading[0][i] << "  = " <<R*r + c*C + s*S << endl;
      if(leading[0][i] != R*r + c*C + s*S)return false;
 
      rep(j,P[i].size())
    {
      if(P[i][j] == '(')r++;
      else if(P[i][j] == '{')c++;
      else if(P[i][j] == '[')s++;
       
      if(P[i][j] == ')')r--;
      else if(P[i][j] == '}')c--;
      else if(P[i][j] == ']')s--;
    }
    }
  return true;
}
 
int main()
{
  while(cin >> p >> q,p|q)
    {
      vector<int> Rv,Cv,Sv;
      rep(i,p)
    {
      cin >> P[i];
      int cnt = 0;
      rep(j,P[i].size())
        {
          if(P[i][j] == '.')cnt++;
          else              break;
        }
      leading[0][i] = cnt;
    }
 
      rep(i,q)
    {
      cin >> Q[i];
      int cnt = 0;
      rep(j,Q[i].size())
        {
          if(Q[i][j] == '.')cnt++;
          else              break;
        }
      leading[1][i] = cnt;
    }
 
      //check(9,5,2);
      //return 0;
      REP(R,1,21)
    {
      REP(C,1,21)
        {
          REP(S,1,21)
        {
          if(check(R,C,S))
            {
              Rv.push_back(R);
              Cv.push_back(C);
              Sv.push_back(S);
            }
        }
        }
    }
 
      int totalCost = 0;
      int r,s,c;
      r = s = c = 0;
      rep(i,q)
    {
      set<int> st;
      rep(j,Rv.size())
        {
          totalCost = r*Rv[j] + c*Cv[j] + s*Sv[j];
          st.insert(totalCost);
        }
 
      if(st.empty() || (int)st.size() >= 2)
        {
          cout << -1;
        }
      else
        {
          set<int>::iterator it = st.begin();
          cout << (*it);
        }
      if(i == q-1)cout << endl;
      else cout << " ";
 
      rep(j,Q[i].size())
        {
          if(Q[i][j] == '(')r++;
          else if(Q[i][j] == '{')c++;
          else if(Q[i][j] == '[')s++;
           
          if(Q[i][j] == ')')r--;
          else if(Q[i][j] == '}')c--;
          else if(Q[i][j] == ']')s--;
        }
     
    }
    }
  return 0;
}

Measured memory_bytes: 1360
#include<iostream>
#include <cmath>
#include <map>
using namespace std;
int main(){
	string w;
	cin >> w;
	map<char,int> mp;
	for(int i=0;i<w.length();i++){
		mp[w[i]]+=1;
	}
	for(int i=0;i<26;i++){
		if(mp['a'+i]%2 != 0){
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}


Measured memory_bytes: 256