akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include<algorithm>
#include <cstdlib>
#include <cmath>
#include <regex>

using namespace std;
int f(int x) {
	if (x % 2 == 0) return 1 + f(x / 2);
	else return 0;
}
int main()
{


	int n, k;
	cin >> n >> k;
	int l[50] = {};
	for (int i = 0; i < n; i++) {
		cin >> l[i];
	}
	sort(l, l + n);
	int ans = 0;
	for (int i = 0; i < k;i++) {
		ans += l[n - i-1];
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
N = int(input())
x = int(N/4)
y = int(N/7)
cnt = 0

if(N != 0):
    for i in range(x+1):
        for j in range(y+1):
            if(i*4 + j*7 == N):
                cnt = cnt + 1
    answer = 'Yes' if (cnt > 0) else 'No'
    print(answer)
else:
    print("No")

Measured memory_bytes: 3060
#include "bits/stdc++.h"

using namespace std;
using ll = long long;
using ull = unsigned long long;

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

const ll MOD = 1e9 + 7;
const ll INF = 9e18;
const double eps = -1e10;
const int di[4] = { 1,0,-1,0 }, dj[4] = { 0,1,0,-1 };

#define ALL(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define fr first
#define sc second


ll n, a[51], ans;

bool check() {
	bool res = 1;
	for (int i = 0;i < n;i++) {
		if (a[i] >= n)res = false;
	}
	return res;
}

int main() {
	cin >> n;
	for (int i = 0;i < n;i++)cin >> a[i];
	while (!check()) {
		ll cnt = 0;
		for (int i = 0;i < n;i++) {
			if (a[i] >= n) {
				ll c = a[i] / n;
				cnt += c;
				a[i] %= n;
				a[i] -= c;
			}
		}
		for (int i = 0;i < n;i++) {
			a[i] += cnt;
		}
		ans += cnt;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <complex>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#include <functional>
#include <cstring>
#include <regex>
#include <random>
#include <cassert>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, s, n) for (int i = (s); i < (int)(n); i++)
#define revrep(i, n) for (int i = (n); i >= 0; i--)
#define revrepr(i, a, b) for (int i = (a); i >= b; i--)
#define debug(x) cerr << #x << ": " << x << "\n"

using ll = long long;
using P = pair<int, int>;

const long long MOD = 1e9+7;

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

template<class T>
istream& operator >>(istream &is, vector<T> &v) {
    for (int i = 0; i < (int)v.size(); i++) cin >> v.at(i);
    return is;
}

int calc_min_time(int l, int r) {
    if (r <= 0 || 0 <= l) return max(abs(l), abs(r));
    return r - l + min(abs(l), abs(r));
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> x(n);
    cin >> x;
    
    int ans = 1e9;
    rep(i, n - k + 1) chmin(ans, calc_min_time(x.at(i), x.at(i + k - 1)));
    cout << ans << endl;
}

Measured memory_bytes: 640
import java.io.PrintWriter;
        import java.util.ArrayList;
        import java.util.Collections;
        import java.util.List;
        import java.util.Scanner;

public class Main {
    static private Scanner scan = new Scanner(System.in);
    public static void main(String args[]) {
//        int int1 = Integer.parseInt(scan.next());
        String str1 = scan.next();
        String str2 = scan.next();
        String str3 = scan.next();
        int ans_int = 0;


        PrintWriter out = new PrintWriter(System.out);
        out.println(str1.substring(0,1)+ str2.substring(1,2) + str3.substring(2,3));
        out.flush();
        scan.close();
    }
}


Measured memory_bytes: 23380
#include <bits/stdc++.h>
using namespace std;
#define Hello ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define endl '\n'
ll solve(ll n)
{
    ll cntr = 0, lvl = 1;
    while(n)
    {
        cntr += lvl;
        n /= 2;
        lvl *= 2;
    }
    //cntr += lvl;
    return cntr;
}
int main()
{
    ll n;
    cin >> n;
    cout << solve(n);
    return 0;
}


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


int main()
{
	int N,K;
	cin>>N>>K;
	int i=1;
	while(K*i-(i-1)<N)
	{
		i++;
	}
	cout<<i<<endl;
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    char[] S = scanner.next().toCharArray();
    for (int i = S.length - 1; i >= 0; i --) {
      if (isEven(S, 0, i)) {
        System.out.println(i);
        return;
      }
    }
  }

  private static boolean isEven(char[] s, int head, int tail) {
    if (head >= tail) return false;
    if ((tail - head) % 2 != 0) return false;
    int mid = (tail - head) / 2 + head;
    for (int i = 0; i < mid - head; i++) {
      if (s[head + i] != s[mid + i]) return false;
    }
    return true;
  }
}


Measured memory_bytes: 21716
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>

using namespace std;

class Knapsack1 {
public:
        void solve(std::istream &in, std::ostream &out) {
                long long n, W;
                in >> n >> W;
                long long weight[n + 1];
                long long value[n + 1];
                for (int i = 1; i <= n; i++) {
                        in >> weight[i] >> value[i];
                }
                long long dp[n + 1][W + 1];
                memset(dp, 0, sizeof(dp));
                for (int i = 0; i <= n; i++) {
                        for (int j = 0; j <= W; j++) {
                                dp[i][j] = 0;
                                if (i - 1 >= 0)
                                        dp[i][j] = max(dp[i - 1][j], dp[i][j]);
                                if (i - 1 >= 0 && j - weight[i] >= 0){
                                        dp[i][j] = max(dp[i][j], dp[i - 1][j - weight[i]] + value[i]);
                                }
                        }
                }
                out << dp[n][W] << "\n";
        }
};

int main() {
        Knapsack1 solver;
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        std::istream &in(std::cin);
        std::ostream &out(std::cout);
        int t = 1;
        for (int i = 0; i < t; ++i) {
                solver.solve(in, out);
        }
        return 0;
}


Measured memory_bytes: 79232
import java.util.*;
import java.lang.Math;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
        int n = sc.nextInt();
      	int ds[] = new int[n+1];
      	int stack;
      	int count = 1;

      	for(int i = 0;i < n;i++) ds[i] = sc.nextInt();
      	ds[n] = 101;
      	Arrays.sort(ds);
      	stack = ds[0];
      	for(int i = 1;i < n;i++){
          if(stack != ds[i]){
            count++;
            stack = ds[i];
          }
        }
      
      	System.out.println(count);
	}
}

Measured memory_bytes: 36040
a, b, m = map(int, input().split())
rei = list(map(int, input().split()))
den = list(map(int, input().split()))
cup = [tuple(map(int, input().split())) for _ in range(m)]

ans = 10 ** 9
for x, y, c in cup:
    ans = min(ans, rei[x-1] + den[y-1] - c)
ans = min(ans, min(rei) + min(den))
print(ans)

Measured memory_bytes: 29032
#include <iostream>
#include <string>
using namespace std;

int main()
{
  int n;
  cin >> n;
  for (int i=0; i<n; i++)
  {
    int score = 0;
    int base = 0;
    int out_count = 0;
    while (true)
    {
      string event;
      getline(cin, event);
      if ( event == "HIT" )
      {
        if ( base == 3 )
        {
          score++;
        }
        else
        {
          base++;
        }
      }
      else if ( event == "HOMERUN" )
      {
        score += 1 + base;
        base = 0;
      }
      else if ( event == "OUT" )
      {
        out_count++;
        if ( out_count == 3 ) break;
      }
    } //  while(true)
    cout << score << endl;
  } //  for
}

Measured memory_bytes: 1212
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<map>
#include<bitset>
using namespace std;

typedef long long ll;
#define rep(i, n) for(int i = 0;i < (n);i++)
#define repr(i, n) for(int i = (n);i >= 0;i--)
#define repf(i, m, n) for(int i = (m);i < (n);i++)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1;} return 0;}
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
//////////////////////////////////////////////////

int main() {
    int r; cin >> r;
    cout << 3*r*r << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

class Phrase {
    public:
    int s,l,p;
    Phrase(int s,int l,int p) {

        this->s = s;
        this->l = l;
        this->p = p;
    }
    Phrase() {
        s=l=p=-1;
    }

};

int n;
Phrase phra[400];
int m;
int w[400];
int dp[400];

int main() {

    cin>>n;
    rep(i,n) {
        int s,l,p;
        cin>>s>>l>>p;
        phra[i] = Phrase(s,l,p);
    }
    cin>>m;
    rep(i,m) cin>>w[i];
    rep(i,400) dp[i]=-1;
    dp[0]=0;

    rep(i,n) {
        for(int j=phra[i].s;j<=phra[i].l;j++) {
            for(int k=j;k<400;k++) {
                dp[k] = max(dp[k],dp[k-j]+phra[i].p);
            }
        }
    }

    vector<int> ans;
    bool flag = false;
    
    rep(i,m) {
        int t = dp[w[i]];
        if(t < 0) flag=true;
        else ans.push_back(t);
    }
    if(flag) {
        cout<<"-1"<<endl;
        return 0;
    }

    rep(i,ans.size()) cout<<ans[i]<<endl;

    return 0;
}

Measured memory_bytes: 1232
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#include<cmath>
#include<math.h>
using namespace std;
int main(){
    long int a[200005],n,k;
    memset(a,0,sizeof(a));
    cin>>n>>k;
    for(long int i=0;i<n;i++){
    	cin>>a[i];
	}
    for(long int i=k;i<n;i++){
    	if(a[i]>a[i-k])cout<<"Yes"<<endl;
    	else cout<<"No"<<endl;
	}
    
    
    
    return 0;
}


Measured memory_bytes: 5152
#include <bits/stdc++.h>
using namespace std;
int main(){
    string S, T, U;
    cin >> S >> T;
    bool flag = false;
    U = S + 'z';
    if(U >=T && S < T) flag = true;
    if(flag){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
return 0;
}

Measured memory_bytes: 3628
#include <stdio.h>
#include <iostream>
#include <cstring>
typedef long long ll;
const int N=500005;
int n,D,q,d[N],arr[N];
ll mn[N];
using namespace std;

int main()
{
	#ifdef Kay
		freopen ("ARC072E.in","r",stdin);
		freopen ("ARC072E.out","w",stdout);
	#endif
	scanf ("%d %d",&n,&D);
	int i;
	for (i=1;i<=n;i++) scanf ("%d",&d[i]);
	arr[0]=D;
	for (i=1;i<=n;i++) arr[i]=min(arr[i-1],max(arr[i-1]-d[i],d[i]-arr[i-1]));
	mn[n+1]=1;
	for (i=n;i>=1;i--)
	if (mn[i+1]<=d[i]/2) mn[i]=mn[i+1];
	else mn[i]=mn[i+1]+d[i];
	scanf ("%d",&q);
	while (q--)
	{
		scanf ("%d",&i);
		if (arr[i-1]>=mn[i+1]) puts("YES");
		else puts("NO");
	}
	return 0;
}


Measured memory_bytes: 9728
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#define rep(i,n) for (int i = 0; i < (n); i++)
#define PI 3.141592653589793
using namespace std;
typedef long long ll;
template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}
int gcd(int a, int b){//ユークリッドの互除法
  if (a < b) gcd(b,a); //aの方がbよりでかいのが前提
  if (b == 0) return a; //aをbで割り切れたらreturn
  else gcd(b, a % b);
}
int lcm(int a, int b){
  return a / gcd(a,b) * b;
}
const int INF = 1<<30;
const int MOD = 1000000007;
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};

int main(){
  int n,k; cin >> n >> k;
  vector<int> v(n),s(n+1);
  
  rep(i,n){
    cin >> v[i];
    v[i]--;
  }
  rep(i,n){
    s[i+1] = (s[i] + v[i]) % k;
  }
  map<int,int> mp;
  queue<int> q;
  ll ans = 0;
  rep(i,n+1){
    ans += mp[s[i]];
    mp[s[i]]++;
    q.push(s[i]);
    if(q.size() == k){
      mp[q.front()]--;
      q.pop();
    }
  }
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 12032
n=int(input().strip())
tmp=n
n_dig=0
while tmp>0:
    n_dig+=1
    tmp//=10
c=0
for i in range(n_dig//2):
    c+=9*100**i
mod=n_dig%2
if mod:
    c+=n-10**(n_dig-1)+1
print(c)

Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define dump(x) cout << (x) << endl
typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;
typedef vector<int> V;

int main() {
  int a, b;
  cin >> a >> b;
  dump((a-1)*(b-1));
  return 0;
}


Measured memory_bytes: 256
//ABC178_B
#include <stdio.h>

int main(){
	long int a,b,c,d;
	long int tmp1=0,tmp2=0;
	
	scanf("%ld %ld %ld %ld",&a,&b,&c,&d);
	
	//条件 a<b c<d
	//すべてが正であったらb*dを出力
	//0も正と考える
	if(a>=0 && b>=0 && c>=0 && d>=0){
		printf("%ld",b*d);
	}
	
	//一つ負の数があったとする
	//条件よりaもしくはcのみ負の値の場合
	//aもしくはcだけ負だとすると、
	//数の大きいほうだけをかければいい(上と同じ)
	else if(a<0 && b>=0 && c>=0 && d>=0 || a>=0 && b>=0 && c<0 && d>=0){
		printf("%ld",b*d);
	}
	
	//2つ負の数があったとする
	//条件よりabが負の場合b*c
	//cdが負の場合a*d
	//acが負の場合、a*c　or c*dの大きいほうを出力
	else if(a<0 && b<0 && c>=0 && d>=0){
		printf("%ld",b*c);
	}
	else if(a>=0 && b>=0 && c<0 && d<0){
		printf("%ld",a*d);
	}
	else if(a<0 && b>=0 && c<0 && d>=0){
		tmp1 = a*c;
		tmp2 = b*d;
		if(tmp1 > tmp2){
			printf("%ld",tmp1);
		}
		else printf("%ld",tmp2);
	}
	
	//3つの負の数があったとする
	//条件よりabcが負の場合a*c
	//acdが負の場合a*c
	else if(a<0 && b<0 && c<0 && d>=0){
	printf("%ld",a*c);
	}
	else if(a<0 && b>=0 && c<0 && d<0){
	printf("%ld",a*c);
	}
	
	//4つの負の数があったとする
	//条件よりabcdが負の場合、a*c
	else if(a<0 && b<0 && c<0 && d<0){
	printf("%ld",a*c);
	}	
	
	return 0;
}


Measured memory_bytes: 1728
#include <cstdio>
#pragma warning(disable : 4996)
int Q, x, lc[500009], rc[500009], key[500009], cnt; char b[10];
void inorder(int pos) {
	if (lc[pos]) inorder(lc[pos]);
	printf(" %d", key[pos]);
	if (rc[pos]) inorder(rc[pos]);
}
void preorder(int pos) {
	printf(" %d", key[pos]);
	if (lc[pos]) preorder(lc[pos]);
	if (rc[pos]) preorder(rc[pos]);
}
int main() {
	scanf("%d", &Q);
	while (Q--) {
		scanf("%s", b);
		if (b[0] == 'i') {
			scanf("%d", &x);
			if (cnt == 0) key[cnt++] = x;
			else {
				int pos = 0;
				while (true) {
					if (x < key[pos]) {
						if (lc[pos]) pos = lc[pos];
						else {
							lc[pos] = cnt;
							key[cnt++] = x;
							break;
						}
					}
					else {
						if (rc[pos]) pos = rc[pos];
						else {
							rc[pos] = cnt;
							key[cnt++] = x;
							break;
						}
					}
				}
			}
		}
		else if (b[0] == 'f') {
			scanf("%d", &x);
			if (cnt == 0) puts("no");
			else {
				int pos = 0;
				while (key[pos] != x) {
					if (x < key[pos]) {
						if (lc[pos]) pos = lc[pos];
						else break;
					}
					else {
						if (rc[pos]) pos = rc[pos];
						else break;
					}
				}
				puts(x == key[pos] ? "yes" : "no");
			}
		}
		else {
			inorder(0); printf("\n");
			preorder(0); printf("\n");
		}
	}
	return 0;
}

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

int main(){
    int n, m, X, Y;
    cin >> n >> m >> X >> Y;

    vector<int> x(n), y(m);
    for(int i=0; i<n; i++){
        cin >> x[i];
    }
    for(int i=0; i<m; i++){
        cin >> y[i];
    }
    sort(x.begin(), x.end());
    sort(y.begin(), y.end());

    for(int z=X+1; z<=Y; z++){
        //cout << x[n-1] << " " << z << " " << y[0] << endl;
        if(x[n-1] < z && z <= y[0]){
            cout << "No War" << endl;
            return 0;
        }
    }
    cout << "War" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repb(i, n) for (int i = (n-1); i >= 0; i--)
#define rea(i, a, b) for (int i = (a); i < (b); i++)
#define reab(i, a, b) for (int i = (a)-1; i >= (b); i--)
#define ALL(a) (a).begin(),(a).end()
#define SZ(x) ((int)(x).size())
#define PRINT(V) for (auto v:(V)) {cerr << v << " ";} cerr << endl
#define dump(x) cerr << #x << " : " << (x) << endl
#define dump2(x, y) cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")" << endl
inline ll GCD(ll a, ll b){return b ? GCD(b, a % b) : a;}
const int MOD = 1000000007;
/* END OF TEMPLATE */

int main(){
    string s, t;
    cin >> s >> t;
    int sz = SZ(s);
    unordered_map<char, char> ch1;
    unordered_map<char, char> ch2;
    rep(i, sz){
        if(ch1.find(s[i]) == ch1.end()){
            ch1[s[i]] = t[i];
        }else if(ch1[s[i]] != t[i]){
            cout << "No" << endl;
            return 0;
        }
    }
    rep(i, sz){
        if(ch2.find(t[i]) == ch2.end()){
            ch2[t[i]] = s[i];
        }else if(ch2[t[i]] != s[i]){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 776
/// kazuki08
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
// #define int long long
typedef long long ll;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
#define ar array
//#define inf 1000000000
#define mod 1000000007
#define dmp(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl
#define fs first
#define sc second
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define mt make_tuple
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
    return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
    o<<"{";
    for(const T& v:vc) o<<v<<",";
    o<<"}";
    return o;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 1<<18;
int n,q,p[MAXN+1],val[MAXN+1],w[MAXN+1],done[MAXN];
ll dp[(1<<10)+1][200020];

signed main(){
IOS;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
  
  cin >> n;
  // n = (1<<18)-1;
  for(int i=1;i<=n;i++){
    cin >> val[i] >> w[i];
    // val[i] = rand()%100000 + 1;
    // w[i] = rand()%100000 + 1;
    if(i!=1){
      p[i] = i/2;
    }
  }
  for(int i=1;i<(1<<10);i++){
    vpi v;
    int cur = i;
    while(cur){
      v.pb({val[cur],w[cur]});
      cur/=2;
    }
    int N = v.size();
    for(int msk=0;msk<(1<<N);msk++){
      int W = 0;
      ll V = 0;
      for(int j=0;j<N;j++){
        if(msk&(1<<j)){
          W+=v[j].second;
          V+=v[j].first;
        }
        if(W>=100000)break;
      }
      if(W<=100000){
        dp[i][W] = max(dp[i][W],V);
      }
    }
    for(int W=1;W<=100000;W++){
      dp[i][W] = max(dp[i][W],dp[i][W-1]);
    }
    done[i] = 1;
  }
  cin >> q;
  // q = 100000;
  while(q--){
    int u,l;
    cin >> u >> l;
    // u = n;
    // l = rand()%100000;
    ll ans = 0;
    int cur = u;
    vpi v;
    while(!done[cur]){
      v.pb({val[cur],w[cur]});
      cur/=2;
      // cerr << cur << endl;
    }
    int N = v.size();
    for(int i=0;i<(1<<N);i++){
      int W = 0;
      ll V = 0;
      for(int j=0;j<N;j++){
        if(i&(1<<j)){
          W+=v[j].second;
          V+=v[j].first;
        }
        if(W>=l)break;
      }
      if(W<=l){
        ans = max(ans,V+dp[cur][l-W]);
      }
    }
    cout << ans << endl;
  }




return 0;
}
///....


Measured memory_bytes: 810708
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
  int n;
  int q,min_s=1000,c=0;
  cin >> n ;
  vector<int> v(n,0);
  for(int i=0;i<n;i++) cin >> v[i];
  sort(v.begin(),v.end(),greater<int>());
  for(int i=0;i<n;i++){
    if(min_s > v[i]){ c++; min_s = v[i];}
  }
  cout << c << endl;
} 


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, j, n) for (ll i = j; i < n; i++)
#define all(x) (x).begin(),(x).end()
#define INF (LLONG_MAX)
#define MOD (1000000007)
#define MAX (100000)
#define pii pair<int, int>

/////////////////////////////////////////////////////////

class XY{
public:
  ll x, y;
  XY() {x = y = 0;}
  XY(ll u, ll v) {x = u; y = v;}
};

template<typename T1, typename T2>
void chmin(T1 &a, T2 b) {if(a > b) a = b;}
template<typename T1, typename T2>
void chmax(T1 &a, T2 b) {if(a < b) a = b;}

template<typename T1, typename T2>
T1 mypow(T1 a, T2 n){
  if(n == 0) return 1;
  if(n == 1) return a;
  if(n % 2) return a * mypow(a, n - 1);
  T1 tmp = mypow(a, n / 2);
  return tmp * tmp;
}

template<typename T>
int BS(vector<T> V, int left, int right, T key){
  int mid = (left + right) / 2;
  if(V[mid] <= key) left = mid;
  else right = mid;
  if(right - mid == 1) return left;
  else return BS(V, left, right, key);
}

/////////////////////////////////////////////////////////

void Main(){
  ll S; cin >> S;
  ll a, b, c, d;
  a = 1000000000;
  d = S / a + 1;
  c = 1;
  b = a * d - S;
  
  if(S == 1000000000000000000){
    a = 1000000000;
    d = 1000000000;
    c = 0;
    b = 0;
  }
  cout << 0 << " " << 0 << " " << a << " " << b << " " << c << " " << d;
}

/////////////////////////////////////////////////////////

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

  Main();
}


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<queue>
#include<map>
#include<functional>
using namespace std;
int main(){
	bool flg[31] = {0};
	for(int i = 0; i < 28; i++){
		int a;
		scanf("%d",&a);
		flg[a] = true;
	}
	for(int i = 1; i <= 30; i++){
		if(!flg[i])printf("%d\n",i);
	}
	return 0;
}

Measured memory_bytes: 1188
#include <iostream>
#include <string>

using namespace std;

int main()
{
	int D, N;
	cin >> D >> N;
	if(N == 100) {
		N ++;
	}
	switch(D) {
		case 0:
			cout << N;
			break;
		case 1:
			cout << N * 100;
			break;
		case 2:
			cout << N * 10000;
			break;
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <set>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <limits>
#include <bitset>

typedef long long int lli;
#define rep(i,s,N) for(int i=s;i<N;i++)
#define MOD 1000000007
using namespace std;

int digits(int N)
{
	int ans = 0;
	while (N > 0) {
		N /= 10;
		ans++;
	}
	return ans;
}

int main(void)
{
	lli N; cin >> N;
	int root = sqrt(N);
	for (int i = root; i >= 1; i--) {
		if (N%i == 0) {
			int B = N / i;
			cout << digits(B) << endl;
			break;
		}
	}

	return 0;
}


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

using namespace std;

constexpr int TIMES = 6;

random_device rnd;
vector<int> random(int n) {
    vector<int> ret(n);
    for (int i = 0; i < n; i++) {
        ret[i] = rnd() % 1 + 1;
    }
    return ret;
}

vector<int> sim(vector<int> a) {
    int n = a.size();
    for (int i = 0; i < TIMES; i++) {
        int k = rnd() % n;
        for (int j : {-1, 1}) {
            int idx = (k + j + n) % n;
            a[k] += a[idx];
        }
    }
    return a;
}

long long solve(vector<int> as, vector<int> bs) {
    int n = as.size();
    priority_queue<pair<int, int>> que;
    for (int i = 0; i < n; i++) que.emplace(bs[i], i);
    long long cnt = 0;
    vector<bool> ok(n);
    while (!que.empty()) {
        auto top = que.top();
        que.pop();
        int v = top.first, i = top.second;
        assert(v == bs[i]);
        if (v < as[i]) {
            return -1;
        } else if (v == as[i]) {
            ok[i] = true;
            continue;
        }
        int yoko = 0;
        int nax = 0;
        for (int j : {-1, 1}) {
            int k = i + j;
            if (k < 0) k += n;
            if (k >= n) k -= n;
            yoko += bs[k];
            nax = max(nax, bs[k]);
        }
        if (v - yoko < as[i]) {
            return -1;
        }
        if (as[i] >= nax) {
            int dif = v - as[i];
            if (dif % yoko) {
                return -1;
            }
            cnt += dif / yoko;
            v -= dif;
            bs[i] = v;
            ok[i] = true;
            continue;
        }
        int dif = v - nax;
        int t = (dif + yoko - 1) / yoko;
        cnt += t;
        v -= yoko * t;
        if (v < as[i]) {
            return -1;
        }
        bs[i] = v;
        que.emplace(v, i);
    }
    return cnt;
}

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

    int n;
    cin >> n;

//    int n = 3;

    vector<int> as(n), bs(n);
    for (int i = 0; i < n; i++) cin >> as[i];
    for (int i = 0; i < n; i++) cin >> bs[i];

//    for (int _ = 0; _ < 10000; _++) {
//        vector<int> as = random(n);
//        vector<int> bs = sim(as);
//        int ret = solve(as, bs);
//        if (ret != TIMES) {
//            for (int a : as) {
//                cout << a << ' ';
//            }
//            cout << endl;
//            for (int b : bs) {
//                cout << b << ' ';
//            }
//            cout << endl;
//            assert(solve(as, bs) == TIMES);
//        }
//    }

    cout << solve(as, bs) << endl;
}

Measured memory_bytes: 5620
#include <iostream>
#include <fstream>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <unordered_set>
#include <bitset>

typedef long long ll;
using std::vector;
using std::string;
template<typename T> void ndarray(vector<T> &vec, int len) { vec.resize(len); }
template<typename T, typename... Args> void ndarray(vector<T> &vec, int len, Args... args) {
    vec.resize(len);
    for (auto &v : vec) ndarray(v, args...);
}

//////////////////////////////////////

//////////////////////////////////////

int main() {
    //std::ifstream in("0_normal_2");
    //std::cin.rdbuf(in.rdbuf());
    
    int N, M, Q;
    std::cin >> N >> M >> Q;
    
    //LとRの２次元の問題：二次元累積和
    vector<vector<int>> arr, res, q;
    ndarray(arr, N+1, N+1);
    ndarray(res, N+1, N+1);
    ndarray(q, Q, 2);
    
    for (int i = 0; i < M; i++) {
        int l, r;
        std::cin >> l >> r;
        arr[l][r] += 1;
    }
    //res[p][q] = (0, 0) ~ (p, q)までで含まれていたarrの累積和
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            res[i+1][j+1] = arr[i+1][j+1] + res[i+1][j] + res[i][j+1] - res[i][j];
        }
    }
    
    //arrの、(l,l) ~ (r,r)の和 = res[r][r]-res[l-1][r]-res[r][l-1]+res[l-1][l-1]
    for (int i = 0; i < Q; i++) {
        int l, r;
        std::cin >> l >> r;
        q[i] = {l, r};
    }
    //arrの、(l,l) ~ (r,r)の和 = res[r][r]-res[l-1][r]-res[r][l-1]+res[l-1][l-1]
    for (int i = 0; i < Q; i++) {
        int l, r;
        l = q[i][0];
        r = q[i][1];
        int ans = res[r][r] - res[l-1][r] - res[r][l-1] + res[l-1][l-1];
        std::cout << ans << std::endl;
    }
    
    return 0;
}


Measured memory_bytes: 8448
#include "bits/stdc++.h"
using namespace std;
 
// GNU C Compiler
//template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }
 
 
/*
--------------------------------------------
 
	type
 
--------------------------------------------
*/
using LL = long long;
using ULL = unsigned long long;
//using pair<T1, T2> = p12;
 
/*
--------------------------------------------
 
	container
 
--------------------------------------------
*/
#define PB emplace_back
#define MP make_pair 
#define SZ(a) int((a).size())
 
/*
--------------------------------------------
 
	repetition
 
--------------------------------------------
*/
#define MAX(a,b) (a>b)?a:b
#define MIN(a,b) (a>b)?b:a
#define REP(n) for(int i=0; i<n; i++)
#define REPj(n) for(int j=0; j<n; j++)
#define REPS(i,n) for(int i=0; i<(n); i++)
#define REPinit(a,n) for(int i=a; i<(n); i++)
#define REPinitj(a,n) for(int j=a; j<n; j++)
 
//algorithm
//#define SORT(c) sort((c).begin(),(c).end())
 
/*
--------------------------------------------
 
	constant
 
--------------------------------------------
*/
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
 
/*
 
	Optimizer
 
*/
//#pragma GCC optimize("Ofast")


/*
 
	Utility Algorithm
 
*/
template <typename T>
void swapAlgorithm(T& a, T& b) {
    T tmp = a;
    a = b;
    b = tmp;
}

LL euclideanAlgorithm(LL a, LL b) {
    LL a_tmp = a;
    LL b_tmp = b;

    if (a_tmp > b_tmp) {
        swapAlgorithm<LL>(a_tmp, b_tmp);
    }

    LL r = a_tmp % b_tmp;
    while (r != 0) {
        a_tmp = b_tmp;
        b_tmp = r;
        r = a_tmp % b_tmp;
    }
    return b_tmp;    
}

LL getLCM(LL a, LL b) {
    return (a * b)/(euclideanAlgorithm(a, b));
}

/*
  Code
*/

double eauclidDistance(pair<double, double>& x1, pair<double, double>& x2) {
  return sqrt((x1.first - x2.first) * (x1.first - x2.first) + (x1.second - x2.second) * (x1.second - x2.second));
}

void swap(int& a, int& b) {
  int tmp;
  tmp = a;
  a = b;
  b = tmp;
}

int main(int argc, char const *argv[])
{
  int a,b;
  cin >> a >> b;
  int ans = 0;

  if (a <= b) {
    ans = a;
  }
  else {
    ans = a-1;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void) {
	
	int P = 0;
	int A = 0;
	int B = 0;
	int C = 0;
	int D = 0;
	scanf("%d %d %d %d %d", &A, &B, &C, &D, &P);



	int X = A * P;
	int Y = B;
	int y = (P - C)*D + B;
	if (P <= C) {
		if (X >= Y) printf("%d\n",Y);
		else if(X < Y) printf("%d\n", X);
	}

	if (P > C) {
		if (X >= y)printf("%d\n", y);
	else if (X < y) printf("%d\n", X);
	}

	return 0;
}

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

## Library

import sys
from fractions import gcd
import math
from math import ceil,floor
import collections
from collections import Counter
import itertools
import copy

## input

# n=int(input())
# A,B,C,D=map(int, input().split())
# string = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]


S = input()

ans = 0
tmp = 0
for i in range(len(S)):
    if S[i] == "W":
        ans += i-tmp
        tmp += 1

print(ans)

Measured memory_bytes: 77904
def factorial(n):
    ans = 1
    for i in range(2, n + 1):
        ans = ans * i % 1000000007
    return ans

N,M = map(int, input().split())
mod = 10**9+7

if abs(N-M) > 1:
    print(0)
    exit()
p = factorial(min(N,M))
if N == M:
    print((p**2)*2%mod)
else:
    print(p**2*max(N,M)%mod)


Measured memory_bytes: 3060
in1 = [int(x) for x in input().strip().split()]

N = in1[0]
K = in1[1]

trees = [int(input()) for i in range(N)]
trees.sort()

ans = 10 ** 10
for i in range(0, N - K + 1):
	#print(trees[i+K-1], trees[i])
	ans = min(ans, trees[i+K-1] - trees[i])
	
print(ans)

Measured memory_bytes: 7384
K = int(input())
A,B = map(int,input().split())
Flag = True
if B-A >= K:
  Flag = False
i = A
while Flag == True and i<B+1 :
  if i%K == 0:
    Flag = False
  i += 1
if Flag == False:
  print('OK')
else:
  print('NG')

Measured memory_bytes: 9180
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
typedef pair<int,int> P;

const int di[]={-1,0,1,0};
const int dj[]={0,-1,0,1};

int main(){
  int h,w;
  cin >> h >> w;
  int sx,sy,gx,gy;
  cin >> sx >> sy;
  cin >> gx >> gy;
  vector<string> s(h);
  for(int i=0;i<h;++i) cin >> s[i];

  sx--;
  sy--;
  gx--;
  gy--;

  const int INF=1001001001;
  vector<vector<int>> dist(h,vector<int>(w,INF));
  deque<P> que;
  que.push_back(P(sx,sy));
  dist[sx][sy]=0;
  while(!que.empty()){
    int i=que.front().first;
    int j=que.front().second;
    int d=dist[i][j];
    que.pop_front();
    for(int dir=0;dir<4;++dir){
      int ni=i+di[dir];
      int nj=j+dj[dir];
      if(ni<0 || nj<0 || ni>=h || nj>=w)continue;
      if(s[ni][nj]=='#')continue;
      if(dist[ni][nj]<=d)continue;
      dist[ni][nj]=d;
      que.emplace_front(ni,nj);
    }
    for(int x=-2;x<=2;++x){
      for(int y=-2;y<=2;++y){
        int ni=i+x;
        int nj=j+y;
        if(ni<0 || nj<0 || ni>=h || nj>=w)continue;
        if(s[ni][nj]=='#')continue;
        if(dist[ni][nj]<=d+1)continue;
        dist[ni][nj]=d+1;
        que.emplace_back(ni,nj);
      }
    }
  }
  int ans=dist[gx][gy];
  if(ans==INF) ans=-1;
  cout << ans << endl;
  return 0;


}


Measured memory_bytes: 9448
l = []
for i in range(5):
    l.append(int(input()))
amari = []
for i in range(5):
    if 10-l[i]%10 == 10 :
        amari.append(0)
    else :
        amari.append(10-l[i]%10)
jikan = []
for i in range(5):
    if amari[i] == 10:
        jikan.append(l[i])
    else :
        jikan.append(l[i] + amari[i])

print(sum(jikan)-max(amari))


Measured memory_bytes: 9200
#include<bits/stdc++.h>
#define Rint register int
using namespace std;
typedef long long LL;
const int N = 103;
char s[N];
int n, k, ans, cnt, cnt1, cnt2;
bool flag = true;
int main(){
	scanf("%s%d", s + 1, &k); n = strlen(s + 1);
	for(Rint i = 2;i <= n;i ++) flag &= (s[i] == s[i - 1]);
	if(flag){printf("%lld", (LL) n * k >> 1); return 0;}
	for(Rint i = 1;i <= n;i ++){
		if(s[i] != s[i - 1]){
			if(!cnt1) cnt1 = cnt;
			else cnt2 = cnt;
			ans += (cnt >> 1); cnt = 1;
		}
		else ++ cnt;
	}
	if(!cnt1) cnt1 = cnt;
	else cnt2 = cnt;
	ans += (cnt >> 1);
	printf("%lld", 1ll * ans * k + (k - 1ll) * (s[1] == s[n] && (cnt1 & 1) && (cnt2 & 1)));
}

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

#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORd(i, a, b) for (int i = (a) ; i >= (b); i--)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define present(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define sp system("pause")
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const int MOD = (int) 1e9 + 7;
const int INF = (int) 1e9;
const ll LINF = (ll) 1e18;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;
const int N = (int) 1e5 + 10;
void TimeExecution() {
    cout << "\n\n===>> Time Execution: " << clock() / (double)1000 << " sec(s).";
}
int t;
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    /*
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif
    */
    int n;
    string s;
    cin >> n >> s;
    int ans = 0, x = 0;
    FOR(i, 0, n - 1)
    {
        if(s[i] == 'I') x++;
        else x--;
        ans = max(ans, x);
    }
    cout << ans;
    return 0;
}


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

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

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

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

int get_gcd(int n, int m) {
	if (n < m) swap(n, m);
	while (m) {
		swap(n, m);
		m %= n;
	}
	return n;
}

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

	int A, B, C, D;
	cin >> A >> B >> C >> D;

	A--;
	int na = A - A / C - A / D + A / (C*D / get_gcd(C, D));
	int nb = B - B / C - B / D + B / (C*D / get_gcd(C, D));

	cout << nb - na << endl;

	return 0;
}

Measured memory_bytes: 256
#k = int(input())
#s = input()
#a, b = map(int, input().split())
#s, t = map(str, input().split())
#l = list(map(int, input().split()))
#l = [list(map(int,input().split())) for i in range(n)]
#a = [list(input()) for _ in range(n)]


h,w = map(int, input().split())
a = [list(input()) for _ in range(h)]

for i in range(h+2):
    for j in range(w+2):
        if (i == 0 or i == h+1):
            print("#", end="")
        else:
            if (j == 0 or j == w+1):
                print("#", end="")
            else:
                print(a[i-1][j-1], end="")
    print("")





Measured memory_bytes: 9168
//#include <bits/stdc++.h>
#include <iostream>
#include <map>
#include <cmath>
#include <ios>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <stack>
#include <numeric>
//#include <windows.h>
using namespace std;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;
template<class T> using VVV = V<VV<T>>;
template<class T> using G = greater<T>;
template<class T1, class T2> using P = pair<T1, T2>;
using I = int;
using D = double;
using B = bool;
using C = char;
using S = string;
using LL = long long;
using LD = long double;
using ULL = unsigned long long;
using PII = P<I, I>;
using VPII = V<PII>;
using PLL = P<LL, LL>;
using VPLL = V<PLL>;
using VI = V<I>;
using VVI = VV<I>;
using VLL = V<LL>;
using VVLL = VV<LL>;
using VC = V<C>;
using VVC = VV<C>;
using VS = V<S>;
using VVS = VV<S>;
using VB = V<B>;
using VVB = VV<B>;
#define REP(type, i, n) for (type i = 0; i < (type)(n); ++i)
#define REP2(type, i, m, n) for (type i = (m); i < (type)(n); ++i)
#define REPR(type, i, n) for (type i = (n)-1; i >= 0; --i)
#define REPR2(type, i, m, n) for (type i = (n)-1; i >= (m); --i)
#define REPx(x, a) for(auto x : a)
#define ALL(a) a.begin(), a.end()
#define SORT(a) sort(ALL(a))
#define SORTR(a, type) sort(ALL(a), G<type>())
#define REVERSE(a) reverse(ALL(a))
#define SIZE(a, type) ((type)(a).size())
#define bit_search(bit, n) REP(LL, bit, 1LL<<(n))
#define bit_check(bit, i) ((bit>>(i)) & 1)
#define setpre(n) fixed << setprecision((n))
#define UNIQUE(a) do {SORT(a); (a).erase(unique(ALL(a)), (a).end());} while(0)
#define MAX(a) *max_element(ALL(a))
#define MIN(a) *min_element(ALL(a))
#define bisect_left(a, x) lower_bound(ALL(a), (x)) - a.begin()
#define bisect_right(a, x) upper_bound(ALL(a), (x)) - a.begin()
#define INPUT(a) REPx(&x, a) cin >> x;
#define INPUTP(a) REPx(&x, a) cin >> x.first >> x.second;
#define OUTPUT_PERMUTATION(n) do{VI v(n); iota(ALL(v), 1); do{REPx(x, v) cout << x << " "; ENDL} while(next_permutation(ALL(v)));} while(0);
#define MAKE_PERMUTATION(n, PER) do{VVI a(fact(n), VI(n)); int idx = 0; VI v(n); iota(ALL(v), 1); do{REP(roop, n) a[idx][roop] = v[roop]; idx++;} while(next_permutation(ALL(v))); PER = a;} while(0); // int fact(), VVI PERを宣言しておく、n=10が限界(500 ms)
#define ENDL cout << endl;

template<class T> using PRIORITY_QUEUE = priority_queue< T, V<T>, G<T> >;

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

const int INF = 2e9;
const LL MOD = 1e9 + 7;

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N, W;
  cin >> N >> W;
  VI v(N), w(N);
  REP(int, i, N) cin >> v[i] >> w[i];
  VVI dp(N+1, VI(W+1, 0));
  REP(int, i, N) REP(int, j, W+1)
  {
    dp[i+1][j] = dp[i][j];
    if (j - w[i] >= 0) chmax(dp[i+1][j], dp[i+1][j-w[i]]+v[i]);
  }
  cout << dp[N][W] << endl;

  return 0;
}


Measured memory_bytes: 6820
#pragma region template
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vld = vector<ld>;
using vvld = vector<vld>;
using vvvld = vector<vvld>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
template <typename T>
using pqrev = priority_queue<T, vector<T>, greater<T>>;
#define rep(i, n) for (ll i = 0, i##_end = (n); i < i##_end; i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repr(i, a, b) for (ll i = (a), i##_end = (b); i < i##_end; i++)
#define reprb(i, a, b) for (ll i = (b)-1, i##_end = (a); i >= i##_end; i--)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((ll)(x).size())
//*
constexpr ll MOD = 1e9 + 7;
/*/
constexpr ll MOD = 998244353;
//*/
constexpr ll INF = 1e+18;
constexpr ld EPS = 1e-12L;
constexpr ld PI = 3.14159265358979323846L;
constexpr ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }
constexpr ll LCM(ll a, ll b) { return a / GCD(a, b) * b; }
template <typename S, typename T>
constexpr bool chmax(S &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename S, typename T>
constexpr bool chmin(S &a, const T &b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
#ifdef OJ_LOCAL
#include "dump.hpp"
#else
#define dump(...) ((void)0)
#endif
template <typename T>
bool print_(const T &a) {
  cout << a;
  return true;
}
template <typename T>
bool print_(const vector<T> &vec) {
  for (auto &a : vec) {
    cout << a;
    if (&a != &vec.back()) {
      cout << " ";
    }
  }
  return false;
}
template <typename T>
bool print_(const vector<vector<T>> &vv) {
  for (auto &v : vv) {
    for (auto &a : v) {
      cout << a;
      if (&a != &v.back()) {
        cout << " ";
      }
    }
    if (&v != &vv.back()) {
      cout << "\n";
    }
  }
  return false;
}
void print() { cout << "\n"; }
template <typename Head, typename... Tail>
void print(Head &&head, Tail &&... tail) {
  bool f = print_(head);
  if (sizeof...(tail) != 0) {
    cout << (f ? " " : "\n");
  }
  print(forward<Tail>(tail)...);
}
#pragma endregion

void Pr(bool f){
  cout << (f ? "Yes" : "No") << "\n";
  exit(0);
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  ll n;
  cin >> n;
  vll a(n);
  rep(i, n){
    cin >> a[i];
  }
  rep(i, n){
    if(a[i] == 0){
      print(0);
      return 0;
    }
  }
  ll x = 1;
  ld y = 1;
  rep(i, n){
    x *= a[i];
    y *= a[i];
    if(y > INF){
      print(-1);
      return 0;
    }
  }
  print(x);
}


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

using namespace std;
using ll = long long;

ll memo[100000];

int main() {
  int N, K;
  string S;
  cin >> N >> K;
  cin >> S;
  int i=0,j=0;
  int ret = 0;
  while(j<N){
    while(j<N&&S[j]=='1')
      j++;
    ret = max(ret, j-i);
    while(j<N&&S[j]=='0')
      j++;
    K--;
    if(K<0){
      while(i<N&&S[i]=='1')
        i++;
      while(i<N&&S[i]=='0')
        i++;
      K++;
    }
    ret = max(ret, j-i);
  }
  cout << ret << endl;
}


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

typedef long long ll;
int N;
string K;
int D;
const ll MOD = 1e9 + 7;

ll dp[11111][2][111];

ll rec(int n, int flag, int sum)
{   
    if(dp[n][flag][sum] != -1) return dp[n][flag][sum];
    if(n == 0)
    {
        if(sum == 0) return dp[0][flag][0] = 1;
        else return dp[0][flag][sum] = 0;
    }

    ll res = 0;
    int digit = K[N - n] - '0';
    if(flag == 1)
    {   
        res += rec(n - 1, 1, (sum + digit) % D) % MOD;
        res %= MOD;
        for(int i = 0; i < digit; i++)
        {
            res += rec(n - 1, 0, (sum + i) % D) % MOD;
            res %= MOD;
        }
    }
    else
    {
        for(int i = 0; i <= 9; i++)
        {
            res += rec(n - 1, 0, (sum + i) % D) % MOD;
            res %= MOD;
        }
    }
    return dp[n][flag][sum] = res ;
}

int main()
{
    cin >> K >> D;
    N = K.length();
    memset(dp, -1, sizeof(dp));
    ll res = rec(N, 1, 0) - 1;
    if(res < 0) res += MOD;
    cout << res << endl; //0の時は含めない。
}

Measured memory_bytes: 20352
first_dict = {'A': "100101", 'B': "10011010", 'C': "0101", 'D': "0001", 'E': "110",
              'F': "01001", 'G': "10011011", 'H': "010000", 'I': "0111", 'J': "10011000",
              'K': "0110", 'L': "00100", 'M': "10011001", 'N': "10011110", 'O': "00101",
              'P': "111", 'Q': "10011111", 'R': "1000", 'S': "00110", 'T': "00111",
              'U': "10011100", 'V': "10011101", 'W': "000010", 'X': "10010010",
              'Y': "10010011", 'Z': "10010000", ' ': "101", "'": "000000",
              ',': "000011", '-': "10010001", '.': "010001", '?': "000001"}
second_dict = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O',
               'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', ' ', '.', ',', '-',
               "'", '?']
while 1:
    try:
        N = list(input())
        num = ""
        first = []
        for i in N: num += first_dict[i]
        if len(num) % 5 != 0:
            for i in range(5 - (len(num) % 5)):
                num += "0"
        count = 0
        number = ""
        for j in num:
            number += j
            count += 1
            if count == 5:
                number += " "
                count = 0
        key = number.split()
        answer = ""
        for k in key:
            pas = int(k[4]) * 1 + int(k[3]) * 2 + int(k[2]) * 4 + int(k[1]) * 8 + int(k[0]) * 16
            answer += second_dict[pas]
        print(answer)

    except:
        break



Measured memory_bytes: 5628
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
const int MAXN=5005,D=1e9+7;
int n;
vector<int> ver[MAXN];
ll f[MAXN][MAXN],tmp[MAXN],fac[MAXN];
int siz[MAXN];
void dfs(int u,int fa) {
	f[u][1]=1;siz[u]=1;
	for(int i=0;i<(int)ver[u].size();i++) {
		int v=ver[u][i];
		if(v==fa) continue;
		dfs(v,u);
		memset(tmp,0,sizeof(tmp));
		for(int j=0;j<=siz[u];j++)
			for(int k=0;k<=siz[v];k++)
				tmp[j+k]=(tmp[j+k]+f[u][j]*f[v][k])%D;
		siz[u]+=siz[v];
		memcpy(f[u],tmp,sizeof(tmp));
	}
	for(int i=0;i<=siz[u];i+=2)
		f[u][0]=(f[u][0]-f[u][i]*fac[i/2])%D;
}
int main() {
	fac[0]=1;
	for(int i=1;i<=2500;i++) fac[i]=fac[i-1]*(i*2-1)%D;
	scanf("%d",&n);
	for(int i=1,aa,bb;i<n;i++) {
		scanf("%d%d",&aa,&bb);
		ver[aa].push_back(bb);
		ver[bb].push_back(aa);
	}
	dfs(1,0);
	printf("%lld\n",(D-f[1][0]%D)%D);
	return 0;
}

Measured memory_bytes: 196608
#include<bits/stdc++.h>
#define rep(i,n) for(int i = 0;i<n;i++)
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0;}


int main() {
    ll n;
    cin >> n;
    vector<pair<int,int>>prime;
    int ans = 0;
    for(ll i = 2;i*i<=n;i++) {
        int cnt = 0;
        if(n%i == 0) {
            while(n%i==0) {
                cnt++;
                n /= i;
            }
            for(int j = 1;;j++) {
                cnt -= j;
                if(cnt>=0) ans++;
                else break;
            }
        }
    }
    if(n != 1) ans++;
    cout << ans << endl;
}
    




Measured memory_bytes: 3628