akhauriyash/Code-Regression huggingface dataset:
# coding: utf-8
import re
import math
import itertools
from copy import deepcopy
import fractions
import random
from functools import lru_cache
from heapq import heappop,heappush
import time
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(2000)
#import numpy as np
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def fac_list(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="int"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
#main

n,k=map(int,input().split())
H=list(map(int,input().split()))
dp=[inf]*n
dp[0]=0
for a in range(n):
    for b in range(1,min(a+1,k+1)):
        dp[a]=min(dp[a],dp[a-b]+abs(H[a]-H[a-b]))
print(dp[n-1])

Measured memory_bytes: 78684
def main():
    N = int(input())
    G = [[] for _ in range(N)]
    for i in range(N):
        a = int(input())
        for j in range(a):
            x, y = (int(i) for i in input().split())
            G[i].append((x-1, y))
            # 人iは人xのことをyと言っている

    ans = 0
    for bit in range(1 << N):
        cur = 0
        good = True  # 矛盾がない
        for i in range(N):
            if bit & (1 << i):
                # 人iは正直者
                cur += 1
                for j, y in G[i]:
                    if (bit & (1 << j)) and y == 1:
                        continue
                    elif not(bit & (1 << j)) and y == 0:
                        continue
                    elif (bit & (1 << j)) and y == 0:
                        good = False
                        break
                    elif not(bit & (1 << j)) and y == 1:
                        good = False
                        break
            else:
                # 人iはうそつき
                for j, y in G[i]:
                    if (bit & (1 << j)) and y == 0:
                        continue
                    elif not(bit & (1 << j)) and y == 1:
                        continue
                    elif (bit & (1 << j)) and y == 0:
                        good = False
                        break
                    elif not(bit & (1 << j)) and y == 1:
                        good = False
                        break
        # print(bit, ":", good)
        if good:
            ans = max(ans, cur)
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 49244
from copy import deepcopy

d=int(input())
c=list(map(int,input().split())) #scoreを減らす
s=[] #scoreを増やす
for i in range(d):
    t=list(map(int,input().split()))
    s.append(t)
last=[0]*26 #それぞれのコンテストが最後に行われたのは何日目か
ans_lst=[]

for i in range(1,d): #364日、1日目ならi=1
    temp_best=-100000000
    for j in range(26): #それぞれの日において、26個のコンテストを順番にピックアップ
        temp=s[i-1][j]
        for k in range(26): #ピックアップされていないコンテストは、スコアを減らす
            if j!=k:
                temp-=(c[k]*(i-last[k]))
        temp_last=deepcopy(last)
        temp_last[j]=i
        for k in range(26):
            temp+=s[i][k]
            for l in range(26):
                if k!=l:
                    temp-=(c[l]*(i+1-temp_last[l]))
        if temp>temp_best:
            temp_best=temp
            rem=j
    ans_lst.append(rem)
    last[rem]=i
    
temp_best=-100000000 #365日目は、次の日のことは考えなくてよい
for j in range(26): #26個のコンテストを順番にピックアップ
    temp=s[i-1][j]
    for k in range(26): #ピックアップされていないコンテストは、スコアを減らす
        if j!=k:
            temp-=(c[k]*(i-last[k]))
    if temp>temp_best:
        temp_best=temp
        rem=j
ans_lst.append(rem) #AtCoder運営お疲れ様です

score=0
las=[0]*26
for i in range(d):
    for j in range(26):
        las[j]+=1
    score+=s[i][ans_lst[i]]
    las[ans_lst[i]]=0
    for j in range(26):
        score-=c[j]*las[j]

for q in range(1,61):
    for p in range(d-q):
        las=[0]*26
        temp_score=0
        temp_ans_lst=deepcopy(ans_lst)
        temp_ans_lst[p],temp_ans_lst[p+q]=temp_ans_lst[p+q],temp_ans_lst[p]
        for i in range(d):
            for j in range(26):
                las[j]+=1
            temp_score+=s[i][temp_ans_lst[i]]
            las[temp_ans_lst[i]]=0
            for j in range(26):
                temp_score-=c[j]*las[j]
        if temp_score>score:
            score=temp_score
            ans_lst=temp_ans_lst

for i in ans_lst:
    print(i+1)

Measured memory_bytes: 80456
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#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;
using ll = long long int;
using int64 = long long int;
 
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;}
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const int INF = 1LL << 29;
const ll LONGINF = 1LL << 60;
const ll MOD = 1000000007LL;

struct Elem {
    int cur; ll cost;
    Elem() {}
    Elem(int cur_, ll cost_) : cur(cur_), cost(cost_) {}
    bool operator<(const Elem &e) const {
        return cost > e.cost;
    }
};

ll dist[110010];
int main() {
    int N, M, K; scanf("%d%d%d", &N, &M, &K);

    int V = N;
    vector< vector< pair<int, int> > > G(V);
    for(int i=0; i<M; i++) {
        int u, v, c; scanf("%d%d%d", &u, &v, &c);
        u--; v--;
        G[u].emplace_back(v, c);
        G[v].emplace_back(u, c);
    }

    fill(dist, dist + V, LONGINF);
    priority_queue<Elem> que;
    for(int i=0; i<K; i++) {
        int v; scanf("%d", &v);
        v--;
        dist[v] = 0;
        que.emplace(v, 0);
    }

    while(que.size()) {
        Elem elem = que.top(); que.pop();
        int cur = elem.cur; ll cost = elem.cost;
        if(dist[cur] < cost) continue;
        for(auto e : G[cur]) {
            int to, d; tie(to, d) = e;
            if(dist[to] > cost + d) {
                dist[to] = cost + d;
                que.emplace(to, dist[to]);
            }
        }
    }

    ll ans = 0;
    for(int i=0; i<V; i++) {
        chmax(ans, dist[i]);
        for(auto e : G[i]) {
            int cur = i, to = e.first, d = e.second;
            ll x = (dist[to] - dist[cur] + d + 1) / 2;
            chmax(ans, dist[cur] + x);
        }
    }
    printf("%lld\n", ans);
    return 0;
}



Measured memory_bytes: 6000
#!/usr/bin/python3
# -*- coding: utf-8 -*-

n = int(input())
a = [int(i) for i in input().split()]
mod = 10 ** 9 + 7
b = [0] * n

for ai in a:
    if n % 2 == ai % 2:
        break
    left = (n - ai) // 2
    right = (n + ai) // 2
    if b[left] == 0:
        b[left] = 1
    elif b[right] == 0:
        b[right] = 1
    else:
        break

if 0 in b:
    ans = 0
elif n % 2 == 0:
    ans = pow(2, len(set(a)), mod)
else:
    ans = pow(2, len(set(a)) - 1, mod)
print(ans)


Measured memory_bytes: 13880
#include <iostream>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <math.h>
using namespace std;
typedef long long ll;

int main() {
	string a, b;
	cin >> a >> b;
	ll c, d;
	cin >> c >> d;
	string t;
	cin >> t;
	if (t == a)
		c--;
	else if (t == b)
		d--;
	cout << c << " " << d;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define f(i,a,b) for( int i = a; i < b ; i++ ) 
#define af(i,a,b) for( int i = a; i >= b ; i--)
#define rep(i,a,b,k) for(int i = a; i < b ; i+= k )
#define arep(i,a,b,k) for( int i = a; i >= b ; i-= k)
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define sor(a) sort( a.begin(), a.end() )
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL)
#define PI 3.14159265358979323846

typedef long double ld;
typedef long long int ll;
typedef vector<int> vi ;
typedef pair<int,int> ii ;
typedef vector<ii> vii 	;

ld p[3010];
ld dp[3010][3010];
int main(){
	fastio;
	cout<<fixed<<setprecision(15);
	int n;
	cin>>n;
	f(i,0,n) cin>>p[i+1];
	dp[0][0]=1.0;
	f(i,1,n+1){
		dp[i][0]=dp[i-1][0]*(1-p[i]);
		dp[i][i]=dp[i-1][i-1]*(p[i]);
		f(j,1,i) dp[i][j]=dp[i-1][j-1]*p[i]+dp[i-1][j]*(1-p[i]);
	}
	ld ans=0;
	f(i,n/2+1,n+1) ans+=dp[n][i];
	cout<<ans;
}

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

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

  int A[N];
  rep(i,N) cin >> A[i];

  int ans = 0;
  while(1) {
    bool odd = false;
    rep(i,N) {
      if(A[i]%2==1) {
        odd = true;
      }
    }
    if(odd) break;
    ans++;
    rep(i,N) {
      A[i] /= 2; 
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
MOD = 10**9+7

n, k = map(int, input().split())
A = list(map(int, input().split()))
dp = [[0]*(k+1) for _ in range(n+1)]
dp[0][0] = 1
for i, a in enumerate(A):
  for j in range(k+1):
    if j == 0:
      dp[i+1][j] = 1
    elif j <= a:
      dp[i+1][j] = dp[i+1][j-1] + dp[i][j]
    else:
      dp[i+1][j] = dp[i+1][j-1] + dp[i][j] - dp[i][j-a-1]
    dp[i+1][j] %= MOD
ans = dp[n][k]
print(ans)

Measured memory_bytes: 119788
#include <bits/stdc++.h>
#define P 1000000007

using namespace std;

typedef long long ll;

ll ape[100010], n, a, b, F[100010], R[100010];

ll powmod(ll x, ll y = P - 2, ll p = P)
{
	ll ans = 1;
	while(y) {
		if(y & 1) ans = ans * x % p;
		x = x * x % p, y >>= 1;
	}
	return ans;
}

ll C(int x, int y) {return x < y ? 0 : F[x] * R[y] % P * R[x - y] % P;}

int main()
{
	scanf("%lld", &n);
	for(int i = 1; i <= n + 1; i++) {
		ll x;
		scanf("%lld", &x);
		if(ape[x]) a = ape[x], b = i; else ape[x] = i;
	}
	for(int i = 0; i <= n + 1; i++) F[i] = !i ? 1 : F[i - 1] * i % P;
	for(int i = n + 1; i >= 0; i--) R[i] = i == n + 1 ? powmod(F[i]) : R[i + 1] * (i + 1) % P;
	for(int i = 1; i <= n + 1; i++) {
		ll ans = C(n - 1, i);
		if(i != n + 1) ans += 2ll * C(n - 1, i - 1) - C(n - b + a, i - 1);
		if(i != 1) ans += C(n - 1, i - 2);
		printf("%lld\n", (ans % P + P) % P);
	}
	return 0;
}

Measured memory_bytes: 3584
n = input()

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

max_sum = sum(A)

a,b = A[0],sum(A[1:])
m = abs(a - b)
#print(a, b)
for i in range(1,len(A)-1):
  #print(a+A[i],b-A[i])
  a = a+A[i]
  b = b-A[i]
  f= abs(a- b)
  if f< m:
    m = f
print(m)
    

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

typedef long long ll;

ll a,b,c;

int main(){
	scanf("%lld%lld%lld",&a,&b,&c);
	ll tmp = min(a,c);
	a-=tmp;
	c-=tmp;
	b = max(0ll,b-c);
	printf("%lld %lld\n",a,b);
	return 0;
}


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

using namespace std;
#define int long long int

constexpr int MOD = 1000000007; // 10 ** 9 + 7
constexpr int SIZE = 2010;

int dp[SIZE][SIZE];

void solve() {
    int N, M;
    cin >> N >> M;

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

    for (int i = 0; i <= N; i++) {
        dp[i][0] = 1;
    }

    for (int i = 0; i <= M; i++) {
        dp[0][i] = 1;
    }

    for (int i = 1; i <= N; i++) {
        for (int p = 1; p <= M; p++) {
            dp[i][p] = dp[i - 1][p] + dp[i][p - 1];
			if (s[i - 1] != t[p - 1]) {
				dp[i][p] -= dp[i-1][p-1];
			}
			dp[i][p] = (dp[i][p] + 10 * MOD) % MOD;
        }
    }
    cout << dp[N][M] << endl;
}

signed main() {
    solve();
    return 0;
}

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

typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update>	tree_set;
typedef long long ll;
typedef long double ld;
void fast()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

ll mod=1e9 + 7;

int main()
{
    fast();
    string str;
    int cnt[26]={0};
    cin>>str;
    for(int i=0;i<str.length();i++)
        cnt[str[i]-'A']++;
    sort(cnt,cnt+26,greater<ll>());
    if(cnt[0]==2 && cnt[1]==2 && cnt[2]==0)
        cout<<"Yes";
    else
        cout<<"No";
}



Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <cstring>
#include <map>
#include <string>
#include <vector>
#include <queue>

using namespace std;
int main()
{
	long long n,m;
	cin>>n>>m;
	int ans=0;
	if(m<=2*n)
	{
		cout<<m/2<<endl; 
    }
	else
	{
		m=m-2*n;
		cout<<n+m/4<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
import Control.Applicative ((<$>), (<*>))
import Control.Monad
import Data.List

main :: IO ()
main = do
  [n,r] <- getl $ wrds toInt
  unless (n == 0 && r == 0) $ do
    solve n <$> replicateM r (getl $ wrds toInt) >>= print
    main

solve :: Int -> [[Int]] -> Int
solve n pcs = head $ foldl sfl [n,n-1 .. 1] pcs
  where
    sfl ns [p, c] = cs ++ ps ++ rs
      where
        (ps,ts) = splitAt (p-1) ns
        (cs,rs) = splitAt c ts

toInt :: String -> Int
toInt = read

wrds :: (String -> a) -> String -> [a]
wrds f = map f . words

getl :: (String -> a) -> IO a
getl f = f <$> getLine

Measured memory_bytes: 4160
#include <bits/stdc++.h>
#include <algorithm>
#include <math.h>
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
#define INF 999999999
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

using llong = long long;
using namespace std;

llong nijou(llong n){
    return n*n;
}

int main(){
    int n,d,x[20][20],ans=0;
    cin >> n >> d;
    rep(i,n) rep(j,d) cin >> x[i][j];
    rep(i,n) for(int j=i+1;j<n;j++){
        int sum=0;
        rep(k,d) sum += nijou(x[i][k]-x[j][k]);
        double y = sqrt(sum);
        int z = (int)y;
        if(y-z==0) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>

#define TRUE 1
#define FALSE 0

int hantei(int W,int x,int r);

int main(void)
{
	int W,H,x,y,r;
	int x_ans,y_ans;
	
	scanf("%d %d %d %d %d",&W,&H,&x,&y,&r);
	
	x_ans=hantei(W,x,r);
	y_ans=hantei(H,y,r);
	
	if(x_ans==TRUE && y_ans==TRUE){
		printf("Yes\n");
	}
	else{
		printf("No\n");
	}
	
	return 0;
}

int hantei(int W,int x,int r)
{
	if(x-r>=0 && x+r<=W){
		return TRUE;
	}
	else{
		return FALSE;
	}
}


Measured memory_bytes: 2116
from fractions import gcd
from functools import reduce

def main():
    n,x = map(int,input().split())
    x_s = [int(i) for i in input().split()]
    x_s = sorted(x_s)
    diffs = []
    for i in x_s:
        diffs.append(abs(x-i))
    print(reduce(gcd,diffs))





if __name__ == '__main__':
    main()


Measured memory_bytes: 16276
"""import sys
input = sys.stdin.readline"""
S=input()
t=10**6
for i in range(1,len(S)):
    if S[i-1]!=S[i]:
        t=min(t,max(i,len(S)-i))
#print(t)
if t==10**6:
    print(len(S))
else:
    print(t)


Measured memory_bytes: 40048
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	Scanner sc = new Scanner(System.in);

	void run() {
		int M = sc.nextInt();
		int N = sc.nextInt();
		int ans = 0;
		int a[][] = new int[M][N];
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				a[i][j] = sc.nextInt();
			}
		}
		for (int i = 0; i < M; i++) {
			int max = 0;
			for (int j = 0; j < N; j++) {
				int line[] = new int[N];
				for (int k = 0; k < N; k++) {
					line[k] = a[i][k];
				}
				int cnt = 0;
				int l = -1;
				int r = N;
				while (++l < j) {
					if (line[l] == 1) {
						cnt++;
					}
					if (l + 1 < N) {
						line[l + 1] = 1 ^ line[l + 1];
					}
				}
				while (--r > j) {
					if (line[r] == 1) {
						cnt++;
					}
					if (r - 1 >= 0) {
						line[r - 1] = 1 ^ line[r - 1];
					}
				}
				if (line[j] == 1) {
					cnt++;
				}
				max = Math.max(max, cnt);
			}

			for (int j = 0; j < N; j++) {
				if (i + 1 < M) {
					a[i + 1][j] = 1 ^ a[i + 1][j];
				}
			}
			ans += max;
		}
		System.out.println(ans);
	}

	public static void main(String[] args) {
		new Main().run();
	}

	void debug(Object... o) {
		System.out.println(Arrays.deepToString(o));
	}
}

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

bool isNotDivisor[1000010], isVisited[1000010] = {0};

void sieveDivisor(int arr[], int max, int n)
{
	for(int i = 0; i <= max; i++) isNotDivisor[i] = true;
	for(int i = 0; i < n; i++)
	{
		if(isNotDivisor[arr[i]] && !isVisited[arr[i]])
		{
			isVisited[arr[i]] = 1;
			for(int j = arr[i] * 2; j <= max; j+=arr[i])
				isNotDivisor[j] = false;
		}
		else isNotDivisor[arr[i]] = false;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, cnt = 0;
	scanf("%d", &n);
	int arr[n];
	for(int i = 0; i < n; i++) scanf("%d", &arr[i]);
	sort(arr, arr + n);
	int max = arr[n-1];
	sieveDivisor(arr, max, n);
	for(int i = 0; i < n; i++)
		if(isNotDivisor[arr[i]])
			cnt++;
	printf("%d", cnt);
	return 0;
}


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

using namespace std;

int cnt = 0;

void merge(vector<int>& A, int left, int mid, int right) {
    vector<int> v1(A.begin() + left, A.begin() + mid), v2(A.begin() + mid, A.begin() + right);
    int i = 0, j = 0, k = left;
    while (i < v1.size() && j < v2.size()) {
        cnt++;
        if (v1[i] <= v2[j]) {
            A[k++] = v1[i++];
        } else {
            A[k++] = v2[j++];
        }
    }
    while (i < v1.size()) {
        cnt++;
        A[k++] = v1[i++];
    }
    while (j < v2.size()) {
        cnt++;
        A[k++] = v2[j++];
    }
}

void merge_sort(vector<int>& A, int left, int right) {
    if (left + 1 < right) {
        int mid = (left + right) / 2;
        merge_sort(A, left, mid);
        merge_sort(A, mid, right);
        merge(A, left, mid, right);
    }
}

int main() {
    //freopen("ALDS1_5_B_Merge_Sort_Data.txt", "r", stdin);
    int n;
    cin >> n;
    vector<int> A(n);
    for (int i = 0; i < n; i++) cin >> A[i];

    merge_sort(A, 0, n);

    for (int i = 0; i < n; i++) {
        if (i) cout << " " ;
        cout << A[i];
    }
    cout << endl;
    cout << cnt << endl;

    return 0;
}


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

using namespace std;

typedef long int li;
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pt;

#define fi first
#define se second
#define dump(x) cout << #x << " = " << x << endl
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int n, res;

int main () {
    fastIO;
    cin >> n;
    res += min(n, 9);
    if(n>=100) res += min(n-99, 900);
    if(n>=10000) res += min(n-9999, 90000);
    cout << res;
}


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

int main(){
    int n; cin >> n;
    vi a(n);
    int cnt = 0;
    for(int ix=0;ix<n;ix++){
        cin >> a.at(ix);
        if((ix+1) % 2 == 1 && a.at(ix) % 2 == 1) cnt++;
    }
    cout << cnt << endl;

}

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

void solve();

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t = 1;
	//cin >> t;
	for(int i = 0; i < t; i++){
		solve();
	}
	return 0;	
}

void solve(){
	int n;
	cin >> n;
	long long arr[n] = {};
	int N[n];
	for(int i = 0; i < n; i++){
		cin >> N[i];
		arr[N[i]-1]++;
	}
	long long total = 0;
	for(int i = 0; i < n; i++){
		total += (arr[i]*(arr[i]-1))/2; 
	}
	for(int i = 0; i < n; i++){
		cout << total - arr[N[i]-1] + 1 << "\n";
	}
	
	
	
}





Measured memory_bytes: 4992
def main()
  line = gets.split(' ')

  window_width = line[0].to_i
  cartain_width = line[1].to_i

  return if not window_width > 0 && window_width <= 100
  return if not cartain_width > 0 && cartain_width <= 100

  # return "window_widthが不正なレンジ: #{window_width}" if not window_width > 0 && window_width <= 100
  # return "cartain_widthが不正なレンジ: #{cartain_width}" if not cartain_width > 0 && cartain_width <= 100

  isnot_covered_catains_width = window_width - cartain_width * 2

  isnot_covered_catains_width > 0 ? isnot_covered_catains_width : 0
end

p main


Measured memory_bytes: 1788
#include<bits/stdc++.h>
#define DEBUG 0
/*
*/

using namespace std;


int main() {
	long long int N, C, K;
	cin >> N >> C >> K;
	vector<long long int>T(N);
	for (size_t i = 0; i < N; i++)
	{
		cin >> T[i];
	}
	sort(T.begin(), T.end());
	long long int ans = 0;
	long long int now = -1e10;
	long long int count = 0;
	for (size_t i = 0; i < N; i++)
	{
		if (now + K < T[i] || count>=C)
		{
			//cout << "! " << T[i] << " " << count << endl;
			ans++;
			count = 0;
			now = T[i];
		}
		count++;
	}
	if (count)
	{
		ans++;

	}

	cout << ans-1 << endl;

	if (DEBUG)
	{
		int ewataeoprgjpsrteog;
		cin >> ewataeoprgjpsrteog;
	}
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int n,m,h[100100],res;
bool ok[100100];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&h[i]),ok[i]=true;
	for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),ok[x]&=(h[x]>h[y]),ok[y]&=(h[x]<h[y]);
	for(int i=1;i<=n;i++)res+=ok[i];
	printf("%d\n",res);	
	return 0;
}

Measured memory_bytes: 4300
#include<iostream>
using namespace std;
int main(){
    char c;
    int count[26]={0},a,i;
    while(cin>>c){
        a=c-'a';
        if(a<0){
            a+=32;
        }
        count[a]++;
    }
    for(i=0;i<26;i++){
        cout<<(char)(i+'a')<<" : "<<count[i]<<endl;
    }
    return 0;
}
        

Measured memory_bytes: 3088
def f(n, s, max = 10)
  if n == 1
    if max > s
      return 1
    else
      return 0
    end
  elsif (max - 1 + max - n) * n  / 2 < s
    return 0
  else
    result = 0
    for i in (s + n * (n + 1) / 2) / (n + 1)...max
      if i <= s
        result += f(n - 1, s - i, i)
      end
    end
    return result
  end
end
while (n, s = gets.split(" ").map(&:to_i)) != [0,0]
  puts f(n, s)
end

Measured memory_bytes: 6104
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;

int main() {
    int N; cin>>N;
    vi a(N);
    for (int i = 0; i < N; i++)cin>>a[i];
    int ans=0;
    int i=1,index=0;
    while(index<N){
        if(i==a[index]){
            i++;
            index++;
        }else{
            index++;
            ans++;
        }
    }
    if(ans==N)ans=-1;
    cout<<ans<<endl;
}

Measured memory_bytes: 4020
#include<bits/stdc++.h>
#include<utility>
using namespace std;
int main () {
  int N;
  cin >> N;
  vector<pair<int, int>>A(N);
  for (int i = 0; i < N; i ++) {
    int a; 
    cin >> a;
    A[i] = make_pair(a, i);
  }
  sort(A.begin(), A.end());
  for (int i = 0; i < N; i ++) {
    if (i == A[N - 1].second) cout << A[N - 2].first << endl;
    else cout << A[N - 1].first << endl;
  }
}


Measured memory_bytes: 3200
import java.util.*;
import java.io.*;

public class Main{
    public static void main(String[] args){
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);

        try{
            String buf = br.readLine();
            String str[] = buf.split(" ", 0);

            int a = Integer.parseInt(str[0]);
            int b = Integer.parseInt(str[1]);

            if(b < a){
		System.out.println(a-1);
	    }   
            else{
		System.out.println(a);
	    }   
        }
        catch(IOException e){
            System.out.println(e);
        }
    }
}

Measured memory_bytes: 21716
#!/usr/bin/env python3

def main():
    n, m, x, y = map(int, input().split())
    xs = list(map(int, input().split()))
    ys = list(map(int, input().split()))
    xs.append(x)
    ys.append(y)
    if max(xs) < min(ys):
        print("No War")
    else:
        print("War")

main()


Measured memory_bytes: 3064
#include<cstdio>
#define pritnf printf
#define scnaf scanf
#define retrun return
#define sizoef sizeof
#define inl inline
#define br break
#define con continue
#define mst(mst_a,mst_b) memset(mst_a,mst_b,sizeof(mst_a))
#define fora(fora_x,fora_a,fora_b) for(re nti (fora_x)=(fora_a);(fora_x)<=(fora_b);++(fora_x))
#define forb(forb_x,forb_a,forb_b) for(re nit (forb_x)=(forb_a);(forb_x)>=(forb_b);--(forb_x))
#define foral(foral_x,foral_a,foral_b) for(re ll (foral_x)=(foral_a);(foral_x)<=(foral_b);++(foral_x))
#define forbl(forbl_x,forbl_a,forbl_b) for(re ll (forbl_x)=(forbl_a);(forbl_x)>=(forbl_b);--(forbl_x))
#define re register
#define stt struct
#define nms namespace
#define gc getchar
#define sl(sl_a) strlen(sl_a)
#define gt(gt_a) goto gt_a
#define rt return
#define infa (0x3f3f3f3f)
#define infb (0x7fffffff)
#define infd (0x7f)
#define in(in_a) freopen("D:/""/in"in_a".in","r",stdin)
#define out(out_a) freopen("D:/""/out"out_a".out","w",stdout)
#define filein(filein_a) freopen(filein_a".in","r",stdin)
#define fileout(fileout_a) freopen(fileout_a".out","w",stdout)
#define file(file_a) filein(file_a);fileout(file_a)
typedef long long ll;
typedef int itn,nti,tin,tni,nit;
using namespace std;
const nit maxa=100004;
const nit maxb=1000004;
const nit maxc=4;
const tni maxd=10004;
#include<cstring>

tni s,ls;
char x[maxa];
bool f=1;

tni main()
{
    scanf("%s",x+1);
    s=sl(x+1);
    //
    ls=s>>1;
    fora(i,1,ls)
    {
        if(x[i]!=x[s-i+1])
        {
            f=0;
            br;
        }
    }
    //
    if(f)
    {
        pritnf("Yes\n");
        rt 0;
    }
    //
    if(!(s%2))
    {
        f=1;
        fora(i,1,ls)
        {
            if(((x[i]=='p')&&(x[s-i+1]!='q'))||((x[i]=='q')&&(x[s-i+1]!='p'))||((x[i]=='b')&&(x[s-i+1]!='d'))||((x[i]=='d')&&(x[s-i+1]!='b')))
            {
                f=0;
                br;
            }
        }
        //
        if(f)
        {
            printf("Yes\n");
            rt 0;
        }
    }
    //
    printf("No\n");
    rt 0;
}

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

int main() {
  ll n,k;
  cin>>n>>k;
  ll plus,minus;
  plus = n%k;
  minus = abs(plus-k);
  if(plus<minus){
    cout<<plus<<endl;
  }else{
    cout<<minus<<endl;
  }
}

Measured memory_bytes: 3640
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	string s; cin >> s;
	rep(i, 26) if(s.find('a' + i) == s.npos){
		cout << s + string(1, 'a' + i) << endl;
		exit(0);
	}
	int i = s.size() - 1;
	for(; i > 0; i--) if(s[i - 1] < s[i]) break;
	if(i == 0){
		cout << -1 << endl;
		exit(0);
	}
	
	s.erase(s.begin() + i, s.end());
	for(int i = s[s.size() - 1] - 'a' + 1; ; i++) if(find(s.begin(), s.end() - 1, 'a' + i) == s.end() - 1){
		s[s.size() - 1] = 'a' + i;
		cout << s << endl;
		exit(0);
	}
	
	return 0;
}

Measured memory_bytes: 256
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define ford(i, n) for (int i = ((int)(n) - 1); i >= 0; --i)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<char> vc;
typedef pair<int, int> pii;
typedef vector<pii> vii;
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()

const int mod = (int)1e9 + 7;
void add (int &a, int b)
{
    a += b;
    if (a >= mod)
        a -= mod;
}
void sub (int &a, int b)
{
    a -= b;
    if (a < 0)
        a += mod;
}
int mult (int a, int b)
{
    return (ll)a * b % mod;
}

void solve (int n)
{
    int k;
    cin >> k;
    vi a(n);
    forn (i, n)
        cin >> a[i];

    int g = 0;
    forn (i, n)
        g = __gcd(g, a[i]);

    if (k % g == 0 && k <= *max_element(all(a)))
        cout << "POSSIBLE" << endl;
    else
        cout << "IMPOSSIBLE" << endl;
}

int main()
{
#ifdef LOCAL
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    while (cin >> n)
        solve(n);
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
typedef  long long ll;
ll gcd(ll x,ll y){
   if(y==0) return x;
   else return gcd(y,x%y);
}
ll lcm(ll x,ll y){
   return x/gcd(x,y)*y;
}
using namespace std;
int main(){ 
   int n,d,x;
   cin>>n>>d>>x;
   vector<int> a(n);
   rep(i,n){
      cin>>a[i];
   }
   int sum=x;
   for(int i=0;i<n;i++){
      for(int j=1;j<=d;j+=a[i]){
         sum++;
      }
   }
   cout<<sum;


}

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

using namespace std;

const int MAX = 100002;

int main() {
	int N, C;

	cin >> N >> C;


	vector<int> s(N), t(N), c(N);
	for (int i = 0; i < N; i++) {
		cin >> s[i] >> t[i] >> c[i];
		c[i]--;
	}

	vector<int> time(2 * MAX, 0), cnt(2 * MAX, 0);

	for (int i = 0; i < C; i++)
	{
		//初期化
		fill(time.begin(), time.end(), 0);
		//録画開始と停止を指定
		for (int j = 0; j < N; j++) if (c[j] == i) time[2 * s[j] - 1]++, time[2 * t[j]]--;
		//録画時間を塗りつぶす
		for (int j = 0; j < 2 * MAX - 1; j++) time[j + 1] += time[j];
		//チェンネルiがレコーダーを専有する時間を塗りつぶす
		for (int j = 0; j < 2 * MAX; j++) if (time[j] > 0)cnt[j]++;
	}
	int ans = 0;
	for (int i = 0; i < 2 * MAX; i++) ans = max(ans, cnt[i]);

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 2944
n = int(input())
d = input().split()
b1 = dict()
for i in d:
    b1[i] = b1.get(i, 0) + 1##b1[難易度]=手持ちの問題案で, 該当する難易度の問題数

m = int(input())
t = input().split()
b2 = dict()
for i in t:
    b2[i] = b2.get(i, 0) + 1##b2[難易度]=予選に使う問題セットで, 該当する難易度の問題数

for tKey in b2.keys():
    if not(tKey in b1) or (b2[tKey] > b1[tKey]):
        print('NO')
        exit()       
print('YES')        

Measured memory_bytes: 68960
# -*- coding: utf-8 -*-

import sys
import os
import pprint

#fd = os.open('DPL_1_A.txt', os.O_RDONLY)
#os.dup2(fd, sys.stdin.fileno())

# n: n???????????????
# m: m?¨????????????????
n, m = list(map(int, input().split()))
C = list(map(int, input().split()))
MAX = 50000

# i???????????§????????????????????£???j????????????????°??????°
# T[i][j]
# m * (MAX + 1) ?¬????
T = [[float('inf') for i in range(MAX + 1)] for j in range(m)]

#print(n, '???????????????')
for i in range(0, m):
    T[i][0] = 0
    for j in range(1, n + 1):
        #print('i', i, 'j', j, 'C[i]', C[i], 'T[i,j]', T[i][j])
        if C[i] <= n:
            T[i][j] = min(T[i-1][j], T[i][j - C[i]] + 1)
        else:
            T[i][j] = T[i - 1][j]

print(T[m-1][n])

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

int main() {
    ll n, l;
    cin >> n >> l;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];

    rep(i, n - 1) {
        if (a[i] + a[i + 1] >= l) {
            puts("Possible");
            for (int j = 1; j <= i; j++) {
                cout << j << endl;
            }
            for (int j = n - 1; j > i; j--) {
                cout << j << endl;
            }
            return 0;
        }
    }
    puts("Impossible");
}

Measured memory_bytes: 4028
#include<bits/stdc++.h>
#define INF (1e9)
#define N 100005
using namespace std;
int n,a[N],l[N],r[N];

int main(){
  cin>>n;
  for(int i=0;i<n;i++)
    cin>>a[i];
  for(int i=0;i<n;i++){
    if(a[i])continue;
    int x=INF;
    r[i]=x;
    for(int j=i+1;j<n;j++){
      if(a[j]<0&&x>-a[j])x=-a[j];
      if(!a[j])x=INF;
      r[j]=x;
      if(x)x--;
    }
    break;
  }
  for(int i=n-1;i>=0;i--){
    if(a[i])continue;
    int x=INF;
    l[i]=x;
    for(int j=i-1;j>=0;j--){
      if(a[j]<0&&x>-a[j])x=-a[j];
      if(!a[j])x=INF;
      l[j]=x;
      if(x)x--;
    }
    break;
  }
  int ans=0;
  for(int i=0;i<n;i++)
    if(a[i]>0)ans+=min(a[i],max(l[i],r[i]));
  cout<<ans<<endl;
  return 0;
}

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

using namespace std;

using ll = long long;
using ld = long double;

const int INF = 1e9 + 10;
const ll MOD = 1e9 + 7;
const int N = 1e6 + 1;

int a[N];
int b[N];

void solve() {
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}

	for (int i1 = 0; i1 < k; ++i1) {
		fill(b, b + n + 1, 0);
		for (int i = 0; i < n; ++i) {
			int l = max(0, i - a[i]);
			int r = min(n, i + a[i] + 1);
			b[l]++;
			b[r]--;
		}
		for (int i = 1; i < n; ++i) {
			b[i] += b[i - 1];
		}
		bool changed = false;
		for (int i = 0; i < n; ++i) {
			if (b[i] != a[i]) changed = true;	
		}
		copy(b, b + n, a);
		if (!changed) break;
	}	
	for (int i = 0; i < n; ++i) {
		cout << a[i] << " ";
	}
	cout << endl;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}


Measured memory_bytes: 5192
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ld long double
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; }
using P=pair<long long,long long>;
#define rep(i,n) for(long long i=0; i<(long long)n; i++)
#define req(i,n) for(long long i=n-1; i>=0; i--)
#define range(i,a,b) for(long long i=a; i<b; i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((long long)(x).size())
#define COUT(x) cout << x << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define onBoard(y,x) (y>=0 && y<h && x>=0 && x<w)
#define vint vector<int>
#define pri_que priority_queue
#define vvint vector<vector<int>>
#define vstr vector<string>
#define vvchar vector<vector<char>>
#define vchar vector<char>
#define vp vector<pair<int,int>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define show(x) cout<<#x<<"="<<x<<endl;
#define SUM(x) accumulate(x.begin(),x.end(),0)
#define MAX(x) *max_element(x.begin(),x.end())
#define MIN(x) *min_element(x.begin(),x.end())
#define couty cout<<"Yes"<<endl
#define coutn cout<<"No"<<endl
#define coutY cout<<"YES"<<endl
#define coutN cout<<"NO"<<endl
#define yn(x) cout<<(x?"Yes":"No")<<endl
#define YN(x) cout<<(x?"YES":"NO")<<endl
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
long long lcm(long long a, long long b){return a/gcd(a,b)*b;}
const long long dx[8]={1,0,-1,0,1,-1,-1,1};
const long long dy[8]={0,1,0,-1,1,1,-1,-1};
const long long INF = 1e12;
const long long MOD = 1e9+7;

vint a;
int n,k;
bool f(int x){
    int cnt=0;
    rep(i,n){
        cnt+=(a[i]-1)/x;
    }
    return (cnt<=k);
}   
signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(15);

    cin >> n >> k;
    a.resize(n);
    rep(i,n)cin>>a[i];
    
    int l=0, r=INF;
    while(r-l>1){
        int mid=(l+r)/2;
        if(f(mid)) r=mid;
        else l=mid;
    }
    cout<<r<<endl;
}

Measured memory_bytes: 4688
let _ =
  let w = Scanf.scanf "%d\n" (fun x -> x) in
  let n = Scanf.scanf "%d\n" (fun x -> x) in
  let ar = Array.init w (fun x -> x + 1) in
  let swap ar i j = 
    let t = ar.(i-1) in
    ar.(i-1) <- ar.(j-1);
    ar.(j-1) <- t in
  for i = 1 to n do
    let a,b = Scanf.scanf "%d,%d\n" (fun x y -> (x, y)) in
    swap ar a b
  done;
  Array.iter (fun x -> Printf.printf "%d\n" x) ar

Measured memory_bytes: 2388
var toInt = x=>parseInt(x,10);
var toIntArr = arr=>arr.map(x=>toInt(x));
var abs = x=>x>0?x:-x;
function min(){var rest=arguments,v=rest[0];for(var i=1;i<rest.length;i++)if(rest[i]<v)v=rest[i];return v}
function max(){var rest=arguments,v=rest[0];for(var i=1;i<rest.length;i++)if(rest[i]>v)v=rest[i];return v}
function gcd(){var rest=arguments,v=rest[0],temp=(a,b)=>b?temp(b,a%b):a;for(var i=1;i<rest.length;i++)v=temp(v,rest[i]);return v}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));
 
function Main(input){
	var input = input.split('\n');
	var n = toInt(input[0]);
	var as = [];
	for(var i = 0; i < n; i++){
		as[i] = toInt(input[i+1]);
	}

	as.sort((a,b)=>a-b);

	var x = 0;
	var y = 0;
	if(n%2===0){
		for(var i = 0; i < n; i++){
			x += i>=n/2? 2*as[i]: -2*as[i];
		}
		x += as[n/2 -1] - as[n/2];
	}else{
		for(var i = 0; i < n; i++){
			x += i>=(n-1)/2? 2*as[i]: -2*as[i];
			y += i>(n-1)/2? 2*as[i]: -2*as[i];
		}
		x -= as[(n-1)/2] + as[(n+1)/2];
		y += as[(n-1)/2] + as[(n-3)/2];
	}
	var ans = max(x,y);

	//console.log(as,bs)
	console.log(ans);

	return 0;
}



Measured memory_bytes: 42436
#include <iostream>

using namespace std;

int main()
{
      string s;
 
  cin>>s;
 
  if(s=="SUN") 
 cout<<7;
 
  else if(s=="SAT") 
 cout<<1;
 
  
 
  else if(s=="MON") 
 cout<<6;
 
 else if(s=="WED") 
 cout<<4;
  
  else if(s=="TUE") 
 cout<<5;
 
  
 
  
 
  
 
  else if(s=="THU") 
 cout<<3;
 

 
  else if(s=="FRI") 
 cout<<2;
 
  
 
 
 
  

    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner cs = new Scanner(System.in);
        int n = cs.nextInt();
        for (int i = 1; i <= n; i++) {
            int x =i;
            if (x % 3 == 0) {
                System.out.printf(" %d", i);
            }
            else {
                while (true) {
                    if (x % 10 == 3) {
                        System.out.printf(" %d", i);
                        break;
                    }
                    x /= 10;
                    if (x != 0) continue;
                    else break;
                }
            }

        }        System.out.printf("\n");

    }
}


Measured memory_bytes: 39396
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;
typedef long long ll;

bool prime[10000000];
void Eratosthenes(int n) {
    rep(i,n) prime[i] = true;
    prime[1] = false;

    REP(i,2,(int)sqrt(n)) {
        if(prime[i]) {
            for(int j=0;i*(j+2)<n;j++) {
                prime[i*(j+2)] = 0;
            }
        }
    }
}

int main() {
    Eratosthenes(1000000);

    int n,m;
    while(cin >> n >> m) {
        if(n == -1 && m == -1) break;
        
        vector<int> v;
        int cnt = 0;
        REP(i,2,1000000) {
            if(cnt > m) break;

            if(n < i && prime[i]) {
                v.push_back(i);
                cnt++;
            }
        }

        vector<int> res;
        rep(i,v.size()) {
            REP(j,i,v.size()) {
                res.push_back(v[i] + v[j]);
            }
        }

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

        cout << res[m-1] << endl;
    }

    return 0;
}

Measured memory_bytes: 2252
#!/usr/bin/env python3
"""
n, k = [int(i) for i in input().split(' ')]

arr = [int(i) for i in input().split(' ')]

dp = [10**10]*n

k += 1
dp[0] = 0

for i in range(0, n):
    for j in range(1, k):
        if i+j < n:
            dp[i+j] = min(dp[i+j], dp[i] + abs(arr[i+j]-arr[i]))

print(dp[n-1])
n = int(input())

a = [int(i) for i in input().split(' ')]

for i in range(1, n):
    new_a = [int(i) for i in input().split(' ')]
    new_a[0] = max(new_a[0]+a[1], new_a[0]+a[2])
    new_a[1] = max(new_a[1]+a[0], new_a[1]+a[2])
    new_a[2] = max(new_a[2]+a[1], new_a[2]+a[0])
    a, new_a = new_a, a

print(max(a))
"""

n, W = [int(i) for i in input().split(' ')]

dp = [10**9+7]*(10**5+1)
dp[0] = 0
for _ in range(n):
    curwt, val = [int(i) for i in input().split(' ')]
    for v in range((10**5) - val, -1, -1):
        dp[v+val] = min(dp[v+val], dp[v]+curwt)

ans = 0
for i, val in enumerate(dp):
    if val <= W:
        ans = max(i, ans)

print(ans)


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

int main() {
    int x;
    rep(i,5) {
        cin >> x;
        if(x == 0) cout << i + 1 << endl;
    }
}

Measured memory_bytes: 3620
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

int main()
{
  int N, R, ans = 0;
  cin >> N >> R;
  if (N >= 10)
  {
    ans = R;
  }
  else
  {
    ans = R + 100 * (10 - N);
  }

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


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

int main(void) {
    int h, w;

    scanf("%d %d", &h, &w);
    while(h != 0 && w != 0) {
        for(int i = 0; i < h; i++) {
            if(i == 0 || i == h-1) {
                for(int j = 0; j < w; j++) printf("#");
                printf("\n");
            }
            else {
                printf("#");
                for(int j = 1; j < w-1; j++) {
                    printf(".");
                }
                printf("#\n");
            }
        }
        printf("\n");
        scanf("%d %d", &h, &w);
    }
    return 0;
}



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

#define pb         push_back

typedef long long ll;
const ll INF = 1000000000000000000ll;
const ll MOD = 1000000007ll;
const double EPS = 1e-8;

ll n, a, b;
vector<ll> h;
bool check(ll m){
	ll cnt = 0;
	for(int i=0; i<n; i++){
		if(h[i] - m*b > 0){
			cnt += (h[i] - m*b + a - b - 1) / (a-b);
		}
	}
	return cnt <= m;
}

int main(void) {
	//ios_base::sync_with_stdio(false);
	//cin.tie(0);
	cin >> n >> a >> b;

	ll ma = 0;
	for(int i=0; i<n; i++){
		ll t;
		cin >> t;
		h.pb(t);
		ma = max(ma, t);
	}

	ll l = 0;
	ll r = ma/b + 1;

	while(r-l > 1){
		ll m = (l + r)/2;
		if(check(m)){
			r = m;
		}else{
			l = m;
		}
	}

	cout << r << endl;
	
	return 0;
}


Measured memory_bytes: 1400
/* Preprocess */
#include <bits/stdc++.h>

#define pow(n) (n)*(n)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()


/* Field */
using namespace std;


/* Function */

int main (void) 
{

  /* Variable_Proclamation */
  int N; // input
  int A; // input
  string ans;    // output

  int mini;



  /* Input, Resize, Initialize */
  cin >> N;
  cin >> A;

  /* Calculation */
  mini = N % 500;
  if(mini <= A)
  {
    ans = "Yes";
  }
  else
  {
    ans = "No";
  }


  /* Output */
  cout << ans << endl;


  return 0;

}

Measured memory_bytes: 256
#include <iostream>

#define MOD 998244353
#define N_MAX 300002

using namespace std;

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

ll inv[N_MAX],fac[N_MAX],finv[N_MAX];

void init(){
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    for(int i=2;i<N_MAX;i++){
        inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
        fac[i]=fac[i-1]*(ll) i%MOD;
        finv[i]=finv[i-1]*inv[i]%MOD;
    }
}

ll inv_(ll n){
    if(n == 1) return 1;
    else return MOD-inv_(MOD%n)*(MOD/n)%MOD;
}

ll comb(ll n, ll r){
  ll ans;
  if(n < r){
      ans = 0;
  }else{
      ans = (fac[n]*finv[r])%MOD;
      ans = (ans*finv[n-r])%MOD;
      ans = (ans+MOD)%MOD;
  }
  return ans;
}

int main(){
    init();
    ll N, A, B, K;
    cin >> N >> A >> B >> K;
    ll ans = 0;
    for(ll i = 0; i <= N; i++){
        if((K-i*A)%B == 0){
            ll j = (K-i*A)/B;
            if(j < 0) continue;
            ans += (comb(N, i)*comb(N, j))%MOD;
            ans %= MOD;
        }
    }
    cout << ans << endl;
}

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

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

    for (int i=x-k+1; i<x+k; i++) {
        if (i >= -1000000 && i <= 1000000) {
            cout << i << endl;
        }
    }
}

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

int main(){
	double a, b, c, d, e, f, x, y;
	while( scanf("%lf %lf %lf %lf %lf %lf", &a, &b, &c, &d, &e, &f) != EOF ){
		x = (c*e-b*f)/(a*e-b*d)+0.0;
		y = (c-a*x)/b+0.0;
		printf("%.3f %.3f\n", x, y);
	}
	return 0;
}

Measured memory_bytes: 0
#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
int n,m,kk,ss,a[15][15],p[15],bm,ans,te;
inline bool alll(int x){
	fo(i,1,m){
		te=0;
		fo(j,0,n-1) if (x&(1<<j)) te+=a[j][i];
		if ((te&1)!=p[i]) return 0;
	}
	return 1;
}
int main(){
	scanf("%d%d",&n,&m);
	fo(i,1,m){
		scanf("%d",&kk);
		while (kk--){
			scanf("%d",&ss);
			a[ss-1][i]++;
		}
	}
	fo(i,1,m) scanf("%d",&p[i]);
	bm=(1<<n)-1;
	fo(i,0,bm) if (alll(i)) ans++;
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 128