akhauriyash/Code-Regression huggingface dataset:
import java.util.*

val sc = Scanner(System.`in`)
val A = sc.nextInt()
val B = sc.nextInt()
val C = sc.nextInt()
val K = sc.nextInt()

fun main(args: Array<String>) {
    val arr = arrayOf(A, B, C)
    println(arr.max()!! * (pow(2, K) - 1) + arr.sum())
}

fun pow(x: Int, n: Int): Int {
    var result = 1
    repeat(n) {
        result *= x
    }
    return result
}


Measured memory_bytes: 35664
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define rep2(i,s,n) for (int i = s; i < n; ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define tmax(a,b,c) max(a,max(b,c))
#define tmin(a,b,c) min(a,min(b,c))
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<P>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class T> istream& operator>>(istream& is,vector<T>& v) { for(T& t:v){is>>t;} return is; }
template<class T> ostream& operator<<(ostream& os,const vector<T>& v) { for(T t:v){os<<t<<" ";} os<<"\n"; return os; }
void Yes(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YES(bool b) { cout << (b ? "YES" : "NO") << endl; }
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 = 1001001001;
const ll linf = 1001001001001001001;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n;
    cin >> n;
    vi a(n);
    cin >> a;
    ll sum = 0,rsum = 0,ans = 0,rans = 0;
    rep(i,n) {
        sum += a[i];
        rsum += a[i];
        if(i%2 == 0) {
            if(sum <= 0) {
                ans += 1-sum;
                sum = 1;
            }
            if(rsum >= 0) {
                rans += rsum+1;
                rsum = -1;
            }
        } else {
            if(rsum <= 0) {
                rans += 1-rsum;
                rsum = 1;
            }
            if(sum >= 0) {
                ans += sum+1;
                sum = -1;
            }
        }
    }
    cout << min(ans,rans) << endl;
}


Measured memory_bytes: 640
#include <cstdio>
#include <stdio.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

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

int main(){
	int n;
	char a[1000];
	cin >>n;

	int c = 0;
	int d = 0;

	REP(i,n){
		cin >> a[i];

		if(a[i] == '(') {
			c++ ;
		}
		if(a[i] == ')') {
			if(c > 0){
				c--;
			}
			else{
				d++;
			}
		}
	}


	REP(i,d){
		cout << "(" ;
	}

	REP(i,n){
		cout << a[i];
	}

	REP(k,c){
		cout << ")";
	}
	cout << endl;
}

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

using namespace std;

int main() {
	int N;
	int B[99];
	cin >> N;
	for (int i = 0;i < N-1;i++) {
		cin >> B[i];
	}
	int A[100] = { 0 };
	A[0] = B[0];
	for (int i = 1;i < N-1;i++) {
		A[i] = min(B[i], B[i-1]);
	}
	A[N-1] = B[N - 2];
	int ans = 0;
	for (int i = 0;i < N;i++) {
		ans += A[i];
	}
	/*cout << N << "#" << A[0] <<"#"<< A[1] <<"#"<<A[2]<< endl;
	cout << B[0] << "!" << B[1] << endl;*/
	cout << ans << endl;
}

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

int main() {
  int H, W;
  while (true) {
    cin >> H >> W;
    if (H == 0 && W == 0) break;
    for (int i{}; i < H; ++i) {
      for (int j{}; j < W; ++j) {
        if (i % 2 == 1)
          cout << (j % 2 == 0 ? '.' : '#');
        else
          cout << (j % 2 == 1 ? '.' : '#');
      }
      cout << endl;
    }
    cout << endl;
  }
}



Measured memory_bytes: 3088
n, k = gets.chomp.split(" ").map {|n| n.to_i}
gra = gets.chomp.split(" ").map {|n| n.to_i - 1}

def go_t(g, pos, cont, c, visi)
  if visi[pos]
    return cont - c[pos], c[pos], pos
  end
  visi[pos] = true
  c[pos] = cont
  go_t(g, g[pos], cont + 1, c, visi)
end

def final(g, pos, j)
  if (j == 0)
    return pos
  end
  final(g, g[pos], j - 1)
end

b, aux, ini = go_t(gra, 0, 0, {}, [false] * n)
if k < aux
  puts final(gra, 0, k) + 1
else
  k -= aux
  j = k % b
  puts final(gra, ini, j) + 1
end
  


Measured memory_bytes: 61836
#include<stdio.h>
#include<iostream>
#include<cmath>

int main(void) {
	unsigned long int X=0;
	unsigned long int A = 100;
	int i = 0;
	scanf("%lu", &X);
	while (true)
	{
		if (X >= 101 && X <= powl(10, 18)) {
			A += A / 100;
			i++;
			if (A >= X) {
				break;
			}
		}
	}
	printf("%d\n", i);
}

Measured memory_bytes: 3800
n, m = gets.chomp.split.map(&:to_i)
h = gets.chomp.split.map(&:to_i)
a = []
b = []
m.times do
  c = gets.split.map(&:to_i)
  a << c[0]
  b << c[1]
end
d = Array.new(n){'yes'}

m.times do |i|
  if h[a[i] - 1] > h[b[i] - 1]
    d[b[i]-1] = 'no'
  elsif h[a[i] - 1] < h[b[i] - 1]
    d[a[i]-1] = 'no'
  elsif h[a[i] - 1] == h[b[i] - 1]
    d[a[i]-1] = 'no'
    d[b[i]-1] = 'no'
  end
end
d.delete('no')
puts d.length

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

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define SUM(x) accumulate(ALL(x), 0)
#define print(x) cout << x;
#define println(x) cout << x << endl;
#define printd(x, f) cout << fixed << setprecision(f) << x << endl;

#define PB push_back
#define MP make_pair
#define F first
#define S second

#define INF 1000000000000
#define MOD 10000007
#define MAXR 100000
#define PI acos(-1.0)

int main()
{
  int n; cin >> n;
  vi a(n);
  REP(i, n) cin >> a[i];

  int res = 0;
  REP(i, n) {
    while (i+1 < n && a[i] == a[i+1]) ++i;
    if (i+1 < n && a[i] < a[i+1]) while (i+1 < n && a[i] <= a[i+1]) ++i;
    else if (i+1 < n && a[i] > a[i+1]) while (i+1 < n && a[i] >= a[i+1]) ++i;
    ++res;
  }
  println(res);
  return 0;
}


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

//#define int long long
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define exrep(i, a, b) for(ll i = a; i < b; i++)
#define out(x) cout << x << endl
#define EPS (1e-7)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<bool> > vvb;
typedef vector<vector<double> > vvd;
typedef vector<vector<string> > vvs;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<vector<vector<ll> > > vvvl;
ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
//cout<<fixed<<setprecision(10);

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;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
//以降 cin の入力元が 'input.txt' になる
//std::ifstream in("input.txt");
//std::cin.rdbuf(in.rdbuf());

struct BellmanFordMax {
	BellmanFordMax() {}
	BellmanFordMax(int n) { init(n); }
	vector<vector<pair<int, int> > > E; 
    int N;
	void init(int n) { N = n; E.resize(0); E.clear(); E.resize(n); }
	void add(int a, int b, int c) { E[a].push_back({ b, c }); }
	vector<ll> solve(int s) {
		vector<ll> res(N, -L_INF); //最終的なコスト
		res[s] = 0;
 
        //最長経路を求める (辺に-1をかけると最短経路になる？)
		rep(i, N - 1) {
			rep(cu, N){
                if (-L_INF < res[cu]){
                    for(auto p:E[cu]) {
                        chmax(res[p.first], res[cu] + p.second);
                    }
                }
            }
		}

        //最長経路において正のサイクルの見つける
		vector<bool> pos(N);
		rep(i, N) {
			rep(cu, N) {
                if (-L_INF < res[cu]) {
                    for(auto p:E[cu]) {
                        if (chmax(res[p.first], res[cu] + p.second)) {
                            pos[p.first] = true;
                        }
                        if (pos[cu]) pos[p.first] = true;
                    }
                }
			}
		}
 
		rep(cu, N) if (pos[cu]) res[cu] = L_INF;
 
		return res;
	}
};
//参考 はまやんさんのサイト
//https://www.hamayanhamayan.com/entry/2019/08/14/131217
//問題 ABC137 E https://atcoder.jp/contests/abc137/tasks/abc137_e
vector<pair<int, int>> E[2500];
signed main()
{   
    gearup;
    int N, M, P; cin >> N >> M >> P;
	BellmanFordMax bf(N);
	rep(i, M) {
		int a, b, c; cin >> a >> b >> c;
		a--; b--;
		bf.add(a, b, c - P);
	}
 
	ll ans = bf.solve(0)[N - 1];
 
	if (ans == L_INF) ans = -1;
	else if (ans < 0) ans = 0;
 
	cout << ans << endl;
}


Measured memory_bytes: 3844
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <numeric>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <functional>
#include <complex>
#include <stack>
#include <tuple>

#define ll long long int

using namespace std;

const int INF = (1<<30) - 1;

bool infield(int h, int w){
    return 0<=h && h<8 && 0<=w && w<8;
}

int turn_field(vector<string> &field, bool flip, int h, int w, char myc, char opc){
    if(field[h][w] != '.')
        return 0;
    
    int count = 0;
    for(int i=-1; i<=1; i++){
        for(int j=-1; j<=1; j++){
            if(i==0 && j==0) continue;
            
            int l = 0;
            int nh = h, nw = w;
            do{
                l++;
                nh = h + i*l;
                nw = w + j*l;
            }while(infield(nh, nw) && field[nh][nw] == opc);
            
            if(infield(nh, nw) && field[nh][nw] == myc){
                count += l - 1;
                if(flip)
                    for(int k=0; k<l; k++)
                        field[h+k*i][w+k*j] = myc;
            }
        }
    }
    return count;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    char turnc[] = {'o', 'x'};
    int yt[] = {0, 7};
    int xt[] = {1, -1};
    
    
    vector<string> field(8);
    for(string &s: field)
        cin >> s;
    
    int pass = 0;
    int turn = 0;
    while (pass < 2) {
        bool update = false;
        char myc = turnc[turn];
        char opc = turnc[turn^1];
        
        int count = 0;
        int th, tw;
        
        for(int i=0; i<8; i++){
            for(int j=0; j<8; j++){
                int h = yt[turn] + xt[turn]*i;
                int w = yt[turn] + xt[turn]*j;
                int tcount = turn_field(field, false, h, w, myc, opc);
                if(count < tcount){
                    count = tcount;
                    th = h;
                    tw = w;
                    update = true;
                }
            }
        }
        
        if(update){
            turn_field(field, true, th, tw, myc, opc);
            pass = 0;
        }else{
            pass++;
        }
        
        turn ^= 1;
    }
    
    for(string s: field)
        cout << s << endl;
    
    return 0;
}

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



int main() {
    ll N;
    cin >> N;
    string res = "";
    while (N) {
        --N;
        res += (char)('a' + (N % 26));
        N /= 26;
    }
    reverse(res.begin(), res.end());
    cout << res << endl;
  return 0;
}
  

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

int n;
int a[100005];
int dp[100005];
vector<int> g[100005];

void dfs(int x){
    for(int i=0;i<g[x].size();i++){
        dfs(g[x][i]);
    }
    sort(g[x].begin(),g[x].end(),[](int u,int v){
        return dp[u]>dp[v];
    });
    for(int i=0;i<g[x].size();i++){
        dp[x]=max(dp[x],dp[g[x][i]]+i+1);
    }
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    for(int i=2;i<=n;i++){
        cin>>a[i];
        g[a[i]].push_back(i);
    }
    dfs(1);
    cout<<dp[1]<<endl;

    return 0;
}

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

int main(int argc, char *argv[]){
    int N;
    std::cin >> N;
    std::vector<int> A(N), B(N), C(N-1);
    for(auto &a : A){
        std::cin >> a;
    }
    for(auto &b : B){
        std::cin >> b;
    }
    for(auto &c : C){
        std::cin >> c;
    }

    int sum = 0;
    for(const auto &b : B){
        sum += b;
    }
    int lastA = A[0], newA;
    for(const auto &a : A){
        newA = a;
        if(newA == lastA + 1){
            sum += C[lastA-1];
        }
        lastA = newA;
    }
    std::cout << sum << std::endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <sstream>
#include <string>
using namespace std;

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

  if(k%2 == 0) cout << (k/2) * (k/2) <<endl;
  else cout << ((k+1)/2) * (k/2) << endl;
  return 0;
}

Measured memory_bytes: 888
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

template <typename T>
void print_vec(const vector<T>& v, bool is_reverse=false, int num=0){
  if(num == 0) num = (int)v.size();
  if(is_reverse) for(int i=num-1; i>=0; i--){ cout<<v[i]; if(i!=0) cout<<" ";}
  else for(int i=0; i<num; i++){ cout<<v[i]; if(i!=num-1) cout<<" ";}
  cout << endl;
}

template <typename T>
void print_pairvec(const vector<T> &v, int num=0){
  if(num == 0) num = (int)v.size();
  cout << endl;
  for(int i=0; i<num; i++){ cout << v[i].first << " " << v[i].second << endl;}
}


template <typename TYPE>
void print_vec2(const vector<vector<TYPE>>& v){
  cout << endl; cout << "       ";
  for(int i=0; i<v[0].size(); i++) cout << i << "   "; 
  cout << endl;
	for(int i=0; i<v.size(); i++){
		cout << "i=" << i << ":   ";
		for(int j=0; j<v[i].size(); j++){
			if(v[i][j] == 0) cout << "\x1B[0m" << v[i][j] << "   ";
      else cout << "\x1B[31m" << v[i][j] << "   ";//https://stackoverrun.com/ja/q/12618775
		}
		cout << "\x1B[0m" << endl;
	}
}

int main(){
  

  int L, R;
  cin >> L >> R;

  int MOD = 2019;
  vector<bool> vec(MOD, false);
  int length = min(MOD, R-L+1);
  for(int i=L; i<L+length; i++) vec[i%MOD]=true;

  int ans = 1e8+1;
  for(int i=0; i<MOD; i++){
    for(int j=i+1; j<MOD; j++){
      if(vec[i] & vec[j]) ans = min(ans, (i * j) %MOD);
    }
  }
  cout << ans << endl;
	return 0;
}



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

int main(void){
  int n1, n2, n3, n4;
  cin >> n1 >> n2 >> n3 >> n4;
  if(n1 == 1 || n2 == 1 || n3 == 1 || n4 == 1){
	if(n1 == 9 || n2 == 9 || n3 == 9 || n4 == 9){
	  if(n1 == 7 || n2 == 7 || n3 == 7 || n4 == 7){
		if(n1 == 4 || n2 == 4 || n3 == 4 || n4 == 4){
		  cout << "YES" << endl;
		}else {
		  cout << "NO" << endl;
		}
	  }else {
		cout << "NO" << endl;
	  }
	}else {
	  cout << "NO" << endl;
	}
  }else {
	cout << "NO" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int N,W;
int w[100100],v[100100];
long long dp[110][100100];
int main(){
  cin >> N >> W;
  for(int i=0;i<N;i++) cin >> w[i] >> v[i];

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

  for(int i=w[0];i<=W;i++) dp[0][i]=v[0];

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


Measured memory_bytes: 80128
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <queue>
#include <list>
#include <bitset>
#include <unordered_map>
#include <algorithm>
#include <functional>
#include <iomanip> // std::std::setprecision(X)
#include <limits>  //std::numeric_limits<int>::max(), min()

int main (void) {
  int L; std::cin >> L;

  std::array<bool, 20> k = { false } ;
  int digit = 0, c = 0;
  int tmpL = L;
  while(tmpL) {
    if ( tmpL & 1 ) {
      k[digit] = true;
      c++;
    }
    tmpL >>= 1;
    digit++;
  }

  int N = digit;
  int M = (digit-1)*2 + (c-1);
  std::cout << N << " " << M << std::endl;

  int t = 1;
  for (int i = 1; i < digit; i++) {
    std::cout << i << " " << i+1 << " " << 0 << std::endl;
    std::cout << i << " " << i+1 << " " << t << std::endl;
    if (k[i-1] == true) {
      std::cout << i << " " << digit << " " << L - t << std::endl;
      L -= t;
    }
    t <<= 1;
  }

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <stack>
#include <functional>
#include <queue>
#include <cmath>
#include <set>

#define rep(i,j,k) for(int i=j;i<k;i++)
#define drep(n,m) for(int i=0;i<n;i++)for(int j=0;j<m;j++)
#define Sort(x) sort((x).begin(),(x).end())
#define fi first
#define se second
#define vi vector<int>
#define INF 1000000000
#define MOD 1000000009
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef unsigned long long ull;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

using namespace std;

ll gcd(ll a,ll b){
    if(a<b){
        int t=a;a=b;b=t;
    }
    int c=a%b;
    while(c!=0){
        a=b;
        b=c;
        c=a%b;
    }
    return b;
}

ll lcm(ll a,ll b){
    return a*b/gcd(a,b);
}

bool isPrime(int x){
    if(x==1)return false;
    if(x==2)return true;
    if(x%2==0)return false;
    for(int i=3;i<=sqrt(x);i+=2){
        if(x%i==0)return false;
    }
    return true;
}

typedef struct Point{
    int x;
    int y;
} P;

int main() {
    string s;
    cin>>s;
    cout<<"2018";
    rep(i,4,s.length()){
        cout<<s[i];
    }
    cout<<endl;
    return 0;
}




Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <string>
using namespace std;
int main()
{
	string s;
	cin >> s;
	int count = 0;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'x') {
			count++;
		}
	}
	if (count >= 8) {
		cout << "NO";
	}
	else {
		cout << "YES";
	}

	return 0;
}

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

int main(){ 

// 各種変数宣言 

    int n,p,i,j,k,c,a=0; int count=0;

// 配列宣言
    int cand[1000],peb;

// メインループ 

    while(1){


// nとpを読み込む
    scanf("%d",&n);
    scanf("%d",&p);


// 否定条件
    if( (n==0) && (p==0) ) break;
       
// 石の個数を初期化
    for(i=0;i<n;i++){
        cand[i]=0;
        
    }
        //椀の中の石の数
    peb=p;

// 候補者の１動作
    j=0;
    while(1){
        if(peb>0){      //椀に石がある場合
            cand[j]++;
            peb--;
            
        }
        else if(peb==0){  //椀に石がない場合
            count=0;
            for(i=0;i<n;i++){  //手持ちに石がない人の数を数える
                if(cand[i]==0){
                    count++;
                    
                }
                
            }
            
            if(count==n-1)break;//一人だけ石を持っている状態ならbreak
            
            peb=cand[j];  //手持ちに石を持っている人が複数人いて、椀に石が０の時の動作
            cand[j]=0;
            
        }
        
        j++;
        if(j==n)
            j=0;
        
    }
    
    for(i=0;i<n;i++){    //全ての石を持っている人の番号を表示
        if(cand[i]==p)
            printf("%d\n",i);
        
    }
       
    }
       
       
       
// 終了
    return 0;
    
}



Measured memory_bytes: 2740
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }
#define ALL(x) (x).begin(), (x).end()
LL POW(LL a,LL p,LL M){ if(!p) return 1LL;LL T = POW(a,p/2,M);T = T*T%M; if(p&1) T=T*(a%M)%M; return T; }
LL SQRT(LL a) { LL b = (LL)sqrtl(((double)a)+0.5); while(b*b<a) ++b; while(b*b>a) --b; return (b*b==a)?b:-1; }
//endl
//<------------------------edits---------------------------------------------->
const LL MOD = 1e9+7;//998244353
// #define LOCAL LDD
// #define int LL

const int N = 4002;
int cnt[N][3];
map<char,int> mm;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.precision(10);cout << fixed;
#ifdef LOCAL
  freopen("input.txt", "rt", stdin);
#endif
  int n;cin >> n;
  string s;cin >> s;
  for(int i=n-2;i>=0;i--){
    cnt[i][0] = cnt[i+1][0] + (s[i+1]=='R');
    cnt[i][1] = cnt[i+1][1] + (s[i+1]=='G');
    cnt[i][2] = cnt[i+1][2] + (s[i+1]=='B');
  }
  mm['R'] = 0;
  mm['G'] = 1;
  mm['B'] = 2;
  LL ans = 0;
  int x,y,z;
  for(int i=n-3;i>=0;i--){
    for(int j=i+1;j<n-1;j++){
      if(s[i]!=s[j]){
        x = mm[s[i]];
        y = mm[s[j]];
        for(int k=0;k<3;k++){
          if(k!=x && k!=y) z = k;
        }
        ans += cnt[j][z];
        if(j+j-i<n && mm[s[j+j-i]]==z) ans--;
        // cout << i << " " << j << " " << x << " " << y << " " << z << endl;
      }
    }
  }
  cout << ans << endl;
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s\n";
  return 0;
}

Measured memory_bytes: 3884
n=int(input())
ab=[map(int,input().split()) for _ in range(n)]
a,b = [list(i) for i in zip(*ab)]

s=0
for i in range(n):
    if (a[n-1-i]+s)%b[n-1-i]==0:
        continue
    else:
        c=b[n-1-i]-((a[n-1-i]+s)%b[n-1-i])
        s+=c
print(s)

Measured memory_bytes: 87512
#include <stdio.h>

int main() {

	int a , b , c , num ;
	scanf ( "%d %d %d" , &a , &b , &c ) ;

	if ( a > b ) {
			num = a ;
			a = b ;
			b = num ;
		}

	if ( a > c ) {
			num = a ;
			a = c ;
			c = num ;
		}

	if ( b > c ) {
			num = c ;
			c = b ;
			b = num ;
		}

	printf ( "%d %d %d\n" , a , b , c );

	return 0 ;

}



Measured memory_bytes: 2716
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>

using namespace std;
using Int = long long;
typedef pair<int,int> Pi; typedef pair<Int,Int> Pl;
constexpr int mod = 1e9+7;
constexpr int INF32 = numeric_limits<int>::max();
constexpr Int INF64 = numeric_limits<Int>::max();
#define END {cout<<ans<<'\n'; return 0;}
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define Pr(t) priority_queue<t>
#define gPr(t) priority_queue<t,vector<t>,greater<t>>
#define V(t) vector<t>
#define rer(i,l,r) for(int(i)=(l); (i)<(r); ++(i))
#define rep(i,n) rer(i,0,n)
#define gnr(i,l,r) for(int (i)=(r)-1; (i)>=(l); --(i))
#define pri(a) cout<<(a)<<'\n'
#define pri2(a,n) {rep(i,n-1)cout<<a[i]<<' '; if(n)cout<<a[n-1]<<'\n';}
#define prip(p) cout<<(p).fi<<' '<<(p).se<<'\n'
template<class T> inline bool cmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool cmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int n,m,_,x,y,q;
string s,sb;
bool ok;
char cf,cb;

int main(){
  cin.tie(nullptr); ios::sync_with_stdio(0);
  //cout<<fixed<<setprecision(20);
  
  while(cin>>n){
    int ans=0;
    rep(i,10)rep(j,10)rep(k,10)if(i+j+k<=n&&n-(i+j+k)<10)ans++;
    pri(ans);
  }
}


Measured memory_bytes: 3020
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    k, x = MAP()
    if 500*k >= x: 
        print('Yes')
    else:
        print('No')

if __name__=='__main__':
    main()


Measured memory_bytes: 5840
#include <iostream>
#include <fstream>
#include <iomanip>
#include <math.h>
#include <limits.h>
#include <algorithm>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <string>
#include <string.h>
#include <sstream>
#include <ctime>

using namespace std;

#define eps 1e-12
#define pi 3.14159265358979323846
#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define bgn begin
#define ll long long
#define ld long double
#define ull unsigned long long
#define ii pair<ll,ll>











int a,b,c,d,e,f,s,w,s2,w2;



void solve()
{
	cin>>a>>b>>c>>d>>e>>f;
	w=a;
	s=0;
	for(int i=0;i*100<=f;i+=a)
	{
		for(int j=0;j*100<=f;j+=b)
		{
			for(int k=0;k<=f;k+=c)
			{
				for(int l=0;l<=f;l+=d)
				{
					w2=i+j;
					if(w2==0)continue;
					s2=k+l;
					if(w2*e>=s2&&(w2*100)+s2<=f&&s2*((w*100)+s)>=((w2*100)+s2)*s)
					{
						w=w2;
						s=s2;
					}
				}
			}
		}
	}
	cout<<(w*100)+s<<" "<<s<<"\n";
}

int main()
{
	std::ios::sync_with_stdio(0);
	cin.tie(0);
#ifdef localProject
	freopen("in.txt","r",stdin);
#endif
	solve();
	return 0;
}

Measured memory_bytes: 256
/**
 *    author:  FromDihPout
 *    created: 2020-06-29
**/

#include <bits/stdc++.h>
using namespace std;

long long nCr(int n, int r) {
    if (r > n) {
        return 0;
    }
    if (r > n / 2) {
        r = n - r;
    }
    if (r == 0) {
        return 1;
    }
    long long choose = n;
    for (int i = 2; i <= r; i++) {
        choose *= n - i + 1;
        choose /= i;
    }
    return choose;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, a, b;
    cin >> n >> a >> b;
    vector<long long> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    sort(nums.begin(), nums.end(), greater<long long>());
    
    map<int,int> freq;
    for (int i = 0; i < n; i++) {
        freq[nums[i]]++;
    }
    
    long double mean = 0;
    long long amt = 0, prev = -1;
    for (int i = 0; i < a; i++) {
        mean += nums[i];
        if (nums[i] != prev) {
            prev = nums[i];
            amt = 1;
        }
        else {
            amt++;
        }
    }
    mean /= a;

    long long ways = 0;
    if (prev == nums[0]) {
        for (int i = a; i <= b; i++) {
            ways += nCr(freq[prev], i);
        }
    }
    else {
        ways = nCr(freq[prev], amt);
    }
    
    printf("%.20Lf\n%lld", mean, ways);
    return 0;
}

Measured memory_bytes: 3748
#include <iostream>
#include <cmath>
using namespace std;

int main(void) {
    int D,N;
    cin>>D>>N;
    if (D == 0) {
        int cnt = 0;
        int cur = 0;
        while (cnt < N) {
            cur++;
            if (cur % 100 > 0) cnt++;
        }
        cout << cur << endl;
    } else if (D == 1) {
        int cnt = 0;
        int cur = 0;
        while (cnt < N) {
            cur++;
            if (cur % 100 == 0 && cur % 10000 > 0) cnt++;
        }
        cout << cur << endl;       
    }
    else {
        int cnt = 0;
        int cur = 0;
        while (cnt < N) {
            cur++;
            if (cur % 10000 == 0 && cur % 1000000 > 0) cnt++;
        }
        cout << cur << endl;           
    }
    return 0;
}

Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
 
typedef long long int ll;
 
vector <ll> adj[200005];
ll grp[200005];
bool visited[200005];

void dfs(ll point,ll parent,ll grp_num)
{
	// cout << point << " " << grp_num << '\n';
	visited[point] = true;
	grp[grp_num]++;
	ll i,j,k;

	for(i=0;i<adj[point].size();i++)
	{
				// cout << "in " << adj[point][i] << '\n';
		if(visited[adj[point][i]] == false)
		{
			if(adj[point][i] != parent)
			{
				dfs(adj[point][i],point,grp_num);
			}
		}
	}
}
 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
 
	ll i,j,k,l,m,n,x,y,z,a,b,c;
 
	cin >> n >> m;

	for(i=0;i<m;i++)
	{
		cin >> x >> y;

		adj[x].push_back(y);
		adj[y].push_back(x);
	}

	for(i=1;i<=n;i++)
	{
		grp[i] = 0;
		visited[i] = false;
	}
	k = 1;

	for(i=1;i<=n;i++)
	{
		if(visited[i] == false)
		{
			dfs(i,-1,k);
			k++;
		}

	}

	ll ans = -1;

	for(i=1;i<=n;i++)
	{
		// cout << grp[i] << " ";
		ans = max(ans,grp[i]);

	}
	// cout << '\n';

	cout << ans << '\n';

	


 
}

Measured memory_bytes: 28800
def main():
    n, m = map(int, input().split())

    islands_to_1 = [0 for _ in range(n+1)]
    islands_to_n = []
    for _ in range(m):
        boat = list(map(int, input().split()))
        if 1 in boat:
            islands_to_1[boat[1]] = 1

        if n in boat:
            islands_to_n.append(min(boat))

    for island_to_n in islands_to_n:
        if islands_to_1[island_to_n] == 1:
            print("POSSIBLE")
            return

    print("IMPOSSIBLE")
    return


if __name__ == "__main__":
    main()


Measured memory_bytes: 8632
N, K = map(int, input().split())

if N == K:
  print(0)
elif N > K:
  if N%K == 0:
    print(0)
  else:
    print(abs(K-N%K))
else:
  if N < K/2:
  	print(N)
  else:
    print(abs(N-K))

Measured memory_bytes: 3060
#include<iostream>
#include<stack>
using namespace std;
typedef long long ll;
int n;
int main(){
	ios::sync_with_stdio(false);
	cin >> n;
	ll ans=0;
	for(int i=1; i<=n ;i++){
		ll a,k;
		cin >> a >> k;
		if(a/k<=32000){
			int b=a/k,c=a%k%(b+1);
			c=(b+1-c)%(b+1);
			while(true){
				if(c==0) break;
				int nxt=(k-1)%b+1;
				if(c>=nxt) c-=nxt;
				else c=c-nxt+b;
				b--;
			}
			ans^=b;
		}
		else{
			while(a%k!=0) a-=a/k+1;
			int b=a/k;
			ans^=b;
		}
	}
	if(ans==0) cout << "Aoki\n";
	else cout << "Takahashi\n";
}

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

using namespace std;

const int Maxn = 210;
int n;
int a[Maxn];

int main() {
	
	scanf("%d",&n);
	n <<= 1;
	for(register int i=1; i<=n; i++)
		scanf("%d",&a[i]);
	
	sort(a+1,a+n+1);
	
	register int ans = 0;
	for(register int i=1; i<=n; i+=2)
		ans += a[i];
	
	printf("%d\n",ans);
	
	return 0;
	
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
int main(){
    int n, cnt=0;
    cin >> n;
    vector<int> vec(n);
    for (int i=0; i<n; i++) cin >> vec.at(i);
    for(int i=0; i<n; i++){
        if(vec.at(i) != i+1) cnt++;
    }
    if(cnt <= 2) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
    
}

Measured memory_bytes: 256
#include<stdio.h>
long long int fact[200005];
long long int modpow(long long int a, long long int n, long long int p)
{
	long long int res = 1;
	while (n > 0)
	{
		if (n % 2 > 0)
			res = res * a % p;
		a = a * a % p;
		n /= 2;
	}
	return res;
}
long long int comb(long long int n, long long int r, long long int p)
{
	long long int res = fact[n];
	res = res * modpow(fact[r], p - 2, p) % p;
	res = res * modpow(fact[n - r], p - 2, p) % p;
	return res;
}
int main()
{
	long long int n, m, k;
	scanf("%lld %lld %lld", &n, &m, &k);
	long long int p = 998244353;
	long long int i;
	fact[0] = 1;
	for (i = 1; i <= n; i++)
		fact[i] = fact[i - 1] * i % p;
	long long int ans = 0;
	for (i = 0; i <= k; i++)
		ans = (ans + comb(n - 1, i, p) * modpow(m - 1, n - i - 1, p) % p * m % p) % p;
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 3252
import qualified Data.Set as S
import qualified Data.ByteString.Char8 as B
import qualified Data.Array.IArray as A
import qualified Data.IntMap.Strict as M
import Control.Monad

readIntPair :: B.ByteString -> [(Int, Int)]
readIntPair = map (pair . map readInt . B.words) . B.lines

pair :: [t] -> (t, t)
pair [x, y] = (x, y)
pair _ = undefined

main = do
  n <- readLn
  es <- readUndirectedEdge <$> replicateM (n-1) B.getLine
  [q,k] <- map read . words <$> getLine
  xys <- readIntPair <$> B.getContents
  let g = buildG (1,n) es
  let m = dijkstra g k
  mapM_ (print . transit m) xys

transit m (x,y) = fst (m M.! x) + fst (m M.! y)  

type Bound = (Vertex, Vertex)
type Vertex = Int
type Weight = Int
type Edge = ((Vertex, Vertex), Weight)
type Path = [Vertex]
type Graph = A.Array Vertex (S.Set (Vertex, Weight))

buildG :: Bound -> [Edge] -> Graph
buildG b = A.accumArray (flip S.insert) S.empty b . map (\((s, t), w) -> (s, (t, w)))

from :: Graph -> Vertex -> S.Set (Vertex, Weight)
from = (A.!)

size :: Graph -> Int
size g = let (i,j) = A.bounds g in j - i + 1

readUndirectedEdge :: [B.ByteString] -> [Edge]
readUndirectedEdge = concatMap (constructTwoWay . map readInt . B.words)

constructTwoWay :: [Int] -> [Edge]
constructTwoWay [s,t,w] = [((s, t), w), ((t, s), w)]
constructTwoWay _ = undefined

readInt :: B.ByteString -> Int
readInt = maybe undefined fst . B.readInt

type Memo = M.IntMap (Weight, Path)

-- accumrated weight and lexical order shortest path
dijkstra :: Graph -> Vertex -> Memo
dijkstra g s = _dijkstra g q0 m0
  where
   q0 = singleton (0, s)
   m0 = M.singleton s (0, [])

_dijkstra :: Graph -> PriorityQueue -> Memo -> Memo
_dijkstra g q m
  | isEmpty q = m
  | otherwise = _dijkstra g q2 m1
  where
    ((w0, s), q1) = deleteFindMin q
    p = s : snd (m M.! s)
    m1 = S.foldr (\(t, w) acc -> M.insertWith min t (w0 + w, p) acc) m vns
    q2 = S.foldr (\(t, w) acc -> insert (w0 + w, t) acc) q1 vns
    vns = S.filter (\(t, w) -> M.notMember t m || w0 + w <= fst (m M.! t)) (from g s)

type PriorityQueue = S.Set (Weight, Vertex)

isEmpty :: PriorityQueue -> Bool
isEmpty = S.null

singleton :: (Weight, Vertex) -> PriorityQueue
singleton = S.singleton

insert :: (Weight, Vertex) -> PriorityQueue -> PriorityQueue
insert = S.insert

deleteFindMin :: PriorityQueue -> ((Weight, Vertex), PriorityQueue)
deleteFindMin = S.deleteFindMin

Measured memory_bytes: 188284
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<tuple>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<deque>
#include<cmath>
#include<stack>
#include<string.h>
#include <iomanip>
#define rep(i,n) for(int i = 0;i<n;i++)
#define _GLIBCXX_DEBUG
using ll = long long; 
using namespace std;
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() {
    int n;
    cin >> n;
    vector<int>a(n);
    vector<int>b(n-1);
    rep(i,n-1) cin >> b[i];
    ll ans = 0;
    rep(i,n) {
        if(i==0) a[0] = b[0];
        if(i>0&&i<n-1) a[i] = min(b[i],b[i-1]);
        if(i==n-1) a[i] = b[i-1];
    }
    rep(i,n) {
        ans += a[i];
    }
    cout << ans << endl;
}

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

const int INF = (int) 1e9;

int main() {
	int n;
	cin>>n;
	
	vector<vector<int> > dp(n, vector<int>(3, INF));
	for(int i=0; i<n; i++) {
		int a, b, c;
		cin>>a>>b>>c;
		if(i==0) {
			dp[0][0]=a;
			dp[0][1]=b;
			dp[0][2]=c;
		} else {
			dp[i][1] = b + max(dp[i-1][0], dp[i-1][2]);
			dp[i][0] = a + max(dp[i-1][1], dp[i-1][2]);
			dp[i][2] = c + max(dp[i-1][0], dp[i-1][1]);
		}
	}
	cout<<*max_element(dp[n-1].begin(), dp[n-1].end())<<endl;
	return 0;
}


Measured memory_bytes: 5760
import java.util.*;
public class Main{
    static Scanner kbd = new Scanner(System.in);
    public  static void main(String[] args){
	while(kbd.hasNext()){
	    int m = kbd.nextInt();
	    if(m!=0){
		solve(m);
	    }
	}
    }

    static void solve(int m){
	int six = 60;
	int n = kbd.nextInt();
	int cnt = 0;
	for(; m<=n; m++){
	    //System.out.println(m);
	    while(six < m){ six*=60; }
	    if(m==1);
	    if(six%m == 0){ 
		//System.out.println(m);
		cnt++;
	    }
	    else{
		int a = m;
		while(a>0 && a%2==0){ a/=2; }
		while(a>0 && a%3==0){ a/=3; }
		while(a>0 && a%5==0){ a/=5; }

		if(a==1){ 
		    //System.out.println(m);
		    cnt++; 
		}
	    }
	}
	System.out.println(cnt);
    }
}

Measured memory_bytes: 19216
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 998244353

N, K = MAP()
A = LIST()

dp = list2d(N+1, K+1, 0)
dp[0][0] = 1
for i, a in enumerate(A):
    for j in range(K+1):
        dp[i+1][j] += dp[i][j] * 2
        dp[i+1][j] %= MOD
        if j+a <= K:
            dp[i+1][j+a] += dp[i][j]
            dp[i+1][j+a] %= MOD
ans = dp[N][K]
print(ans)


Measured memory_bytes: 139296
#include <iostream>

using namespace std;

int main() {
  int H,W;
  while (true) {
    cin >> H >> W;
    if(H == 0 && W == 0)break;
    for(int i=0; i < H; ++i){
      for(int j=0; j < W ;++j){
        if (i==0 || i == H-1 || j == 0 || j == W-1) {
          cout << '#';
        }
        else cout << '.';
      }
      cout << endl;
    }
    cout << endl;
  }
  return 0;
}


Measured memory_bytes: 3128
#include<iostream>
#include<cmath>
#include<complex>
#include<cstdlib>
#include<algorithm>
#include<functional>
using namespace std;
int main() {
    int x,ans=0;
    cin>>x;
    for(int i=1;i<=34;i++){
        for(int j=2;j<=32;j++){
        if(pow(i,j)<=x&&ans<pow(i,j)){
            ans=pow(i,j);
        }
    }
}
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    static Scanner scanner;
    static int getInt(){
        return Integer.parseInt(scanner.next());
    }
    public static void main(String[] args) {
        scanner = new Scanner(System.in);
        int a = getInt();
        int b = getInt();
        System.out.println(a * b + " " + (2 * a + 2 * b));
    }
}



Measured memory_bytes: 26084
#include <stdio.h>

int main(){
        char n;
        scanf("%c",&n);
        switch(n){
                case 'S':
                        puts("Cloudy");
                        break;
                case 'C':
                        puts("Rainy");
                        break;
                case 'R':
                        puts("Sunny");
        }
        return 0;
}

Measured memory_bytes: 128
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Integer> prices = new ArrayList<>();
        for (int i = 0; i < n; i++) prices.add(sc.nextInt());

        int mostExpensive = prices.stream().mapToInt(v -> v).max().getAsInt() / 2;

        int result = 0;
        for (int i = 0; i < n; i++) {
            result += prices.get(i);
        }
        System.out.println(result - mostExpensive);
    }
}

Measured memory_bytes: 32516
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
X = LI()

X.sort()

ans = float('inf')
for p in range(X[0],X[-1]+1):
    now = 0
    for i in range(N):
        now += (X[i]-p)**2
    if now < ans:
        ans = now

print(ans)

Measured memory_bytes: 39152
import static java.lang.Math.*;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskX solver = new TaskX();
		solver.solve(1, in, out);
		out.close();
	}

	static int INF = 1 << 30;
	static int MOD = 1000000007;
	static int[] mh4 = { 0, -1, 1, 0 };
	static int[] mw4 = { -1, 0, 0, 1 };
	static int[] mh8 = { -1, -1, -1, 0, 0, 1, 1, 1 };
	static int[] mw8 = { -1, 0, 1, -1, 1, -1, 0, 1 };

	static class TaskX {

		public void solve(int testNumber, InputReader in, PrintWriter out) {

			int n = in.nextInt(), W = in.nextInt();
			int[][] dp = new int[n+1][W+1];
			int[] v = new int[n];
			int[] w = new int[n];
			for (int i = 0; i < n; i++) {
				v[i] = in.nextInt();
				w[i] = in.nextInt();
			}

			for (int i = 0; i < n; i++) {
				for (int j = 0; j < W+1; j++) {
					if (j-w[i] >= 0) {
						dp[i+1][j] = max(max(dp[i+1][j-w[i]] + v[i], dp[i][j-w[i]] + v[i]), dp[i][j]);
					} else {
						dp[i+1][j] = dp[i][j];
					}
				}
			}

			out.println(dp[n][W]);

		}
	}

	static class InputReader {
		BufferedReader in;
		StringTokenizer tok;

		public String nextString() {
			while (!tok.hasMoreTokens()) {
				try {
					tok = new StringTokenizer(in.readLine(), " ");
				} catch (IOException e) {
					throw new InputMismatchException();
				}
			}
			return tok.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(nextString());
		}

		public long nextLong() {
			return Long.parseLong(nextString());
		}

		public double nextDouble() {
			return Double.parseDouble(nextString());
		}

		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextInt();
			}
			return res;
		}

		public long[] nextLongArray(int n) {
			long[] res = new long[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextLong();
			}
			return res;
		}

		public InputReader(InputStream inputStream) {
			in = new BufferedReader(new InputStreamReader(inputStream));
			tok = new StringTokenizer("");
		}
	}

}



Measured memory_bytes: 29200
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1000000007;
const LL LINF=1LL<<60;
const int INF=1<<30;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};


int main(){
    LL n,t;cin >> n >> t;
    vector<LL> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    LL ans = t;
    for (int i = 0; i < n-1; i++) {
        if(a[i+1] >= a[i] + t) ans += t;
        else ans += a[i+1] - a[i];
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1792
my $N=<>;chomp $N;
my $ans=0;
my $num = $N;
for(my $i=2;$i<=sqrt($N);$i++){
    #print "$i $num\n";
    my $count = 0;
    my $sre =1;
    while(){
        if(($num % $i)==0 ){
           $num = $num /$i;
           $count++;
           if( $count == $sre){
             $ans++;
             $sre++;
             $count =0;
           }
        }else{
            last;
        }
    }
    #print "$i $num\n";
    if($num == 1){last;}
}
#print "$ans $num\n";
if($num!=1){$ans++;}
print "$ans";

Measured memory_bytes: 4724
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(asd, fgh) for(ll asd = 0; asd < fgh; asd++)

struct P{
  ll pos;
  ll dir;
  bool stopped;
};


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

  ll N, T, Q; cin >> N >> T >> Q;
  vector<P> p(N);

  REP(i, N){
    ll a, d;
    cin >> a >> d;
    p[i].pos = a;
    if(d == 1){
      p[i].dir = 1;
    }else{
      p[i].dir = -1;
    }
    p[i].stopped = false;
  }

  for(ll i = 0; i < N-1; i++){
    if(p[i].dir == 1 && p[i+1].dir == -1){
      if((p[i+1].pos - p[i].pos) / 2 <= T){
        p[i+1].pos = p[i].pos = (p[i+1].pos + p[i].pos)/2;
      }else{
        p[i+1].pos -= T;
        p[i].pos += T;
      }
      p[i+1].stopped = p[i].stopped = true;
    }
  }

  for(ll i = 0; i < N; i++){
    if(p[i].stopped) continue;

    if(p[i].dir == 1){
      bool flg = false;
      for(ll j = i+1; j < N; j++){
        if(p[j].pos - p[i].pos > T){
          p[i].pos += T;
          flg = true;
          break;
        }else if(p[j].stopped == true){
          p[i].pos = p[j].pos;
          flg = true;
          break;
        }
      }
      if(!flg){
        p[i].pos += T;
      }

    } else {
      bool flg = false;
      for(ll j = i-1; j >= 0; j--){
        if(p[i].pos - p[j].pos > T){
          p[i].pos -= T;
          flg = true;
          break;
        }else if(p[j].stopped == true){
          p[i].pos = p[j].pos;
          flg = true;
          break;
        }
      }
      if(!flg){
        p[i].pos -= T;
      }
    }
  }

  REP(i, Q){
    int q; cin >> q; q--;
    cout << p[q].pos << endl;
  }

  return 0;
}

Measured memory_bytes: 3380
package main

import (
	"fmt"
)

// main is ...
func main() {
	var a1, a2, a3 int
	fmt.Scan(&a1, &a2, &a3)

	if a1+a2+a3 >= 22 {

		fmt.Print("bust")
		return
	}
	fmt.Print("win")
}



Measured memory_bytes: 512
use std::io::*;
use std::str::FromStr;
use utils::*;

pub fn main() {
    let i = stdin();
    let mut o = Vec::new();
    run(i.lock(), &mut o);
    stdout().write_all(&o).unwrap();
}

fn run<R: BufRead, W: Write>(i: R, o: &mut W) {
    let mut i = CpReader::new(i);
    let n = i.read::<usize>();

    let mut edges = vec![Vec::new(); n];
    for _ in 0..n - 1 {
        let (u, v, w) = i.read3::<usize, usize, usize>();
        let (u, v, w) = (u - 1, v - 1, (w % 2) as u8);

        edges[u].push((v as u32, w));
        edges[v].push((u as u32, w));
    }
    let start = 0;
    let mut ds = vec![None; n];
    let mut q = vec![start];
    ds[start] = Some(0);

    while let Some(u) = q.pop() {
        let d = ds[u].unwrap();
        for &(v, w) in &edges[u] {
            let v = v as usize;
            if ds[v].is_none() {
                ds[v] = Some(d ^ w);
                q.push(v);
            }
        }
    }
    for d in ds {
        writeln!(o, "{}", d.unwrap()).unwrap();
    }
}

mod utils {
    use super::*;

    pub struct CpReader<R: BufRead> {
        r: R,
        s: String,
    }

    macro_rules! fn_read {
        { $f:ident($($t:ident),*) } => {
            #[allow(dead_code)]
            pub fn $f<$($t: FromStr),*>(&mut self) -> ($($t),*) {
                let i = &mut self.read_line().split(' ');
                ($(read_next::<$t,_>(i)),*)
            }
        };
    }

    impl<R: BufRead> CpReader<R> {
        pub fn new(r: R) -> Self {
            CpReader {
                r: r,
                s: String::new(),
            }
        }
        pub fn read_line(&mut self) -> &str {
            self.s.clear();
            self.r.read_line(&mut self.s).unwrap();
            self.s.trim()
        }

        pub fn read<T: FromStr>(&mut self) -> T {
            self.read_line().parse().ok().unwrap()
        }
        fn_read! { read2(T1, T2) }
        fn_read! { read3(T1, T2, T3) }
        fn_read! { read4(T1, T2, T3, T4) }
        fn_read! { read5(T1, T2, T3, T4, T5) }
    }
    fn read_next<'a, T: FromStr, I: Iterator<Item = &'a str>>(i: &mut I) -> T {
        i.next().unwrap().parse().ok().unwrap()
    }

}


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

int main()
{
    int A, B, C;
    cin >> A >> B >> C;
    if (A == B)
    {
        cout << C;
    }
    else if (B == C)
    {
        cout << A;
    }
    else
    {
        cout << B;
    }

    cout << "\n";

    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

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

		// 入力値の取得
		int N = sc.nextInt();
		int M = sc.nextInt();
		
		// 結果の出力
		System.out.println((N * (N-1) / 2) + (M * (M-1) / 2));

		sc.close();
	}
}


Measured memory_bytes: 21716
#include <iostream>  
#include <string.h> 
using namespace std;
int main() {
    int a, b, c, d;
    cin >> a >> b >> c ;
    if (a == b&&b == c)
        cout << 1;
    else if (a != b && b != c && c != a)
        cout << 3;
    else 
        cout<<2;
    return 0;
}
 


Measured memory_bytes: 3600