akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>

#define rep(i,n) for(int i = 0; i < (n); i++)
#define ll long long

using namespace std;

int main(){
  ll n,c;cin>>n>>c;
  ll dists[n],cals[n];
  ll n_cals[n], r_cals[n], n_cal_uppers[n], r_cal_uppers[n];
  ll result=0;
  n_cal_uppers[0]=-1*(1LL<<50), r_cal_uppers[0]=-1*(1LL<<50);
  rep(i,n){
    cin>>dists[i]>>cals[i];
  }

  n_cals[0]=cals[0];
  r_cals[0]=cals[n-1];
  rep(i,n-1){
    n_cals[i+1]=n_cals[i]+cals[i+1];
    r_cals[i+1]=r_cals[i]+cals[n-1-(i+1)];
  }
  rep(i,n){
    n_cals[i]-=dists[i];
    r_cals[i]-=(c-dists[n-1-i]);
  }

  n_cal_uppers[0]=max(0LL, n_cals[0]);
  r_cal_uppers[0]=max(0LL, r_cals[0]);
  rep(i,n-1){
    n_cal_uppers[i+1]=max(n_cal_uppers[i], n_cals[i+1]);
    r_cal_uppers[i+1]=max(r_cal_uppers[i], r_cals[i+1]);
  }

  rep(i,n){
    ll current_cal = max(n_cals[i], r_cals[i]);
    result = max(result, current_cal);
  }

  rep(i,n-1){
    ll current_cal = n_cals[i]+r_cal_uppers[n-1-i-1]-dists[i];
    ll reverse_cal = r_cals[i]+n_cal_uppers[n-1-i-1]-(c-dists[n-1-i]);

    ll tmp_cal = max(current_cal, reverse_cal);
    result = max(result, tmp_cal);
  }

  cout<<result<<endl;

//  rep(i,n)cout<<n_cals[i]<<' ';
//cout<<endl;
//  rep(i,n)cout<<n_cal_uppers[i]<<' ';
//cout<<endl;

//  rep(i,n)cout<<r_cals[i]<<' ';
//cout<<endl;
//  rep(i,n)cout<<r_cal_uppers[i]<<' ';

  return 0;
}

Measured memory_bytes: 4992
#!/usr/bin/ruby --

#2007 Domestic A
def judge(n)
  ma=0
  mi=1000
  s=0
  n.times do |i|
    x=gets.to_i
    if(x<mi) then mi=x end
    if(x>ma) then ma=x end
    s+=x
  end
  puts (s-ma-mi)/(n-2)
end

while(true)
  n=gets.to_i
  if(n==0) then break end
  judge(n)
end

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

#define jaldi ios_base::sync_with_stdio(false)
#define si(x) scanf("%d",&x)
#define sl(x) scanf("%ld",&x)
#define sll(x) scanf("%lld",&x)
#define sc(x) scanf("%c",&x)
#define ss(x) scanf("%s",x)
#define pi(x) printf("%d",x)
#define pl(x) printf("%ld",x)
#define pll(x) printf("%lld",x)
#define pc(x) printf("%c",x)
#define ps(x) printf("%s",x)
#define vi vector<int> 
#define vl vector<long> 
#define vll vector<long long>
#define vc vector<char>  
#define vs vector<string>
#define vvi vector<vector<int>> 
#define vvll vector<vector<long long>> 
#define F first
#define S second
#define ll long long
#define pb push_back
#define PI 3.1415926535897932384626
#define precision(x) cout<<fixed<<setprecision(x) 
#define all(x) x.begin(),x.end()
#define mod 1000000007

int x_d[8] = {-1,1,0,0,-1,-1,1,1};
int y_d[8] = {0,0,-1,1,-1,1,-1,1};

ll power(ll b,ll e)
{
    if(b==0)
        return 0;
    
    ll r=1;
    while(e>0)
    {
        if(e%2)
            r=(r*b)%mod;
        b=(b*b)%mod;
        e/=2;
    }
    return r;
}
ll root(ll a,vll &head)
{
    while(a!=head[a])
    {
        head[a]=head[head[a]];
        a=head[a];
    }
    return a;
}
void merge(ll a,ll b,vll &head, vll &size)
{
    ll p_a = root(a,head);
    ll p_b = root(b,head);
    if(p_a==p_b)
        return;
    
    if(size[p_a]>size[p_b])
    {
        size[p_a]+=size[p_b];
        head[p_b]=head[p_a];
    }
    else
    {
        size[p_b]+=size[p_a];
        head[p_a]=head[p_b];
    }
    
}

int main()
{
    jaldi;
    precision(20);
    ll i,j;
    ll t;
    t=1;
    // cin>>t;
    while(t--)
    {
        ll x,n;
        cin>>n;
        ll ans=1;
        vll A;
        for(i=0;i<n;i++)
        {
            cin>>x;
            A.pb(x);
            
        }
        sort(all(A));
        // cout<<A[0]<<" ";
        if(A[0]==0)
            cout<<0;
        else
        {
            for(i=0;i<n;i++)
            {
                if((ans>=1000000001 && A[i]>=1000000000) || (ans>=1000000000 && A[i]>=1000000001))
                {
                    ans=-1;
                    break;
                }
                ans=ans*A[i];
                
                if(ans>=1000000000000000001)
                {
                    ans=-1;
                    break;
                }
                else if(ans<0)
                {
                    ans=-1;
                    break;
                }
            }
            cout<<ans;
        }
    }
    return 0;
}

Measured memory_bytes: 4348
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define sz(x) (int)x.size()
#define int long long
typedef pair<int,int>pii;
const int mxN=55,M=1e9+7;
int n,v[mxN];
int ans;
// LONG LONG CASE
int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            ans+=v[i]*v[j];
        }
    }
    cout<<ans;
}

Measured memory_bytes: 3608
fn get_line() -> String {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).unwrap();
    line.trim().to_string()
}

fn main() {
    let s = get_line().chars().collect::<Vec<char>>();
    let t = get_line().chars().collect::<Vec<char>>();

    if &s[..] == &t[..t.len() - 1] {
        println!("Yes");
    } else {
        println!("No");
    }
}


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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);--i)
#define RREP(i,n) RFOR(i,n,0)

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int INT_INF = 2147483647;
const long long LL_INF = 1LL<<60;
const long long MOD = 1000000007;

#define CLR(a) memset((a), 0 ,sizeof(a))

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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

int main(void){
    int N; cin >> N;
    string S; cin >> S;
    char c = S[0];
    int ans = 1;
    REP(i,N-1){
        if(S[i+1] == c) continue;
        ans++;
        c = S[i+1];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 512
import sys
table = [0] * 2001
for i in xrange(1001):
    for ii in xrange(1001):
        table[i+ii] += 1
for line in sys.stdin.readlines():
    count = 0
    n = int(line.strip())
    for i in xrange(2001 if n+1 > 2001 else n+1):
        if not n-i > 2000:
            count += table[n-i] * table[i]
    print count
        

Measured memory_bytes: 4256
#include <iostream>
#include <algorithm>
using namespace std;
int a[3],m;
void f()
{
    int s=0,sum=0;
    for(int i=0; i<3; i++)
        if((m-a[i])%2!=0)s+=1;
    for(int i=0; i<3; i++)
        sum+=(m-a[i])/2;
    if(s==0)
        cout<<sum;
    else if(s==1)
        cout<<sum+2;
    else if(s==2)
        cout<<sum+1;
    else if(s==3)
        cout<<sum+3;
}
int main()
{
    cin>>a[0]>>a[1]>>a[2];
    m=a[0];
    for(int i=1; i<3; i++)
        if(a[i]>m)m=a[i];
    f();
    return 0;
}


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

template<int MAX>
struct Combination {
    vector<long long> _inv, _fac, _ifac;
    const long long MOD;
    Combination(long long mod) : _inv(MAX+1), _fac(MAX+1), _ifac(MAX+1), MOD(mod) { init(); }
    inline void init() { init_inv(), init_fac(); }

    inline void init_inv() {
        _inv[0] = 0;
        for (int i = 1; i <= MAX; i++) {
            if (i == 1) _inv[i] = 1;
            else {
                _inv[i] = (MOD - (MOD / i) * _inv[MOD % i]) % MOD;
                if (_inv[i] < 0) _inv[i] += MOD;
            }
        }
    }
    inline void init_fac() {
        _fac[0] = _ifac[0] = 1;
        for (int i = 1; i <= MAX; i++) {
            _fac[i] = _fac[i-1] * i % MOD;
            _ifac[i] = _ifac[i-1] * _inv[i] % MOD;
        }
    }

    inline long long modpow(long long n, long long r) {
        n %= MOD, r %= (MOD-1);
        if (!n) return 0;
        long long ret = 1; long long tmp = n;
        while (r != 0) {
            if (r % 2) ret *= tmp;
            tmp *= tmp; tmp %= MOD; ret %= MOD;
            r /= 2;
        }
        return ret;
    }
    inline long long invb(int i) const { return (i <= MAX) ? _inv[i] : this->modpow(i, MOD-2); }
    inline long long inv(int i) const { return _inv[i]; }
    inline long long fac(int i) const { return _fac[i]; }
    inline long long ifac(int i) const { return _ifac[i]; }

    long long operator()(int n, int r) const {
        if (n < r) return 0;
        return fac(n) * ifac(r) % MOD * ifac(n-r) % MOD;
    }
};

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int K; string S;
    cin >> K >> S;
    int N = S.size();
    int M = N + K;
    Combination<4001000> C(mod);
    long long Ans = C.modpow(26, M);
    for (int i = 0; i < N; i++) {
        long long tmp = C(M, i) * C.modpow(25, M-i) % mod;
        Ans += mod - tmp;
    }
    cout << Ans % mod << "\n";
    return 0;
}

Measured memory_bytes: 98224
#include <algorithm>
#include <iostream>

using namespace std;
using ll = long long;
using ld = long double;

#define ALL(x) begin(x), end(x)
#define REP(i, n) for (size_t i = 0, i##_len = (n); i < i##_len; ++i)

const string YES = "Yes";
const string NO = "No";

void solve(string S) {
  sort(ALL(S));
  bool pred = S == "abc";
  cout << (pred ? YES : NO) << endl;
}

int main() {
  string S;
  cin >> S;
  solve(S);
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF (int)1e9
#define endl "\n"
#define ll long long
#define ull unsigned long long

using namespace std;

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

    string a;
    cin >> a;

    a[k - 1] -= 'A';
    a[k - 1] += 'a';
    cout << a << endl;
}

Measured memory_bytes: 256
n,k = map(int,input().split())
s = input()
h = 0
if s[0] == 'R':
    if s[1] == 'R':
        h = h+1

if s[n-1] == 'L':
    if s[n-2] == 'L':
        h = h+1
        
for i in range(1,n-1):
    if s[i] == 'R':
        if s[i+1] == 'R':
            h = h+1
    else:
        if s[i-1] == 'L':
            h = h+1

if (h + 2*k) >= n:
    print(n-1)
else:
    print(h + 2*k)

Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long k;
    double x, d;
    cin >> x >> k >> d;
    x = abs(x);
    long long dm;
    if(x>=d*k) dm = x - d*k;
    else{
        long long a;
        a = floor(x/d);
        if(k%2 == a%2){
            dm = abs(x-a*d);
        }else{
            dm = abs(x-(a+1)*d);
        }
    }
    cout << dm << endl;
    return 0;
}

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

const static ll MOD = (1e+9)+7;

bool lessR(const P&a,const P&b){
    return a.second < b.second;
}

int main(){
    int n;cin>>n;
    vector<P> lst(n);
    rep(i,n){
        int x,l;cin>>x>>l;
        lst[i] = make_pair(x-l,x+l);
    }
    sort(lst.begin(),lst.end(),lessR);
    int ans = 1;
    int before_R = lst[0].second;
    rep1(i,n-1){
        if(before_R <= lst[i].first){
            ans++;
            before_R = lst[i].second;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
using namespace std;
int main()
{
	int a, b;
	int c = 0;
	cin >> a;
	cin >> b;
	cin >> c;

	int i = 0;
	for (i = 0; i < 10; i++) {
		c = a * c - b;
		cout << c;
		cout << endl;
	}


	return 0;
}


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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    long int W, H, x, y;
    cin >> W >> H >> x >> y;

    cout << fixed << setprecision(6) << ((double)W * H / 2.0) << " ";
    if (W == x * 2 && H == y * 2) {
        cout << 1 << endl;
    } else {
        cout << 0 << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
#define mypw(x) (x)*(x)
int main()
{
    int n, p = 0;
    int ans[2] = {};
    int x[100] = {};
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> x[i];
        p += x[i];
    }
    p /= n;
    for(int i = 0; i < n; i++) {
        ans[0] += mypw(x[i] - p);
        ans[1] += mypw(x[i] - p - 1);
    }
    cout << (ans[0] < ans[1] ? ans[0] : ans[1]) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long n, i, j, ans=0, pro, tas;
    cin >> n;
    vector<long long> a(n), rui(n+1);
    rui.at(0)=0;
    for(i=0;i<n;i++){
        cin >> a.at(i);
        rui.at(i+1)=rui.at(i)+a.at(i);
        rui.at(i+1);
        
    }
    for(i=0;i<n-1;i++){
        tas = (rui.at(n)-rui.at(i+1));
        tas%=1000000007;
        if(tas<0) tas+=1000000007;
        pro=(a.at(i)%1000000007)*tas;
        pro%=1000000007;
        ans+=pro;
        ans%=1000000007;
    }

    cout << ans <<endl;
}

Measured memory_bytes: 6368
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int mx=101;
char c[mx];int len;
int fun(){
	len=strlen(c);
	while(len>=3){
		cout<<c[0]<<len-2<<c[len-1];
		break;
	}
}
int main(){
	cin>>c;
	fun();
	return 0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10000000)

V = 100005
N = int(input())

lines = [[] for _ in range(V * 2)]
visited = [False] * V * 2

count = []
def dfs(v):
	global count
	if visited[v]:
		return
	visited[v] = True
	count[v // V] += 1
	for u in lines[v]:
		dfs(u)


for i in range(N):
	x, y = [int(x) for x in input().split()]
	y += V
	lines[x].append(y)
	lines[y].append(x)

ans = 0
for i in range(V * 2):
	if visited[i]:
		continue
	count = [0, 0]
	dfs(i)
	ans += count[0] * count[1]

ans -= N
print(ans)

Measured memory_bytes: 85024
import java.util.Scanner;

public class Main { 
    public static void main(String[] args) {
    	
    	Scanner sc = new Scanner(System.in);
        int i, j, k, l;
        int N = sc.nextInt();
        int A[] = new int[N];
        
        for(i = 0; i < N; i++){
            j = sc.nextInt();
            A[i] =j;
        }
 
        for(i = 1; i <= N - 1; i++){
            for(k = 0; k < N; k++){
                System.out.print(A[k]);
                
                if(k != N - 1) System.out.print(" ");
            }
            
            System.out.println();
            l = A[i];
            j = i - 1;
            while(j >= 0 && A[j] > l){
                A[j + 1] = A[j];
                j--;
            }
            A[j + 1] = l;   
        }
        for(k = 0; k < N; k++){
            System.out.print(A[k]);
            if( k != N - 1) System.out.print(" ");
        }
        System.out.println();
    }
}



Measured memory_bytes: 33956
#include <iostream>

using namespace std;

int main(){
    int W,H,N;
    cin>>W>>H>>N;
    int x[N],y[N],a[N];
    for(int i=0;i<N;i++){
        cin>>x[i];
        cin>>y[i];
        cin>>a[i];
    }
    int X[W] = {0};
    int Y[H] = {0};
    for(int i=0;i<N;i++){
        if(a[i]==1){
            for(int j=0;j<x[i];j++){
                X[j] = 1;
            }
        }else if(a[i]==2){
            for(int j=x[i];j<W;j++){
                X[j] = 1;
            }
        }else if(a[i]==3){
            for(int j=0;j<y[i];j++){
                Y[j] = 1;
            }
        }else{
            for(int j=y[i];j<H;j++){
                Y[j] = 1;
            }
        }
    }
    int xcounter = 0;
    int ycounter = 0;
    for(int i=0;i<W;i++){
        if (X[i] == 0){
            xcounter++;
        }   
    }
    for(int i=0;i<H;i++){
        if (Y[i] == 0){
            ycounter++;
        }
    }
    cout<<xcounter*ycounter<<endl;
}

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

int main(void){
    int a, b;
    string s;
    cin >> a >> b >> s;
    for(int i=0;i<a;++i){
        if(s[i]=='-'){
            cout << "No" << endl;
            return 0;
        }
    }
    if(s[a]!='-'){
        cout << "No" << endl;
        return 0;
    }
    for(int i=0;i<b;++i){
        if(s[a+1+i]=='-'){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll> 
typedef pair<ll,ll> P;
#define rep(i,n) for(ll (i)=0; i<(n); ++(i))
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll h,w,x=0,y=0,ans=0,ans_=0;cin>>h>>w;
  string s;
  vector<P> start;
  vector<char> v(w,' ');vector<vector<char>> vv(h,v);
  lvector z(w+1,0),z_(h+1,0);vector<lvector> L(h,z),R(h,z),U(w,z_),D(w,z_);
  rep(i,h) {
    cin>>s;
    rep(j,w) {vv[i][j]=s[j]; if(s[j]=='.') start.push_back(P(i,j));}
  }
  rep(i,h) {
    rep(j,w) {
      if(vv[i][w-1-j]=='.') L[i][w-1-j]=L[i][w-j]+1;
      if(vv[i][j]=='.') R[i][j+1]=R[i][j]+1;
    }
  }
  rep(i,w) {
    rep(j,h) {
      if(vv[h-1-j][i]=='.') U[i][h-1-j]=U[i][h-j]+1;
      if(vv[j][i]=='.') D[i][j+1]=D[i][j]+1;
    }
  }
  for(auto itr:start) {
    x=itr.first,y=itr.second;
    ans_=L[x][y]+R[x][y+1]+U[y][x]+D[y][x+1]-3;
    if(ans_>ans) ans=ans_;
  }
  print(ans);
  return 0;
}


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

using ll =int64_t;
const ll MOD=1e9+7;
vector<vector<ll>>dp(1e5+10,vector<ll>(3,0));
int main(){
  ll N;
  cin>>N;
  for(ll i=0;i<N;i++){
    ll a,b,c;
    cin>>a>>b>>c;
    dp[i+1][0]=max(dp[i][1],dp[i][2])+a;
    dp[i+1][1]=max(dp[i][2],dp[i][0])+b;
    dp[i+1][2]=max(dp[i][0],dp[i][1])+c;
  }
  cout<<max(dp[N][0],max(dp[N][1],dp[N][2]))<<endl;
  return 0;

}

Measured memory_bytes: 5760
def main():
    SHOP_NUM = int(input())
    open_info = [input().split() for _ in range(SHOP_NUM)]
    profit = [list(map(int, input().split())) for _ in range(SHOP_NUM)]
    answer = -float("inf")
    for i in range(1, 1024):
        open = str(format(i, '10b'))
        now_profit = 0
        for shop in range(SHOP_NUM):
            tmp = 0
            for j in range(10):
                if open[j] == "1" and open_info[shop][j] == "1":
                    tmp += 1
            now_profit += profit[shop][tmp]
        answer = max(answer, now_profit)
    print(answer)


if __name__ == '__main__':
    main()

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

using namespace std;

#define DIM 1000009
#define INF ((long long)1e18+9ll)
#define pairll pair<long long,long long>
#define fi first
#define se second
#define ld long double
#define amen exit(0)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl '\n'
#define y1 trymax_lox
#define y2 sijgkvdfbo
#define eps 1000000

long long i,j,k,l,n,m;

int main(){

   // freopen("boards.in","r",stdin);
   // freopen("boards.out","w",stdout);
    fast;

    cin>>n>>m;

    if(n>m)swap(n,m);

    for(i=1;i<=m;i++)cout<<n;
    cout<<endl;

    amen;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.stream.IntStream;

/**
 * 解説通りに実装したソースコード
 * 
 * https://atcoder.jp/contests/abc164/submissions/12384200 にも参考
 */
public class Main {

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int n = scanner.nextInt(), m = scanner.nextInt();
			int s = scanner.nextInt();
			@SuppressWarnings("unchecked")
			List<Path>[] paths = new List[n];
			IntStream.range(0, n).forEach(i -> paths[i] = new ArrayList<>());
			int[] a = new int[m];
			IntStream.range(0, m).forEach(i -> {
				int from = scanner.nextInt() - 1;
				int to = scanner.nextInt() - 1;
				a[i] = scanner.nextInt();
				long b = scanner.nextLong();
				paths[from].add(new Path(from, to, a[i], b));
				paths[to].add(new Path(to, from, a[i], b));
			});
			int[] c = new int[n], d = new int[n];
			IntStream.range(0, n).forEach(i -> {
				c[i] = scanner.nextInt();
				d[i] = scanner.nextInt();
			});
			final int maxS = Arrays.stream(a).max().getAsInt() * (n - 1);
			long[][] times = new long[n][maxS + 1];
			IntStream.range(0, n).forEach(i -> Arrays.fill(times[i], Long.MAX_VALUE));
			Queue<State> queue = new PriorityQueue<>();
			queue.add(new State(0, 0, s));
			while (!queue.isEmpty()) {
				State state = queue.poll();
				int nowS = (int) Math.min(state.s, maxS);
				if (times[state.node][nowS] > state.time) {
					times[state.node][nowS] = state.time;
					if (state.s < maxS) {
						queue.add(new State(state.node, state.time + d[state.node], state.s + c[state.node]));
					}
					for (Path path : paths[state.node]) {
						long nextTime = state.time + path.time;
						long nextS = state.s - path.cost;
						if (nextS >= 0) {
							queue.add(new State(path.to, nextTime, nextS));
						}
					}
				}
			}
			IntStream.range(1, n).mapToLong(i -> Arrays.stream(times[i]).min().getAsLong())
					.forEach(System.out::println);
		}
	}

	/**
	 * ノード間の一つのパスを表すクラス
	 */
	private static class Path {
		/** 開始ノード */
		int from;
		/** 終了ノード */
		int to;
		/** 移動コスト */
		int cost;
		/** 移動時間 */
		long time;

		/**
		 * コンストラクタ
		 * 
		 * @param from 開始ノード
		 * @param to   終了ノード
		 * @param cost 移動コスト
		 * @param time 移動時間
		 */
		Path(int from, int to, int cost, long time) {
			super();
			this.from = from;
			this.to = to;
			this.cost = cost;
			this.time = time;
		}
	}

	/**
	 * 状態を表すクラス
	 */
	private static class State implements Comparable<State> {
		/** 現在の所在ノード */
		int node;
		/** 現在までかかった時間 */
		long time;
		/** 所持金 */
		long s;

		/**
		 * コンストラクタ
		 * 
		 * @param node 現在の所在ノード
		 * @param time 現在までかかった時間
		 * @param s    所持金
		 */
		State(int node, long time, long s) {
			super();
			this.node = node;
			this.time = time;
			this.s = s;
		}

		/**
		 * 比較
		 * 
		 * @param state 比較対象
		 * @return 比較結果
		 */
		@Override
		public int compareTo(State state) {
			return Long.compare(this.s, state.s);
		}
	}
}


Measured memory_bytes: 62056
#include<cstdio>
#include<array>
#include<vector>
#include<stack>
using namespace std;
const int MAX_V=101;
array<int,MAX_V> open{0};
array<int,MAX_V> close{0};
array<vector<int>,MAX_V> edge;
int t=0;

void dfs(int f){
  open[f]=++t;
  for(int a:edge[f]){
    if(open[a]==0){
      dfs(a);
    }
  }
  close[f]=++t;
}

int main(){
  int n;scanf("%d",&n);
  for(int i=0;i<n;i++){
    int u;scanf("%d",&u);
    int k;scanf("%d",&k);
    for(int j=0;j<k;j++){
      int v;scanf("%d",&v);
      edge[u].push_back(v);
    }
  }
  for(int i=0;i<n;i++)
    if(open[i+1]==0)
      dfs(i+1);
  for(int i=0;i<n;i++){
    printf("%d %d %d\n",i+1,open[i+1],close[i+1]);
  }
}

Measured memory_bytes: 1036
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int cm = 1 << 15;
char cn[cm], * ci = cn, ct;
inline int getint() {
	int A = 0;
	while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

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

	fread_unlocked(cn, 1, cm, stdin);
	int N = getint(), K = getint(), Q = getint();
	ll A[2002];
	int LR[2002];
	rep1(i, N) A[i] = ((ll)getint() << 16) + i;
	rep(i, N + 2) LR[i] = -1;

	priority_queue<int> q;
	priority_queue<int, vector<int>, greater<int>> q2[2002];
	auto q3 = q2;
	int kotae = 1e9;
	int saishou = 2e9;
	sort(A + 1, A + N + 1);
	const int m = (1 << 16) - 1;

	for (int i = N; i >= 1; i--) {
		int a = A[i] >> 16;
		int k = A[i] & m;

		int l = (LR[k - 1] == -1) ? k : LR[k - 1];
		int r = (LR[k + 1] == -1) ? k : LR[k + 1];
		LR[l] = r;
		LR[r] = l;

		if (k + k > l + r) swap(q3[l], q3[k + 1]);
		while (q3[k + 1].size()) {
			int tmp = q3[k + 1].top();
			q3[l].push(tmp);
			q3[k + 1].pop();
		}
		q3[l].push(a);
		while (q3[l].size() >= K) {
			int tmp = q3[l].top();
			q.push(tmp);
			q3[l].pop();
		}
		while (q.size() >= Q) {
			int tmp = q.top();
			chmin(saishou, tmp);
			q.pop();
		}
		chmin(kotae, saishou - a);
	}

	printf("%d", kotae);

	Would you please return 0;
}

Measured memory_bytes: 10880
#include <iostream>
#include <vector> 
#include <set>
#include <map>
#include <math.h>

using namespace std;

#define loop(i,a,b) for(int i = a; i<b; i++)
#define square(a) (a)*(a)

typedef long long ll;
typedef string str;


int main ()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int a, b;
	cin >> a >>b;
	
	
	
	int sum = 0;
	loop(i,0,b)
	{
		int c;
		cin >> c;
		sum += c;
	} 
	
	if (a >= sum)
	cout << a - sum;
	else
	cout << -1;
}


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

#define N 300

int n;
int a[N][N];

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

	int flag = 0;
	long long ans = 0;
	for( int i = 0; i < n; i++ ) {
		for( int j = i + 1; j < n; j++ ) {
			if( i == j ) {
				continue;
			}
			int flag2 = 0;
			for( int k = 0; k < n; k++ ) {
				if( k == i || k == j ) {
					continue;
				}
				if( a[i][j] > a[i][k] + a[k][j] ) {
					flag = 1;
					break;
				}
				if( a[i][j] == a[i][k] + a[k][j] ) {
					flag2 = 1;
				}
			}
			if( flag ) {
				break;
			}
			if( flag2 == 0 ) {
				ans += a[i][j];
			}
		}
		if( flag ) {
			break;
		}
	}
	if( flag ) {
		ans = -1;
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 640
N,K = map(int,input().split())
tmp_A = [0]*N
ans = 0

for i in range(K):
    d = int(input())
    A = list(map(int,input().split()))
    for j in range(d):
        tmp_A[A[j]-1] += 1
        
for i in range(N):
    if tmp_A[i] == 0:
        ans += 1
        
print(ans)

Measured memory_bytes: 9184
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, l, r) for (int i = (l); i < (r); i++)
#include <bits/stdc++.h>
//~ #include <atcoder/all>
using namespace std;
using ll = long long;
//~ using P = pair<int, int>;

template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
//~ int A = (1<<2) | (1<<3) | (1<<5) | (1<<7);
//~ for (int bit=A; ; bit=(bit-1)&A){
//~ if (!bit) break;
//~ }
int next_combination(int sub)
{
    int x = sub & -sub, y = sub + x;
    return (((sub & ~y) / x) >> 1) | y;
}
//~ int n=5;
//~ int k=3; // nCkの組み合わせ、ただしk=0には対応してない
//~ int bit=(1<<k)-1; // 1000 -> 0111
//~ for(; bit < (1<<n); bit=nex_combination(bit){
//~ }
bool isPrime(int a)
{
    if (a == 2)
        return true;
    if (a <= 1 || a % 2 == 0)
        return false;

    for (int i = 3; i * i <= a; i += 2)
    {
        if (a % i == 0)
            return false;
    }
    return true;
}
//~ vector<int> a = {1, 14, 32, 51, 51, 51, 243, 419, 750, 910};
vector<int> a;
// index が条件を満たすかどうか
bool isOK(int index, int key)
{
    if (a[index] >= key)
        return true;
    else
        return false;
}
// 汎用的な二分探索のテンプレ
int binary_search(int key)
{
    int ng = -1;            //「index = 0」が条件を満たすこともあるので、初期値は -1
    int ok = (int)a.size(); // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()

    /* ok と ng のどちらが大きいかわからないことを考慮 */
    while (abs(ok - ng) > 1)
    {
        int mid = (ok + ng) / 2;

        if (isOK(mid, key))
            ok = mid;
        else
            ng = mid;
    }
    return ok;
}

long long modpow(long long a, long long n, long long mod)
{
    long long res = 1;
    while (n > 0)
    {
        if (n & 1)
            res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

//~ int v[100100];
//~ int INF = 1 << 30;
//~ vector<vector<int>> dp(310, vector<int>(310));
//~ ll dp[110][100100];
//~ vector<int> dp(100100, 0));

//~ int seen[110];
//~ int ans[110][2];
//~ ll MOD = 1e9 + 7;

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

    string con;
    con = a + b;

    rep(i, 10000)
    {
        if (i * i == stoi(con))
        {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;

    return 0;
}


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

using namespace std;

using ll = long long;
using ull = unsigned long long;

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

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

  ll ans = 0;

  while (x >= 500) {
    x -= 500;
    ans += 1000;
  }

  while (x >= 5) {
    x -= 5;
    ans += 5;
  }

  cout << ans << "\n";
}

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

#define PB push_back

int main(int argc,char* argv[]){
  int n,k,i,count,x,N;
  bool flag;
  int data[100001];
  vector<int> vec;

  while(cin>>n>>k){
    if(n==0 && k==0) break;

    flag=false;
    for(i=0;i<100001;i++) data[i]=0;
    vec.clear();
    count=0;

    
    for(i=0;i<k;i++){
      cin>>x;
      if(!x) flag=true;
      else data[x]=1;
    }
    

    for(i=1;i<=n;i++){
      if(data[i]==1){
	count++;
      }
      else if(i>1 && data[i]==0 && data[i-1]==0){
	vec.PB(0);
      }
      else if(data[i]==0){
	vec.PB(count);
	count=0;
      }
    }
    vec.PB(count);
    
    //ワイルドカードがある場合の処理
    if(flag){
      N=(int)vec.size();
      for(i=0;i<N-1;i++) vec.PB(vec[i]+vec[i+1]+1);
    }

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

    cout<<vec.back()<<endl;
  }
  return 0;
}

Measured memory_bytes: 1864
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> vvl;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvec;
typedef vector<vector<bool>> vveb;
typedef vector<vector<string>> vves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pb push_back
#define pp pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
typedef long long int64;
//const int64 INF = 1LL << 58;
#define dame { puts("-1"); return 0;}
#define YES { cout << "YES" << endl; return 0; }
#define NO { cout << "NO" << endl; return 0; }
#define Yes { cout << "Yes" << endl; return 0; }
#define No { cout << "No" << endl; return 0; }
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 (a>b) { a=b; return 1; } return 0; }
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};



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

	int n;
	cin >> n;

	vector<vi> a(26,vi(15,0));
	rep(i,26){
		rep(j,15){
			a[i][j] = 4*i + 7*j;
			if(a[i][j]==n) Yes;
		}
	}

	No;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<stack>
#include<vector>
#include<queue>
#include<set>
#include<algorithm>
const int N = 1e9;
using namespace std;
#define INF 0x3f3f3f3f
#define mod 1000000009
#define e  2.718281828459045
#define PI acos(-1)
#define lowbit(x) (x&(-x))
#define read(x) scanf("%d",&x)
#define put(x) printf("%d\n",x)
#define memset(x,y) memset(x,y,sizeof(x))
#define ll long long

int main(){

	long long n,m,k;
	cin>>n>>m>>k;
	if(k<=n) cout<<n-k<<" "<<m<<endl;
	else if(k<=m+n) cout<<0<<" "<<m+n-k<<endl;
	else cout<<"0 0"<<endl;
	return 0;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

func main() {
	r := bufio.NewReader(os.Stdin)
	var n, k int
	fmt.Fscan(r, &n, &k)
	a := make([]int, n)
	var max int
	for i := 0; i < n; i++ {
		fmt.Fscan(r, &a[i])
		if max < a[i] {
			max = a[i]
		}
	}

	ans := sort.Search(max, func(x int) bool {
		if x == 0 {
			return false
		}
		var cnt int
		for i := 0; i < n; i++ {
			if a[i] <= x {
				continue
			}
			cnt += a[i] / x
		}
		return cnt <= k
	})
	fmt.Println(ans)
}


Measured memory_bytes: 5988
#include<iostream>
#include<set>
#include<algorithm>
#include<vector>
#include<math.h>
#include<map>
#include<queue>
#include <iomanip>
#include<string.h>
using namespace std;
const int  N = 105;
vector<int>result[N];



int main()
{
    int L,R,d;
    cin>>L>>R>>d;
    int count  =0;
    int temp =0;
    int i =1;
    if(d!=1)
    while (temp<=R) {
        if(i*d>=L&&i*d<=R)
            count++;
        temp = i*d;
        i++;
    }
    else
        count = R-L+1;
    cout<<count;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
 
using namespace std;
 
#define INF 1000000007
#define LINF 1000000000000000007
 
typedef long long ll;
typedef pair<ll,ll> P;


string s;

int main(){
	cin >> s;
	
	int ans = INF;
	for(int i = 0; i < 26; i++){
		int cnt = 0, c = 0;
		for(int j = 0; j <= s.size(); j++){
			if(j == s.size()){
				cnt = max(cnt, c);
			}
			if(s[j] == (char)('a'+i)){
				cnt = max(cnt, c);
				c = 0;
				continue;
			}
			c++;
		}
		ans = min(ans, cnt);
	}
	
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 256
s = input()

for bit in range(1 << (3)):
    f = s[0]
    
    for i in range(3):
        # if bit & (1 << i)で、bitにiが含まれているか（フラグが立っているか）を判定してくれるらしい
        if bit & (1 << i):
            f += '+'
        else:
            f += '-'
        f += s[i+1]    
    if eval(f)  == 7:
        f += "=7"
        print(f)
        exit()

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		String a = sc.next();
		String b = sc.next();
		String s = sc.next();
		sc.close();
		System.out.println(s.matches("[0-9]{" + a + "}-[0-9]{" + b + "}") ? "Yes" : "No");
	}
}

Measured memory_bytes: 23764
n,q = map(int,input().split())
p = [0 for _ in range(n)]
time = 0
for i in range(n):
    a,m = input().split()
    p[i] = [a,int(m)]

while len(p) > 0:
    t = p.pop(0)
    if t[1] <= q:
        print(t[0],time + t[1])
        time += t[1]
    else:
        time += q
        t[1] -= q
        p.append(t)


Measured memory_bytes: 13024
#include <bits/stdc++.h>
#define WHOLE(v) (v).begin(), (v).end()
#define REV_WHOLE(v) (v).rbegin(), (v).rend()
using i64 = int64_t;
using namespace std;
template <size_t I, class H, class... T> struct TupleReaderWriter{static tuple<H,T...> r(istream&i){H v;i>>v;return tuple_cat(tuple<H>(v),TupleReaderWriter<sizeof...(T)-1,T...>::r(i));}static void w(ostream&o,tuple<H,T...>&t,string d){TupleReaderWriter<I-1,H,T...>::w(o,t,d);o<<d<<get<I>(t);}};
template <class H, class... T> struct TupleReaderWriter<0,H,T...>{static tuple<H,T...> r(istream&i){H v;i>>v;return tuple<H>(v);}static void w(ostream&o,tuple<H,T...>&t,string d){o<<get<0>(t);}};
template<class T>istream&operator>>(istream&i,vector<T>&v){for(auto&x:v)i>>x;return i;}
template<class T>ostream&operator<<(ostream&o,vector<T>&v){string delim="";for(auto&x:v)o<<delim<<x,delim=" ";return o;}
template <class... T> istream& operator>>(istream&i,tuple<T...>& t) { t = TupleReaderWriter<sizeof...(T), T...>::r(i); return i; }
template <class... T> ostream& operator<<(ostream& o, tuple<T...>& t) { string delim = " "; TupleReaderWriter<sizeof...(T) - 1, T...>::w(o, t, delim); return o; }
template<typename T> using rev_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<typename T> using vector2d = vector<vector<T>>;
void R_YESNO(bool p) { cout << (p ? "YES" : "NO") << endl; }
void R_YesNo(bool p) { cout << (p ? "Yes" : "No") << endl; }
//UnionFind 木
// T (typename) : グラフの頂点を表す型, (int)parent を持つ必要あり
template <typename T>
struct UnionFind {
    vector<T>& u;
    UnionFind(vector<T>& u) : u(u) {
        for (int i = 0; i < u.size(); i++) {
            u[i].parent = i;
        }
    }
    int root(int x) {
        if (x < 0 || u.size() <= x)
            return -1;
        else if (x == u[x].parent)
            return x;
        else
            return u[x].parent = root(u[x].parent);
    }
    bool connect(int a, int b) {
        a = root(a), b = root(b);
        if (a == b || a < 0 || b < 0) return false;
        { /* do something */
        }
        u[b].parent = a;
        return true;
    }
};

struct Node {
    int parent;
};

int main() {
    using P = pair<int, int>;
    int N, K, L;
    cin >> N >> K >> L;
    vector<Node> v0, v1;
    v0 = vector<Node>(N),
    v1 = vector<Node>(N);
    UnionFind<Node> uf0(v0), uf1(v1);
    for(int b = 0; b < 2; b++) {
        for(int i = 0; i < K; i++) {
            int p, q;
            cin >> p >> q;
            p--, q--;
            uf0.connect(p, q);
        }
        swap(v0, v1);
        swap(K, L);
    }
    map<P, int> m;
    for(int i = 0; i < N; i++) {
        m[{uf0.root(i), uf1.root(i)}]++;
    }
    vector<int> ans(N);
    for(int i = 0; i < N; i++) {
        ans[i] = m[{uf0.root(i), uf1.root(i)}];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 14336
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class AtCoderA
{
    static void Main()
    {
        var sc = new Scanner();

        string s = sc.Next();

        long answer = s.Where(c => c == '2').Count();

        Console.WriteLine(answer);
    }

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}


Measured memory_bytes: 26568
#include <bits/stdc++.h>
    #define N 100005
    #define ll long long
    #define For(i,x,y) for(int i=(x);i<=(y);++i)
    #define Rof(i,x,y) for(int i=(x);i>=(y);--i)
    #define Edge(x) for(int i=head[x];i;i=e[i].nxt)
    #define mset(x,y) memset(x,y,sizeof(x))
    #define strL strlen
    #define p_b push_back
    #define mcpy(x,y) memcpy(x,y,sizeof(x))
    #define lson l,mid,(o<<1)
    #define rson mid+1,r,((o<<1)|1)
    #define Ls (t[o].ls)
    #define Rs (t[o].rs)
    #define mod
    #define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
    using namespace std;
    vector<int> g[N];
    int mch[N];
    void dfs(int x,int f){
    	for(auto to:g[x])
    		if(to!=f){
    			dfs(to,x);
    			if(!mch[to]) mch[x]=to,mch[to]=x;
    		}
    	if(!mch[x]){
    		if(mch[f] || f==0){
    			puts("First");
    			exit(0);
    		} 
    		mch[x]=f,mch[f]=x;
    	}
    }
    int main(){
    	int n,u,v;
    	scanf("%d",&n);
    	if(n==1) return puts("First"),0;
    	For(i,1,n-1){
    		scanf("%d%d",&u,&v);
    		g[u].push_back(v),g[v].push_back(u);
    	}
    	dfs(1,0);
    	puts("Second");
    }

Measured memory_bytes: 6144
import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int w = sc.nextInt();
		
		int[] weight = new int[n + 1];
		int[] value = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			weight[i] = sc.nextInt();
			value[i] = sc.nextInt();
		}
		
		long[][] dp = new long[n + 1][w + 1];
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= w; j++) {
				dp[i][j] = dp[i - 1][j];
				if (j - weight[i] >= 0)
					dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - weight[i]] + value[i]);
			}
		}
		
		System.out.println(dp[n][w]);
		
//		for (long[] arr : dp)
//			System.out.println(Arrays.toString(arr));
 		
		sc.close();
	}
}



Measured memory_bytes: 131948
#include <bits/stdc++.h>
using namespace std;
int main() {
	string s;
	string t;
	cin >> s;
	t = s;
	reverse(t.begin(), t.end());
	int ans = 0;
	for(int i = 0; i < s.size(); ++i) {
		ans += s[i] != t[i];
	}
	cout << ans / 2 << '\n';
	return 0;
}


Measured memory_bytes: 256
N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

tot = 0
for i in range(N):
    if A[i] <= B[i]:
        tot += A[i]
        B[i] -= A[i]
        A[i] = 0
    else:
        tot += B[i]
        B[i] = 0
        A[i] = A[i] - B[i]
    if B[i] >= 0:
        if A[i+1] <= B[i]:
            tot += A[i+1]
            A[i+1] = 0
            B[i] -= A[i+1]
        else:
            A[i+1] -= B[i]
            tot += B[i]
            B[i] = 0

print(tot)



Measured memory_bytes: 19648
MOD = 10 ** 9 + 7
ONE = '1'.freeze

def nCk(n, k)
  res = 1
  i = k
  j = 1
  while i > 0
    res = res * (n - i + 1)
    res %= MOD
    j *= i
    j %= MOD
    i -= 1
  end
  res *= inv(j)
  res %= MOD
  res
end

def inv(x)
  res = 1
  beki = x
  (MOD - 2).to_s(2).reverse.chars do |digest|
    res = (beki * res) % MOD if digest == ONE
    beki = (beki * beki) % MOD
  end
  res
end

def puts_0
  puts 0
  exit
end

x, y = gets.split.map(&:to_i)
count, mod = (x + y).divmod(3)
puts_0 if mod > 0
right_count = x - count
up_count = y - count
puts_0 if right_count < 0 || up_count < 0
puts nCk(count, right_count)


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

int main() {
  vector<string> s(3);
  rep(i,3) cin >> s[i];

  int cur = 0;
  while (true) {
    string t = s[cur];
    if (t.empty()) {
      cout << char(cur + 'A') << endl;
      return 0;
    }
    s[cur] = t.substr(1,t.size()-1);
    cur = t[0] - 'a';
  }
  return 0;
}

Measured memory_bytes: 3604
#include <iostream>
using namespace std;
int main ()
{
    //input data
    int a, b;

    //stream
    cin >> a >> b;

    int num = b - a;
int higher = 0;

for(int i = 1; i <= num; i++){
higher += i;
}

int ans = higher - b;

cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
program main
    use,intrinsic :: iso_fortran_env
    implicit none
    integer(int32):: a,b

    read*, a,b

    if (a==b) then
        print'(a)', 'Draw'
    else if (a==1) then
        print'(a)', 'Alice'
    else if (b==1) then
        print'(a)', 'Bob'
    else if (a > b) then
        print'(a)', 'Alice'
    else
        print'(a)', 'Bob'
    end if
end program main

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,ini,n) for(int i=ini;i<n;i++)
#define _rep(i,ini,n) for(int i=ini;i>=n;i--)
#define ToEnd(a) a.begin(),a.end()
uint64_t MOD=1000000007;

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

    set<string> setW;
    string ans="Yes",preW;
    rep(n,0,N){
        string w; cin>>w;
        if(setW.count(w)){ans="No"; break;}
        else if(n!=0  && w.at(0)!=preW.at(preW.size()-1)){
            ans="No"; break;
        }

        setW.insert(w);
        preW=w;
    }

    cout<<ans<<endl;
}

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

int main() {
    int h, w;
    cin >> h >> w;
    string bar(w+2, '#'), tmp;
    cout << bar << endl;
    for (int i=0; i<h; i++) {
        cin >> tmp;
        cout << '#' << tmp << '#' << endl;
    }
    cout << bar << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, e) for(int (i) = 0; (i) < (e); ++(i))
#define FOR(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define ALL(c) (c).begin(), (c).end()
#define PRINT(x) cout << (x) << "\n"
using namespace std;
using ll = long long; using pint = pair<int, int>; using pll = pair<ll, ll>;
const long long MOD = 1000000007;

signed main(){
    ll N, K;
    string S;
    cin >> N >> K >> S;
    S[K - 1] = 'a' + (S[K - 1] - 'A');
    PRINT(S);
    return 0;
}

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

int N;
int sum = 0;

void f(string s) {
	if (s != "" && stoll(s) > N) {
		return;
	}

	else if (s == "" || stoll(s) < 357) {
		f(s + "7");
		f(s + "5");
		f(s + "3");
	}
	else if (stol(s) >= 357) {
		if (s.find('3') != string::npos && s.find('5') != string::npos && s.find('7') != string::npos)
			sum++;
		f(s + "7");
		f(s + "5");
		f(s + "3");
	}
}

int main() {
	cin >> N;
	f("");
	cout << sum << endl;
}

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

step=0
for i in range(N):
    if i == 0:
        pass
    else:
        if A[i]-A[i-1]>=0:
            pass
        else:
            step += (A[i-1]-A[i])
            A[i] += (A[i-1]-A[i])
print(step)

Measured memory_bytes: 32240
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<utility>
#include<tuple>
#include<algorithm>
#include<cmath>
using namespace std;

#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;

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

int main(){
  int n;
  cin >> n;
  vector<pair<int,int>> a(n);
  rep(i,n) cin >> a[i].second >> a[i].first;
  sort(a.begin(),a.end());
  vector<vector<int>> dp(n+1, vector<int>(n+1, 1e9+1));
  dp[0][0]=0;
  for(int i=1; i<=n; i++){
    for(int j=0; j<=n; j++){
      chmin(dp[i][j], dp[i-1][j]);
      if(j && dp[i-1][j-1]+a[i-1].second<=a[i-1].first)
        chmin(dp[i][j], dp[i-1][j-1]+a[i-1].second);
    }
  }
  for(int i=n; i>=0; i--){
    if(dp[n][i]!=1e9+1){
      cout << i << endl;
      return 0;
    }
  }
}


Measured memory_bytes: 3164
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,m;
  cin>>n>>m;
  vector<vector<int>> v(m);
  for(int i=0;i<m;i++){
    int p,y;
    cin>>p>>y;
    v.at(i)={p,y,i};
  }
  sort(v.begin(),v.end());
  vector<string> id(m);
  int p=0;
  int c=1;
  string o="000000";
  for(int i=0;i<m;i++){
    if(v.at(i).at(0)==p)
      c++;
    else{
      c=1;
      p=v.at(i).at(0);
    }
    string ps=to_string(p);
    string pc=to_string(c);
    id.at(v.at(i).at(2))=o.substr(0,6-ps.size())+ps+o.substr(0,6-pc.size())+pc;
  }
  for(int i=0;i<m;i++)
    cout<<id.at(i)<<endl;
}

Measured memory_bytes: 13952
def merge(A,left,mid,right):
	L=A[left:mid]+[10**9]
	R=A[mid:right]+[10**9]
	i = 0
	j = 0
	c = 0
	for k in range(left,right):
		c += 1
		if L[i] <= R[j]:
			A[k] = L[i]
			i+=1
		else:
			A[k] = R[j]
			j+=1
	return c

def merge_sort(A,left,right):
	if left+1 < right:
		mid = (left+right) // 2
		cL=merge_sort(A,left,mid)
		cR=merge_sort(A,mid,right)
		return(merge(A,left,mid,right) + cL + cR)
	return 0

c=0
n = int(input())
A = [int(i) for i in input().split()]
c=merge_sort(A,0,n)
print(*A)
print(c)


Measured memory_bytes: 61648
import sys
import numpy as np
from scipy.sparse import*
F = csgraph.floyd_warshall
CSR = csr_matrix
input = sys.stdin.readline

n,m,l = map(int,input().split())
cost = [[0]*n for i in range(n)]
for i in range(m):
  a,b,c = map(int,input().split())
  cost[a-1][b-1] = c
  cost[b-1][a-1] = c  

Cost = F(CSR(cost))
Cost = F(CSR(np.where((0<Cost)&(Cost<=l),1,0)))

q = int(input())
for i in range(q):
  s,t = map(int,input().split())
  print(-1 if np.isinf(Cost[s-1][t-1]) else int(Cost[s-1][t-1])-1)

Measured memory_bytes: 20352