akhauriyash/Code-Regression huggingface dataset:
n,m=map(int,input().split())
a=[[int(i) for i in input().split()] for i in range(n)]
a=sorted(a)
money=0
cnt=0
for i in a:
    if cnt+i[1]<=m:
        cnt+=i[1]
        money+=i[0]*i[1]
    else:
        money+=(m-cnt)*i[0]
        break
print(money)

Measured memory_bytes: 61272
import heapq
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
def li(): return map(int, stdin.readline().split())
i_a, i_b, i_c, K = tuple(li())
A = list(li())
B = list(li())
C = list(li())
A.sort()
B.sort()
C.sort()

memo = {}
heap = []
def val(a,b,c):
    if a<0 or b<0 or c<0:
        return False
    return A[a] + B[b] + C[c]
total = val(i_a-1, i_b-1, i_c-1)
heap = [(-total, i_a-1, i_b-1, i_c-1)]
while K > 0:
    K -= 1
    cur = heapq.heappop(heap)
    print(-cur[0])
    a,b,c = cur[1], cur[2], cur[3]
    if (a-1, b,c) not in memo:
        va = val(a-1,b,c)
        if va:
            memo[(a-1,b,c)] = True
            heapq.heappush(heap, [-va, a-1, b, c])
    if (a, b-1,c) not in memo:
        vb = val(a,b-1,c)
        if vb:
            memo[(a,b-1,c)] = True
            heapq.heappush(heap, [-vb, a, b-1, c])

    if (a, b,c-1) not in memo:
        vc = val(a,b,c-1)
        if vc:
            memo[(a,b,c-1)] = True
            heapq.heappush(heap, [-vc, a, b, c-1])


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

#define ll long long
#define INF 99999999
#define MOD (ll)1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

template < typename T > std::string to_string( const T& n )
{
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
}

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }


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

    vector<int> first(N);
    rep(i,N) cin >> first[i];
    vector<int> second(N);
    rep(i,N) cin >> second[i];

    vector<int> a;
    rep(i,N) a.push_back(i+1);
    
    ll i = 1;
    ll first_pos = 1; 
    ll second_pos = 1; 
    do
    {
        if( a == first ) first_pos = i;
        if( a == second ) second_pos = i;
        i++;
    } while(next_permutation(all(a)));
    cout << abs(first_pos-second_pos) << endl;
}


Measured memory_bytes: 256
a, b = map(int, input().split())

car = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N',
'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']

for H in range(a):
	tmp = list(map(str, input().split()))
	for j in range(b):
		if tmp[j]=='snuke':
			ans = [car[j], str(H+1)]

print(''.join(ans))

Measured memory_bytes: 3064
import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as BS

tuplify2 (x:y:_) = (x,y)
tuplify2 _ = undefined

--Input functions with ByteString
readInt = fst . fromJust . BS.readInteger
readIntTuple = tuplify2 . map readInt . BS.words
readIntList = map readInt . BS.words

getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine
getIntNList n = map readIntList <$> replicateM (fromIntegral n) BS.getLine
getIntMatrix = map readIntList . BS.lines <$> BS.getContents
getIntTuple = readIntTuple <$> BS.getLine
getIntNTuples n = map readIntTuple <$> replicateM (fromIntegral n) BS.getLine
getIntTuples = map readIntTuple . BS.lines <$> BS.getContents

main = do
  getLine 
  a <- getIntList
  if elem 0 a 
    then print 0
    else print $ get $ solve a 1


mul :: Integer -> Integer -> Maybe Integer
mul n m
  | n*m <= 1000000000000000000 = Just (n*m)
  | otherwise = Nothing 

get :: Maybe Integer -> Integer
get (Just n) = n
get Nothing  = -1      

solve :: [Integer] -> Integer -> Maybe Integer
solve [] cur = Just cur
solve (fa:sa) cur = do
  p <- mul cur fa
  solve sa p

      
      


Measured memory_bytes: 13456
#include <cstdio> 
#include <cstdlib> 
#include <cmath> 
#include <cstring> 
#include <climits> 
#include <cfloat> 
#include <map> 
#include <utility> 
#include <set> 
#include <iostream> 
#include <memory> 
#include <string> 
#include <vector> 
#include <algorithm> 
#include <functional> 
#include <sstream> 
#include <complex> 
#include <stack> 
#include <queue> 
#include <numeric>
#include <cassert>

#define FOR(i, min, max) for (int i = (min); i < (max); ++i) 
#define FORE(i, min, max) for (int i = (min); i <= (max); ++i) 
#define REP(i, n) for (int i = 0; i < (n); ++i) 
#define REPV(vec, i) for (int i = 0; i < (int)(vec.size()); ++i) 
#define FOR_EACH(vec, it) for (typeof((vec).begin()) it = (vec).begin(); it != (vec).end(); ++it)

using namespace std; 
static const double EPS = 1e-12; 
typedef long long ll; 

int main(void)
{
    ll A;
    double Bd;
    cin >> A >> Bd;
    ll B = (ll)round(Bd * 100.0);
    cout << (A*B)/100 << endl;
    return 0;
}


Measured memory_bytes: 3776
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
//a以下の素数を配列に格納
int primenumber(int a,int *count){ //素数を配列に格納
  int i,j,num=1,check;
  count[0]=2;
  for(i=3;i<=a;i+=2){ //3以上√a以下の奇数の場合
    check=0;
    for(j=0;j<num;j++){
      if(i%count[j]==0){
        check=1;
        break;
      }
    }
    if(check==0)
      count[num++]=i;
  }
  return num;
}


int main(){
  int n,i;
  scanf("%d",&n);
  int prime[10000],a[56];
  int num=primenumber(55555,prime);
  int j=0;
  for(i=0;i<num;i++){
    if(prime[i]%5==1){
      a[j]=prime[i];
      j++;
    }
    if(j==n)
      break;
  }
  for(i=0;i<n;i++)
    printf("%d ",a[i]);
  puts("");
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <iomanip>
#include <vector>
#include <valarray>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <bitset>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <complex>
#include <string>
#include <sstream>

#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cmath>

using namespace std;

#define all(c) c.begin(),c.end()
#define repeat(i,n) for(int i=0;i<static_cast<int>(n);i++)
#define debug(x) #x << "=" << (x)
#define dump(x) cerr << debug(x) << " (L:" << __LINE__ << ")"<< endl

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<string> vs;

template<typename T>
ostream& operator<<(ostream& os, const vector<T>& vec){
    os << "[";
    for(int i = 0; i < vec.size(); i++){
        os << vec[i] << ",";
    }
    os << "]";
    return os;
}

template<typename T>
T input(){
    T t;
    cin >> t;
    return t;
}

template<typename T>
vector<T> input(const int N){
    vector<T> v(N);
    repeat(i,N) cin >> v[i];
    return v;
}

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

long long lcm(long long a, long long b){
    return (a / gcd(a, b)) * b;
}

long long mul(const long long& a, const long long& b, const long long& mod) {
    return ((a % mod) * (b % mod)) % mod;
}

long long power(const long long& x, const long long& y, const long long& mod) {
    if (y == 0) {
        return 1;
    } else if (y == 1) {
        return x % mod;
    } else {
        long long value = power(x, y / 2, mod);
        if (y % 2 == 0) {
            return mul(value, value, mod);
        } else {
            return mul(value, value, mod) * x % mod;
        }
    }
}

long long div(const long long& a, const long long& b, const long long& mod) {
    return mul(a, power(b, mod - 2, mod), mod);
}

map<long long, long long> factorials;
long long factorial(const long long& n, const long long& mod) {
    if (n == 0 || n == 1) {
        return 1;
    }
    if (factorials[n] != 0) {
        return factorials[n];
    }
    factorials[n] = n * factorial(n - 1, mod) % mod;
    return factorials[n] % mod;
}

long long combination(const long long& n, const long long& x, const long long& mod) {
    long long numerator = 1;
    long long denominator = 1;
    repeat(i, x) {
        numerator *= (n - i) % mod;
        numerator %= mod;
        denominator *= (i + 1) % mod;
        denominator %= mod;
    }
    return div(numerator, denominator, mod);
}

int main(){
    int A, B;
    cin >> A >> B;
    cout << (A + B) % 24 << endl;
    return 0;
}


Measured memory_bytes: 256
from collections import deque
n = int(input())
a = list(map(str,input().split()))
d = deque()
if n % 2 == 0:
  for i in range(n//2):
    d.append(a[2*i])
    d.appendleft(a[2*i+1])
  l = list(d)
  print(' '.join(l))
else:
  for i in range(n//2):
    d.appendleft(a[2*i])
    d.append(a[2*i+1])
  d.appendleft(a[n-1])  
  l = list(d)
  print(' '.join(l))


Measured memory_bytes: 107916
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
typedef long long ll;

int main() {
  int n;
  cin >> n;
  unordered_map<ll, ll> mp;

  for (int i = 2; i <= n; ++i) {
    int j = 2, k = i;
    while (k > 1) {
      if (k % j == 0)
        mp[j]++, k /= j;
      else
        j++;
    }
  }
  ll ans = 1;
  for (auto m : mp) ans *= m.second + 1, ans %= MOD;

  cout << ans << endl;
}


Measured memory_bytes: 256
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def find_root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]
        
    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
                
    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]

    
f=lambda:map(int,input().split())
N,M=f()
uf=UnionFind(N+1)

p=list(f())
p_index=[[] for _ in [0]*(N+1)]
for i in range(1,N+1):
    p_index[p[i-1]]=i
for _ in [0]*M:
    uf.unite(*f())


index_list=[[] for _ in [0]*(N+1)]
group_list=[[] for _ in [0]*(N+1)]

for i in range(1,N+1):
    index_list[uf.find_root(i)].append(p_index[i])
    group_list[uf.find_root(i)].append(i)
    
res=0
for i in range(1,N+1):
    if i==uf.find_root(i):
        res+=len(set(index_list[i]) & set(group_list[i]))

print(res)

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

int main() {
    int n,m;cin>>n>>m;
    vector<int> a[m];
    for (int i=0;i<m;i++) {
        int k;cin>>k;
        for (int j=0;j<k;j++) {
            int t;cin>>t;
            a[i].push_back(t-1);
        }
    }
    int p[m];
    for (int i=0;i<m;i++)
        cin>>p[i];
    int ans=0;
    for (int i=0;i<1<<n;i++) {
        int f=1;
        for (int j=0;j<m;j++) {
            int cnt=0;
            for (int k:a[j])
                if (i&1<<k)
                    cnt++;
            f&=cnt%2==p[j];
        }
        ans+=f;
    }
    cout<<ans<<endl;
}

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

int main(){


	int n;
	cin >> n;

	vector<int> mod(n+1,0);
	vector<int> a(n+1,0);

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

	vector<int> ans;
	for(int i=n;i>=1;i--){
		int j=2;
		int cnt = 0;
		while(j*i<=n){
			if(a[j*i]==1){
				cnt++;
			}
			j++;
		}

		if(mod[i]==1){
			if(cnt%2==0){
				a[i]=1;
				ans.push_back(i);
			}else{
				a[i]=0;
			}
		}else{
			if(cnt%2==0){
				a[i]=0;
			}else{
				a[i]=1;
				ans.push_back(i);
			}
		}

	}

	sort(ans.begin(),ans.end());

	cout  << ans.size() << "\n";

	for(int i=0;i<ans.size();i++){
		cout << ans[i] << " ";
	}
	cout << "\n";



	return 0;
}

Measured memory_bytes: 3064
_,x,y=$<.map{|e|e.chop.chars};x=x.zip(y).map{|a,b|a==b}.chunk{|e|e}.map{|k,v|n=v.size;k ?2**~-n: 2*3**(n/2-1)};p x.reduce(:*)*3%(10**9+7)

Measured memory_bytes: 1788
a,b,k = map(int,input().split())
ans = []
if 2*k <= b-a+1:
    for i in range(k):
        ans.append(a+i)
        ans.append(b-i)
    ans = list(set(ans))
    ans = sorted(ans)
    for i in ans:
        print(i)
else:
    for i in range(a,b+1):
        print(i)


Measured memory_bytes: 3060
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<math.h>
#include<map>
#include<iomanip>
#include<queue>

const long long INF = 1e6+7;
const long long MOD = 1e9+7;
const double PI=acos(-1);

using namespace std;

int main(){
	int x,y;
	cin >> x >> y;
	for(int i=0;i<=x;i++){
		int leg=i*2+(x-i)*4;
		if(leg==y){
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 3632
N = int(input())
s = input()
a = [chr(i) for i in range(65, 65+26)]
ls = []
for x in a:
  ls.append(x)
for x in a:
  ls.append(x)
ans = []
for x in s:
  ans.append(ls[ls.index(x)+N])
print(''.join(ans))

Measured memory_bytes: 9200
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int (i)=0;i<(n);i++)
#define REP(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define INF LLONG_MAX - 100
#define MOD 1000000007
#define fcout cout << fixed << setprecision(15)
#define int long long
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)?"YES":"NO")
#define lower_bound lowb
#define upper_bound upb
typedef long long ll;
typedef pair<int, int> P;
typedef priority_queue<int> pque;
int gcd(int a,int b){return b?gcd(b,a%b):a;};
int lcm(int a,int b){return a*b/gcd(a,b);};
int mod(int a,int b){return (a+b-1)/b;};
int month[12] = {31,28,31,30,31,30,31,31,30,31,30,31};
template<typename A, size_t N, typename T>
void Fill(A(&array)[N],const T &val){std::fill((T*)array,(T*)(array+N),val);}
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;};



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

    int n;
    cin >> n;
    int a[n];
    rep(i, n) cin >> a[i];

    int cur = 0;
    int next = 1;

    rep(i, n) {
        if(a[i] == next) {
            next++;
            cur++;
        }
    }

    if(cur == 0) cout << -1 << endl;
    else cout << n - cur << endl;
    return 0;
}

Measured memory_bytes: 1792
#include<iostream>
using namespace std;
int main()
{
  int N,odd;
  double prob;
  cin>>N;
  if(N%2==1){
    odd=(N+1)/2;
  }
  if(N%2==0)
  {
    odd=N/2;
  }
  prob=(odd*1.0)/N;
  cout<<prob;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int inf = 0x3f3f3f3f,oo = inf;
#define pi 3.14159265358979323846
#define IL inline
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define Rep(i,a,b) for(int i=(a);i<=(b);++i)
#define Dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pc putchar
#define gc getchar
IL ll read(){
    ll x=0;char f=0;char c=gc();
    for(;!isdigit(c);c=gc())f|=(c=='-');
    for(;isdigit(c);c=gc())x=(x<<1)+(x<<3)+(c^48);
    return f?-x:x;
}
IL void write(ll x){if(x<0)x=-x,pc('-');if(x>=10)write(x/10);pc(x%10+'0');}
IL void writeln(ll x){write(x);pc('\n');}
IL void wri(ll x){write(x),pc(' ');}
#define debug(x) printf(#x" = %d\n",x);
#define rd() read()
#define rdb() readdb()
#define mem(x,v) memset(x,v,sizeof(x))
#define pb push_back
#define mp make_pair
#define sqr(x) ((x)*(x))
#define lowbit(x) ((x)&(-(x)))
#define y1 ____y1
#define hash __hash
#define union _union
#define ramdom ((double)rand() / RAND_MAX)
#define x first
#define y second
const int maxn = 5e5+233;
struct Edge{
	int to,nxt;
	Edge(){}
	Edge(int to,int nxt):to(to),nxt(nxt){}
}edge[maxn*2];
int first[maxn],nume;
void Addedge(int a,int b){
	edge[nume] = Edge(b,first[a]);
	first[a] = nume++;
}
int mxdep[maxn],wson[maxn],sz[maxn];
int dfn[maxn],dfx[maxn],n,k;
int dp_array[maxn];
int *f[maxn];
void init(int u,int fa){
	mxdep[u] = 0;wson[u] = 0;sz[u] = 1;
	for(int e=first[u];~e;e=edge[e].nxt){
		int v=edge[e].to;
		if(v == fa) continue;
		init(v,u);
		mxdep[u] = max(mxdep[u],mxdep[v] + 1);
		sz[u] += sz[v];
		if(!wson[u] || mxdep[v] > mxdep[wson[u]])
			wson[u] = v;
	}
}
void pre(int u,int fa){
	dfx[dfn[u] = ++*dfn] = u;
	f[u] = dp_array + dfn[u];
	if(wson[u]) pre(wson[u],u);
	for(int e=first[u];~e;e=edge[e].nxt){
		int v=edge[e].to;
		if(v==fa || v==wson[u]) continue;
		pre(v,u);
	}
}
int g[maxn],h[maxn],ans;
void dfs(int u,int fa){
	if(wson[u]) dfs(wson[u],u);
	f[u][0] = wson[u] ? sz[wson[u]] : 0;
//	printf("#8999 %d %d\n",u,mxdep[u]);
	int m = min(k,mxdep[u]);
//	Rep(i,0,m) wri(f[u][i]);puts("");
	for(int e=first[u];~e;e=edge[e].nxt){
		int v = edge[e].to;
		if(v==wson[u] || v==fa) continue;
		dfs(v,u);
		int len = min(k,mxdep[v] + 1);
		g[0] = sz[v];Rep(i,1,len) g[i] = f[v][i-1];
		Rep(i,0,len) h[i] = f[u][i];
//		puts("~~"); 
//		wri(g[0]),writeln(h[0]);

//		Rep(i,0,len) wri(g[i]);puts("");
//		Rep(i,0,len) wri(h[i]);puts("");
//		puts("~~~~~~~~~~~~");

		Rep(i,0,len) f[u][i] = min(g[i]+h[min(i,k-i)],g[min(i,k-i)] + h[i]);
		Rep(i,len+1,min(m,k-len-1)) f[u][i] += g[len];
		Rep(i,max(len+1,k-len),min(m,k)) f[u][i] += g[k-i];
		
		Rep(i,1,len) f[u][i] = min(f[u][i],f[u][i-1]);
		Rep(i,max(len+1,k-len),min(m,k)) f[u][i] = min(f[u][i],f[u][i-1]);
	}Rep(i,1,m) assert(f[u][i] <= f[u][i-1]);
	ans = min(ans,n - sz[u] + f[u][min(k,m)]);
	//从root往上搞一格
}
int main(){
	mem(first,-1);nume = 0;
	n = read();k = read();ans = n;
	rep(i,1,n) {
		int x = read(),y = read();
		Addedge(x,y);
		Addedge(y,x);
	} init(1,0);
	*dfn = 0;
	pre(1,0);
	dfs(1,0);
	writeln(ans);
	return 0;
}


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

int main() {
    string S;
    long long K;
    cin >> S >> K;
    vector<long long> v;
    for (int i = 0; i < S.size();) {
        int j = i;
        while (j < S.size() && S[j] == S[i]) ++j;
        v.push_back(j - i);
        i = j;
    }
    if (S[0] != S.back()) {
        long long sum = 0;
        for (auto c : v) sum += c/2;
        cout << sum * K << endl;
    }
    else {
        if (v.size() == 1) cout << v[0] * K / 2 << endl;
        else {
            long long left = v[0], right = v.back(), mid = 0;
            for (int i = 1; i+1 < v.size(); ++i) mid += v[i]/2;
            cout << mid*K + (left+right)/2 * (K-1) + left/2 + right/2 << endl;
        }
    }
}

Measured memory_bytes: 3568
/*
    Author:zeke
    
    pass System Test!
    GET AC!!
*/
#include <iostream>
#include <queue>
#include <vector>
#include <iostream>
#include <vector>
#include <string>
#include <cassert>
#include <algorithm>
#include <functional>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <map>
#include <iomanip>
#include <utility>
#include <stack>
using ll = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define rep3(var, min, max) for (ll(var) = (min); (var) < (max); ++(var))
#define repi3(var, min, max) for (ll(var) = (max)-1; (var) + 1 > (min); --(var))
#define Mp(a, b) make_pair((a), (b))
#define F first
#define S second
#define Icin(s) \
    ll(s);      \
    cin >> (s);
#define Scin(s) \
    ll(s);      \
    cin >> (s);
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef vector<V> VV;
typedef vector<P> VP;
ll MOD = 1e9 + 7;
ll INF = 1e18;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll x;
    cin >> x;
    cout << x * x << endl;
}

Measured memory_bytes: 256
import java.io.IOException;

import java.io.BufferedReader;
import java.io.InputStreamReader;

import java.io.PrintWriter;

import java.util.Arrays;

@SuppressWarnings("unchecked")
public class Main {
    static long[] B;
    static long[] P;

    public static void main(String[] args) throws IOException {
        final String s;

        try (
            BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in))) {
            s = reader.readLine();
        }

        PrintWriter out = new PrintWriter(System.out);

        final String[] sl = s.split(" ");
        int N = Integer.parseInt(sl[0]);
        long X = Long.parseLong(sl[1]);

        B = new long[N];
        P = new long[N];

        B[0] = 1L;
        P[0] = 1L;

        for (int i = 1; i < N; i++) {
            B[i] = 2 * B[i - 1] + 3;
            P[i] = 2 * P[i - 1] + 1;
        }

        long ans = f(N, X);

        out.println(ans);

        out.flush();
    }

    // レベル N
    // 下から X
    // パティ 数
    static long f(int N, long X) {
        if (X <= 0) return 0L;
        if (N == 0) return 1L;
        if (X == 1) return 0L;
        if (1 < X && X <= B[N - 1] + 1) return f(N - 1, X - 1);
        return P[N - 1] + 1 + f(N - 1, X - 2 - B[N - 1]);
    }
}


Measured memory_bytes: 21204
H, W, K = [int(_) for _ in input().split()]
fib = [1, 1, 2, 3, 5 ,8, 13, 21]
dp = [[1] + [0] * (W - 1)]
if W == 1:
    print(1)
else:
    for j in range(1, H + 1):
        dp.append([0] * W)
        for i in range(W):
            if i == 0:
                dp[j][i] = (dp[j - 1][i] * fib[i] * fib[W - i - 1] + dp[j - 1][i + 1] * fib[i] * fib[W - i - 2]) % 1000000007
            elif i == W - 1:
                dp[j][i] = (dp[j - 1][i] * fib[i] * fib[W - i - 1] + dp[j - 1][i - 1] * fib[i - 1] * fib[W - i - 1]) % 1000000007
            else:
                dp[j][i] = (dp[j - 1][i] * fib[i] * fib[W - i - 1] + dp[j - 1][i + 1] * fib[i] * fib[W - i - 2] + dp[j - 1][i - 1] * fib[i - 1] * fib[W - i - 1]) % 1000000007
    print(dp[H][K - 1])

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,k,n) for(int i=k;i<n;i++)
#define MAX_N 100100
using namespace std;
bool p[MAX_N];
int a[MAX_N];
void makeprime(){
  memset(p,true,sizeof p);
  p[0] = false;
  p[1] = false;
  REP(i,2,(int)sqrt(MAX_N)){
    if(p[i]==false) continue;
    REP(j,i,MAX_N){
      if(i*j>=100100) break;
      p[i*j] = false;
    }
  }

  memset(a,0,sizeof a);
  int t = 0;
  for(int i=3;i<MAX_N;i+=2){
    if(p[i]&&p[(i+1)/2]) t++;
    a[i]=t;
    a[i+1]=t;
  }
}
int main(){
  makeprime();
  int q;
  cin >> q;
  rep(i,q){
    int l,r;
    cin >> l >> r;
    cout << a[r]-a[l-1] << endl;
  }
  return 0;
}


Measured memory_bytes: 1152
n,m,q  = map(int,input().split())
abcd = [list(map(int,input().split())) for i in range(q)]
import itertools
ans = 0
for i in itertools.combinations_with_replacement(range(1,m+1),n):
         tmp = 0
         for j in range(len(abcd)):
                  if i[abcd[j][1] - 1] - i[abcd[j][0] - 1] == abcd[j][2]:
                           tmp += abcd[j][3]
         if ans < tmp:
                  ans = tmp
print(ans)


Measured memory_bytes: 9068
#include<stdio.h>

int main(){

	int arr[7] = {0};
	for(int i=1;i<7;i++){
		scanf("%d",&arr[i]);
	}


	int dice[8][3] = { {arr[1],arr[2],arr[3]},{arr[1],arr[5],arr[4]},{arr[1],arr[4],arr[2]},{arr[1],arr[3],arr[5]},{arr[2],arr[4],arr[6]},{arr[3],arr[6],arr[5]},{arr[4],arr[5],arr[6]},{arr[3],arr[2],arr[6]}};

	int q;
	scanf("%d",&q);


	for(int i=0;i<q;i++){


	int top,front,right = 0;
	scanf("%d %d",&top,&front);

	for(int i=0;i<8;i++){
		if(dice[i][0] == top && dice[i][1] == front)
		right = dice[i][2];
		if(dice[i][1] == top && dice[i][2] == front)
		right = dice[i][0];
		if(dice[i][2] == top && dice[i][0] == front)
		right = dice[i][1];
	}

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

	}



	return 0;
}


Measured memory_bytes: 2064
#include<bits/stdc++.h>
#define ll long long
#define all(a) a.begin(),a.end()
#define sz(a) a.size()
#define re return 
#define MP make_pair
#define pb push_back
#define pii pair<int,int>
#define se second
#define fi first
using namespace std;
int ans;
signed main(){
	ios_base::sync_with_stdio(0);
	int n;
	cin>>n;
	while(n--){
		int l,r;
		cin>>l>>r;
		ans+=r-l+1;
	}
	cout<<ans;
	re 0;
}

Measured memory_bytes: 3652
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
# include <numeric>
#include <tuple>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
constexpr int INF = 2000000000;
constexpr int HINF = INF / 2;
constexpr double DINF = 100000000000000000.0;
constexpr long long LINF = 9223372036854775807;
constexpr long long HLINF = 4500000000000000000;
const double PI = acos(-1);
int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
#define ALL(x)   (x).begin(),(x).end()
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define mp       make_pair
#define eb       emplace_back
LL n, a[101010], b[101010], c[101010];
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> b[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> c[i];
	}
	sort(a, a + n), sort(b, b + n), sort(c, c + n);
	LL ans = 0;
	for (int i = 0; i < n; i++) {
		ans += distance(a, lower_bound(a, a + n, b[i]))*distance(upper_bound(c, c + n, b[i]), c + n);
	}
	cout << ans << endl;
}

Measured memory_bytes: 2688
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
struct edge {
	int to, next;
} e[N * 2];
int head[N], ecnt, mark[N];
inline void adde(int from, int to) {
	e[++ecnt] = (edge){to, head[from]}, head[from] = ecnt;
	e[++ecnt] = (edge){from, head[to]}, head[to] = ecnt;
}
void dfs(int u, int f) {
	mark[u] = 1; int ct = 0;
	for (int i = head[u]; i; i = e[i].next)
		if (e[i].to != f) dfs(e[i].to, u), ct += mark[e[i].to];
	if (ct > 1 || (u == 1 && ct == 0)) puts("First"), exit(0);
	if (ct == 1) mark[u] = 0;
}
int main() {
	int n; scanf("%d", &n);
	for (int i = 1, a, b; i < n; i++) scanf("%d%d", &a, &b), adde(a, b);
	dfs(1, 0), puts("Second");
}

Measured memory_bytes: 2560
s = input()

st = []
leftn = 0

def pushv(s, x):
        tmp = s.pop()
        tmpsum = 0
        while tmp[0] != 'left':
                tmpsum += tmp[1]
                tmp = s.pop()
        else:
                tmpsum += x - tmp[1]
                s.append(('v', tmpsum))

for x in range(len(s)):
        if s[x] == '\\':
                st.append(('left', x))
                leftn += 1
        elif s[x] == '/':
                if leftn != 0:
                        pushv(st, x)
                        leftn -= 1

st = [x[1] for x in st if x[0] == 'v']

if len(st) != 0:
       print(sum(st))
       print(len(st), ' '.join([str(x) for x in st]))
else:
      print(0)
      print(0)

Measured memory_bytes: 9424
def areDistinct(arr) : 
  
    n = len(arr) 
  
    # Put all array elements in a map 
    s = set() 
    for i in range(0, n):  
        s.add(arr[i]) 
      
    # If all elements are distinct,  
    # size of set should be same array. 
    return (len(s) == len(arr)) 
  
# Driver code 
N = int(input())
S =  [int(x) for x in input().split()]
  
if (areDistinct(S)):  
    print("YES") 
  
else :  
    print("NO") 

Measured memory_bytes: 25936
#include <iostream>
#include <vector>

using namespace std;

int main(void) {
    int N, tmp, count = 0;
    vector<int> p;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> tmp;
        p.push_back(tmp);
    }
    for (int i = 0; i < N; i++) {
        for (int j = N-1; j >= i+1; j--) {
            if (p[j] < p[j-1]) {
                int tmp2 = p[j];
                p[j] = p[j-1];
                p[j-1] = tmp2;
                count++;
            }
        }
    }
    for (int i = 0; i < N-1; i++) {
        cout << p[i] << " ";
    }
    cout << p[N-1] << endl;
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 1216
n = gets.chomp.to_i
titles = []
seconds = []
n.times do
    a, b = gets.chomp.split
    titles << a
    seconds << b.to_i
end
x = gets.chomp
ans = 0
count_flag = false
n.times do |i|
    ans += seconds[i] if count_flag
    count_flag = true if x == titles[i]
end
puts ans

Measured memory_bytes: 14212
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <string>

using namespace std;

bool is_palindrome(const string& s) {
  string r = s;
  reverse(r.begin(), r.end());
  return s == r;
}

int main() {
  string s;
  cin >> s;

  bool is_strong_palindrome = true;

  if (!is_palindrome(s)) {
    is_strong_palindrome = false;
  }

  int n = s.size();
  const string& head = s.substr(0, (n-1)/2);

  if (!is_palindrome(head)) {
    is_strong_palindrome = false;
  }

  const string& tail = s.substr((n+1)/2, n - (n+1)/2);

  if (!is_palindrome(tail)) {
    is_strong_palindrome = false;
  }

  cout << (is_strong_palindrome ? "Yes" : "No")  << endl;
  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 105000
int n,a[N],b[N],v[N*2],id1[N],id2[N];
long long su1,su2,su[N*2],as=1e18;
long long solve(int i)
{
	if(id1[i]>n&&id2[i]>n)return su[n];
	else if(id1[i]>n+1||id2[i]>n+1)return su[n+1]-(id1[i]<=n+1?v[id1[i]]:0)-(id2[i]<=n+1?v[id2[i]]:0);
	else return su[n+2]-v[id1[i]]-v[id2[i]];
}
int main()
{
	scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]),v[i*2-1]=a[i],v[i*2]=b[i],su1+=a[i],su2+=b[i];
	sort(v+1,v+n*2+1);for(int i=1;i<=n;i++)id1[i]=lower_bound(v+1,v+n*2+1,a[i])-v,id2[i]=lower_bound(v+1,v+n*2+1,b[i])-v;
	for(int i=1;i<=n*2;i++)su[i]=su[i-1]+v[i];
	as=min(su1,su2);for(int i=1;i<=n;i++)as=min(as,solve(i));
	printf("%lld\n",as);
}//

Measured memory_bytes: 4224
#include<bits/stdc++.h>
using namespace std;
#define MAXN	200005
#define P	1000000007
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
struct info {int p, v; };
struct interval {int l, r; };
info a[MAXN], b[MAXN];
interval A[MAXN];
int l[MAXN], r[MAXN];
int opt[MAXN], sum[MAXN];
bool cmp(info x, info y) {
	return x.v < y.v;
}
bool cnp(interval a, interval b) {
	if (a.l == b.l) return a.r < b.r;
	else return a.l < b.l;
}
int add(int x, int y) {
	return (x + y) % P;
}
int mns(int x, int y) {
	return (x - y + P) % P;
}
int main() {
	int n; read(n);
	for (int i = 1; i <= n; i++)
		read(a[i].p), read(a[i].v);
	sort(a + 1, a + n + 1, cmp);
	for (int i = 1; i <= n; i++)
		b[i] = (info) {i, a[i].p};
	sort(b + 1, b + n + 1, cmp);
	int pos = 0;
	for (int i = 1; i <= n; i++) {
		pos = max(pos, b[i].p);
		r[b[i].p] = pos;
	}
	pos = n + 1;
	for (int i = n; i >= 1; i--) {
		pos = min(pos, b[i].p);
		l[b[i].p] = pos;
	}
	for (int i = 1; i <= n; i++)
		A[i] = (interval) {l[i], r[i]};
	sort(A + 1, A + n + 1, cnp);
	int ans = 0; pos = 1;
	for (int i = 1; i <= n; i++) {
		if (A[i].l == 1) opt[i] = 1;
		else opt[i] = 0;
		while (pos < i && A[pos].r + 1 < A[i].l) pos++;
		opt[i] = add(opt[i], mns(sum[i - 1], sum[pos - 1]));
		sum[i] = add(opt[i], sum[i - 1]);
		if (A[i].r == n) ans = add(ans, opt[i]);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 8064
A, B = map(int, input().split())

def mark(x, v):
    if x%4 in [1,2]:
        v[0] = 1
    for i in range(1,40):
        p = 2**(i+1)
        if x%p >= p/2 and (x%p - p/2-1)%2 == 1:
            v[i] = 1

a = [0] * 40
if A >= 2:
    mark(A-1, a)

b = [0] * 40
mark(B, b)

ans = 0
for i in range(40):
    if a[i]^b[i]:
        ans += 2**i

print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#define FOR(i,k,n)  for(int i = (k);i < (n);++i)
#define REP(i,n)    FOR(i,0,n)

using namespace std;
using ll = int64_t;
using vecint = vector<int>;
using vecll = vector<ll>;

vector<vecint> solve(int n) {
  if (n == 2) {
    return vector<vecint>(1, vecint(1, 1));
  } else if (n == 3) {
    vector<vecint> res(2);
    res[0] = vecint(2);
    res[0][0] = 1;
    res[0][1] = 2;
    res[1] = vecint(1);
    res[1][0] = 1;
    return res;
  }
  auto r1 = solve(n/2);
  auto r2 = solve(n-n/2);
  int mx = 0;
  for(auto&& l : r2) mx = max(mx, *boost::max_element(l));
  int idx = mx + 1;
  vector<vecint> res(n-1);
  REP(i,n-1) {
    res[i] = vecint(n-i-1);
    if (i < n/2) {
      int idxmx = n/2-i-1;
      REP(j,idxmx) {
        res[i][j] = r1[i][j];
      }
      FOR(j,idxmx,n-i-1) {
        res[i][j] = idx;
      }
    } else {
      REP(j,n-i-1) {
        res[i][j] = r2[i-n/2][j];
      }
    }
  }
  return res;
}

int main()
{
  int n;
  cin>>n;
  auto res = solve(n);
  REP(i,n-1){
    REP(j,n-i-1) {
      if (j) cout<<' ';
      cout<<res[i][j];
    }
    cout<<endl;
  }
  return 0;
}


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

const int N = 7e2 + 5;
const int K = 7e2 + 5;

#define int long long

int dp[N][K] , n , m , C[N][N] , mod , k , S[N][K];

void Add(int &x , int y) {
	if((x += y) >= mod)
	x -= mod;
}

void Sub(int &x , int y) {
	if((x -= y) < 0)
	x += mod;
}

void Mul(int &x , int y) {
	x = 1LL * x * y % mod;
}

bool vis[N][K] , vis2[N][K];

int solve(int x , int y);

int sum(int x , int y) {
	if(vis2[x][y])
	return S[x][y];
	if(!x || y > k)
	return 0;
	vis2[x][y] = 1;
	for(int i = y;i <= k;++ i) 
	Add(S[x][y] , solve(x , i));
	return S[x][y];
}

int solve(int x , int y) {
	if(!x) {
		return 0;
	}
	if(x == 1) {
		return dp[x][y] = 1;
	}
	if(vis[x][y])
	return dp[x][y];
	vis[x][y] = 1;
	dp[x][y] = 0;
	for(int i = 1;i < x;++ i) {
		Add(dp[x][y]  , C[x - 2][i - 1] * solve(x - i , y) % mod * sum(i , y + 1) % mod);
	}
	return dp[x][y];
}

main() {
	scanf("%lld%lld%lld" , &n , &k , &mod);
	
	for(int i = 0;i <= n;++ i) 
	for(int j = 0;j <= i;++ j) 
	C[i][j] = ((!j) ? 1 : ((C[i - 1][j - 1] + C[i - 1][j]) % mod));
	
	printf("%lld\n" , solve(n + 1 , 0));
}

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

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = n - 1; i >= 0; i--)
#define repone(i, n) for(ll i = 1; i <= (ll)(n); i++)
#define each(i, mp) for(auto i:mp)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll half_inf = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);


ll N, T;
vector<ll> A;

void solve() {
    ll temp_min = ll_inf;
    vector<ll> mina;
    rep(i, N) {
        temp_min = min(temp_min, A[i]);
        mina.emplace_back(temp_min);
    }
    vector<ll> diffa;
    rep(i, N) diffa.emplace_back(A[i] - mina[i]);
    ll maxd = *max_element(diffa.begin(), diffa.end());

    ll ans = 0;
    ll cur_min = -1;
    ll i = 0;
    while (i < N) {
        if (A[i] != cur_min && diffa[i] == 0) {
            cur_min = A[i];
        } else if (A[i] - cur_min == maxd) {
            ans++;
        }
        i++;
    }
    cout << ans << endl;
}

int main() {
    cin >> N >> T;
    A.resize(N);
    rep(i, N) cin >> A[i];
    solve();
    return 0;
}

Measured memory_bytes: 3316
#include <iostream>

using namespace std;

int main()
{
        int a;
        cin>>a;
                if(a==999){
                    cout<<"111";
        }
                if(a==991){
                    cout<<"119";
        }
                if(a==919){
                    cout<<"191";
        }
                if(a==199){
                    cout<<"911";
        }
                if(a==911){
                    cout<<"199";
        }
                if(a==191){
                    cout<<"919";
        }
                if(a==119){
                    cout<<"991";
        }
                if(a==111){
                    cout<<"999";
        }
    }


Measured memory_bytes: 256
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    s = input()
    ans = 700
    for i in s:
        if i=='o':
            ans += 100
    
    print(ans)

solve()


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i=0; i<(int)(n); i++)
int main(){
int N, Q, S, T, X, D; cin >> N >> Q; vector<int> ans(Q, -1);
vector< vector<int> > A(N);
REP(i, N){ cin >> S >> T >> X; A[i]={X, S, T}; }
sort(A.begin(), A.end());
set< pair<int, int> > P;
REP(i, Q){ cin >> D; P.insert(make_pair(D, i)); }
REP(i, N){
  int x=A[i][0], s=A[i][1], t=A[i][2], j=0;
  pair<int, int> l=make_pair(s-x, -1), r=make_pair(t-x, -1);
  auto L=P.lower_bound(l), R=P.lower_bound(r);
  vector< pair<int, int> > K;
  while(L!=R){ j=(*L).second; ans[j]=x; K.push_back(*L); L++; }
  REP(k, K.size()){ P.erase(K[k]); }
}
REP(i, Q){ cout << ans[i] << "\n"; }
}

Measured memory_bytes: 26468
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
const ll M=1e5+5;
ll dp[4][M];
ll mat[4][M];
ll rec(ll par,ll index)
{
	if(dp[par][index]!=-1)
		return dp[par][index];
	else
	{
		if(par==1)
			dp[par][index]=max(mat[2][index]+rec(2,index-1),mat[3][index]+rec(3,index-1));
		else if(par==2)
			dp[par][index]=max(mat[1][index]+rec(1,index-1),mat[3][index]+rec(3,index-1));
		else if(par==3)
			dp[par][index]=max(mat[1][index]+rec(1,index-1),mat[2][index]+rec(2,index-1));

		return dp[par][index];
	}
}

int main()
{
	ll n,i,j,k,x,y,t,m;
	cin >> n;
	
	ll mx=-1;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=3;j++)
		{
			cin >> mat[j][i];
			mx=max(mx,mat[j][i]);
		}
	}
	memset(dp,-1,sizeof(dp));
	
	dp[1][1]=max(mat[2][1],mat[3][1]);
	dp[2][1]=max(mat[3][1],mat[1][1]);
	dp[3][1]=max(mat[1][1],mat[2][1]);
	

	if(n==1)
		cout << mx << endl;
	else
	cout << max(max(mat[1][n]+rec(1,n-1),mat[2][n]+rec(2,n-1)),mat[3][n]+rec(3,n-1)) << endl;
}	

Measured memory_bytes: 10368
#include <stdio.h>

int main() {
	int a, b, c, d, l, r;

	scanf("%d%d%d%d", &a, &b, &c, &d);
	l = a > c ? a : c;
	r = b < d ? b : d;
	printf("%d\n", l >= r ? 0 : r - l);
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define maxn 100010
#define ll long long
#define db double
#define vi vector<int>
#define pb push_back
#define mod 998244353
ll ksm(ll a, ll b) {
   if (!b) return 1;
   ll ns = ksm(a, b >> 1);
   ns = ns * ns % mod;
   if (b & 1) ns = ns * a % mod;
   return ns;
}
ll work(ll a, ll b) {
	if (a > b) swap(a, b);
	if (!(b % a)) return 2 * b - a;
	ll ns = b / a;
	return ns * (2 * a) + work(b % a, a);
} 
int main() {
	ll n, x;
	cin >> n >> x;
	cout << (n + work(x, n - x)) << endl;
	return 0;
}


Measured memory_bytes: 256
#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>;

struct edge {int to, cost;};

int main(void){
    int n;
    cin >> n;
    vector<edge> d[n];
    rep(i, n){
        int u, k;
        cin >> u >> k;
        rep(j, k){
            int v, c;
            cin >> v >> c;
            d[u].push_back({v, c});
        }
    }
    vector<int> v(n);
    fill(v.begin(), v.end(), INT_MAX);
    priority_queue<P,vector<P>, greater<P>> q;
    q.push({0, 0});
    while(!q.empty()){
        P p = q.top(); q.pop();
        int g = p.second;
        if(v[g] < p.first) continue;
        v[g] = p.first;
        for(auto x : d[g]){
            if(v[x.to] > v[g] + x.cost)
                q.push({v[g] + x.cost, x.to});
        }
    }
    rep(i, n) cout << i << ' ' << v[i] << endl;
    return 0;
}


Measured memory_bytes: 3228
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<bitset>
#include<vector>
#include<deque>
#include<list>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<iomanip>
#include <functional>
using namespace std;
typedef long long ll;
const int mod = 1000000007;
const int INF = 1 << 28;
const double EPS = 1e-10;
//cout << fixed << std::setprecision(9)
//memset(a, 0, sizeof(a));
//--------------------------

int n, k;
int t[100005];
int d[100005];

class sushi {
public:
	int num;
	int del;
};

bool comp(sushi s1, sushi s2)
{
	return s1.del > s2.del;
}

int main()
{
	int var;
	ll sum = 0;
	ll ans = 0;

	cin >> n >> k;
	vector<sushi> sushis(n);

	for (int i = 0;i < n;i++) {
		cin >> t[i] >> d[i];
		sushis[i].num = t[i];
		sushis[i].del = d[i];
	}

	sort(sushis.begin(), sushis.end(), comp);

	// create add list
	set<int> st;
	for (int i = 0;i < k;i++) {
		st.insert(sushis[i].num);
		sum = sum + (ll)sushis[i].del;
	}
	var = st.size();

	ans = sum + (ll)var * var;

	map<int, int> rm;
	for (int i = k;i < n;i++) {
		int key = sushis[i].num;
		if (st.find(key) == st.end()) {
			if (rm.find(key) == rm.end()) {
				rm.insert(make_pair(key, sushis[i].del));
			}
			else {
				rm[key] = max(rm[key], sushis[i].del);
			}
		}
	}

	priority_queue<int> rq;
	map<int, int> ::iterator itr;
	for (itr = rm.begin(); itr != rm.end(); itr++) {
		rq.push(itr->second);
	}

	//create delete list
	map<int, priority_queue<int> > lm;
	for (int i = 0;i < k;i++) {
		int key = sushis[i].num;

		if (lm.find(key) == lm.end()) {
			priority_queue<int> *q = new priority_queue<int>;
			q->push(sushis[i].del);
			lm.insert(make_pair(key, *q));
		}
		else {
			lm[key].push(sushis[i].del);
		}
	}

	vector<int> lv;
	map<int, priority_queue<int> >::iterator it;
	for (it = lm.begin(); it != lm.end(); it++) {
		if (it->second.size() > 1) {
			it->second.pop();
			while (it->second.size()) {
				lv.push_back(it->second.top());
				it->second.pop();
			}
		}
	}

	sort(lv.begin(), lv.end());

	// implement the core parts
	int i = 0;
	while (i < lv.size() && rq.size()) {
		sum = sum - (ll)lv[i];
		sum = sum + (ll)rq.top();
		var++;
		ans = max(ans, sum + (ll)var * var);
		i++;
		rq.pop();
	}
	
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 16640
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
#define ar array
#define pb push_back



int main()
{
	// #ifndef ONLINE_JUDGE
	// 	freopen("input.txt","r",stdin);
	// 	freopen("outputc.txt","w",stdout);
	// #endif
	
	//int t;
	//cin>>t;
	//while(t--)
	{
		int n,k;
		cin>>n>>k;
		int a[n];
		for(auto &x:a)
		{
			cin>>x;
		}
		int dp[k+1];
		memset(dp,0,sizeof(dp));
		for(int j=1;j<=k;j++)
		{
			for(int i=0;i<n;i++)
			{
				if(j-a[i]>=0&&dp[j-a[i]]==0)
				{
					dp[j]=1;
				}
			}
		}
		if(dp[k])
		{
			cout<<"First";
		}
		else
		{
			cout<<"Second";
		}
		
	}
		
}


Measured memory_bytes: 3992
n = int(input())
s = input()

a = [int(i) for i in s.split(" ")]
a.sort()
a.reverse()
pairs = []
buf = None
sq = 0
for c in a:
    if buf == c:
        pairs.append(c)
        buf = None
        if len(pairs)==2:
            sq = pairs[0] * pairs[1]
            break
    else:
        buf = c
print(sq)

Measured memory_bytes: 15192
from collections import Counter

s = []
for _ in range(int(input())):
    s.append(input())

for _ in range(int(input())):
    t = input()
    if t in s:
        s.remove(t)

if len(s) == 0:
    print(0)
else:
    c = Counter(s)
    print(c.most_common(1)[0][1])

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

long long pow_mod(long long x, long long y){

    long long tmp = 1;
    for(int i=1; i<=y; i++){
        tmp *= x;
        tmp %= MOD;
    }
    return tmp;
}

int main()
{
    long long n;
    cin >> n;
    vector<int> d(n);
    int v[100000] = {0};
    int max_n = 0;
    rep(i, n){
        cin >> d[i];
        max_n = max(max_n, d[i]);
        v[d[i]]++;
    }

    if(d[0] != 0 || v[0] != 1){
        cout << 0;
        return 0;
    }

    long long hen = v[1], youso;
    long long ans = 1;
    for(int i=2; i<=max_n; i++){
        youso = v[i];
        if(v[i] == 0){
            cout << 0;
            return 0;
        }
        ans *= pow_mod(hen, youso);
        ans %= MOD;
        hen = youso;
    }

    cout << ans;

    return 0;
}


Measured memory_bytes: 1024
#include<cstdio>
#include<iostream>
#include<bitset>
using namespace std;
int n,i,x,y;
bitset<4000010> a;
int main()
{
	scanf("%d",&n);
	a[0]=1;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&x);
		y+=x;
		a|=a<<x;
	}
	if(y&1)y=y/2+1;else y/=2;
	while(a[y]==0)y++;
	printf("%d\n",y);
}

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

int main() {
  double N;
  cin>>N;
  vector<int>X(N);
  double T=0;
 for(int i=0;i<N;i++){
    cin>> X.at(i);
    T+=X.at(i);
 }
  double Y=0;
  int EX=T/N+0.5;

  for(int i=0;i<N;i++){
    Y+=(X.at(i)-EX)*(X.at(i)-EX);
  }
  cout<<Y<<endl;
}


Measured memory_bytes: 256
/*
貪欲
後ろから見る
DP
順位表をチェック
二分探索


*/
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
#include <cmath>
#include <limits>
#include <iostream>
#include <map>
#include<tuple>
#include<set>
using namespace std;
#define INF 1100000000000000000
#define MAX 100000
#define MOD 1000000007
typedef long long ll;
//typedef pair<int,int> P;
//typedef pair< pair<int,int>,pair<int,int> > p;
#define bit(n,k) ((n>>k)&1) /*nのk bit目*/
#define rad_to_deg(rad) (((rad)/2/M_PI)*360)
struct edge{ll to,cost,val;};
template<class T,class U>bool chmin(T&a,const U&b){if(a<=b)return false;a=b;return true;}
template<class T,class U>bool chmax(T&a,const U&b){if(a>=b)return false;a=b;return true;}
//__builtin_popcount(S);
//C.erase(unique(C.begin(),C.end()),C.end());

int C[3];

int main(){
    string S;
    cin>>S;
    int N=(int)S.size();
    for(int i=0;i<(int)S.size();i++){
        C[S[i]-'a']++;
    }
    sort(C,C+3,greater<int>() );

    if(C[0]-C[2]>1){
        cout<<"NO"<<endl;
    }else cout<<"YES"<<endl;
}


Measured memory_bytes: 512
#!/usr/bin/env python3
import sys
from collections import Counter
INF = float("inf")


def cmb(n, r):
    r = min(r, n-r)
    if r == 0:
        return 1
    if r == 1:
        return n

    numer = [n - r + k + 1 for k in range(r)]
    denom = [k + 1 for k in range(r)]

    for p in range(2, r+1):
        pivot = denom[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1, r, p):
                numer[k - offset] /= pivot
                denom[k] /= pivot

    result = 1
    for k in range(r):
        if numer[k] > 1:
            result *= int(numer[k])

    return result


def solve(N: int, s: "List[str]"):
    for i in range(N):
        buf = list(s[i])
        buf.sort()
        s[i] = "".join(buf)
    s.sort()
    # print(s, sep="\n")
    c = Counter(s)
    # print(c)
    tot = 0
    for k in c:
        if c[k] >= 2:
            tot += cmb(c[k], 2)
    print(tot)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    s = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, s)


if __name__ == '__main__':
    main()


Measured memory_bytes: 19840
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <math.h>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#define PI 3.14159265359
typedef long long ll;
const int MOD = 1e9+7;
const ll LLINF = 1e18;
using namespace std;

ll llmax(ll x, ll y){
	if (x > y) return x;
	return y;
}

int main(){
	int n, k;
	cin >> n >> k;
	vector<ll> p(n+1), c(n+1);
	for (int i = 1; i <= n; i++) cin >> p[i];
	for (int i = 1; i <= n; i++) cin >> c[i];

	ll ans = -LLINF;
	for (int i = 1; i <= n; i++){
		int now = i;
		ll loopsum = 0, loopnum = 0;
		while (1){
			loopnum++;
			now = p[now];
			loopsum += c[now];
			if (now == i) break;
		}

		ll temp = 0, coun = 0;
		while (1){
			coun++;
			now = p[now];
			temp += c[now];
			if (coun > k) break;
			ll tempans = temp + llmax(0, loopsum) * ((k - coun)/loopnum);
			ans = llmax(ans, tempans);
			if (now == i) break;
		}

	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 3728
s = input()

#sが2文字以下の場合は要素数
if len(s)<=2:
    print(len(set(list(s))));exit()

#dp[i]はsをi-1文字目まで見た時の分割の最大数
dp=[0]*(len(s)+1)

dp[0]=0
dp[1]=1
dp[2]=(len(set(list(s[:2]))))

#4文字目からスタート
for i in range(3,1+len(s)):
    if s[i-1]!=s[i-2]:
        dp[i]=dp[i-1]+1
    else:
        dp[i]=dp[i-3]+2
print(dp[-1])


Measured memory_bytes: 11240