akhauriyash/Code-Regression huggingface dataset:
'use strict'

function main(input) {
  const n = ~~input.trim()
  let count = 0
  for (let i = 1; i <= n; i++) {
    if ((i + '').length % 2) count++
  }
  console.log(count)
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'))


Measured memory_bytes: 11468
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <sstream>
#include <stdio.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <list>
#include <numeric>
#include <stack>
#include <iomanip>

using namespace std;

#define Rep(i,a,b) for(int i = a; i < b; i++)
#define rep(i,b) Rep(i,0,b)
#define rrep(i,a) for(int i = a; i >= 0; i--)
#define allof(a) (a).begin(), (a).end()

typedef long long ll;
const int inf = 1e9 + 7;
const ll infll = 1ll << 60ll;
const ll mod = 1e9 + 7;
// 0~3までは右攜下昴 4~7までは斜め
constexpr int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
constexpr int dy[] = { 0, -1, 0, 1, 1, -1, -1, 1 };

/*
// 敘大公約摧
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

// 敘擣公倍摧
ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}*/


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

	int n, m;
	cin >> n >> m;
	vector<int> s(n), t(m);
	rep(i, n) cin >> s[i];
	rep(i, m) cin >> t[i];

	vector<vector<ll>> sum(n + 1, vector<ll>(m + 1, 0));
	vector<vector<ll>> dp(n + 1, vector<ll>(m + 1, 0));
	dp[0][0] = 1;
	rep(i, n) {
		rep(j, m) {
			if (s[i] == t[j]) {
				dp[i + 1][j + 1] = sum[i][j] + 1;
				dp[i + 1][j + 1] %= mod;
			}

			sum[i + 1][j + 1] = dp[i + 1][j + 1] +
				sum[i + 1][j] + sum[i][j + 1] - sum[i][j];
		}
	}

	ll ans = 0;
	rep(i, n + 1) {
		rep(j, m + 1) {
			ans += dp[i][j];
			ans %= mod;
		}
	}

	cout << ans << endl;

	return 0;
}


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

int main(void){
	string s;
	cin >> s;
	bool f = false;
	for(int i = 0; i < 3; ++i){
		if(s[i]==s[i+1]) f=true;
	}
	string ans = "Good";
	if(f) ans = "Bad";
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll (i) = 0; (i) < (n); (i)++)
#define rep1(i, n) for(ll (i) = 1; (i) <= (n); (i)++)
#define rrep(i, n) for(ll (i) = (n) - 1; (i) >= 0; (i)--)
#define rrep1(i, n) for(ll (i) = (n); (i) >= 1; (i)--)
const ll INF = 1145141919;
const ll MOD = 1000000007;
template<class T> void chmax(T &a, const T &b){if(a < b){a = b;}}
template<class T> void chmin(T &a, const T &b){if(a > b){a = b;}}

int main(){

    ll a, b, c;
    cin >> a >> b >> c;
    if(a + b + c >= 22)cout << "bust" << endl;
    else cout << "win" << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main()
{
    long long int n;
    cin>>n;
    long long int c=0,d,f,g,h;
    d=n/500;
    n=n-(d*500);
    c+=d*1000;
    d=n/5;
      n=n-(d*5);
        c+=d*5;
        cout<<c<<endl;
return 0;
}


Measured memory_bytes: 256
n,k=map(int,input().split())
mod=10**9+7

DP=[0]*(n+2)
DP[0]=1
point=n
n=n+1

for i in range(1,n+1):
    DP[i]=DP[i-1]+point
    point -=2
print(sum(DP[k:])%mod)

Measured memory_bytes: 66916
n, m = map(int, input().split())
a = list()
for _ in range(n):
    a.append(str(input()))
b = list()
for _ in range(m):
    b.append(str(input()))

for H in range(n if m == 1 else n-m+1):
    for W in range(n if m == 1 else n-m+1):
        cnt = 0
        for M in range(m):
            if a[H+M][0+W:m+W] == b[M]:
                cnt+=1
        if cnt==m:
            print('Yes')
            exit()

print('No')


Measured memory_bytes: 3064
/*
гонфлад
*/
#pragma ARCENIY_KIRILLOV_UVIDEL_KROKODILOV
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC push_options
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC pop_options
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define rng(a) a.begin(), a.end()
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define int long long
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
int binpow(int a, int n){
    if (n == 0)
        return 1ll;
    if (n%2 == 0){
        int q = binpow(a, n / 2);
        return (q * q)%mod;
    }else
        return (a * binpow(a, n - 1))%mod;
}
main(){
    int n;
    cin >> n;
    vector <int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<int> obr(n + 1);
    for (int i = 1; i <= n; i++){
        obr[i] = binpow(i, mod - 2);
    }
    vector<int> prefix(n + 1);
    for (int i = 1; i <= n; i++){
        prefix[i] = (prefix[i - 1] + obr[i]) % mod;
    }
    int ans = 0;
    int ce;
    for (int i = 0; i < n; i++){
        ce = (((prefix[i + 1] + prefix[n - i] - 1)% mod) * a[i])%mod;
        ans = (ans + ce)%mod;
    }
    for (int i = 2; i <= n; i++){
        ans = (ans * i)%mod;
    }
    cout << ans;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define pi acos(-1.0)
const ll INF = 1LL<<61;
template<class T>bool chmax(T &a, const T &b) { 
  if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) {
  if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
ll jou(ll N, ll P){if(P==0) return 1;
  if(P%2==0){ll t = jou(N, P/2);return t*t % mod;
  }return (N * jou(N, P-1)) % mod;}  //jou(n,mod-2)で逆元
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'大文字'+=32;    で小文字に
//  cout << fixed << setprecision (20);   小数点以下2０桁まで
//実行時間制約2秒では２×10^8回くらいまで計算できる




//—————————————————BFSグラフ————————————————

using Graph = vector<vector<pair<ll,ll>>>;

int main() {
    // 頂点数と辺数
    ll n;
    cin >> n;


    // グラフ入力受取
    Graph G(n);
    rep(i,n-1) {
        ll a,b,c;
        cin >> a >> b >> c;
        auto x=mp(b-1,c);
        G[a-1].pb(x);
        auto y=mp(a-1,c);
        G[b-1].pb(y);
    }

    ll q,k;
    cin>>q>>k;
    k--;

    // BFS のためのデータ構造
    vector<ll> dist(n, 1000000000000000000); // 全頂点を「未訪問」に初期化
    deque<ll> que;

    // 初期条件 (頂点 0 を初期ノードとする)
    dist[k] = 0;
    que.pb(k); // 0 を橙色頂点にする

    // BFS 開始 (キューが空になるまで探索を行う)
    while (!que.empty()) {
        ll v = que.front(); // キューから先頭頂点を取り出す
        que.pop_front();

        // v から辿れる頂点をすべて調べる
        for (auto nv : G[v]) {
            // 新たな白色頂点 nv について距離情報を更新してキューに追加する
            if(dist[nv.fi]>dist[v] + nv.se){
            dist[nv.fi] = dist[v] + nv.se;
            que.pb(nv.fi);
            }
        }
    }

  rep(i,q){
    ll x,y;
    cin>>x>>y;
    cout << dist[x-1]+dist[y-1] << endl;
  }

}


Measured memory_bytes: 9984
#include<iostream>
int main(){int n,k,x,y,i;std::cin>>n>>k;n++;for(;k;k--){std::cin>>x>>y;x=x>n/2?n-x:x;y=y>n/2?n-y:y;i=(x<y?x:y)%3;std::cout<<(i?i:3)<<"\n";}return 0;}

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

using namespace std;

#define DUMP(x) std::cout << (#x) << " = " << (x) << "\n"
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define ALL(r) r.begin(), r.end()

using ll = std::int64_t;
using vint = std::vector<int>;
using pint = std::pair<int, int>;

constexpr std::int32_t INF = 1001001001;


void Main() {
    int a, b, t;
    cin >> a >> b >> t;

    int ans = 0;
    for (int i = 1; i <= t + 0.5; ++i) {
        if (i % a == 0)ans += b;
    }
    cout << ans << endl;
}

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 256
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String {
            bytes
                .by_ref()
                .map(|r| r.unwrap() as char)
                .skip_while(|c| c.is_whitespace())
                .take_while(|c| !c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        n: usize,
        m: usize,
        s: chars,
        t: chars
    }
    let g = gcd(n,m);
    let l = n * m / g;
    let d1 = l / n;
    let d2 = l / m;
    for i in 0..g {
        if s[i * d2] != t[i * d1] {
            println!("-1");
            return;
        }
    }
    println!("{}", l);
}

fn gcd(mut n: usize, mut m: usize) -> usize {
    while m > 0 {
        let t = m;
        m = n % m;
        n = t;
    }
    n
}


Measured memory_bytes: 4352
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
X = B[A[0]-1]
for i in range(1,N):
  if A[i] == A[i-1]+1 :
    X += (B[(A[i]-1)]+C[(A[i-1]-1)])
  else:
    X += B[(A[i]-1)]
print(X)

Measured memory_bytes: 3064
/*input
5
24 11 8 3 16
*/
 
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <climits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <stdint.h>
#include <tgmath.h>
 
using namespace std;
 
/*******  All Required define Pre-Processors and typedef Constants *******/
#define ar array
#define scd(t) scanf("%d",&t)
#define scld(t) scanf("%ld",&t)
#define sclld(t) scanf("%lld",&t)
#define scc(t) scanf("%c",&t)
#define scs(t) scanf("%s",t)
#define scf(t) scanf("%f",&t)
#define sclf(t) scanf("%lf",&t)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define FOREACH(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define tests int r; cin >> r; while(r--)
#define MP make_pair
#define PI acos(-1)
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef map<int,int> MPII;
typedef set<int> SETI;
typedef multiset<int> MSETI;
typedef long int int32;
typedef unsigned long int uint32;
typedef long long int int64;
typedef unsigned long long int  uint64;
#define godspeed ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
 
#define M(x) ((x)%(1000000007))
 

int arr[1010][1010];

int h;
int w;



bool legal(int x, int y){
	if(x>=1&&x<=h){
		if(y>=1&&y<=w){
			if(arr[x][y]){
				return true;

			}
		}
	}
	return false;
}





int main() {
 	int n;
 	cin>>n;
 	int arr[n];
 	map<int,int> mp;
 	rep(i,n){
 		int a;
 		cin>>a;
 		arr[i] = a;
 		mp[a]++;
 	}
 	if(mp[1]>1){
 		cout<<0<<endl;
 	}
 	else if(mp[1]==1){
 		cout<<1<<endl;
 	}
 	else{
 		int count = n;
 		sort(arr,arr+n);
 		rep(i,n){
 			int a = arr[i];
 			if(mp[a]>1){
 				count--;
 			}
 			else{
 				for(int j = 2; j<=sqrt(a);j++){

 					if(a%j==0){
 						

 						if(mp.find(j)!=mp.end()||mp.find(a/j)!=mp.end()){
 							count--;
 							break;
 						}
 					}
 				}
 			}
 		}
 		cout<<count<<endl;
 	}

}



 


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

#define FastRead  ios_base::sync_with_stdio(0);cin.tie(0);
#define endl      "\n"
#define INF       1<<30

typedef long long ll;

map<ll,set<char>>mp;
set<ll>s;
set<ll>::iterator it_s;

int main()
{
    FastRead

    long double n;

    cin>>n;

    long double ans = n/2.0;

    ll p = ceil(ans);

    cout<<p;
}


Measured memory_bytes: 256
n, a = map(int, input().split())
x = list(map(int, input().split()))

m = a * n

# dp[i][j]: j 個使って合計がi
dp = [[0 for j in range(n+1)] for i in range(m+1)]
dp[0][0] = 1


for xk in x:
    # xkまで見たときを計算
    dpk = [dp[i][:] for i in range(m+1)]
    for i in range(m+1):
        if i - xk >= 0:
            for j in range(1,n+1):
                dpk[i][j] += dp[i-xk][j-1]
    dp = dpk

ans = 0

for i in range(1,m+1):
    for j in range(1,n+1):
        if i / j == a:
            ans += dp[i][j]

print(ans)

Measured memory_bytes: 6196
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<vector>
#include<functional>
using namespace std;
typedef long long LL;
inline LL read()
{
	LL kk=0,f=1;
	char cc=getchar();
	while(cc<'0'||cc>'9'){if(cc=='-')f=-1;cc=getchar();}
	while(cc>='0'&&cc<='9'){kk=(kk<<1)+(kk<<3)+cc-'0';cc=getchar();}
	return kk*f;
}
const LL mod=1e9+7;
LL cun[2000222];
LL qp(LL a,LL b)
{
	LL kk=1;
	while(b)
	{
		if(b&1)kk=(kk*a)%mod;
		b>>=1;
		a=(a*a)%mod;
	}
	return kk;
}
LL n,k;
int main()
{
	scanf("%lld%lld",&n,&k);
	LL asd=0;
	for(LL i=k;i>=1;--i)
	{
		cun[i]=qp(k/i,n);
		for(LL j=2;j<=k/i;++j)
		{
			cun[i]-=cun[i*j];
		}
		asd=(asd+(i*cun[i]%mod)+mod)%mod;
	}
	printf("%lld\n",(asd+mod)%mod);
}

Measured memory_bytes: 4608
N = int(input())
M = 10 ** 5 + 1
A = list(map(int, input().split()))
A2 = [0 for i in range(M)]
for a in A:
  A2[a] += 1
ans = sum(A)
Q = int(input())
for j in range(Q):
  b, c = map(int, input().split())
  ans = ans + (c - b) * A2[b]
  A2[c] += A2[b]
  A2[b] = 0
  print(ans)

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


#define li          long long int
#define rep(i,to)   for(li i=0;i<((li)(to));i++)
#define repp(i,start,to)    for(li i=(li)(start);i<((li)(to));i++)
#define pb          push_back
#define sz(v)       ((li)(v).size())
#define bgn(v)      ((v).begin())
#define eend(v)     ((v).end())
#define allof(v)    (v).begin(), (v).end()
#define dodp(v,n)       memset(v,(li)n,sizeof(v))
#define bit(n)      (1ll<<(li)(n))
#define mp(a,b)     make_pair(a,b)
#define rin rep(i,n)
#define EPS 1e-12
#define ETOL 1e-8
#define MOD 1000000007
typedef pair<li, li> PI;

#define INF bit(60)

#define DBGP 1


#define idp if(DBGP)
#define F first
#define S second
#define p2(a,b)     idp cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)       idp cout<<a<<"\t"<<b<<"\t"<<c<<endl
#define p4(a,b,c,d)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<endl
#define p5(a,b,c,d,e)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<endl
#define p6(a,b,c,d,e,f)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<endl
#define p7(a,b,c,d,e,f,g)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<endl
#define p8(a,b,c,d,e,f,g,h)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<endl
#define p9(a,b,c,d,e,f,g,h,i)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<endl
#define p10(a,b,c,d,e,f,g,h,i,j)        idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<"\t"<<j<<endl
#define foreach(it,v)   for(__typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it)
#define p2p(x)      idp p2((x).F, (x).S)
#define dump(x,n)   idp{rep(i,n){cout<<x[i]<<" ";}puts("");}
#define dump2(x,n)  idp{rep(i,n){cout<<"["<<x[i].F<<" , "<<x[i].S<<"] ";}puts("");}
#define dumpi(x)    idp{foreach(it, x){cout<<(*it)<<" ";}puts("");}
#define dumpi2(x)   idp{foreach(it, x){cout<<"["<<(it)->F<<" , "<<(it)->S<<"] ";}puts("");}

#define read2d(a,w,h)   rep(i,h)rep(j,w)cin>>a[i][j]
#define dump2d(a,w,h)   rep(i,h){rep(j,w)cout<<a[i][j]<<" ";puts("");}

typedef pair<li, li> PI;

li fact_mod[200100];

li n, x;
li s[222];


// dp[i][j] : jをs[0..i]で処理した場合の合計
li dp[202][100020];

int main() {
    fact_mod[0] = 1;
    repp(i, 1, 500) {
        fact_mod[i] = fact_mod[i - 1] * i % MOD;
    }
    cin >> n >> x;
    rin{
        cin >> s[i];
    }
    sort(s, s + n);

    rep(j, x + 1) {
        dp[0][j] = j % s[0];
    }
    repp(i, 1, n) {
        rep(j, x + 1) {
            dp[i][j] = (dp[i - 1][j % s[i]] + dp[i - 1][j] * i % MOD) % MOD;
        }
    }

    cout << dp[n - 1][x] << endl;



    return 0;
}

Measured memory_bytes: 157952
#include <iostream>
#include <vector>
#include <set>
using namespace std;

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

    multiset<int> S;
    for (int i=0; i<N; i++)
    {
        int A;
        cin>>A;

        multiset<int>::iterator p = S.lower_bound(A);
        if (p!=S.begin())
        {
            p--;
            S.erase(p);
        }
        S.insert(A);
    }
    cout<<S.size()<<endl;
}


Measured memory_bytes: 4992
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int k=sc.nextInt();
        int po[]=new int[n];
        for(int i=0;i<n;i++){
            po[i]=sc.nextInt();
        }
        Arrays.sort(po);
        long sum=0;
        for(int i=0;i<n-k;i++)sum+=po[i];
        System.out.println(sum);
    }
}


Measured memory_bytes: 65060
from math import sqrt
n, p = map(int, input().split())
a = []

if n == 1:
    print(p)
    exit()

for i in range(2, int(sqrt(p))+10):
    tmp = 0
    while p % i == 0:
        p //= i
        tmp += 1
    if tmp >= n:
        tmp //= n
        a.append(i**tmp)

ans = 1
for i in a:
    ans *= i

print(ans)



Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#define pi 3.14159265358979323846264338327950

int main() {
	int N, x; std::cin >> N >> x;
	std::vector<int> a(N);
	for (auto& r : a) std::cin >> r;
	std::sort(a.begin(), a.end());
	int count = 0;
	for (auto& r : a) {
		x -= r;
		++count;
		if (x == 0) break;
		if (x < 0) {
			--count;
			break;
		}
	}
	if (x > 0) --count;
	std::cout << count << std::endl;

	return 0;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
 
//const int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
//const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
 
int main()
{
	string s;
	getline(cin, s);
	REP(i, (int)s.size()){
		if ('a' <= s[i] and s[i] <= 'z') cout << (char)(s[i] - 0x20);
		else if ('A' <= s[i] and s[i] <= 'Z') cout << (char)(s[i] + 0x20);
		else cout << s[i];
	}
	cout << endl;
}



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

using namespace std;

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

    int minans, maxans;
    minans = X-K+1;
    maxans = X+K-1;
    for(int i = minans; i <= maxans; ++i){
        cout << i << " ";
    }
    cout << endl;


    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  int H, W;
  cin>>H>>W;
  int N;
  cin>>N;
  int a[N];
  for(int i=0;i<N;++i) cin>>a[i];
  int ans[H][W];
  for(int i=0;i<H;++i) {
    for(int j=0;j<W;++j) {
      ans[i][j] = 0;
    }
  }
  vector<int> arr;
  for(int i=0;i<N;++i) {
    for(int j=0;j<a[i];++j) {
      arr.push_back(i+1);
    }
  }
  int index = 0;
  for(int i=0;i<H;++i) {
    if(i%2==0) {
      for(int j=0;j<W;++j) {
        ans[i][j] = arr[index];
        index++;
      }
    }
    else {
      for(int j=W-1;j>=0;--j) {
        ans[i][j] = arr[index];
        index++;
      }
    }
  }
  for(int i=0;i<H;++i) {
    for(int j=0;j<W;++j) {
      cout<<ans[i][j]<<" ";
    }
    cout<<endl;
  }
}



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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
vector<int> E[202020];
int R[202020];
int G[202020];
set<int> S[202020];
int in[202020];

int dfs(int cur,int tar,int cand,int pre,int fir) {
	int hoge=0;
	while(S[cur].count(hoge) || hoge==cand) hoge++;
	if(R[cur]==tar) return (pre==-1 || pre==hoge) && (hoge!=fir);
	return dfs(R[cur],tar,hoge,pre,fir);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		E[x-1].push_back(i);
		R[i]=x-1;
	}
	
	queue<int> Q;
	MINUS(G);
	FOR(i,N) {
		in[i]=E[i].size();
		if(in[i]==0) Q.push(i);
	}
	while(Q.size()) {
		x=Q.front();
		Q.pop();
		G[x]=0;
		while(S[x].count(G[x])) G[x]++;
		
		y=R[x];
		in[y]--;
		S[y].insert(G[x]);
		if(in[y]==0) Q.push(y);
	}
	
	FOR(i,N) if(G[i]==-1) {
		int cand=0,pre=-1;
		for(j=0;cand<2;j++) {
			if(S[i].count(j)) continue;
			
			if(dfs(R[i],i,j,pre,j)) return _P("POSSIBLE\n");
			
			
			pre=j;
			cand++;
		}
	}
	_P("IMPOSSIBLE\n");
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n';
	FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	solve(); return 0;
}


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

int main(){
	int N, W;
	cin >> N >> W;
	int w[N], v[N];
	for(int i=0; i<N; i++){
		cin >> w[i] >> v[i];
	}
	ll dp[N][W+1];
	for(int i=0; i<=W; i++){
		if(i < w[0]){
			dp[0][i] = 0;
		}else{
			dp[0][i] = v[0];
		}
	}
	for(int i=1; i<N; i++){
		for(int j=0; j<=W; j++){
			if(j >= w[i]){
				dp[i][j] = max(v[i] + dp[i-1][j-w[i]], dp[i-1][j]);
			}else{
				dp[i][j] = dp[i-1][j];
			}
		}
	}
	cout << dp[N-1][W] << endl;
	return 0;
}

Measured memory_bytes: 78336
import java.math.BigInteger;
import java.util.*;
import java.util.stream.Collectors;

public class Main {
  public static void main(String[] args){
    BigInteger MOD = new BigInteger("1000000007");
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    List<BigInteger> a = new ArrayList<>();
    for (int i = 0; i < n; i++) {
      BigInteger tmp = new BigInteger(sc.next());
      a.add(tmp);
    }
    List<BigInteger> sumList = new ArrayList<>();
    for (int i = n - 1; i >= 0; i--) {
      sumList.add(BigInteger.ZERO);
    }
    BigInteger sum = BigInteger.ZERO;
    for (int i = n - 1; i >= 0; i--) {
      sum = sum.add(a.get(i)).remainder(MOD);
      sumList.set(i, sum);
    }
    BigInteger result = BigInteger.ZERO;
    for (int i = 0; i < n - 1; i++) {
      result = result.add(a.get(i).multiply(sumList.get(i + 1)).remainder(MOD)).remainder(MOD);
    }
    System.out.println(result);
  }
}


Measured memory_bytes: 80712
A =[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
k = int(input())
print(A[k-1])

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

#define ll long long
#define p_q priority_queue
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define str string
#define s_vec(data,name,vertical,horizontal) vector<vector<(data)>> (name)((vertical),vector<(data)>((horizontal)));


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

    ll co = b-a+1;

    int aj,bj;
    ll ans,stn;
    aj = a%2;
    bj = b%2;
    if(aj==1&&bj==1){
        co--;
        co /= 2;
        stn = a;
    }else if(aj==1&&bj==0){
        co -= 2;
        co /= 2;
        stn = a^b;
    }else if(aj==0&&bj==1){
        co /= 2;
        stn = -1;
    }else if(aj==0&&bj==0){
        co--;
        co /= 2;
        stn = b;
    }


    if(co%2==1){
        if(stn!=-1){
            ans = stn ^ 1;
            cout<<ans;
        }else{
            cout<<1;
        }
    }else{
        if(stn!=-1){
            ans = stn ^ 0;
            cout<<ans;
        }else{
            cout<<0;
        }
    }




}

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

int fa[2005];
int b[2005],a[2005];

int find(int x,int &cnt,int y)
{
	b[cnt++] = x;
	if(x==y) return 1;
	if(x==fa[x]) return 0;
	return find(fa[x],cnt,y);
}

int main()
{
	int n,m; cin>>n>>m;
	int cnt = 0;
	int ans = INT_MAX;
	for(int i=0;i<=n;++i) fa[i] = i;
	for(int i=0;i<m;++i)
	{
		int u,v;
		cin>>u>>v;
		cnt = 0;
		if(find(v,cnt,u))
		{
			if(cnt<ans)
			{
				ans = cnt;
				for(int i=0;i<cnt;++i) a[i] = b[i];
			}
		}
		else fa[u] = v;
		
	}
	if(ans==INT_MAX) {
		cout<<"-1"<<"\n"; return 0;
	}
	cout<<ans<<"\n";
	for(int i=0;i<ans;++i) cout<<a[i]<<"\n";
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log,gcd
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')

#Pythonを用いる場合
#numpy 1.18.0, scipy 1.4.1, scikit-learn 0.22, numba 0.47.0, networkx 2.4
 
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n=ii()
arr=limii()
ans=0
for i in range(n):
    if i%2==0 and arr[i]%2==1:
        ans+=1
print(ans)

Measured memory_bytes: 37640
n, m = map(int, input().split())
array = [list(map(int, input().split())) for i in range(m)]
result = [1, n]
for el in array:
    if el[0] > result[1] or result[0] > el[1]:
        result = [1, 0]
        break
    else:
        work = sorted(result + el)
        result = [work[1], work[2]]
print(result[1]-result[0]+1)

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

namespace ConsoleApp2
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            var an = Console.ReadLine().Split().Select(s => int.Parse(s)).OrderByDescending(x=>x).ToArray();
            var ans = 0;
            var sub = 0;
            for(var i=0;i<N;i++)
            {
                if (i % 2 == 0) ans += an[i];
                else sub += an[i];
            }
            Console.WriteLine(ans-sub);
        }
    }
}

Measured memory_bytes: 13396
#include <iostream>
#include <cmath>
#include <set>
#include <string>

using namespace std;
using LLONG = long long;

int main()
{
    int A, B, C, X;
    cin >> A >> B >> C >> X;
    int count = 0;
    for (int a = 0; a <= A; ++a)
    {
        for (int b = 0; b <= B; ++b)
        {
            for (int c = 0; c <= C; ++c)
            {
                int price = 500 * a + 100 * b + 50 * c;
                if (price == X) ++count;
            }
        }
    }
    cout << count << endl;
    return 0;
}

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

int main(){
  long long M,d,c,a=0,b=0,e=0;cin>>M;
  for(int i=0;i<M;i++){
    scanf("%lld%lld",&d,&c);
    b+=d*c;
    a+=c;
  }
  while(b/10){
    a+=b/10;
    b=b%10+b/10;
  }
  cout<<--a<<endl;
}

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

int N, A, B;

int main() {
	cin >> N; assert(1 <= N && N <= 2);
	if (N == 1) cout << "Hello World" << endl;
	else { cin >> A >> B; assert(1 <= A && A <= 9); assert(1 <= B && B <= 9); cout << A + B << endl; }
	return 0;
}

Measured memory_bytes: 256
x,n = map(int,input().split())

if n == 0:
    print (x)
    exit ()

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

for i in range(201):
    if not x-i in p:
        print (x-i)
        exit ()
    elif not x+i in p:
        print (x+i)
        exit ()
    else:
        pass


Measured memory_bytes: 9004
#include <stdio.h>
#include <algorithm>
using namespace std;

int main() {
    int a, b, c, d, e, f;
    scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f);
    int x = a * 100, y = 0;
    for (int i = 0; i <= f; i += a * 100)
        for (int j = 0; j + i <= f; j += b * 100)
        if (i + j <= f) {
            for (int k = 0; k + i + j <= f && 100 * k <= e * (i + j); k += c) {
                int l = min((e * (i + j) / 100 - k), f - i - j - k) / d * d;
                int n_x = i + j + k + l, n_y = k + l;
                if (n_y * x > n_x * y) {
                    y = n_y;
                    x = n_x;
                }
            }
        }
    printf("%d %d\n", x, y);
    return 0;
}


Measured memory_bytes: 128
n,q = map(int, input().split())
s = input()

a = [0 for i in range(n+1)]

for i in range(n):
    if s[i:i+2]=='AC':
        a[i+1]=a[i]+1
    else:
        a[i+1]=a[i]

for i in range(q):
    l,r = map(int, input().split())
    print(a[r-1]-a[l-1])


Measured memory_bytes: 55328
#include <cstdio>
#include <cstring>
#include <deque>
#define maxn 100005
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
inline void read(int& x)
{	char c=getchar();x=0;int y=1;
	while(c<'0'||c>'9'){if(c=='-') y=-1;c=getchar();}
	while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	x*=y;
}
deque<int>q;
int dis[maxn],n;
inline void bfs()
{	q.push_front(1);mem(dis,0x3f);dis[1]=0;
	while(!q.empty())
	{	int u=q.front(),t1=(u*10)%n,t2=(u+1)%n;q.pop_front();
		if(dis[t1]>dis[u])
		{	dis[t1]=dis[u];
			q.push_front(t1);
		}
		if(dis[t2]>dis[u]+1)
		{	dis[t2]=dis[u]+1;
			q.push_back(t2);
		}
	}
}
int main()
{       read(n);bfs();
	printf("%d",dis[0]+1);
	return 0;
}

Measured memory_bytes: 816
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
#include <stdio.h>

//#include <map>

using namespace std;

int main()
{
	string str;
	//str = "5 4 2 4 1";
	getline(cin, str);

	vector<string> vStr;

	while (str.find(' ') != -1)
	{
		vStr.push_back(str.substr(0, str.find(' ')));
		str.erase(0, str.find(' ') + 1);
	}
	vStr.push_back(str);

	int W, H, x, y, r;
	W = stoi(vStr[0]);
	H = stoi(vStr[1]);
	x = stoi(vStr[2]);
	y = stoi(vStr[3]);
	r = stoi(vStr[4]);

	bool judge = true;

	for (int i = -1; i < 2; i++)
	{
		if (x + i * r >= 0 && x + i * r <= W &&
			y + i * r >= 0 && y + i * r <= H)
		{

		}
		else
		{
			judge = false;
		}
	}

	string ans;
	judge ? ans = "Yes" : ans = "No";
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1212
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define codefor int test;scanf("%d",&test);while(test--)
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define yn(ans) if(ans)printf("Yes\n");else printf("No\n")
#define YN(ans) if(ans)printf("YES\n");else printf("NO\n")
#define vector2d(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__))
#define umap unordered_map
#define uset unordered_set
using namespace std;
using ll = long long;
const int MOD=1000000007;
//入力系
void scan(int& a){scanf("%d",&a);}
void scan(long long& a){scanf("%lld",&a);}
template<class T> void scan(T& a){cin>>a;}
template<class T> void scan(vector<T>& vec){for(auto&& it:vec)scan(it);}
void in(){}
template <class Head, class... Tail> void in(Head& head, Tail&... tail){scan(head);in(tail...);}
//出力系
void print(const int& a){printf("%d",a);}
void print(const long long& a){printf("%lld",a);}
void print(const double& a){printf("%.15lf",a);}
template<class T> void print(const T& a){cout<<a;}
template<class T> void print(const vector<T>& vec){if(vec.empty())return;print(vec[0]);for(auto it=vec.begin();++it!= vec.end();){putchar(' ');print(*it);}}
void out(){putchar('\n');}
template<class T> void out(const T& t){print(t);putchar('\n');}
template <class Head, class... Tail> void out(const Head& head,const Tail&... tail){print(head);putchar(' ');out(tail...);}
//デバッグ系
template<class T> void dprint(const T& a){cerr<<a;}
template<class T> void dprint(const vector<T>& vec){if(vec.empty())return;cerr<<vec[0];for(auto it=vec.begin();++it!= vec.end();){cerr<<" "<<*it;}}
void debug(){cerr<<endl;}
template<class T> void debug(const T& t){dprint(t);cerr<<endl;}
template <class Head, class... Tail> void debug(const Head& head, const Tail&... tail){dprint(head);cerr<<" ";debug(tail...);}
ll intpow(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans *= a; a *= a; b /= 2; } return ans; }
ll modpow(ll a, ll b, ll p){ ll ans = 1; while(b){ if(b & 1) (ans *= a) %= p; (a *= a) %= p; b /= 2; } return ans; }

int main(){
    INT(n);
    vector<ll> vec(n),vec2(n);
    int zero=0,minus=0;
    ll sum=0;
    rep(i,n){
        in(vec[i]);
        if(vec[i]==0)zero=1;
        else if(vec[i]<0){
            minus++;
        }
        sum+=abs(vec[i]);
        vec2[i]=abs(vec[i]);
    }
    if(minus%2==0||zero==1){
        out(sum);
    }else{
        sort(all(vec2));
        out(sum-2*vec2[0]);
    }
}

Measured memory_bytes: 4820
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>


using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair
#define mt make_tuple

class BipartiteMatching {
public:
    // V1, V2: 左側・右側それぞれの頂点数
    BipartiteMatching(int V1, int V2) : m_V1(V1), m_V2(V2) {
        m_G.resize(m_V1 + m_V2);
        m_match.resize(m_V1 + m_V2, -1);
        m_used.resize(m_V1 + m_V2);
    }
    // 左側の頂点と右側の頂点の間に辺を張る
    void add_edge(int v1, int v2) {
        v2 += m_V1;
        m_G[v1].push_back(v2);
        m_G[v2].push_back(v1);
    }
    // 二部グラフの最大マッチングを求める
    int bipartite_matching() {
        int res = 0;
        fill(ALL(m_match), -1);
        REP(v, m_V1 + m_V2) {
            if (m_match[v] < 0) {
                fill(ALL(m_used), 0);
                if (dfs(v)) ++res;
            }
        }
        return res;
    }
    void debug_print() {
        REP(i, SIZE(m_match)) {
            cout << "v" << i << " ";
            auto m = m_match[i];
            if (m == -1) cout << "has no pair" << endl;
            else cout << "is matched with " << m << endl;
        }
    }
    bool has_matching(int v1, int v2) { return m_match[v1] == m_V1 + v2; }
private:
    bool dfs(int v) {
        m_used[v] = true;
        for(auto u: m_G[v]) {
            int w = m_match[u];
            if (w < 0 || !m_used[w] && dfs(w)) {
                m_match[v] = u;
                m_match[u] = v;
                return true;
            }
        }
        return false;
    }
    int m_V1;
    int m_V2;
    vector<vector<int>> m_G; // グラフの隣接リスト表現
    vector<int> m_match; // マッチングのペア
    vector<char> m_used; // DFSですでに調べたかのフラグ
};


int main(void)
{
    cin.sync_with_stdio(false);
    int N;
    cin >> N;
    BipartiteMatching bm(N, N);
    vector<pair<int, int>> reds(N);
    vector<pair<int, int>> blues(N);
    REP(n, N) cin >> reds[n].first >> reds[n].second;
    REP(n, N) cin >> blues[n].first >> blues[n].second;
    REP(n1, N) {
        REP(n2, N) {
            auto& r = reds[n1];
            auto& b = blues[n2];
            if (r.first < b.first && r.second < b.second) {
                bm.add_edge(n1, n2);
            }
        }
    }
    cout << bm.bipartite_matching() << endl;
    return 0;
}


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

#define ll            long long
#define pb            push_back
#define si            set <int>
#define F             first
#define S             second
#define mii           map<int ,int >
#define msi           map<string,int >
#define mis           map<int , string>
#define fr(i,a,b)     for(int  i=a;i<=b;i++)
#define loop(i,n)     for(int i=0;i<n;i++)
#define all(v)        v.begin(),v.end()
#define vi            vector<int >
#define vii           vector<pair<int , int >>
#define vs            vector<string>
#define sz(x)         (int )x.size()
#define M             1000000007
#define mp            make_pair
#define input(arr,n)  loop(i,n) cin>>arr[i]
#define output(arr,n) loop(i,n) cout<<arr[i]<<" "
#define mod           998244353
#define sof           sizeof
using namespace std;
int gcd(int a,int b){
  if(b==0)return a;
  return gcd(b,a%b);
}

bool isPrime(int num){
    
    if(num==2) return true;
    if(num<2 || num%2==0) return false;
    for(int i = 3; i*i <=num; i+=2) {
       if(num % i == 0) {
          
          return false;
       }
    }
    return true;
   
}

bool comp(const pair<int,int> &a,const pair<int,int> &b){
  return a.F>b.F;
}



void solve(){
  
  int n,W;
  cin>>n>>W;
  int w[n+1]; ll v[n+1];
  fr(i,1,n) cin>>w[i]>>v[i];
  ll dp[n+1][W+1];
  loop(i,n+1){
    loop(j,W+1){
      if(i==0 || j==0 ) dp[i][j]=0;
      else{
        dp[i][j]=dp[i-1][j];
        if(j>=w[i]){
          dp[i][j]=max( dp[i][j], dp[i-1][j-w[i]] + v[i] );
        }
      }
    }
  }
  ll ma=0;
  loop(i,W+1){
    ma=max(ma, dp[n][i]);
  }
  cout<<ma;

}




signed main()   
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); 
  cout.tie(0);
  #ifndef ONLINE_JUDGE
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout); 
  #endif  

  int t;
  t=1;
  //cin>>t;
  loop(i,t){

      solve();
      if(i<t-1) cout<<"\n";
  }

  
  
  //directed graph
    



}
  


  



Measured memory_bytes: 82376
#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define For(i, a, b) for (int i = int(a); i < int(b); i++)
#define Dor(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define Foz(i, a) For(i, 0, a)
#define Doz(i, a) Dor(i, 0, a)
#define Trav(e, v) for (auto& e : v)
#define pb push_back
#define mp make_pair
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vii = vector<ii>;
template <typename T> bool ckmin (T& a, T b) { return (b < a) ? a = b, 1 : 0; }
template <typename T> bool ckmax (T& a, T b) { return (b > a) ? a = b, 1 : 0; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#ifdef XVENOM
	#define errp(...) fprintf(stderr, __VA_ARGS__)
	#define dbg(...) errp("[%s]: ", #__VA_ARGS__), dbg_str(__VA_ARGS__)
#else
	#define errp(...)
	#define dbg(...)
#endif
template <typename U, typename V> string to_string (pair<U, V>);
string to_string (string& e) { return "\"" + e + "\""; }
string to_string (char e) { return "\'" + string(1, e) + "\'"; }
string to_string (bool e) { return e ? "true" : "false"; }
template <typename T> string to_string (T e) {
	string s = "[ ";
	for (auto& x : e) s += to_string(x) + " ";
	return s + "]";
}
template <typename U, typename V> string to_string (pair<U, V> e) {
	return "(" + to_string(e.first) + ", " + to_string(e.second) + ")";
}
void dbg_str () { errp(" \n"); }
template <typename U, typename... V> void dbg_str (U u, V... v) {
 	errp(" %s", to_string(u).c_str()); dbg_str(v...);
}
/* --- */
int n, ans = 0;
int x[] = {7, 3, 5};

bool valid (int num) {
	if (num > n) return false;
	int has[] = {0, 0, 0};
	while (num) {
		int p = num % 10;
		num /= 10;
		Foz(i, 3) if (p == x[i]) has[i] = 1;
	}
	return has[0] && has[1] && has[2];
}

void calc (int d, int num) {
	if (d == 0) {
		ans += valid(num);
		return;
	}
	Foz(i, 3) calc(d - 1, 10 * num + x[i]);
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	/* --- */
	cin >> n;
	For(i, 1, 10) calc(i, 0);
	cout << ans << '\n';
}



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

int main() {
  char c;
  scanf("%c", &c);
  if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
    printf("vowel");
  else
    printf("consonant");
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include<stdio.h>
#include <math.h>
#include<vector>
#include <algorithm>
#include<cassert>
using namespace std;
int main(void){
    int k,i,temp,sum=0;
    vector<int> a;
    for(i = 0; i < 3; i++){
        cin >> temp;
    a.push_back(temp);
    }
    auto maxitr = max_element(a.begin(),a.end());
    cin  >> k;
    for(auto itr = a.begin(); itr != a.end(); ++itr){
        if(itr == maxitr)
        continue;
    else{
        sum += *itr;
    }
    }
    sum += (int)(*maxitr)*pow(2,k);
    cout << sum << "\n";
}


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

def func(n, a, b):
    if n < 2:
        if (n == 1) and (a == b):
            return 1
        else:
            return 0
    if a > b:
        return 0
    return 1 + (n - 2) * (b - a)

print(func(n, a, b))

Measured memory_bytes: 2940
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int count = 0, space, work;
        boolean judge;
        char[] s = sc.next().toCharArray();
        for(int i=0; i<n; i++){
            char[] s2 = sc.next().toCharArray();
            judge = false;
            for(int j=0; j<s2.length; j++){
                if(s[0]==s2[j]){              
                    for(int k=j+1; k<s2.length; k++){
                        if(s[1]==s2[k]){                          
                            space = k-j;
                            if(s2.length<=space*(s.length-1)+j) break;
                            work = k;                           
                            for(int l=2; l<s.length; l++){
                                work+=space;
                                if(s2[work]!=s[l]) break;
                                if(l==s.length-1){
                                    count++;
                                    judge = true;
                                }
                            }
                            if(judge==true) break;
                        }
                    }
                }
                if(judge==true) break;
            }
        }         
        System.out.println(count);
    }
 
}
 

Measured memory_bytes: 27624
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <iomanip>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
#ifdef _DEBUG_
#define dump(val) cerr << __LINE__ << ":\t" << #val << " = " << (val) << endl
#else
#define dump(val)
#endif

using namespace std;

typedef long long int ll;

template<typename T>
vector<T> make_v(size_t a, T b) {
    return vector<T>(a, b);
}

template<typename... Ts>
auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v(ts...))>(a, make_v(ts...));
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<double> p(N);
    REP(i, 0, N) {
        cin >> p[i];
    }

    auto dp = make_v(N + 1, N + 5, 0.0);
    dp[0][0] = 1.0;
    REP(i, 0, N) {
        REP(j, 0, N + 1) {
            dp[i + 1][j + 1] += dp[i][j] * p[i];
            dp[i + 1][j] += dp[i][j] * (1 - p[i]);
        }
    }

    double ans = 0.0;
    REP(i, N / 2 + 1, N + 1) {
        ans += dp[N][i];
    }

    cout << fixed << setprecision(20) << ans << endl;
    return 0;
}


Measured memory_bytes: 70784
#include<bits/stdc++.h>
using namespace std;
long gcd(long a, long b){
  if(a < b){
    int temp = a;
    a = b;
    b = temp;
  }
  if(a%b==0)return b;
  return  gcd(a-b, b);
}

int main(){
  long long K;
  cin >> K;
  long long sum=0;
  for(int i=1;i<=K; i++ ){
    for(int j=1; j<=K; j++){
      for(int k=1; k<=K; k++){
        sum+= gcd(i,gcd(j,k));
      }
    }
  }
  cout << sum << endl;
  return 0;
}

Measured memory_bytes: 3632
package main

import (
	"fmt"
)

func main() {
	var a, b int
	fmt.Scanf("%d %d", &a, &b)

	prod := a * b

	if prod%2 == 0 {
		fmt.Printf("%s \n", "Even")
	} else {
		fmt.Printf("%s \n", "Odd")
	}

}


Measured memory_bytes: 512
import sys
sys.setrecursionlimit(10**7)
def dfs(v,p):
    deg[v]=len(G[v])
    res=0
    dp[v]=[0]*deg[v]
    for i in range(deg[v]):
        nv,c=G[v][i]
        if nv==p:
            pi[v]=i
            continue
        dp[v][i]=dfs(nv,v)+c
        res=max(res,dp[v][i])

    return res
def reroot(v,res_p,p):
    if p!=-1:
        dp[v][pi[v]]=res_p
        h[v]=max(dp[v])
    dpl=[0]*(deg[v]+1)
    dpr=[0]*(deg[v]+1)
    for i in range(deg[v]):
        dpl[i+1]=max(dpl[i],dp[v][i])
    for i in reversed(range(deg[v])):
        dpr[i]=max(dpr[i+1],dp[v][i])
    for i in range(deg[v]):
        nv,c=G[v][i]
        if nv==p:
            continue
        reroot(nv,max(dpl[i],dpr[i+1])+c,v)

n=int(input())
G=[[] for i in range(n)]
dp=[[] for i in range(n)]
deg=[0]*n
pi=[-1]*n

for i in range(n-1):
    s,t,w=map(int,input().split())
    G[s].append((t,w))
    G[t].append((s,w))
z=dfs(0,-1)
h=[0]*n
h[0]=z
reroot(0,0,-1)
print(*h,sep='\n')


Measured memory_bytes: 25424
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<set>

using namespace std;
using ll = long long;


int main() {
    ll n,ans=0;
    cin >> n;
    vector<ll> a(3*n);
    for(ll i=0;i<3*n;i++) cin >> a[i];
    sort(a.begin(),a.end());
    for(ll i=0;i<n*2;i+=2){
        ans+=a[3*n-i-2];
    }
    cout << ans << endl;
	return 0;
}

Measured memory_bytes: 2560
//#define _CRT_SECURE_NO_WARNINGS
//#include <bits/stdc++.h>
#include "bits/stdc++.h"

#define rep(i,n) for(ll (i)=0;(i)<(ll)(n);(i)++)
#define all(x) (x).begin(),(x).end()

#define MOD 1000000007LL
#define INF (1LL<<60LL)
#define int long long
#define MAX_N (100001)
typedef long long ll;

using namespace std;



signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int k, a, b; cin >> k >> a >> b;
	int ans = false;
	for (int i = a; i <= b; i++) {
		if (i % k == 0) ans = true;
	}
	if (ans) cout << "OK" << endl;
	else cout << "NG" << endl;
}


Measured memory_bytes: 3652