akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;

int main() {
  int n;
  int answer = 0;
  bool a = false;
  vector<int> vec(105);
  
  cin >> n;
  rep(i, n){
    cin >> vec.at(i);
  }
  
  sort(vec.begin(), vec.end());
  
  for(int i = vec.size() - 1; i >= 0; i--){
    if(a == false){
      answer += vec.at(i);
      a = true;
    }
    else{
      answer -= vec.at(i);
      a = false;
    }
  }
  
  cout << answer << endl;
}

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

using namespace std;

const int md = 998244353;

inline void add(int &x, int y) {
  x += y;
  if (x >= md) {
    x -= md;
  }
}

inline void sub(int &x, int y) {
  x -= y;
  if (x < 0) {
    x += md;
  }
}

inline int mul(int x, int y) {
  return (int) ((long long) x * y % md);
}

inline int inv(int a) {
  if (a < 0) {
    a += md;
  }
  int b = md, u = 0, v = 1;
  while (a) {
    int t = b / a;
    b -= t * a;
    swap(a, b);
    u -= t * v;
    swap(u, v);
  }
  if (u < 0) {
    u += md;
  }
  return u;
}

int main() {
#ifdef wxh010910
  freopen("input.txt", "r", stdin);
#endif
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin >> n;
  vector<int> a(1 << n);
  int sum = 0;
  for (int i = 0; i < 1 << n; ++i) {
    cin >> a[i];
    sum += a[i];
  }
  sum = inv(sum);
  for (int i = 0; i < 1 << n; ++i) {
    a[i] = mul(a[i], sum);
  }
  for (int i = 1; i < 1 << n; i <<= 1) {
    for (int j = 0; j < 1 << n; j += i << 1) {
      for (int k = 0; k < i; ++k) {
        int u = a[j + k], v = a[j + k + i];
        a[j + k] = (u + v) % md;
        a[j + k + i] = (u - v + md) % md;
      }
    }
  }
  a[0] = 0;
  for (int i = 1; i < 1 << n; ++i) {
    a[i] = inv(a[i] - 1);
  }
  for (int i = 1; i < 1 << n; i <<= 1) {
    for (int j = 0; j < 1 << n; j += i << 1) {
      for (int k = 0; k < i; ++k) {
        int u = a[j + k], v = a[j + k + i];
        a[j + k] = (u + v) % md;
        a[j + k + i] = (u - v + md) % md;
      }
    }
  }
  cout << 0 << "\n";
  for (int i = 1; i < 1 << n; ++i) {
    sub(a[i], a[0]);
    cout << a[i] << "\n";
  }
  return 0;
}


Measured memory_bytes: 3840
#include<cstdio>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
#include<functional>
#include<cstring>
using namespace std;

/**** Type Define ****/

typedef long long ll;
typedef pair<ll, ll> P;

/**** Const List   ****/

const ll INF = ((ll)1 << 31) - 1;
const ll DINF = (ll)1e20;
const ll UNION_FIND_MAX = 100000;
const ll SEGMENT_TREE_MAX = (1 << 18) - 1;
const ll MAX_FLOW_MAX_V = 10000;
const ll MIN_COST_FLOW_MAX_V = 10000;
const ll BIPARTITE_MATCHING_MAX_V = 10000;
const ll DIJKSTRA_MAX_V = 1000000;


/**** General Functions ****/

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

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

template <typename T>
T tadd(T a, T b) { return a + b; };

template <typename T>
T tmul(T a, T b) { return a * b; };

template <typename T>
T tpow(T a, T b) { return a * b; };

ll gcd(ll a, ll b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}

ll lmin(ll a, ll b) { return a > b ? b : a; };

ll lmax(ll a, ll b) { return a > b ? a : b; };

/**** main function ****/

ll h, w;
char s[50][51];
ll d[50][50];
ll dx[4] = {1, 0, -1, 0};
ll dy[4] = {0, 1, 0, -1};

int main() {
  scanf("%lld%lld", &h, &w);
  for (ll i = 0; i < h; i++) scanf("%s", s[i]);
  ll sum = 0;
  for (ll i = 0; i < h; i++) for (ll j = 0; j < w; j++) if (s[i][j] == '.') sum++;
  for (ll i = 0; i < h; i++) for (ll j = 0; j < w; j++) d[i][j] = -1;
  d[0][0] = 1;
  queue<P> que;
  que.push(P(0, 0));
  while (!que.empty()) {
    P p = que.front(); que.pop();
    ll x = p.first, y = p.second;
    if (x == w-1 && y == h-1) break;
    for (ll i = 0; i < 4; i++) {
      ll nx = x + dx[i], ny = y + dy[i];
      if (nx < 0 || ny < 0 || nx == w || ny == h) continue;
      if (s[ny][nx] == '#' || d[ny][nx] != -1) continue;
      d[ny][nx] = d[y][x] + 1;
      que.push(P(nx, ny));
    }
  }
  if (d[h-1][w-1] == -1) printf("-1\n");
  else printf("%lld\n", sum - d[h-1][w-1]);
}


Measured memory_bytes: 636
N, M = map(int, input().split())
graph = [[] for i in range(N)]
for i in range(M):
    A, B = map(lambda x: int(x) - 1, input().split())
    graph[A].append(B)
    graph[B].append(A)

from collections import deque

dist = [-1] * N
prev = [-1] * N
dist[0] = 0
queue = deque([0])
while queue:
    tmp = queue.popleft()
    for i in graph[tmp]:
        if dist[i] != -1:
            continue
        dist[i] = dist[tmp] + 1
        prev[i] = tmp
        queue.append(i)


print("Yes")
for i in prev[1:]:
    print(i+1)

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

int main() {
  int k, n;
  cin >> k >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  a.push_back(a[0]+k);
  int l = 0;
  rep(i, n) {
    l = max(l, a[i+1]-a[i]);
  }
  int ans = k-l;
  cout << ans << endl;
  return 0;
};

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define ll  long long
#define endl '\n'
const ll mod = 1000000007;
const double PI = 3.141592653589793238463;
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int x;
    cin>>x;
    ll a[x];
    ll sum=0;
    for (ll i=0;i<x;i++){
        cin>>a[i];
    }
    for (ll i=0;i<64;i++){
        ll e=0,o=0;
        ll p=0;
        for (ll j=0;j<x;j++){
             if (a[j]%2==0) 
                e++; 
            else
                o++; 
            a[j]/= 2; 
        }
        ll m=((o*e)+mod)%mod;
      ll yy=(((ll)1<<i)+mod)%mod;
        p=((m*yy)+mod)%mod;
        sum=(sum+p+mod)%mod;
    }
    cout<<sum<<endl;
    return 0;
}

Measured memory_bytes: 2688
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<iostream>
#include<cmath>

using namespace std;
typedef vector<string>vs;
typedef vector<int>vi;
typedef vector<vi>vvi;
typedef vector<double>vd;
typedef pair<int,int>pii;
typedef long long ll;
typedef pair<ll,ll>pll;
typedef vector<ll>vl;
#define rrep(i,x,n) for(int i=(x);i<(n);++i)
#define rep(i,x) rrep(i,0,(x))
#define fi first
#define se second
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();++i)
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define pb push_back
#define maxs(a,b) (a)=max(a,b)
#define mins(a,b) (a)=min(a,b)

struct data{
    int p,h,cost;
    data(int a,int b,int c):
        p(a),h(b),cost(c){}
    data(){}
};

int n;
int state[2][100];

void solve(){
    bool visited[2][100]={{0}};
    queue<data>Q;
    Q.push(data(0,0,0));
    Q.push(data(1,0,0));
    while(!Q.empty()){
        data d=Q.front();Q.pop();
        while(d.h<n&&state[d.p][d.h]==1){
            int th=d.h+1;
            if(th>=n)break;
            if(state[d.p][th]!=1)break;
            d.h++;
        }
        while(state[d.p][d.h]==2)d.h--;



        if(d.h==n-1){
            printf("%d\n",d.cost);

            return;
        }

        if(visited[d.p][d.h])continue;
        visited[d.p][d.h]=true;
        rep(i,3){
            int tp=1-d.p,th=min(d.h+i,n-1);
            Q.push(data(tp,th,d.cost+1));
        }

    }

    puts("NA");
}

int main(){
    while(scanf("%d",&n),n){
        rep(i,2)rep(j,n)scanf("%d",&state[i][j]);
        solve();
    }
    return 0;
}

Measured memory_bytes: 1216
#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <queue>
 
using namespace std;
 
typedef long long ll;
 
const ll INF = 1e9, MOD = 1e9 + 7, MOD2 = 1e6 + 3;

int l[1000000], r[1000000], n;

int main () {

	cin >> n;

	for (int i = 0; i < n; i++)
		scanf ("%d%d", &l[i], &r[i]);

	sort (l, l + n + 1);
	sort (r, r + n + 1);
	reverse (l, l + n + 1);

	ll ans = 0, sum = 0;

	for (int i = 0; i <= n; i++) {
		sum += 2 * (l[i] - r[i]);
		ans = max (ans, sum);
	}

	cout << ans;
}

Measured memory_bytes: 4736
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
template<typename T> bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<typename T> bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) vec.begin(),vec.end()
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef tuple<ll,ll,ll> tlll;
typedef tuple<int,int,int> tiii;
const ll mod=1e9+7;
const int inf=1<<30;

struct unionfind{
  vector<int> par;
  vector<int> rank;
  unionfind(int n=1){
    init(n);
  }
  void init(int n=1){
      par.resize(n); rank.resize(n);
      for(int i=0;i<n;++i) par[i]=i,rank[i]=0;
  }
  int root(int x){
    if(par[x]==x){
      return x;
    }
    else{
      int r=root(par[x]);
      return par[x]=r;
    }
  }
  bool issame(int x,int y){
    return root(x)==root(y);
  }
  bool merge(int x,int y){
    x=root(x); y=root(y);
    if(x==y) return false;
    if(rank[x]<rank[y]) swap(x,y);
    if(rank[x]==rank[y]) ++rank[x];
    par[y]=x;
    return true;
  }
};

struct edge{int u,v,cost;};

bool comp(const edge& e1,const edge& e2){
  return e1.cost<e2.cost;
}

ll kruskal(int n,int m,vector<edge>& es){
  sort(es.begin(),es.end(),comp);
  unionfind uf(n);
  ll res=0;
  rep(i,m){
    if(!uf.issame(es[i].u,es[i].v)){
      uf.merge(es[i].u,es[i].v);
      res+=es[i].cost;
    }
  }
  return res;
}

int main(){
  int n; cin >> n;
  vector<pii> x(n);
  vector<pii> y(n);
  rep(i,n){
    cin >> x[i].first >> y[i].first;
    x[i].second=i; y[i].second=i;
  }
  sort(all(x));
  sort(all(y));
  vector<edge> es(0);
  rep(i,n-1){
    int a=x[i].second;
    int b=x[i+1].second;
    int c=x[i+1].first-x[i].first;
    //cout << a << b << c << endl;
    es.push_back({a,b,c});
  }
  rep(i,n-1){
    int a=y[i].second;
    int b=y[i+1].second;
    int c=y[i+1].first-y[i].first;
    //cout << a << b << c << endl;
    es.push_back({a,b,c});
  }
  int m=es.size();
  cout << kruskal(n,m,es) << endl;
}

Measured memory_bytes: 6516
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(n);i++)
int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}
int lcm(int a,int b){
	return a/gcd(a,b)*b;
}
int c[51][51];
void comb(){
    rep(i,51){
        rep(j,i+1){
            if(j==0||j==i)c[i][j]=1;
            else c[i][j]=c[i-1][j-1]+c[i-1][j];
        }
    }
}
int n,a,b,v[50],cnt=0,k=0,s=0,ans=0;
signed main(){
    comb();
    cin>>n>>a>>b;
    rep(i,n)cin>>v[i];
    sort(v,v+n);
    reverse(v,v+n);
    rep(i,n)if(v[i]==v[a-1])k++;
    rep(i,a)if(v[a-1]==v[i])s++;
    rep(i,a)cnt+=v[i];
    printf("%.12lf\n",1.0*cnt/a);
    if(v[0]==v[a-1]){
        for(int i=a;i<=min(b,k);i++)ans+=c[k][i];
        cout<<ans<<endl;
    }
    else cout<<c[k][s]<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main(){
int flag=0;

  string s;
  cin>>s;
  if(s.at(2)==s.at(3)&&s.at(4)==s.at(5)){
    cout<<"Yes";

  }
  else
    cout<<"No";

 return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main(){
  int n,k;
  string s;
  cin >> n >> s >> k;
  
  for(int i=0;i<n;i++){
    if(s[k-1]!=s[i]){
      s[i] = '*';
  }
  }
  cout << s << endl;
  return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#include <list>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
//#define cerr if(false) cerr
#ifdef DEBUG
#define show(...) cerr << #__VA_ARGS__ << " = ", debug(__VA_ARGS__);
#else
#define show(...) 42
#endif
using namespace std;
using ll = long long;
using pii = pair<int, int>;
template <typename T, typename S>
ostream& operator<<(ostream& os, pair<T, S> a) {
    os << '(' << a.first << ',' << a.second << ')';
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for (auto x : v) os << x << ' ';
    return os;
}
void debug() {
    cerr << '\n';
}
template <typename H, typename... T>
void debug(H a, T... b) {
    cerr << a;
    if (sizeof...(b)) cerr << ", ";
    debug(b...);
}
template <typename T>
vector<T> divisor(T n) {
    vector<T> res;
    for (T i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            res.push_back(i);
            if (i * i != n) {
                res.push_back(n / i);
            }
        }
    }
    sort(res.begin(), res.end());
    return res;
}
template <typename T>
map<T, int> prime_factor(T n) {
    map<T, int> res;
    for (T i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            res[i]++;
            n /= i;
        }
    }
    if (n != 1) {
        res[n]++;
    }
    return res;
}
template <typename T>
T gcd(T a, T b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}
template <typename T>
T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}
int main(){
    ll a, b;
    cin >> a >> b;
    cout << lcm(a,b) << endl;
}


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

int main() {
  string s;
  int a = 0,b = 0;
  cin >> s;
  for (int i = 0; i < s.size(); i++){
    if(i % 2 == 1){
      if(s.at(i) == '0')
        b++;
      else
        a++;
    }
    else{
      if(s.at(i) == '0')
        a++;
      else
        b++;
    }
  }
  if(a > b)
    cout << b << endl;
  else
    cout << a << endl;
}


Measured memory_bytes: 512
#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>

#define _GLIBCXX_DEBUG
using namespace std;
using vi = vector<int64_t>;
using vvi = vector<vi>;

int main(int argc, const char * argv[]) {
    // fasten cin
    cin.tie(0);
    ios::sync_with_stdio(false);
    // implement
    int64_t n;
    string s;
    cin >> n >> s;
    char k;
    for(int i=0; i<s.size(); i++){
        k = s.at(i) + n;
        if(k > 'Z'){
            k -= 'Z' - '@';
        }
        s.at(i) = k;
    }
    cout << s << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
using ll=long long;
using vec=vector<ll>;
using Graph = vector<vector<ll>>;
#define loop(i,n) for(ll i=0;i<n;i++)
#define Loop(i, m, n) for(ll i = m;i < n;i++)
#define pool(i,n) for(ll i=n-1;i>=0;i--)
#define Pool(i, m, n) for(ll i=n-1;i>=m;i--)
#define MAX 99999999999ll
#define MIN -99999999999ll
#define setbit bitset<8>
#define flagcount __builtin_popcount
#define flag(x) (1<<x)
#define flagadd(bit,x) bit|=flag(x)
#define flagpop(bit,x) bit&=~flag(x) 
#define flagon(bit,i) bit&flag(i)
#define flagoff(bit,i) !(bit & (1<<i))
#define all(v) v.begin(),v.end()
#define low2way(v,x) lower_bound(all(v),x)
#define high2way(v,x) upper_bound(all(v),x)
#define count2way(v,x) high2way(v,x)-low2way(v,x)
#define lower(v,x) low2way(v,x)-v.begin() //1番左が0、もし見つから無いならｎを出力
#define higher(v,x) high2way(v,x)-v.begin()-1 //1番左が0、もし見つからないならn-1を出力（注意）
#define putout(x) cout<<x<<endl
#define Gput(a,b) G[a].push_back(b)
int main() {
 ll a,b,c,k;
 cin>>a>>b>>c>>k;
 if(k%2==1)putout(b-a);
  else putout(a-b);
 
 
 
 
 
 
 
 
 
 
 
}


Measured memory_bytes: 256
N, P = map(int, input().split())
A = map(int, input().split())

odds, evens = 0, 0

for i in A:
    if i & 1:
        odds += 1
        
    else:
        evens += 1

from math import factorial

if P == 0:
    ans = 0
    fo = factorial(odds)
    for r in range(0, odds + 1, 2):
        ans += fo // (factorial(odds - r) * factorial(r))
    ans *= 2**evens

else:
    ans = 0
    fo = factorial(odds)
    for r in range(1, odds + 1, 2):
        ans += fo // (factorial(odds - r) * factorial(r))

    ans *= 2**evens
print(ans)


Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

int main() {
    ll n;
    cin >> n;
 
    vl dp(n+1, INF);  // dp[i] : i円引き出すのに必要な操作回数の最小値
 
    dp[0] = 0;
    exrep(i, 1, n) {
        ll x = 1;
        while(x <= i) {
            dp[i] = min(dp[i], dp[i-x] + 1);
            x *= 6;
        }
        ll y = 1;
        while(y <= i) {
            dp[i] = min(dp[i], dp[i-y] + 1);
            y *= 9;
        }
    }
 
    out(dp[n]);
    re0;
}

Measured memory_bytes: 1024
import sys
imput =sys.stdin.readline
N, Q =map(int,input().split())
S =[i for i in input()]
q = [[int(i) for i in input().split()] for _ in range(Q)]
num = 0
for i in range(N-1):
    if S[i]+S[i+1]=="AC":
        num += 1
    S[i] = num
S[-1] = num
S.append(0)
for lr in q:
  print(S[lr[1]-2] -S[lr[0]-2])

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

typedef long long ll;
typedef pair<int,int> ii;
typedef tree<ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int h,n,x; cin>>h>>n;
	for (int i=0; i<n; i++)
		cin>>x, h-=x;
	if(h<=0) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
	int h;
	int first,second,third;
	int i;
	int bf;

	first = 0;
	second = 0;
	third = 0;

	for(i=1;i<=10;i++){
		scanf("%d",&h);
		if(h > third){
			third = h;
			if(third > second){
				bf = second;
				second = third;
				third = bf;
				if(second > first){
					bf = first;
					first = second;
					second = bf;
				}
			}
		}
	}

	printf("%d\n%d\n%d\n",first,second,third);

	return 0;
}

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

int sqr(int x){
    return x*x;
}

double dist(int x,int y){
    return sqrt(sqr(x)+sqr(y));
}

int main()
{
    int n;
    cin>>n;
    vector<int> x;
    vector<int> y;
    vector<int> m;
    double sum=0;
    int cnt=0;
    for (int i=0;i<n;++i)
    {
        int tempx,tempy;
        cin>>tempx>>tempy;
        x.push_back(tempx);
        y.push_back(tempy);
        m.push_back(i);
    }
    do{
        for(int i=0;i<n-1;i++)
        {
            sum+=dist(x[m[i]]-x[m[i+1]],y[m[i]]-y[m[i+1]]);
        }
        cnt++;
    }while(next_permutation(m.begin(),m.end()));
    cout<<fixed<<setprecision(8)<<sum/cnt<<endl;
}

Measured memory_bytes: 3760
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def main():
    n=int(input())
    graph=[[]for _ in range(n)]
    for i in range(n-1):
        a,b=map(int,input().split())
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    C=list(map(int,input().split()))
    C.sort(reverse=True)#頂点の値が大きい順に
    node_c=[0]*n #各頂点の値 0なら初めて
    node_c[0]=C[0]
    queue=deque([0])
    i=1
    while queue:
        node=queue.popleft()
        for xnode in graph[node]:
            if node_c[xnode]>0:continue
            node_c[xnode]=C[i]
            i+=1
            queue.append(xnode)
    print(sum(C[1:]))
    print(' '.join(map(str,node_c)))

if __name__=='__main__':
    main()

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

#define M 7000000
#define L 14

char H[M][L]; /* Hash Table */
int c=0;

int getChar(char ch){
  if(ch == 'A') return 1;
  else if(ch == 'C') return 2;
  else if(ch == 'G') return 3;
  else if(ch == 'T') return 4;
}

/* convert a string into an integer value */
long long getKey(char str[]){
  long long sum=0,p=1,i;
  for(i=0; i < strlen(str); i++){
    sum += p*(getChar(str[i]));
    p *= 5;
  }
  return sum;
}

int h1(int key){
  int k;
  k = key % M;
  return k;
}

int h2(int key){
  int k;
  k = 1 + (key % (M-1));
  return k;
}

int find(char str[]){
  int i=0,j,a;
  
  while(1){
    j = (h1(getKey(str)) + (i*h2(getKey(str))))%M;
    if(strcmp(H[j],str) == 0){
      return 1;
    } else if((H[j][0] == '\0') || (i >= M)) {
      return 0;
    } else {
      i++;
    }
  }
}

int insert(char str[]){
  int i,t1,t2,t3;
  t1 = h1(getKey(str));
  t2 = h2(getKey(str));
  for(i=0; i < M; i++){
    t3 = (t1 + (i*t2))%M;
    if(H[t3][0] == '\0'){
      strcpy(H[t3],str);
      return 0;
    }
  }
}

int main(){
  int i,n,h,j;
  char str[L],com[9];
  for(i=0; i < M; i++) H[i][0] = '\0';
  
  scanf("%d",&n);
  
  for(i=0; i < n; i++){
    scanf("%s %s",com,str);
    
    if(com[0] == 'i'){
      insert(str);
    } else {
      if(find(str) == 1){
	printf("yes\n");
      } else {
	printf("no\n");
      }
    }
  }

  return 0;
}



Measured memory_bytes: 97492
INT_MAX = 10000000000
n = int(input())
a = list(map(int,input().split()))
dp =[INT_MAX]*(n+1)
dp[0] = 0
if n==2:
    print(a[1] - a[0])
else:
    for i in range(n):
        if i+1<n:
            dp[i+1] = min(dp[i+1], dp[i] + abs(a[i+1] - a[i]))
        if i+2<n:
            dp[i+2] = min(dp[i+2], dp[i] + abs(a[i+2] - a[i]))
    print(dp[n-1])

Measured memory_bytes: 13924
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <iomanip>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;

int dp[100][3][2];
int fx[100];
int N,K;
int main() {
	memset(fx,-1,sizeof(fx));
	cin >> N >> K;
	for(int i=0;i<K;i++){
		int a,b;
		cin >> a >> b;
		fx[a-1]=b-1;
	}
	for(int i=0;i<N;i++){
		for(int p=0;p<3;p++){
			if(fx[i]!=-1&&fx[i]!=p){
				continue;
			}
			if(i==0){
				dp[i][p][0]=1;
				continue;
			}
			for(int q=0;q<3;q++){
				if(q==p){
					dp[i][p][1]+=dp[i-1][q][0];
				}
				else
				{
					dp[i][p][0]+=dp[i-1][q][0]+dp[i-1][q][1];
				}
			}
			dp[i][p][0]%=10000;
			dp[i][p][1]%=10000;
		}
	}
	int ret=0;
	for(int i=0;i<3;i++){
		ret+=dp[N-1][i][0]+dp[N-1][i][1];
	}
	ret%=10000;
	cout << ret << endl;
}

Measured memory_bytes: 1160
K, N = map(int, input().split())
A =  list(map(int, input().split()))

mini = K
right = left = K
for i in range(N):
	l_begin = i-1
	r_begin = i+1
	if i == 0:
		l_begin = N-1
		right = A[l_begin] - A[i]
		left = K - (A[r_begin]-A[i])
	elif i == N-1:
		r_begin = 0
		right = K - (A[i]-A[l_begin])
		left = A[i] - A[r_begin]
	else:
		right = K - (A[i]-A[l_begin])
		left = K - (A[r_begin]-A[i])
	local = min(right, left)
	if local < mini:
		mini = local
		

print(mini)

Measured memory_bytes: 26444
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
typedef long long ll;
struct Trio{
	int to,v;
	ll cost;
	bool operator<(const Trio& right)const{
		return (cost > right.cost);
	}
};
priority_queue<Trio,vector<Trio>> qu;

int a,b,c;
int nextv(int v){ return (a*v+b)%c;}

int main(void){
	int n,m,v0;
	cin>>n>>m;
	vector<int> x(m),y(m);
	vector<ll> t(m);
	rep(i,m) cin>>x[i]>>y[i]>>t[i];
	cin>>v0>>a>>b>>c;
	vector<Trio> G[(n+1)*2][c];
	ll dp[(n+1)*2][c];
	rep(i,m)rep(v,c){
		G[x[i]][v].push_back({y[i],nextv(v),t[i]*v});
		G[y[i]][v].push_back({x[i],nextv(v),t[i]*v});
		G[n+x[i]][v].push_back({n+y[i],nextv(v),t[i]*v});
		G[n+y[i]][v].push_back({n+x[i],nextv(v),t[i]*v});
	}
	rep(v,c) G[n][v].push_back({n*2,v,0});

	rep(i,(n+1)*2)rep(v,c) dp[i][v]=LLONG_MAX;
	dp[1][v0]=0;
	qu.push({1,v0,0});
	while(qu.size()){
		Trio u=qu.top(); qu.pop();
		if(u.to==n+1){
			cout<<dp[u.to][u.v]<<endl;
			return 0;
		}
		if(dp[u.to][u.v] < u.cost)continue;
		for(auto e:G[u.to][u.v]){
			if(dp[e.to][e.v] > dp[u.to][u.v] + e.cost){
				dp[e.to][e.v] = dp[u.to][u.v] + e.cost;
				qu.push({e.to,e.v,dp[e.to][e.v]});
			}
		}
	}
}

Measured memory_bytes: 28388
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;

int main(){
    string s,t;
    cin>>s>>t;
    bool flag=false;
    for(int i=s.length()-t.length();i>=0;i--){
        flag=true;
        for(int j=0;j<t.length();j++){
            if(s[i+j]=='?') continue;
            if(t[j]!=s[i+j]) {
                flag=false;
                break;
            }
        }
        if(flag){
            for(int j=0;j<t.length();j++){
                s[i+j]=t[j];
            }
            for(int i=0;i<s.length();i++){
                if(s[i]=='?') s[i]='a';
            }
            break;
        }
    }
    if(flag){
        cout<<s<<endl;
    }else{
        cout<<"UNRESTORABLE"<<endl;
    }
    
    return 0;
}

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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n; string up,lo; cin>>n>>up>>lo;
	int ans=3,i=1; bool p2=false;
	if(!(up.front()==lo.front()))ans=6,p2=true,++i;
	while(i<n){
		if(up.at(i)==lo.at(i)){
			if(!p2)ans=ans*2%mod;
			else p2=false;
			++i;
		}
		else{
			if(p2)ans=(1L*ans*3)%mod;
			else ans=ans*2%mod,p2=true;
			i+=2;
		}
	}
	cout<<ans<<"\n"s;
}


Measured memory_bytes: 3672
using System;
using System.Linq;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            string s = Console.ReadLine();
            char[] a = s.ToCharArray();
            char[] b = s.Reverse().ToArray();

            int cnt = 0;
            for (int i = 0; i < s.Length; i++)
            {
                if (a[i] != b[i])
                {
                    b[i] = a[i];
                    a[s.Length - (i + 1)] = b[i];
                    cnt++;
                }
            }
            Console.WriteLine(cnt);   
        }
    }
}


Measured memory_bytes: 13268
#include<bits/stdc++.h>
using namespace std;
const double pi=acos(-1.0);
void read(int &x){
	char c=getchar();
	int f=1;
	x=0;
	while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
	x*=f;
}
int main(){
	int i,j,k,m,n;
	double a,b,x;
	cin>>a>>b>>x;
	double num=2.*x/a/b;
	if(num<=a){
		double ans=2.*x/b/a/b;
		printf("%.10lf",(90.-atan(ans)*180./pi));
	}
	else{
		double tmp=2*b-2.*x/a/a;
		double ans=a/tmp;
		printf("%.10lf",(90.-atan(ans)*180./pi));
	}
	return 0;
}


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

namespace AtCoder
{

    static class Program
    {
        static void Main()
        {
            Solve();

            Console.ReadKey();
        }

        static void Solve()
        {
            int N = GetInt();
            string Str = GetStr();
            var E = new int[N+1];
            var W = new int[N+1];
            E[0] = 0;
            W[0] = 0;
            for(int i = 1; i < N+1; i++)
            {
                if (Str[i-1] == 'E')
                {
                    E[i] += E[i - 1] + 1;
                    W[i] = W[i - 1];
                }
                else
                {
                    E[i] = E[i - 1];
                    W[i] = W[i - 1] + 1;
                }
            }

            var min = int.MaxValue;
            for(int i = 1; i < N + 1; i++)
            {
                min = Math.Min(min, W[i - 1] + E[N] - E[i]);
            }

            Console.WriteLine(min);
        }


        static public string GetStr() { return Console.ReadLine(); }
        static public int GetInt() { return int.Parse(Console.ReadLine()); }
        static public long GetLong() { return long.Parse(Console.ReadLine()); }
        static public string[] GetStrArray() { return Console.ReadLine().Split(' '); }
        static public int[] GetIntArray() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
        static public long[] GetLongArray() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
        static public List<double> GetDoubleList() { return Console.ReadLine().Split(' ').Select(double.Parse).ToList(); }
        static public void WriteObjects<T>(IEnumerable<T> values) { foreach (var o in values) { Console.Write(o + " "); } }
        static string yesno(this bool b) { return b ? "yes" : "no"; }
        static string YesNo(this bool b) { return b ? "Yes" : "No"; }
        static string YESNO(this bool b) { return b ? "YES" : "NO"; }

        static bool eq<T, U>() => typeof(T).Equals(typeof(U));
        static T ct<T, U>(U a) => (T)Convert.ChangeType(a, typeof(T));
        static T cv<T>(string s) => eq<T, int>() ? ct<T, int>(int.Parse(s))
                           : eq<T, long>() ? ct<T, long>(long.Parse(s))
                           : eq<T, double>() ? ct<T, double>(double.Parse(s))
                           : eq<T, char>() ? ct<T, char>(s[0])
                                             : ct<T, string>(s);
        static void Multi<T>(out T a) => a = cv<T>(GetStr());
        static void Multi<T, U>(out T a, out U b)
        {
            var ar = GetStrArray(); a = cv<T>(ar[0]); b = cv<U>(ar[1]);
        }
        static void Multi<T, U, V>(out T a, out U b, out V c)
        {
            var ar = GetStrArray(); a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]);
        }
    }
}

Measured memory_bytes: 14432
#[allow(unused_imports)]
use std::char::*;
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::*;
use std::str::FromStr;

#[allow(unused_macros)]
macro_rules! debug {($($a:expr),*) => {println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);}}
#[allow(unused_macros)]
macro_rules! input {(source=$s:expr,$($r:tt)*) => {let mut iter=$s.split_whitespace(); let mut next=||{iter.next().unwrap()}; input_inner! {next,$($r)*}};($($r:tt)*) => {let stdin=std::io::stdin();let mut bytes=std::io::Read::bytes(std::io::BufReader::new(stdin.lock())); let mut next=move||->String{bytes.by_ref().map(|r|r.unwrap() as char).skip_while(|c|c.is_whitespace()).take_while(|c|!c.is_whitespace()).collect()}; input_inner! {next,$($r)*}};}
#[allow(unused_macros)]
macro_rules! input_inner {($next:expr) => {}; ($next:expr,) => {}; ($next:expr,$var:ident:$t:tt$($r:tt)*) => {let $var=read_value!($next,$t); input_inner! {$next$($r)*}};}
#[allow(unused_macros)]
macro_rules! read_value {($next:expr,($($t:tt),*)) => {($(read_value! ($next,$t)),*)}; ($next:expr, [$t:tt; $len:expr]) => {(0..$len).map(|_|read_value! ($next,$t)).collect::<Vec<_>>()}; ($next:expr,chars) => {read_value! ($next,String).chars().collect::<Vec<char>>()}; ($next:expr,usize1) => {read_value! ($next,usize)-1}; ($next:expr,$t:ty) => {$next().parse::<$t>().expect("Parse error")};}

#[derive(PartialEq, PartialOrd)]
pub struct Total<T>(pub T);
impl<T: PartialEq> Eq for Total<T> {}
impl<T: PartialOrd> Ord for Total<T> {
    fn cmp(&self, other: &Total<T>) -> std::cmp::Ordering {
        self.0.partial_cmp(&other.0).unwrap()
    }
}

#[allow(dead_code)]
const MAX: usize = 100006;
#[allow(dead_code)]
const INF_U32: u32 = 1 << 31;
#[allow(dead_code)]
const INF_I32: i32 = 1 << 30;
#[allow(dead_code)]
const INF_U64: u64 = 1 << 63;
#[allow(dead_code)]
const INF_I64: i64 = 1 << 62;
#[allow(dead_code)]
const MOD: i64 = 1e9 as i64 + 7;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

#[allow(unused_imports)]
use std::f64;

fn main() {
    input!{n:usize, s:[String;n]};
    let mut map = BTreeMap::new();
    let mut mx = 0i64;
    for i in 0..n {
        let count = map.entry(&s[i]).or_insert(0i64);
        *count += 1;
        mx = max(mx, count.clone());
    }

    for (k,v) in map {
        if v == mx {
            println!("{}", k);
        }
    }

}


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

int main() {

	char alp[3];
	int i, a = 0, b = 0, c = 0;

	for (i = 0; i < 3; i++) {
		cin >> alp[i];
		if (alp[i] == 'a')a++;
		if (alp[i] == 'b')b++;
		if (alp[i] == 'c')c++;
	}

	if (a == 1 && b == 1 && c == 1) {
		cout << "Yes";
	}
	else {
		cout << "No";
	}

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define For(i, l, r) for (register int i = l, _r = r; i <= _r; ++i)
#define Ford(i, l, r) for (register int i = r, _l = l; i >= _l; --i)
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 20;

char a[10];

int main()
{
	scanf("%s",a+1);
	if(a[7]=='\0'&&a[3]==a[4]&&a[5]==a[6]) puts("Yes");
	else puts("No");
	return 0;
}


Measured memory_bytes: 256
import sys
from random import choice,randint
inp=sys.stdin.readline
out=sys.stdout.write
flsh=sys.stdout.flush
 
sys.setrecursionlimit(10**9)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]
 
def MI(): return map(int, inp().strip().split())
def LI(): return list(map(int, inp().strip().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines().strip()]
def LI_(): return [int(x)-1 for x in inp().strip().split()]
def LF(): return [float(x) for x in inp().strip().split()]
def LS(): return inp().strip().split()
def I(): return int(inp().strip())
def F(): return float(inp().strip())
def S(): return inp().strip()
def pf(s): return out(s+'\n')
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def main():
    n = I()
    s=0
    for i in range(1,n+1):
        if i%3!=0 and i%5!=0:
            s+=i
    print(s)

if __name__ == "__main__":
    main()

Measured memory_bytes: 9580
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 1000000007;
#define lcm(x, y) ((x) * (y) / __gcd((x), (y)))
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define debug(x) cout << #x << " : " << x << endl
#define part cout << "----------------------------------\n";
#include <iostream>

#define fastinput                     \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);

LL POW(LL x, LL y)
{
    LL ans = 1;
    LL base = x;
    while (y)
    {
        if (y & 1)
        {
            ans *= base;
        }
        base = base * base;
        y = y >> 1;
    }
    return ans;
}

int main()
{
    fastinput;
    LL n,i,j,k,t,temp,b,tc;
    string s;
    LL a[6];
    for(i=1;i<=5;i++)
    {
        cin>>a[i];
        if(a[i]==0)
        {
            cout<<i<<endl;
        }
    }

    return 0;
}


Measured memory_bytes: 3612
import math
d,g = map(int,input().split())
ans = []
data = []

for i in range(0,d):
    P,C = map(int,input().split())
    data.append((P,C,(i+1)*100))

def dfs(i,sum,a,last):
    if i >= d:
        p,c,point = data[last]
        if sum >= g-(c+p*point):
            global ans
            a += max(0,min(math.ceil((g-sum)/point),p))
            ans.append(a)
        return
    dfs(i+1,sum,a,last)
    p,c,point = data[i]
    if i != last:
        dfs(i+1,sum+c+p*point,a+p,last)

for i in range(0,d):
    p,c,point = data[i]
    dfs(0,0,0,i)
print(min(ans))


Measured memory_bytes: 3188
#include <iostream>

int main() {
  int N;
  std::cin >> N;
  int max_p = 1+1, min_p = 1000000000+1000000000, max_m = 1-1000000000, min_m = 1000000000-1;
  for (int i = 0; i < N; i++) {
    int xi, yi;
    std::cin >> xi >> yi;
    max_p = std::max(max_p,xi+yi);
    min_p = std::min(min_p,xi+yi);
    max_m = std::max(max_m,xi-yi);
    min_m = std::min(min_m,xi-yi);
  }
  std::cout << std::max(max_p-min_p,max_m-min_m) << std::endl;
  return 0;
}


Measured memory_bytes: 3156
using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
class Program
{
static long n = 200000;
static long q = long.Parse(Console.ReadLine());
static long[] parents = new long[n];//親
static long[] edgeCounts = new long[n];
static List<long>[] parentList = new List<long>[n];
  
	static void Main()
	{
    long answer = 0;
    
    for(int i = 0; i < (int)n; i++) parentList[i] = new List<long>();//リストの宣言
    for(long i = 1; i < n; i++)
    {
      parents[i] = i;
    }
    
    for(long i = 0; i < q; i++)
    {
      long[] nums = Array.ConvertAll(Console.ReadLine().Split(' '),long.Parse);
      edgeCounts[nums[0]-1]++;
      if(whatParent(nums[0]-1) != whatParent(nums[1]-1+100000))
        parents[whatParent(nums[0]-1)] = whatParent(nums[1]-1+100000);//親を結合して統一。親が2人できることはない。
    }

    for(int i = 0; i < n; i++) parentList[whatParent(i)].Add(i);

    for(int i = 0; i < n; i++)
    {
      long x = 0;
      long y = 0;
      long ll = 0;
      for(int j = 0; j < parentList[i].Count(); j++)
      {
        if(parentList[i][j] < 100000) x++;
        else y++;

        ll += edgeCounts[parentList[i][j]];
      }
      answer += x*y-ll;
    }
    Console.WriteLine(answer);
	}

  static long whatParent(long child)
  {
    if(parents[child] == child) return child;
    else return parents[child] = whatParent(parents[child]);
  }
  
}

Measured memory_bytes: 44148
#include <bits/stdc++.h>
#define ll long long int
#define FASTIO std::ios::sync_with_stdio(false);
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define inf 1e18
#define err(x) cout<<x<<endl
#define all(x) x.begin(),x.end()
#define input_from_file  freopen("input.txt", "r", stdin);
#define sz 100005
using namespace std;



int main()
{

    FASTIO
    string s;
    cin >> s;
    ll n = s.length();
    string pre = "";
    string now = "";
    ll ans = 0;
    for(ll i=0;i<n;i++)
    {
      now+=s[i];
      if(now != pre)
      {
        ans++;
        pre = now;
        now = "";

      }
    }
cout << ans;
return 0;
}


Measured memory_bytes: 720
import math
for i in range(30):
    n = int(input())
    if n == 0:
        break
    else:
        ls = []
        for i in range(n):
            ls.append(int(input()))
        ls.sort()
        ls.remove(ls[0])
        ls.remove(ls[-1])
        print(math.floor(sum(ls)/len(ls)))


Measured memory_bytes: 5668
n,k = map(int,input().split())
height_lst = [int(input()) for _ in range(n)]
height_lst.sort()

remainder_lst = []
for i in range(n-k+1):
    remainder = height_lst[i+k-1] - height_lst[i]
    remainder_lst.append(remainder)

answer = min(remainder_lst)
print(answer)

Measured memory_bytes: 11272
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = float('inf')
# ----------------------------------------------------------- #

n, m = Is()
AB = TIR(n)
AB.sort(key=itemgetter(0))
ans = 0
k = 0
for a, b in AB:
    if k+b < m:
        ans += a*b
        k += b
    else:
        ans += a*(m-k)
        print(ans)
        exit()


Measured memory_bytes: 82264
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()
#define let auto const

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

  vector<vector<i64>> a(N, vector<i64>(N));
  rep(i, 0, N) rep(j, 0, N) cin >> a[i][j];

  vector<vector<i64>> dp(N + 1, vector<i64>(1 << N, 0));
  const i64 mod = 1e9 + 7;
  dp[0][0] = 1;

  rep(i, 1, N + 1) {
    rep(s, 0, 1 << N) {
      if(i != __builtin_popcount(s)) continue;
      rep(j, 0, N) {
        if(!(s & (1 << j))) continue;
        if(a[i - 1][j] == 0) continue;
        i64 t = (s) & ~(1 << j);
        dp[i][s] = (dp[i][s] + dp[i - 1][t]) % mod;
      }
    }
  }

  cout << dp[N][(1 << N) - 1] << endl;
}


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

typedef long long int llint;

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

  if(a * b % 2 == 1 || a * b * 3 % 2 == 1) cout<< "Yes" <<endl;
  else cout<< "No" <<endl;
  
  return 0;
}


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

int h[100010];

int main() {
  int N, K;
  cin >> N >> K;
  for (int i = 0; i < N; i++) cin >> h[i];
  sort(h, h + N);
  int ans = 1000000010;
  for (int i = 0; i + K - 1 < N; i++) {
    if (h[i + K - 1] - h[i] < ans) ans = h[i + K - 1] - h[i];
  }
  cout << ans << endl;
}


Measured memory_bytes: 640
import Control.Monad

main :: IO ()
main = do
  n <- readLn
  ls <- replicateM n getLine
  let ans = counting' ls
  mapM_ putStrLn ans

counting :: [String] -> [String] -> [String]
counting [] ss = ss
counting (s:rs) [a,b,c,d,e,f]
  | s < "165.0" = counting rs [(a++"*"),b,c,d,e,f]
  | s < "170.0" = counting rs [a,(b++"*"),c,d,e,f]
  | s < "175.0" = counting rs [a,b,(c++"*"),d,e,f]
  | s < "180.0" = counting rs [a,b,c,(d++"*"),e,f]
  | s < "185.0" = counting rs [a,b,c,d,(e++"*"),f]
  | otherwise   = counting rs [a,b,c,d,e,(f++"*")]

counting' :: [String] -> [String]
counting' ss = counting ss ["1:","2:","3:","4:","5:","6:"]

Measured memory_bytes: 3676
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b, n;
  cin >> a >> n >> b;
  
  int plan1;
  plan1 = a * n;
  if (plan1 > b){
    cout << b << endl;
  } else if (plan1 < b) {
    cout << plan1 << endl;
  } else if (plan1 == b) {
    cout << b << endl;
  }
}

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

#define ll long long
#define vecll vector<long long>
#define vec2ll vector<vector<long long>>
#define vecpairll vector<pair<long long,long long>>
#define forll(s,a,b) for(long long s = a;s < b;s++)
#define forllde(s,a) for(long long s = a;s > 0;s--)


int main()
{
  ll x, c=0;
  cin >> x;
  c += 2 * (x / 11);
  x = x % 11;
  if (x <= 6 && x > 0)
	c ++;
  else if (x!=0)
	c += 2;
  cout << c << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

#define int long long

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);	
	
	int n;
	cin >> n;
	vector<int> a(n);
	int s = 0;
	for (auto &t : a) {
		cin >> t;
		s += t;
	}	
	int one = (n * (n + 1)) / 2;
	if (s % one) {
		cout << "NO\n";
		return 0;
	}
	int cnt = s / one;
	vector<int> v(n);
	for (int i = 0; i < n; i++) {
		int dt = (a[(i + 1) % n] - a[i] - cnt);
		// cerr << dt << endl;
		if (dt > 0) {
			cout << "NO\n";
			return 0;
		}
		if (dt % n) {
			cout << "NO\n";
			return 0;
		}
		v[(i + 1) % n] += abs(dt) / n;
	}
	int sv = 0;
	for (auto t : v) {
		sv += t;
	}
	if (sv != cnt) {
		cout << "NO\n";
		return 0;
	}
	cout << "YES\n";
}

Measured memory_bytes: 4392
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define pii std::pair<int,int>
#define pli std::pair<ll,int>
#define pil std::pair<int,ll>
#define psi std::pair<string,int>
#define pll std::pair<ll,ll>
#define pci std::pair<char,int>
#define sll(x) scanf("%lld",&x)
#define prll(x) printf("%lld ",x)
#define pri(x) printf("%d ",x)
#define si(x) scanf("%d",&x)
#define pb push_back
#define vll std::vector<ll>
#define vpi std::vector<std::pair<int,int>>
#define vi std::vector<int>
#define vvi std::vector<std::vector<int>>
#define vvpil std::vector<std::vector<std::pair<int,ll>>>
#define vlpii std::vector<std::list<pii>>
#define vlpil std::vector<std::list<pil>>
#define li std::list<int>
#define lpil std::list<pil>
#define Endl printf("\n")
#define vli vector<list<int>>
#define vvll vector<vector<ll>>
#define mp make_pair
#define x first
#define y second
#define ull uint64_t
#define ma 100000000
#define imie(...) "[" << #__VA_ARGS__": " << (__VA_ARGS__) << "] "
const ll  INF=10000000000000;
const ll mod =  1e9 + 7;
using namespace std;
void add(ll& a , ll b){
	a += b;
	if(a >= mod) a -= mod;
}
ll mul(ll a , ll b){
	return (a * b) % mod;
}
ll Pow(ll a , ll b){
	if(b == 0) return 1 ;
	ll c = Pow(a , b / 2) ;
	if(b % 2) return (a * ((c * c) )) ;
	return (c * c)  ;
}
string s ="" ;
void f(ll x){
	//cout << x << endl ;
	//if(abs(x) > 20) return ; 
	if(x == 0) return ; 
	if(x < 0){
		long double y = (1.0 / 2.0) * (Pow(2 , (int)log2(-x) + 1) - 1.0  - (1.0 - Pow(-2 , (int)log2(-x) + 1)) / 3.0) ; 
		//cout <<y <<" " << Pow(-2 , log2(-x)) << " "  << log2(-x) << endl ;
		
		if(x >= -y  && (int)log2(-x) % 2){
			 s[log2(-x)] = '1' ;
			 f(x + Pow(2 , log2(-x))) ;
		 }
		else if(x + Pow(2 , (int)log2(-x) + 1) >= 0 && ((int)log2(-x) + 1) % 2){
			s[(int)log2(-x) + 1]  ='1' ;
			f(x + Pow(2 , (int)log2(-x) + 1)) ;
		}
		else {
			s[(int)log2(-x) + 2]  ='1' ;
			f(x + Pow(2 , (int)log2(-x) + 2)) ;
		}
	}
	else{
		long double y = (1.0 / 2.0) * (Pow(2 , log2(x) + 1) - 1  + (1.0 - Pow(-2 , log2(x) + 1)) / 3.0) ; 
		if(x  <= y  && (int)log2(x) % 2 == 0){
			 s[log2(x)] = '1' ;
			 f(x - Pow(2 , log2(x))) ;
		 }
		else if(x - Pow(2 , (int)log2(x) + 1) <= 0 && ((int)log2(x) + 1) % 2 == 0){
			s[(int)log2(x) + 1] = '1' ;
			f(x - Pow(2 , (int)log2(x) + 1)) ;
		}
		else{
			s[(int)log2(x) + 2] = '1' ;
			f(x - Pow(2 , (int)log2(x) + 2)) ;
		}
			
	}
}
int main(){
	IOS;
	cout.precision(30) ;
	for(int i = 0 ; i < 40 ; i++) s += "0" ;
	int n ; cin >> n ;
	f(n) ;
	int fin = 39 ;
	while(fin >= 0 && s[fin] == '0') fin-- ;
	if(fin < 0) return cout << 0 << endl , 0;
	string res ="" ;
	for(int i = 0 ; i <= fin ; i++) res += s[i] ;
	reverse(res.begin() , res.end()) ;
	cout << res << endl ;
	return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    long n = sc.nextLong();
    long m = sc.nextLong();
    long ans = 0;
    if((n == 1) && (m == 1)) {
      ans = 1;
    } else if(n == 1) {
      ans = m - 2;
    } else if(m == 1) {
      ans = n - 2;
    } else if((n > 2) && (m > 2)) {
      ans = (n - 2) * (m - 2);
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 23636
use std::io::*;//Not mine.
use std::str::FromStr;
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main(){
    let a:i32 = read();
    let b:i32 = read();
    let c:i32 = read();
    if b / a >= c{
        println!("{}", c);
    }
    else {
        println!("{}", b / a);
    }
}

Measured memory_bytes: 4352