akhauriyash/Code-Regression huggingface dataset:
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <stack>
#include <bitset>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>

#define PI 3.1415926535897932384626433832795
#define inf 0x3f3f3f3f
#define MAXN 100005
using namespace std;
typedef long long ll;
const double EPS=1e-6;

int a[MAXN];
ll ans=-1;
int n;

void sp()
{
	vector<int>v;
	int i=0,j=n-1;
	int flag=0;//0 s 1 b
	while(i<=j)
	{
		if(!flag)
		{
			if(i==0)
				v.push_back(a[i++]);
			else
			{
				if(i<=j)
					v.push_back(a[i++]);
				if(i<=j)
					v.push_back(a[i++]);
			}
			flag=1;
		}else
		{
			if(i<=j)
				v.push_back(a[j--]);
			if(i<=j)
				v.push_back(a[j--]);
			flag=0;
		}			
	}
	
	vector <int>v1,v2;
	if(n&1)
	{
		for(i=1;i<n;i+=2)
		{
			v1.push_back(v[i]);
			v2.push_back(v[i+1]);
		}
		
		int t=v[0];
		v.clear();
		
		for(i=v1.size()-1;i>=0;i--)
			v.push_back(v1[i]);
		v.push_back(t);
		for(i=0;i<v2.size();i++)
			v.push_back(v2[i]);
	}else
	{
		for(i=0;i<n;i+=2)
		{
			v1.push_back(v[i]);
			v2.push_back(v[i+1]);
		}
		
		v.clear();
		
		for(i=v1.size()-1;i>=0;i--)
			v.push_back(v1[i]);
		for(i=0;i<v2.size();i++)
			v.push_back(v2[i]);
	}
	
	ll res=0;	
	for(i=0;i<v.size()-1;i++)
	{
	//	cout<<v[i+1]<<' '<<v[i]<<endl;
		res+=abs(v[i+1]-v[i]);
	}
	ans=max(ans,res);
}

void mp()
{
	vector<int>v;
	int i=0,j=n-1;
	int flag=1;//0 s 1 b
	while(i<=j)
	{
		if(!flag)
		{
			if(i<=j)
				v.push_back(a[i++]);
			if(i<=j)
				v.push_back(a[i++]);
			flag=1;
		}else
		{
			if(j==n-1)
				v.push_back(a[j--]);
			else
			{
				if(i<=j)
					v.push_back(a[j--]);
				if(i<=j)
					v.push_back(a[j--]);
			}
			flag=0;
		}			
	}
	
//	for(i=0;i<n;i++)
//		cout<<v[i]<<' ';
//	cout<<endl;
	
	vector <int>v1,v2;
	if(n&1)
	{
		for(i=1;i<n;i+=2)
		{
			v1.push_back(v[i]);
			v2.push_back(v[i+1]);
		}
		
		int t=v[0];
		v.clear();
		
		for(i=v1.size()-1;i>=0;i--)
			v.push_back(v1[i]);
		v.push_back(t);
		for(i=0;i<v2.size();i++)
			v.push_back(v2[i]);
	}else
	{
		for(i=0;i<n;i+=2)
		{
			v1.push_back(v[i]);
			v2.push_back(v[i+1]);
		}
		
		v.clear();
		
		for(i=v1.size()-1;i>=0;i--)
			v.push_back(v1[i]);
		for(i=0;i<v2.size();i++)
			v.push_back(v2[i]);
	}
	
	ll res=0;	
	for(i=0;i<v.size()-1;i++)
	{
	//	cout<<v[i+1]<<' '<<v[i]<<endl;
		res+=abs(v[i+1]-v[i]);
	}
	ans=max(ans,res);
}

int main()
{
	//ios::sync_with_stdio(false);
	int i,j;
	scanf("%d",&n);
	for(i=0;i<n;i++)
		scanf("%d",&a[i]);
	
	sort(a,a+n);
	
	sp();
	mp();
	printf("%lld",ans);
	return 0;
}


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

#define For(k,i) for(ll i=0;i<k;i++)

using namespace std;
using ll = long long;
using pii = pair<int,int>;

bool compare_f(pii x, pii y) {
  return x.second < y.second;
}

int main() {
    int ans = 0;
    int n;
    cin >> n;

    vector<int> x(n),l(n);
    vector<pii> j(n);
    For(n,i){
        int s,f,ss,ff;
        cin >> ss >> ff;
        s = min(ss + ff,1000000000);
        f = max(ss - ff,0);
        // cout << s << " " << f << "\n";
        j[i] = make_pair(f,s);
    }
    sort(j.begin(), j.end(), compare_f);
    int f = 0;
    For(n,i) {
        if (j[i].first >= f) {
            ++ans;
            f = j[i].second;
        }
    }
    cout << ans;
}


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

typedef long long ll;

int main(){
    ll n, q;
    string s;
    cin >> n >> s >> q;
    for(;q>0;q--){
        ll k, ans = 0, dcnt = 0, mcnt = 0, dmcnt = 0;
        cin >> k;
        for(int i=0;i<n;i++){
            if(s[i] == 'D') dcnt++;
            if(s[i] == 'M'){
                mcnt++;
                dmcnt += dcnt;
            }
            if(s[i] == 'C') ans += dmcnt;

            if(i>=k-1){
                if(s[i-k+1] == 'D'){
                    dcnt--;
                    dmcnt -= mcnt;
                }
                if(s[i-k+1] == 'M') mcnt--;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 1412
#include <stdio.h>

long long dp[2][101][301] = {}; // turn, n put, rest
long long w[100] = {};
long long v[100] = {};

int main() {
  long long N, W, best = 0;
  scanf("%lld %lld", &N, &W);

  for (int i = 0; i < N; i++) {
    scanf("%lld %lld", w + i, v + i);
  }

  for (int i = 0; i < N; i++) {
    int cur = i % 2, prev = (i + 1) % 2;
    for (int j = 0; j < 101; j++) {
      for (int k = 0; k < 301; k++) {
	dp[cur][j][k] = 0;
      }
    }
    
    for (int j = 0; j <= i; j++) {
      for (int k = 0; k <= 300; k++) {
	long long cost = w[0] * j + k;
	if (cost > W) continue;

	int prev_value = dp[prev][j][k];
	// do not use the i-th item
	if (dp[cur][j][k] < prev_value) {
	  dp[cur][j][k] = prev_value;
	}

	// use the i-th item
	cost += w[i];
	if (cost > W) continue;
	long long next_value = prev_value + v[i];
	if (dp[cur][j + 1][k + w[i] - w[0]] < next_value) {
	  dp[cur][j + 1][k + w[i] - w[0]] = next_value;
	}
      }
    }

    if (i == N - 1) {
      for (int j = 0; j < 101; j++) {
	for (int k = 0; k < 301; k++) {
	  if (best < dp[cur][j][k]) {
	    best = dp[cur][j][k];
	  }
	}
      }
    }
  }

  printf("%lld\n", best);
  return 0;
}


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

#define ll long long int
#define vi vector<int>

int main() {

    vector<vector<int>> A(3, vector<int>(3));

    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            cin >> A[i][j];
        }
    }

    int N;
    cin >> N;

    vector<vector<bool>> B(3, vector<bool>(3, false));
    int b;
    for (int x = 0; x < N; ++x) {
        cin >> b;
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (A[i][j] == b) {
                    B[i][j] = true;
                }
            }
        }
    }


    for (int i = 0; i < 3; ++i) {
        if (B[i][0] && B[i][1] && B[i][2]) {
            cout << "Yes" << endl;
            return 0;
        }
        if (B[0][i] && B[1][i] && B[2][i]) {
            cout << "Yes" << endl;
            return 0;
        }
    }

    if (B[0][0] && B[1][1] && B[2][2]) {
        cout << "Yes" << endl;
        return 0;
    }

    if (B[0][2] && B[1][1] && B[2][0]) {
        cout << "Yes" << endl;
        return 0;
    }

    cout << "No" << endl;

    return 0;
}


Measured memory_bytes: 256
import java.util.*;


public class Main {
	static boolean stability = true;
	
	public static int partition(String [] arr, int left, int right) {
		int pivot = Integer.parseInt(arr[right].substring(2));
		int i = left - 1;
		
		
		for(int j = left; j < right; j++) {
			if(Integer.parseInt(arr[j].substring(2)) <= pivot) {
				
				i++;
				
				
				String tempS = arr[j].substring(0, 2);
				int temp = Integer.parseInt(arr[j].substring(2));
				arr[j] = arr[i];
				arr[i] = tempS + temp;		
			}	
		}
		String tempS = arr[i + 1].substring(0, 2);
		int temp = Integer.parseInt(arr[i + 1].substring(2));
		
		
		arr[i + 1] = arr[right];
		arr[right] = tempS + temp;
		return i + 1;
	}
	
	public static void sort(String [] arr, int left, int right) {
		if(left < right) {
			int mid = partition(arr, left, right);
			sort(arr, left, mid - 1);
			sort(arr, mid + 1, right);
		}
	}
public static void main(String [] args) {
		
		Scanner in = new Scanner(System.in);
		
		
		int n = Integer.parseInt(in.nextLine());
		String [] arr = new String [n];
		Map<String, Integer> order = new HashMap<String, Integer>();
		
		for(int i = 0; i < n; i++) {
			String s = in.nextLine();
			arr[i] = s;
			order.put(s, i);
		}
		
		sort(arr, 0, n - 1);
		
		for(int i = 0; i < n - 1; i++) {
			if(Integer.parseInt(arr[i].substring(2)) == Integer.parseInt(arr[i + 1].substring(2)) && 
					order.get(arr[i]) > order.get(arr[i + 1])) {
				stability = false;
			}
		}
		
		if(stability) {
			System.out.println("Stable");
		}
		
		else {
			System.out.println("Not stable");
		}
		
		for(int i = 0; i < n; i++) {
			System.out.println(arr[i]);
			
		}
		
		
}
}



Measured memory_bytes: 222592
#include <stdio.h>

int main(void)
{
  int n[10];
  int i, j,tmp;

  for (i = 0; i < 10; i++){
    scanf("%d", &n[i]);
  }

  for (i = 0; i < 10; i++){
    for (j = i + 1; j < 10; j++){
      if (n[j] > n[i]){
        tmp = n[i];
        n[i] = n[j];
        n[j] = tmp;
      }
    }
  }

  for (i = 0; i < 3; i++){
    printf("%d\n", n[i]);
  }

  return (0);
}

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

int main(){
    string S; cin >> S;
    int ans=0;
    rep(i,S.size()-1){
        if(S[i]==S[i+1] && S[i]=='0'){
            S[i+1]='1';
            ans++;
        }
        else if(S[i]==S[i+1] && S[i]=='1'){
            S[i+1]='0';
            ans++;
        }
    }
    cout << ans;
}



Measured memory_bytes: 512
#include <stdio.h>
long long p, g, k, h;
long long a[3000];
long long b[3000];
long long c[3000];
long long f[3000];
long long rui(long long x, long long y) {
	if (y == 0)return 1;
	if (y == 1)return x;
	if (y == 2)return x * x % p;
	if (y % 2)return (rui(rui(x, y / 2), 2)) * x % p;
	else return rui(rui(x, y / 2), 2);
}
int main() {
	scanf("%lld", &p);
	g = 2;
	while (true) {
		k = 1;
		for (int i = 2; i * i <= p - 1; i++) {
			if ((p - 1) % i == 0) {
				if (rui(g, (p - 1) / i) == 1)k = 0;
				if (rui(g, i) == 1)k = 0;
			}
		}
		if (k)break;
		g++;
	}
	for (int i = 0; i < p; i++) {
		scanf("%lld", a + i);
	}
	if (p == 2 && a[0] == 1 && a[1] == 1) {
		printf("1 0\n");
		return 0;
	}
	if (p == 2 && a[0] == 0 && a[1] == 1) {
		printf("0 1\n");
		return 0;
	}
	for (int i = 1; i < p; i++) {
		c[i] = a[rui(g, i)];
	}
	for (int i = 1; i < p; i++) {
		a[i] = c[i];
	}
	if (a[0] == 1) {
		b[0] = 1;
		for (int i = 1; i < p; i++) {
			a[i] += p - 1;
			a[i] %= p;
		}
	}
	f[0] = 1;
	for (int i = 1; i < p; i++) {
		f[i] = g * f[i - 1] % p;
	}
	for (long long i = 1; i < p; i++) {
		for (long long j = 1; j < p; j++) {
			b[i] += a[j] * (p - 1) * f[i * j * (p - 2) % (p - 1)];
			b[i] %= p;
		}
	}
	for (int i = 0; i < p - 1; i++) {
		printf("%lld ", b[i]);
	}
	printf("%lld\n", b[p - 1]);
}

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

using ll = long long;
using pii = pair<ll, ll>;
using vi = vector<ll>;
using vvi = vector<vi>;

template <class T>
using max_heap = priority_queue<T>;
template <class T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;

template <class T, class U>
void chmax(T &a, U b) {
    if (a < b) a = b;
}
template <class T, class U>
void chmin(T &a, U b) {
    if (b < a) a = b;
}

#define rep(i, j) for (int i = 0; i < j; i++)
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
#define debug(x) cerr << #x << ": " << x << endl;
#define int ll

const ll mod = 1e9 + 7;
const ll inf = (1LL << 50);

void solve(long long L) {
    long double l = L;
    cout << (l / 3.0) * (l / 3.0) * (l / 3.0) << endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    cout << fixed;

    long long L;
    scanf("%lld", &L);
    solve(L);
    return 0;
}


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

#define ll long long
#define all(x) (x).begin(), (x).end()
const long long INF = 1LL << 60;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)  //(i, 10) i=0～i=9まで
#define repr(i, n) for (int i = n; i >= 0; i--)   // (i, 10) i=10～i=0まで
#define FOR(i, m, n) for (int i = m; i < n; i++)  // (i, 3, 10) i=3～i=9まで

// 総数を1000000007で割った余り
const long long mod = 1e9 + 7;

int main() {
    // cin.tie(0);
    // ios::sync_with_stdio(false);
    // cout << fixed << setprecision(5);

    // 入力
    string S;
    cin >> S;

    int max = 0;
    // 処理
    for (int i = 0; i < S.size(); i++) {
        // cout << S[i];
        int cnt = 0;
        if (S[i] == 'A' || S[i] == 'C' || S[i] == 'G' || S[i] == 'T') {
            for (int j = i; j < S.size(); j++) {
                if (S[j] == 'A' || S[j] == 'C' || S[j] == 'G' || S[j] == 'T') {
                    // cout << S[j];
                    cnt++;
                } else {
                    break;
                }
            }
        }
        if (max < cnt) {
            max = cnt;
        }
        // cout << cnt << endl;
    }

    // 出力
    cout << max << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a) for (int i = 0; i < (a); ++i)
#define REP(i, a, b) for (int i = (a); i < (b); ++i)
#define pb push_back
typedef long long ll;
typedef long double la;
using namespace std;

int main(){
    ll k,n,ans;
    cin >> k >> n;
    ll a[n];
    rep(i,n){
        cin >> a[i];
    }
    ans = 0;
    vector<int> b;
    REP(i,1,n){
        if(a[i] - a[i-1] > ans){
            b.pb(a[i] - a[i-1]);   
        }
    }
    b.pb(k - a[n-1] + a[0]);

    sort(b.begin(),b.end(),greater<int>());

    cout << k - b[0] << endl;
}

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

const int N = 303;

int n;
long long a[N];

int solve() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) scanf("%lld", &a[i]);

  long long sum = 0;
  for (int i = 2; i < n; ++i) sum ^= a[i];

  long long t = ((a[0] + a[1]) - sum);

  if (t < 0 || (t & 1)) return 0 * printf("-1\n");
  t >>= 1;
  if (t > a[0]) return 0 * printf("-1\n");

  bool lim = true;
  long long ans = t;
  for (int i = 50; i >= 0; --i) {
    if (sum >> i & 1) {
      if ((t >> i & 1) == 1) return 0 * printf("-1\n");
      if ((lim && (a[0] >> i & 1) == 0) || (1LL << i) + ans > a[0]) {
        lim &= (a[0] >> i & 1) == 0;
      } else {
        ans |= 1LL << i;
        lim &= (a[0] >> i & 1) == 1;
      }
    } else {
      lim &= (a[0] >> i & 1) == (t >> i & 1);
    }
  }

  if (ans == 0) return 0 * printf("-1\n");

  printf("%lld\n", a[0] - ans);
  return 0;
}

int main() {
  int t = 1;
  // scanf("%d", &t);
  while (t--) solve();
  return 0;
}


Measured memory_bytes: 3764
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<queue>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<functional>
#include<set>
#include<map>
#include<climits>
#include<numeric>
#include<utility>
#define ul unsigned long long int
#define ll long long int
#define MAX 1000000+1
using namespace std;
#define F first
#define S second
#define pi 2*acos(0.0)
#define PB push_back
#define CL clear()



int main()
{

    int a, b;
    cin >> a>> b;
    string s[a];
    for(int i=0; i < a; i++)
        cin >> s[i];
    string x(b+2,'#');
    cout << x<< endl;
    for(int i = 0; i <a; i++)
    {
        cout <<'#'<<s[i]<<'#'<<endl;
    }
    cout <<x;
    return 0;

}




Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define MAX 10000
#define INFTY (1<<29)
class DisjointSet{
public:
  vector<int>rank,p;
  DisjointSet() {}
  DisjointSet(int size){
    rank.resize(size,0);
    p.resize(size,0);
    for(int i=0;i<size;i++) makeSet(i);
  }
  void makeSet(int x){
    p[x]=x;
    rank[x]=0;
  }
  bool same(int x,int y){
    return findSet(x)==findSet(y);
  }
  void unite(int x,int y){
    link(findSet(x),findSet(y));
  }
  void link(int x,int y){
    if(rank[x]>rank[y]){
      p[y]=x;
    }else{
      p[x]=y;
      if(rank[x]==rank[y]){
	rank[y]++;
      }
    }
  }
  int findSet(int x){
    if(x!=p[x]){
      p[x]=findSet(p[x]);
    }
    return p[x];
  }
};
class Edge{
public:
  int source,target,cost;
  Edge(int source=0,int target=0,int cost=0):
    source(source),target(target),cost(cost){}
  bool operator<(const Edge &e)const{
    return cost<e.cost;
  }
};
int kruskal(int N,vector<Edge> edges){
  int totalCost=0;
  sort(edges.begin(),edges.end());
  DisjointSet dset=DisjointSet(N+1);
  for(int i=0;i<edges.size();i++){
    Edge e=edges[i];
    if(!dset.same(e.source,e.target)){
      //MST.push\back(e);
      totalCost+=e.cost;
      dset.unite(e.source,e.target);
    }
  }
  return totalCost;
}
int main(){
  int N,M,cost;
  int source,target;
  cin>>N>>M;
  vector<Edge>edges;
  for(int i=0;i<M;i++){
    cin>>source>>target>>cost;
    edges.push_back(Edge(source,target,cost));
  }
  cout<<kruskal(N,edges)<<endl;
  return(0);
}



Measured memory_bytes: 5380
nom,dis = gets.split.map!{|i| i.to_i}
yoko=Array.new(nom)
tate=Array.new(nom)

for i in 0..nom-1
  yoko[i],tate[i]= gets.split.map!{|i| i.to_i}
end
kazu=0
for j in 0..nom-1
  if dis**2>=(yoko[j]**2+tate[j]**2)
    kazu+=1
  end
end
puts kazu


Measured memory_bytes: 17392
#include<bits/stdc++.h>
using namespace std;
#define _   int v, int tl, int tr, int l, int r
#define tm  (tl + tr >> 1)
#define sol v+v, tl, tm, l, r
#define sag v+v+1, tm+1, tr, l, r
#define pb push_back
#define mp make_pair
#define st first
#define nd second
typedef pair < int , int > pp;
const int mod = 1e9 + 7;
const int N   = 1e5 + 5;    

signed main(){  
	int n;
    cin >> n;
    int mx, mx2, mxx;
    mx = mx2 = mxx = 0;
    map < int , int > M;
    for(int i=1; i<=n; i++){
        int x;
        scanf("%d",&x);
        if(++M[x] == 2){
            if(x > mx) { mx2 = mx; mx = x; }
            else { mx2 = max(mx2 , x); }
        }
        if(M[x] == 4) mxx = max(mxx , x);
    }
    
    cout << max(1LL*mxx*mxx , 1LL*mx*mx2);
    return 0;
}

Measured memory_bytes: 4992
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  REP(i, n) {
    cin >> a[i];
    --a[i];
  }
  int cnt{};
  REP(i, n) {
    if (a[a[i]] == i)
      ++cnt;
  }
  cout << cnt / 2 << endl;
}


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

using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define pb push_back
#define pf push_front

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

ll gcd(ll x, ll y) {
	ll r;
	while ((r = x % y) != 0) {
		x = y;
		y = r;
	}
	return y;
}
ll lcm(ll x, ll y) {
	x /= gcd(x, y);
	y /= gcd(x, y);
	return (x*y);
}

int main()
{
	bool b = false;
	string s;
	cin >> s;
	rep(i, s.size()) {
		rep(j, s.size()) {
			if (i != j && s[i] == s[j]) {
				b = true;
			}
		}
		if (b) {
			cout << "no";
			return 0;
		}
	}
	cout << "yes";
	return 0;
}

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

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

int main()
{
    fastinput;
    LL n, i, j, k, t, temp, m, capacity, queries;
    cin >> n >> m >> capacity;
    //vector<pair<LL, LL>> adj[n + 1];
    LL dis[n + 1][n + 1];
    const LL INF = 100000000000000;
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= n; j++)
        {
            dis[i][j] = INF;
        }
        dis[i][i] = 0;
    }

    for (i = 1; i <= m; i++)
    {
        cin >> j >> k >> t;
        if (t <= capacity)
        {
            dis[j][k] = t;
            dis[k][j] = t;
        }
    }
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                dis[i][j] = min(dis[i][j],
                                dis[i][k] + dis[k][j]);
            }
        }
    }

    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= n; j++)
        {
            if (dis[i][j] <= capacity)
            {
                dis[i][j] = 1;
            }
            else
            {
                dis[i][j] = INF;
            }
        }
    }

    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                dis[i][j] = min(dis[i][j],
                                dis[i][k] + dis[k][j]);
            }
        }
    }

    cin >> queries;
    while (queries--)
    {
        //part;
        cin >> j >> k;

        LL distance = dis[j][k];
        //debug(j);
       // debug(k);
       // debug(distance);
        if (distance == INF)
        {
            cout << -1 << endl;
            continue;
        }
        cout<<distance-1<<endl;
        
    }

    return 0;
}


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

#define loop(s, e, i) for (int i=s; i<e; ++i)
#define print(s) cout << s << endl;
using namespace std;
using ll = long long;

#define DIV 1000000007
 
int main() {

  ll N, M;
  cin >> N >> M;
  vector<ll> NUM(N+1);

  loop(0, M, i) {
    int tmp;
    cin >> tmp;
    tmp;
    NUM[tmp] = -1;
  }

  if (NUM[1] != -1) {
    NUM[1] = 1;
  }
  NUM[0] = 1;


  loop(2, N+1, i) {
    if (NUM[i] == -1) {
      continue;
    }
    ll n1 = NUM[i-1];
    ll n2 = NUM[i-2];
    if (n1 == -1) n1 = 0;
    if (n2 == -1) n2 = 0;
    NUM[i] = (n1+n2) % DIV;
  }
  print(NUM[N]);
}

Measured memory_bytes: 4032
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=100010, inf=2e9;

int n, k;
vector<int> G[MX];
int A[MX];
int ans=0;

int dep[MX];
int D[MX];

void dfs1(int v, int now=0){
    dep[v]=now;
    for(int x:G[v]) dfs1(x,now+1);
}

int up(int x){
    int m=min(n,k-1);
    for(int i=1; i<=m; i++)
        if(x==1) break;
        else x=A[x];
    return x;
}

vector<pii> V;
bool done[MX];

void erase(int v){
    done[v]=true;
    for(int x:G[v])
        if(!done[x])
            erase(x);
}

void solve(){
    dfs1(1);
    for(int i=1; i<=n; i++){
        V.push_back({dep[i], i});
    }
    sort(V.begin(), V.end(), greater<pii>());
    for(pii &q:V){
        int v=q.second;
        if(done[v]) continue;
        done[v]=true;
        int p=up(v);
        erase(p);
        if(A[p]!=1) ans++;
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>k;
    for(int i=1; i<=n; i++) cin>>A[i];
    if(A[1]!=1) A[1]=1, ans++;
    for(int i=2; i<=n; i++)
        G[A[i]].push_back(i);

    solve();

    cout<<ans;
    return 0;
}

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

using namespace std;

int main(){
int N; cin >> N; vector<bool> flag( N , false);
  
  
  for(int i = 0; i < N; i++){
    int a; cin >> a; 
    if( a == i + 1){ flag[i] = true;}}
  int cnt = 0;
  for(int start = 0; start < N; start++){
    if( !(flag[start])){ continue;}
   int search = start;
    while( search < N && search  - start < 2 && flag[search]){
      flag[search] = false; search++; }
    cnt++;}
  
  cout << cnt << endl; return 0;}
    
    

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <cstdlib>
#include <queue>
#include <stack>
using namespace std;


int main(){
	int N,H,W;
	cin>>N>>H>>W;
	cout<<(N-H+1)*(N-W+1)<<endl;
	
	
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
const int N = 51;

vector<vector<int>> g(N, vector<int>());
vector<vector<int>> adj(N, vector<int>(N, 0));

void dfs(int v, int e, vector<bool>& visited){
	visited[v]=true;
  	for(int i=0; i<g[v].size(); ++i){
      	int to=g[v][i];
      	if(adj[v][to]==e) continue;
      	if(!visited[to]){
        	dfs(to, e, visited);
        }
    }
}

int main(){
    ios_base::sync_with_stdio (false);
    //freopen ("joke.in","r",stdin);
	//freopen ("joke.out","w",stdout);
	int n, m;
  	cin >> n >> m;
  
  	int a, b;
  	for(int i=1; i<=m; ++i){
    	cin >> a >> b;
      	g[a].push_back(b);
      	g[b].push_back(a);
      	adj[a][b] = i;
      	adj[b][a] = i;
    }
  
  	vector<bool> visited(n+1);

  	int res=0;
  	for(int j=1; j<=m; ++j){
  		int cc=0;	
        fill(visited.begin(), visited.end(), 0);
      	for(int i=1; i<=n; ++i){
    		if(!visited[i]){
        		dfs(i, j, visited);
                cc++;
        	}
    	}
     	if(cc>1) res++;
  	}
  	cout << res;
    return 0;
}

Measured memory_bytes: 256
/* tempate
 *
 *
 */

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>

using namespace std;


#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int (i)=(n); (i)>=(0); (i)--)
#define SIZE(x) ((int)(x).size())
#define GCD(a, b) int gcd(int a,int b){return b?gcd(b,a%b):a;}
#define QP(a, b) int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define all(v) (v).begin(),(v).end()


template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
template<typename A, size_t N, typename T>
void FILL(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

typedef vector<int, int> vint;
typedef pair<int,int> pint;
typedef vector<pint>vpint;
typedef long long ll;

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1LL << 60;
const ll MOD = 1000000007LL;


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll x, a; cin >> x >> a;
    if(x < a) cout << 0;
    else cout << 10; 
    cout << endl;
    return 0;
}


Measured memory_bytes: 256
S = list(input())
Q = int(input())
reverse, front, tail = False, [], []

for q in range(Q):
    query = list(input().split())

    if len(query) == 1:
        reverse ^= 1

    elif len(query) == 3:
        f, c = int(query[1]), query[2]
        f -= 1

        if f ^ reverse:
            tail.append(c)
        else:
            front.append(c)

if reverse:
    print(''.join((front[::-1] + S + tail)[::-1]))
else:
    print(''.join(front[::-1] + S + tail))


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

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int N;

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

	cin >> N;

	vector<P> ans;

	int tmp = N;
	if(tmp%2 == 1) tmp--;

	int S = 1+tmp;

	for (int i = 1;i <= tmp;i++){
		for (int j = i+1;j <= tmp;j++){
			if(i+j == S) continue;
			ans.push_back(P(i,j));
		}
	}

	if(N%2 == 1){
		for (int i = 1;i < N;i++){
			ans.push_back(P(i,N));
		}
	}

	cout << ans.size() << endl;

	for (int i = 0;i < ans.size();i++){
		cout << ans[i].first << " " << ans[i].second << endl;
	}

	return 0;

}


Measured memory_bytes: 384
#include<iostream>
#define MAX 9999999999
using namespace std;

long long a[100005];

int main() {
    long long n, midx, nidx = 0, maxn = 0, res = MAX, half;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (maxn < a[i]) {
            maxn = a[i];
            midx = i;
        }
    }

    half = int(maxn / 2);

    for (int i = 0; i < n; i++) {
        if (i != midx) {
            if (abs(a[i] - half) <= res) {
                if (abs(a[i] - half) == res && a[i] > a[nidx]) {
                    nidx = i;
                    res = abs(a[i] - half);
                }
                else if (abs(a[i] - half) < res) {
                    nidx = i;
                    res = abs(a[i] - half);
                }
            }
        }
    }

    cout << maxn << " " << a[nidx] << endl;

    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int n, a[100005], sum[100005];
long long m;
namespace BIT
{
	long long c[500005];
	inline long long lowbit(long long x) { return x & (~x + 1); }
	inline void add(long long x, long long val)
	{
		for (long long i = x; i < 4 * n; i += lowbit(i))	c[i] += val;
	}
	inline long long sum(long long x)
	{
		long long res = 0;
		for (long long i = x; i; i -= lowbit(i))	res += c[i];
		return res;
	}
}
bool check(int x)
{
	long long cnt = 0;
	sum[0] = 0;
	for (int i = 1; i <= n; ++i)
	{
		sum[i] = (a[i] >= x);
		sum[i] += sum[i - 1];
	}
	for (int i = 0; i <= n; ++i)
	{
		sum[i] = (2 * sum[i] - i) + n + 1;
	}
	memset(BIT::c, 0, sizeof(BIT::c));
	for (int i = 0; i <= n; ++i)
	{
		cnt += BIT::sum(sum[i]);
		BIT::add(sum[i], 1);
	}
	return cnt >= (m+1)/2;
}
int main()
{
	int l = 1000000005, r = 1, ans, mid;
	scanf("%d", &n);
	m = 1ll*n * (n + 1) / 2;
	for (int i = 1; i <= n; ++i)
	{
		scanf("%d", a + i);
		l = min(l, a[i]);
		r = max(r, a[i]);
	}
	while (l <= r)
	{
		mid = (l + r) >> 1;
		if (check(mid))	l = mid + 1, ans = mid;
		else r = mid - 1;
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 4992
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    class Program
    {
        static long l;
        static int n;
        static List<long> x_list;

        static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));
#if DEBUG
            ReadLine();
#endif
        }

        void Solve(ConsoleInput cin)
        {
            int n = cin.ReadInt;
            int[] h = cin.ReadIntArray(n);
            int[] dp = new int[n];
            dp[0] = 0;
            dp[1] = Math.Abs(h[1] - h[0]);

            for (int i = 2; i < n; i++)
            {
                int tmp1 = dp[i - 2] + Math.Abs(h[i] - h[i - 2]);
                int tmp2 = dp[i - 1] + Math.Abs(h[i] - h[i - 1]);

                dp[i] = Math.Min(tmp1, tmp2);
            }

            Console.WriteLine(dp[n - 1]);
        }

        class ConsoleInput
        {
            private readonly System.IO.TextReader _stream;
            private char _separator = ' ';
            private Queue<string> inputStream;

            public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
            {
                this._separator = separator;
                this._stream = stream;
                inputStream = new Queue<string>();
            }

            public string Read
            {
                get
                {
                    if (inputStream.Count != 0) return inputStream.Dequeue();
                    string[] tmp = _stream.ReadLine().Split(_separator);
                    for (int i = 0; i < tmp.Length; ++i)
                        inputStream.Enqueue(tmp[i]);
                    return inputStream.Dequeue();
                }
            }

            public string ReadLine { get { return _stream.ReadLine(); } }
            public int ReadInt { get { return int.Parse(Read); } }
            public long ReadLong { get { return long.Parse(Read); } }
            public double ReadDouble { get { return double.Parse(Read); } }
            public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret; }
            public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }
            public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }
        }
    }
}


Measured memory_bytes: 18784
#include<cstdio>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=1005;

struct Point
{
	int x,y;
	Point(int _x=0,int _y=0)
	{x=_x;y=_y;}
};

int n;
double dis[MAXN][MAXN],f[MAXN];
int r[MAXN];
Point S,T,P[MAXN];
queue<int> Q;
bool inq[MAXN];

int main()
{
	scanf("%d%d%d%d",&S.x,&S.y,&T.x,&T.y);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d%d",&P[i].x,&P[i].y,&r[i]);
	P[0]=S;P[n+1]=T;
	for(int i=0;i<=n+1;i++)
		for(int j=0;j<=i;j++)
			dis[i][j]=dis[j][i]=max(0.0,sqrt(1.0*(P[i].x-P[j].x)*(P[i].x-P[j].x)+1.0*(P[i].y-P[j].y)*(P[i].y-P[j].y))-r[i]-r[j]);
	
	for(int i=1;i<=n+1;i++)
		f[i]=1e100;
	
	f[0]=0;
	Q.push(0);
	inq[0]=true;
	while(!Q.empty())
	{
		int u=Q.front();
		Q.pop();
		inq[u]=false;
		for(int i=0;i<=n+1;i++)
			if(i!=u)
				if(f[u]+dis[u][i]<f[i])
				{
					f[i]=f[u]+dis[u][i];
					if(!inq[i])
					{
						inq[i]=true;
						Q.push(i);
					}
				}
	}
	
	printf("%.10lf\n",f[n+1]);
	
	return 0;
}


Measured memory_bytes: 8192
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define RFOR(i,l,r) for(long long i=(l);i>=(r);--i)
#define RREP(i,n) RFOR(i,n-1,0)
#define RREPS(i,n) RFOR(i,n,1)
#define int long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
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;
}
const int INF=1e18;
const int MOD=1e9+7;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

signed main(){
    int h,w;cin>>h>>w;
    char ma[h][w];
    queue<pair<int,int>>q;
    int depth[h][w];
    REP(i,h)REP(j,w){
        cin>>ma[i][j];
        depth[i][j]=INF;
        if(ma[i][j]=='#'){
            q.push({i,j});
            depth[i][j]=0;
        }
    }
    int ans=0;
    while(!q.empty()){
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        REP(i,4){
            int nx=x+dx[i];int ny = y +dy[i];
            if(nx>=0&&nx<h&&ny>=0&&ny<w&&depth[nx][ny]==INF){
                depth[nx][ny]=depth[x][y]+1;
                q.push({nx,ny});
            }
        }
    }
    REP(i,h)REP(j,w)chmax(ans,depth[i][j]);
    cout<<ans<<endl;
}

Measured memory_bytes: 25396
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <string>

using namespace std;

using lint = long long;
using ldouble = long double;

int solve(const string& s, int& i) {
    if (s[i] == '[') {
        vector<int> ch;
        ++i;
        while (s[i] != ']') {
            ch.push_back(solve(s, i));
        }
        ++i;

        sort(ch.begin(), ch.end());
        return accumulate(ch.begin(), ch.begin() + ch.size() / 2 + 1, 0);
    } else {
        int ret = 0;
        while (s[i] != ']') {
            ret = ret * 10 + (s[i] - '0');
            ++i;
        }
        return (ret + 1) / 2;
    }
}

int main() {
    int Q;
    cin >> Q;
    for (int q = 0; q < Q; ++q) {
        string s;
        cin >> s;

        int i = 0;
        cout << solve(s, i) << endl;
    }
    return 0;
}



Measured memory_bytes: 3196
from itertools import chain
X,Y,A,B,C = map(int,input().split())
P = map(int,input().split())
Q = map(int,input().split())
R = map(int,input().split())

apples = sorted(chain(((v,0) for v in P), ((v,1) for v in Q),((v,2) for v in R)))

res = 0
total = 0
x = 0
y = 0
for v,k in reversed(apples):
    if k == 0:
        if x < X:
            x += 1
            total += 1
            res += v
    elif k == 1:
        if y < Y:
            y += 1
            total += 1
            res += v
    else:
        total += 1
        res += v
    if total == X+Y:
        break

print(res)


Measured memory_bytes: 122092
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MOD=1e9+7;
const long double Pi=acos(-1);
int main(){
  ll N;
  cin>>N;
  if(N%2==0){cout<<N/2-1<<endl;}
  else{cout<<N/2<<endl;}
} 

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

using namespace std;

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

	vector<int> A(N);
	for (auto& x : A) {
		cin >> x;
	}

	int D = A[0] + K - A[N - 1];
	for (int i = 0; i + 1 < N; ++i) {
		D = max(D, A[i + 1] - A[i]);
	}

	int ans = K - D;
	cout << ans << endl;
}


Measured memory_bytes: 1024
#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>;
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)

const int INF = 1e9 + 10;

int N;
vector<long long> A, B;

long long solve() {
    if (A == B) return 0;
    long long sum = 0, mi = 1LL<<60;
    for (int i = 0; i < N; ++i) {
        sum += A[i];
        if (A[i] > B[i]) mi = min(mi, B[i]);
    }
    return sum - mi;
}

int main() {
    cin >> N;
    A.resize(N), B.resize(N);
    for (int i = 0; i < N; ++i) cin >> A[i] >> B[i];
    cout << solve() << endl;
}


Measured memory_bytes: 3584
dice = map(int, raw_input().split())
n = int(raw_input())
temp = [0 for i in range(2)]

for i in range(n):
    hint = map(int, raw_input().split())
    
    for j in range(len(dice)):
        if hint[0] == dice[j]:
            temp[0] = j
        elif hint[1] == dice[j]:
            temp[1] = j
    
    if (temp[0] == 1 and temp[1] == 2) or (temp[0] == 2 and temp[1] == 4) or (temp[0] == 4 and temp[1] == 3) or (temp[0] == 3 and temp[1] == 1):
        print dice[0]
    elif (temp[0] == 0 and temp[1] == 3) or (temp[0] == 3 and temp[1] == 5) or (temp[0] == 5 and temp[1] == 2) or (temp[0] == 2 and temp[1] == 0):
        print dice[1]
    elif (temp[0] == 0 and temp[1] == 1) or (temp[0] == 1 and temp[1] == 5) or (temp[0] == 5 and temp[1] == 4) or (temp[0] == 4 and temp[1] == 0):
        print dice[2]
    elif (temp[0] == 0 and temp[1] == 4) or (temp[0] == 4 and temp[1] == 5) or (temp[0] == 5 and temp[1] == 1) or (temp[0] == 1 and temp[1] == 0):
        print dice[3]
    elif (temp[0] == 0 and temp[1] == 2) or (temp[0] == 2 and temp[1] == 5) or (temp[0] == 5 and temp[1] == 3) or (temp[0] == 3 and temp[1] == 0):
        print dice[4]
    else:
        print dice[5]
    
        

Measured memory_bytes: 6492
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N = int(input())
A = list(map(int, input().split()))

minN, maxN = A[N], A[N]

mins = [0] * (N + 1)
maxs = [0] * (N + 1)


mins[N], maxs[N] = A[N], A[N]
for i in range(N - 1, -1, -1):
    mins[i] = (mins[i + 1] + 1) // 2 + A[i]
    maxs[i] = maxs[i + 1] + A[i]

# print(mins, maxs)


def ok():
    c = 1
    ret = 0
    for i in range(N + 1):
        if not mins[i] <= c:
            return -1
        c = min(c, maxs[i])
        ret += c
        # print(i, c)
        c = 2 * (c - A[i])

    return ret

print(ok())

Measured memory_bytes: 23432
s = gets.chop

sum = 0
sz = s.size - 1 
(2**sz).times { |i|
  _s = s.dup
  cnt = 1
  sz.times { |j|
    if i & (1 << j) != 0
      _s.insert(j+cnt, "+")
      cnt += 1
    end
  }
  sum += eval(_s)
}
p sum


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

int main() {
  
  int n,m;
  cin >> n >> m;
  
  vector<int> a(m);
  int sum = 0;
  
  for( int i = 0; i < m; i++){
    cin >> a.at(i);
    sum += a.at(i);
  }
  
  if ( n - sum >= 0 ){
    cout << n - sum << endl;
  }else{
    cout << -1 << endl;
  }
  
}



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

int main() {
    string s,t,u;
    int a,b;
    cin >> s >> t >> a >> b >> u;
    if(s == u)a--;
    else b--;
    cout << a << " " << b << endl;
    return 0;
}

/*
やっほい！
　　　　　　　やほほい！
　　　　+　　 　*
　　　 ∧∧　　. ∧∞∧　*
*　ヽ(=´ω｀)人(´ω｀*)ﾉ
　.～（ O x.） （ 　 O)～　+
。*　 　∪　　　　∪
*/

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define M 1000000007
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pie acos(-1)
#define loop(i,a,n) for(int i=a;i<n;i++)
#define trav(a,x) for(auto &a:x)
#define vi vector<int>
#define vl vector<ll>
#define pii pair<ll,ll>
#define endl "\n"

void solve()
{
    ll n,w;
    cin>>n>>w;
    vector<ll>weight(n+1),value(n+1);
    loop(i,0,n)
    cin>>weight[i]>>value[i];
    ll sum_value=0;
    for(auto i:value)
    sum_value+=i;
    vector<ll>dp(sum_value+1,1e18L);
    dp[0]=0;
    for(ll item=0;item<n;item++)
    {
        for(ll val=sum_value-value[item];val>=0;val--)
        {
            dp[val+value[item]]=min(dp[val+value[item]],weight[item]+dp[val]);
        }
    }
    ll ans=-1;
    for(ll i=0;i<dp.size();i++)
    {
        
        if(dp[i]<=w)
        ans=max(ans,i);
    }
   
    cout<<ans;
}
int main() {
	// your code goes here
	io;
	
    solve();
	return 0;
}


Measured memory_bytes: 3880
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <numeric>
#include <iterator>

using namespace std;

int main(){
   int N, total, answer, tmp;
   cin >> N ;
   vector<int> A(N);
   for(int i = 0; i < N; i++) cin >> A.at(i);

   for(int k = 0; k < N - 1; k++){
        total += abs(A.at(k) - A.at(k + 1));
   }
   total += abs(A.at(0)) + abs(A.at(N - 1));

   answer = total - abs(A.at(0)) - abs(A.at(0) - A.at(1)) + abs(A.at(1));
   
   cout << answer << endl;
   
   for(int i = 1; i < N - 1; i++){
       answer = total - abs(A.at(i) - A.at(i - 1)) - abs(A.at(i) - A.at(i + 1));
       answer += abs(A.at(i - 1) - A.at(i + 1));
       cout << answer << endl;
   }
    
   answer = total - abs(A.at(N - 1)) - abs(A.at(N - 1) - A.at(N - 2)) + abs(A.at(N - 2));
   cout << answer << endl;
}


Measured memory_bytes: 1664
# -*- coding: utf-8 -*-
 
A, B = map(int, input().split())

tap = 0
count = 0

if B <= 1:
	print(0)
else:
	while True:
		count += A
		tap += 1
		
		if count < B:
			count -= 1
		else:
			break

	print(tap)

Measured memory_bytes: 2940
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <sstream>
#include <vector>
using namespace std;

#define REP2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define REP(i, n) REP2(i, 0, n)
#define ALL(c) (c).begin(), (c).end()
#define FOREACH(i, c) for(auto i = (c).begin(); i != (c).end(); ++i)
#define BIT(n, m) (((n) >> (m)) & 1)

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

const ll inf = 1e15;
const ll mod = 1000 * 1000 * 1000 + 7;
const double eps = 1e-9;

template <typename S, typename T> ostream &operator<<(ostream &out, const pair<S, T> &p) {
  out << "(" << p.first << ", " << p.second << ")";
  return out;
}

template <typename T> ostream &operator<<(ostream &out, const vector<T> &v) {
  out << "[";
  REP(i, v.size()){
    if (i > 0) out << ", ";
    out << v[i];
  }
  out << "]";
  return out;
}


int main(){
  int n, a, s, g;
  while (cin >> n >> a >> s >> g && n){
    vector<int> F(a), T(a);
    vector<string> S(a);
    REP(i, a) cin >> F[i] >> T[i] >> S[i];
    vector<string> D(n, string(1, 'z' + 1));
    D[g] = "";

    bool ng = false;
    REP(i, 10 * n + 1){
      REP(j, a){
        if (D[T[j]][0] != 'z' + 1 && D[F[j]] > S[j] + D[T[j]]){
          D[F[j]] = S[j] + D[T[j]];
          if (i >= n && F[j] == s) ng = true;
        }
      }
    }
    // cout << D[s] << endl;
    cout << (ng || D[s][0] == 'z' + 1 ? "NO" : D[s]) << endl;
  }
  return 0;
}

Measured memory_bytes: 2008
n, k = map(int, input().split())
a = list(map(int, input().split()))

wa = [0]
for i in range(n):
    wa.append(wa[i]+a[i])

t = wa[k]-wa[0]
for i in range(k+1,n+1):
    if t < wa[i]-wa[i-k]:
        print("Yes")
    else:
        print("No")
    t = wa[i]-wa[i-k]
    # print(wa[i]-wa[i-k],t)



Measured memory_bytes: 31560
#include <bits/stdc++.h>
#include <unordered_map>
#include <queue>
 
using namespace std;
 
int parent[100001];
int r[100001];
long long mp[100001];
 
int find(int a) {
    if (parent[a] == a) return a;
    return parent[a] = find(parent[a]);
}
 
long long merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return 0;
    if (r[a] > r[b]) {
        int t=a;
        a=b;
        b=t;
    }
    parent[a] = b;
    if (r[a] == r[b]) ++r[b];
    int ans=mp[b]*mp[a];
    mp[b]+=mp[a];
 
    return ans;
}
 
int main() {
    long long N;
    int M, i;
    cin >> N >> M;
    int bridges[100001][2];
    long long ans[100001];
 
    for (i = 0; i < M; i++) {
        cin >> bridges[i][0] >> bridges[i][1];
    }
    for (i=0;i<=N;i++) {
        parent[i]=i;
        r[i]=1;
        mp[i]=1;
    }
 
    ans[M-1]=(N * (N - 1)) / 2;
    for (i = M - 2; i >= 0; i--) {
        long long nn=merge(bridges[i+1][0], bridges[i+1][1]);
        ans[i]=max(0ll,ans[i+1]-nn);
    }
 
    for(i=0;i<M;i++){
        cout<<ans[i]<<endl;
    }
    return 0;
}

Measured memory_bytes: 4480
import numpy as np
N = int(input())
As = input().split()
for i in range(N):
    As[i] = int(As[i])
As = np.array(As)


def get_sign(x):
    if x>0:
        return +1
    elif x<0:
        return -1
    else:
        return 0

ans = 1
a0 = None
a1 = None
for a in As:
    if a0 is None:
        a0 = a
    elif a1 is None:
        a1 = a
    else:
        if (get_sign(a-a1)==get_sign(a1-a0))|(get_sign(a1-a0)==0):
            a0 = a1
            a1 = a
        elif get_sign(a-a1)==0:
            pass
        else:
            ans += 1
            a0 = a
            a1 = None
print(ans)

Measured memory_bytes: 20164
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long a, b, x; 
	long long z=0;
	cin>>a>>b>>x;

		
 			if (1<=x){
				
					for(int i=a;i<=b;i++)
					z=(b/x)-(a/x);
					if(a%x==0){
						z++;
						cout<<z;
					}
				
				else {
					cout<<z;
				}

			}
		
	return 0;		
}

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

#define vec     vector<int>
#define vecll   vector<ll>
#define vec2    vector<vector<int>>
#define vec2ll  vector<vector<ll>>
#define vpair   vector<pair<int, int>>
#define vpairll vector<pair<ll, ll>>

#define rep(i,n)         for(ll i=(ll)0; i<(ll)n; i++)
#define REP(i,m,n)       for(ll i=(ll)m; i<(ll)n; i++)
#define arr(var, n)      vec var(n); rep(i,n){cin >> var[i];}
#define arrll(var, n)    vecll var(n); rep(i,n){cin >> var[i];}
#define all(var)         (var).begin(), (var).end()
#define sortall(var)     sort(all(var))
#define f_sum(var)       accumulate(all(var), 0)
#define f_sumll(var)     accumulate(all(var), 0LL)
#define chmin(v1, v2)    v1 = min(v1, v2)
#define chmax(v1, v2)    v1 = max(v1, v2)
#define mpair(v1, v2)    make_pair(v1, v2)
#define pb(var)          push_back(var)
#define prt(var)         cout << var << "\n"
#define scn(var)         cin >> var;
#define pYes()           prt("Yes")
#define pNo()            prt("No")
#define prtd(n, var)     cout << fixed << setprecision(n) << var << "\n"
#define prt2(v1, v2)     cout << v1 << " " << v2 << "\n"
#define prt3(v1, v2, v3) cout << v1 << " " << v2 << " " << v3 << "\n"
#define prtall(var)      rep(i,var.size()){cout << var[i] << " ";} cout << "\n"
//----------------------------------------------------------------
ll a[51]={};
ll p[51]={};

ll func_p(ll n, ll x){
  if(n==0){
    if(x>0) return 1;
    else return 0;
  }
  if(x<=1){
    return 0;
  } else if(x<=a[n-1]+1){
    return func_p(n-1, x-1);
  } else {
    return p[n-1]+1+func_p(n-1, x-2-a[n-1]);
  }
}

int main(void) {
  ll n, x;
  cin >> n >> x;

  p[0]=1; a[0]=1;
  REP(i,1,51){
    a[i] = 2*a[i-1]+3;
    p[i] = 2*p[i-1]+1;

  }

  prt(func_p(n, x));
}


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

using namespace std;

typedef long long ll;

#define MOD 1000000007

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  vector<ll> cnt(100001);
  for (int i = 0; i < n; ++i) {
    cnt[a[i]]++;
  }
  ll sum = 0;
  for (int i = 1; i <= 100000; ++i) {
    sum += cnt[i] * i;
  }
  int q;
  cin >> q;
  for (int i = 0; i < q; ++i) {
    int b, c;
    cin >> b >> c;
    if (0 < cnt[b]) {
      sum -= b * cnt[b];
      sum -= c * cnt[c];
      cnt[c] += cnt[b];
      cnt[b] = 0;
      sum += c * cnt[c];
    }
    cout << sum << endl;
  }
  return 0;
}

Measured memory_bytes: 4572