akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <utility>
#include<vector>
#include<iomanip>
#include<map>
#include <queue>
#include<cmath>
#include<cstdio>
#include<iomanip>
#include<set>

using namespace std;
using ll = long long int;


int main(void){
  
  string s;
  cin>>s;
  int n = s.size();

  //step1
  for(int i=0;i<n/2;i++){
    int j = n-1-i;
    if(s[i]!=s[j]){
      cout<<"No"<<endl;
      return 0;
    }
  }

  //step2
  int start=0, end=(n-1)/2;
  for(int i=start;i<end;i++){
    int j=end-1-i;
    if(s[i]!=s[j]){
      cout<<"No"<<endl;
      return 0;
    }
  }  

  //step3
  start=(n+3)/2 -1, end=n;
  for(int i=start;i<end;i++){
    int j=end-1-i;
    if(s[i]!=s[j]){
      cout<<"No"<<endl;
      return 0;
    }
  }  

  cout<<"Yes"<<endl;

  return 0;
}

Measured memory_bytes: 256
n, m = map(int,input().split())
x = [0]*m

for i in range(n):
    ipt = list(map(int,input().split()))
    k = ipt[0]
    a = ipt[1:len(ipt)]
    for j in range(k):
        x[a[j]-1]+=1

print(x.count(n))

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

#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define lfs <<fixed<<setprecision(10)<<
#define test cout<<"test"<<endl;
#define fi first
#define se second
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define rep(i,n,m) for(ll i = n; i < (ll)(m); i++)
#define rrep(i,n,m) for(ll i = n - 1; i >= (ll)(m); i--)
typedef long long ll;
typedef long double ld;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const ll INF = 1e18;
using P = pair<ll, ll>;
template<typename T>
void chmin(T &a,T b){if(a>b)a=b;}
template<typename T>
void chmax(T &a,T b){if(a<b)a=b;}
void pmod(ll &a,ll b){a=(a+b)%MOD;}
void pmod(ll &a,ll b,ll c){a=(b+c)%MOD;}
void qmod(ll &a,ll b){a=(a*b)%MOD;}
void qmod(ll &a,ll b,ll c){a=(b*c)%MOD;}
ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
template<typename T1,typename T2>
void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}  
template<typename T>
void debug(vector<vector<T>>v,ll h,ll w){for(ll i=0;i<h;i++)
{cout<<v[i][0];for(ll j=1;j<w;j++)cout spa v[i][j];cout<<endl;}};
void debug(vector<string>v,ll h,ll w){for(ll i=0;i<h;i++)
{for(ll j=0;j<w;j++)cout<<v[i][j];cout<<endl;}};
template<typename T>
void debug(vector<T>v,ll n){cout<<v[0];
for(ll i=1;i<n;i++)cout spa v[i];cout<<endl;};
template<typename T>
vector<vector<T>>vec(ll x, ll y, T w){
  vector<vector<T>>v(x,vector<T>(y,w));return v;}
ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;}
template<typename T>
void emp(map<T,ll>&m, T x){m.emplace(x,0).first->second++;}

int main(){
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);
  ll res=0,res1=INF,res2=-INF,buf=0;
  bool judge = true;
  string s;cin>>s;
  string t;cin>>t;
  ll n=s.size(),m=t.size();
  ll q;cin>>q;
  vector<ll>l1(q),l2(q),r1(q),r2(q);
  rep(i,0,q)cin>>l1[i]>>r1[i]>>l2[i]>>r2[i];
  vector<ll>a(n+1),b(m+1);
  rep(i,0,n){
    if(s[i]=='A')a[i+1]=a[i]+1;
    else a[i+1]=a[i]+2;
  }
  rep(i,0,m){
    if(t[i]=='A')b[i+1]=b[i]+1;
    else b[i+1]=b[i]+2;
  }
  rep(i,0,q){
    ans2((a[r1[i]]-a[l1[i]-1])%3==(b[r2[i]]-b[l2[i]-1])%3);
  }
  return 0;
}

Measured memory_bytes: 5584
(defun sum (from to)
  (/ (* (+ from to)
        (1+ (- to from)))
     2))

(defun solve (n)
  (if (= n 1)
      0
      (1+ (sum 2 (1- n)))))

#-swank
(let* ((n (read)))
  (format t "~A~%" (solve n)))


Measured memory_bytes: 8676
N = int(input())


def simple_factrization(n):
    table = []  # 素因数を格納する
    temp = n    # nを素因数で割っていった値を一時的に格納する

    for i in range(2, int(n**0.5//1) + 1):
        if temp % i == 0:
            cnt = 0

            while temp % i == 0:
                cnt += 1
                temp //= i

            table.append([i, cnt])

    if temp != 1:
        table.append([temp, 1])

    if temp == []:
        table.append([n, 1])

    return table


f = simple_factrization(N)

count = 0
for i, f_i in enumerate(f):

    tmp_f_i = f_i[1]

    for j in range(1, f_i[1] + 1):
        tmp_f_i -= j
        if tmp_f_i < 0:
            break
        count += 1

print(count)

        





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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

const ll INF = (1ll<<60);
ll dp[1010][20101];

struct block{
	ll w, s, v;
	bool operator<(const block &right)const{
		return (w+s < right.w + right.s);
	}
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    REP(i, 1010)REP(j, 20101) dp[i][j] = -INF;
    dp[0][0] = 0;

    ll N;
    cin >> N;
    vector<block> A(N);
    REP(i, N){
    	cin >> A[i].w >> A[i].s >> A[i].v;
    }
    sort(A.begin(), A.end());

    REP(i, N){
    	REP(j, 20101){
    		if(dp[i][j] == -INF) continue;
    		dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
    		if(j+A[i].w<20101 && j<=A[i].s) dp[i+1][j+A[i].w] = max(dp[i+1][j+A[i].w], dp[i][j]+A[i].v);
    	}
    }
    ll res = 0;
    REP(i, 20101){
    	res = max(res, dp[N][i]);
    }
    cout << res <<  endl;
    return 0;
}

Measured memory_bytes: 158848
N = int(input())
T = list(map(int,input().split()))
M = int(input())
ans = 0
b = []
for j in range(M):
    P, X = map(int,input().split())
    for i in range(N):
        if i + 1 == P:
            ans += X
        else:
            ans += T[i]
    b.append(ans)
    ans = 0
for i in range(M):
    print(b[i])

Measured memory_bytes: 8900
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define REP(i,m,n) for(int i=m;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define sort(vec) sort(vec.begin(),vec.end())
#define reverse(vec) reverse(vec.begin(),vec.end())
int gcd(int x,int y){
    if(x%y==0)return y;
    return gcd(y,x%y);
}
string s;
int o=0,z=0;
signed main(){
    cin>>s;
    int l=s.size();
    rep(i,l){
        if(s[i]=='0')z++;
        else o++;
    }
    int ans=min(o,z);
    ans*=2;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 512
import java.io.IOException;
import java.io.InputStream;
import java.util.*;
import java.lang.Math;

public class Main {
    public static void main(String[] args) {
        FS reader = new FS();
        // write reader
        int    N = reader.nextInt();
        int    K = reader.nextInt();
        long[] H = new long[N];
        for (int i=0; i<N; i++) {
            H[i] = reader.nextLong();
        }
        long[] C = new long[N];
        Arrays.fill(C, Long.MAX_VALUE);
        C[0] = 0;

        for (int i=0; i<N; i++) {
            for (int j=1; j<=K; j++) {
                if (N <= i+j) break;
                C[i+j] = Math.min(C[i+j], C[i]+Math.abs(H[i]-H[i+j]));
            }
        }
        System.out.println(C[N-1]);
    }

    // Read Class
    static class FS {
        private final InputStream in = System.in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;
        private boolean hasNextByte() {
            if (ptr < buflen) {
                return true;
            } else {
                ptr = 0;
                try {
                    buflen = in.read(buffer);
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (buflen <= 0) {
                    return false;
                }
            }
            return true;
        }
    
        private int readByte() { return hasNextByte() ? buffer[ptr++] : -1;}
        private boolean isPrintableChar(int c) {return 33 <= c && c <= 126;}
        private void skipUnprintable() {while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}
    
        public boolean hasNext() { skipUnprintable(); return hasNextByte();}
        public String next() {
            if (!hasNext()) throw new NoSuchElementException();
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while(isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }
        public int nextInt() {
            return (int)nextLong();
        }
        public long nextLong() {
            if (!hasNext()) throw new NoSuchElementException();
            long n = 0;
            boolean minus = false;
            int b = readByte();
            if (b == '-') {
                minus = true;
                b = readByte();
            }
            if (b < '0' || '9' < b) {
                throw new NumberFormatException();
            }
            while(true) {
                if ('0' <= b && b <= '9') {
                    n *= 10;
                    n += b - '0';
                } else if(b == -1 || !isPrintableChar(b)) {
                    return minus ? -n : n;
                } else {
                    throw new NumberFormatException();
                }
                b = readByte();
            }
        }
    }
}



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

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

  ll N; cin >> N;
  N = N % 10;

  string ans = "hon";
  if (N == 3) ans = "bon";
  if (N == 0) ans = "pon";
  if (N == 1) ans = "pon";
  if (N == 6) ans = "pon";
  if (N == 8) ans = "pon";

  cout << ans << '\n';
  return 0;
}

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

int main(){
  string S;
  cin >> S;
  for(int i=2; i<S.size(); i+=2){
    bool flag = true;
    for(int j=0; j<(S.size()-i)/2; j++){
      if(S[j]!=S[(S.size()-i)/2+j]){
        flag = false;
        break;
      }
    }
    if(flag){
      cout << S.size()-i << endl;
      return 0;
    }
  }
  return 0;
}

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

int main(){
  long N;
  int f1, f2, f3, f4, f5, f6, f7, f8, f9, fn;
  cin >> N;
  
  f9 = N / 100000000;
  f8 = (N / 10000000) - f9 * 10;
  f7 = (N / 1000000) - f9 * 100 - f8 * 10;
  f6 = (N / 100000) - f9 * 1000 - f8 * 100 - f7 * 10;
  f5 = (N / 10000) - f9 * 10000 - f8 * 1000 - f7 * 100 - f6 * 10;
  f4 = (N / 1000) - f9 * 100000 - f8 * 10000 - f7 * 1000 - f6 * 100 - f5 * 10;
  f3 = (N / 100) - f9 * 1000000 - f8 * 100000 - f7 * 10000 - f6 * 1000 - f5 * 100 - f4 * 10;
  f2 = (N / 10) - f9 * 10000000 - f8 * 1000000 - f7 * 100000 - f6 * 10000 - f5 * 1000 - f4 * 100 - f3 * 10;
  f1 = N - f9 * 100000000 - f8 * 10000000 - f7 * 1000000 - f6 * 100000 - f5 * 10000 - f4 * 1000 - f3 * 100 - f2 * 10;
  fn = f1 + f2 + f3 + f4 + f5 + f6 + f7 + f8 + f9;
  
  if(N % fn == 0){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n; cin >> n;
    vector <int> a(n); cin >> a[0] >> a[1]; int res = 0;
    for(int i = 2; i < n; i += 1) {
      cin >> a[i];
      if((a[i - 1] > a[i - 2] && a[i - 1] < a[i]) || (a[i - 1] < a[i - 2] && a[i - 1] > a[i])) {
        res += 1;
      }
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<array>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<numeric>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<unordered_map>
#include<queue>
#include<vector>
using namespace std;

//#define int long long
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define dump(o) {cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) {cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
const int MOD = 1e9 + 7;
string s = "ABCDE";
signed main() {
	int s1[5], s2[5], sum[5];
	for (; cin >> s1[0] >> s2[0] && s1[0];) {
		rep(i, 1, 5)cin >> s1[i] >> s2[i];
		rep(i, 0, 5)sum[i] = s1[i] + s2[i];
		cout << s[max_element(sum, sum + 5) - sum] << " " << *max_element(sum, sum + 5) << endl;
	}
	return 0;
}

Measured memory_bytes: 3140
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define all(x) x.begin(), x.end()

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

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

int main(){
  ll n,a,b;
  cin >>n >>a >>b;
  if((b-a)%2==0) cout << (b-a)/2 << endl;
  else if((b-a)%2!=0){
    ll ans = min(a-1, n-b)+1+(b-a-1)/2;
    cout << ans << endl;
  }
  return 0; 
}

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

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll k,a,b,c,s;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>k;
    for(a=1;a<=k;a++)
        for(b=1;b<=k;b++)
            for(c=1;c<=k;c++)
    {
        s+=__gcd(a,__gcd(b,c));
    }
    cout<<s;
    return 0;
}


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

R,C,K = map(int, input().split())

items = [[0 for _ in range(C+1)] for _ in range(R+1)]
for i in range(K):
  r,c,v = map(int, input().split())
  items[r][c] = v

DP_prev = [0 for _ in range(C+1)]
DP1 = [0 for _ in range(C+1)]
DP2 = [0 for _ in range(C+1)]
DP3 = [0 for _ in range(C+1)]
for r in range(1,R+1):
  for c in range(1,C+1):
    item = items[r][c]
    DP1[c] = max(DP_prev[c]+item,DP1[c-1])
    DP2[c] = max(DP1[c],DP2[c-1],DP1[c-1]+item)
    DP3[c] = max(DP2[c],DP3[c-1],DP2[c-1]+item)
  DP_prev = DP3
        
print(DP_prev[C])

Measured memory_bytes: 149656
#include<stdio.h>
#include<string.h>
 
int main()
{
    char str[50];
 
    gets(str);
 
    if(strcmp(str, "Sunny")==0)
                    printf("Cloudy");
    if(strcmp(str, "Cloudy")==0)
              printf("Rainy");
    if(strcmp(str, "Rainy")==0)
                printf("Sunny");
 
    return 0;
    getch();
}

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

int main() {

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

    int n, k ;
    cin >> n >> k ;
    if(k > (n-1)*(n-2)/2)
        cout << -1 ;
    else{

        cout << n*(n-1)/2 - k << '\n';
        int ans = n*(n-1)/2 - k;
        for(int i = 2; i <= n; i++){

            cout << 1 << ' ' << i << '\n' ;

        }
        int b = n ;
        for(int i = 2; i <= n && b <= ans; i++){

            for(int j = i+1; j <= n && b <= ans; j++){

                b++ ;
                cout << i << ' ' << j << '\n' ;

            }

        }

    }

}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define hhh cerr<<"hhh"<<endl
#define see(x) cerr<<(#x)<<'='<<(x)<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0,f=1;char c=getchar();while(c!='-'&&(c<'0'||c>'9'))c=getchar();if(c=='-')f=-1,c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}

const int maxn = 3e5+7;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;

ll dp[100][10];

vector<ll> v;

void dfs(int pos, int pre, ll num) {
    if(pos==0) { v.push_back(num); return; }
    if(pre!=0) dfs(pos-1,pre-1,num*10+pre-1);
    dfs(pos-1,pre,num*10+pre);
    if(pre!=9) dfs(pos-1,pre+1,num*10+pre+1);
}

int main() {
    int k=read();
    if(k<10) return printf("%d\n", k), 0;
    for(int i=0; i<10; ++i) dp[1][i]=1;
    int len=0, p=0; ll s=9;
    for(int i=2; ; ++i) {
        int f=0;
        for(int j=0; j<10; ++j) {
            if(j==0) dp[i][j]=dp[i-1][j]+dp[i-1][j+1];
            else if(j==9) dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
            else dp[i][j]=dp[i-1][j-1]+dp[i-1][j]+dp[i-1][j+1];
            if(j) s+=dp[i][j];
            if(s>=k) {
                len=i, p=j; f=1;
                break;
            }
        }
        if(f) break;
    }
    for(int i=1; i<=len; ++i) {
        for(int j=1; j<10; ++j) dfs(i-1,j,j);
    }
    sort(v.begin(),v.end());
    printf("%lld\n", v[k-1]);
}

Measured memory_bytes: 2420
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <complex>

#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

#include <stdexcept>

using namespace std;

// type alias
using ll = long long;
using ull = unsigned long long;
using comp = complex<double>;

const ll MOD = 1000000007LL;
const double PI = 3.14159265358979323846;

//conversion
//------------------------------------------
inline int toint(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class t> inline string tostring(t x) { ostringstream sout; sout << x; return sout.str(); }

//debug
#define DUMP(x)  cerr << #x << " = " << (x) << endl
#define DEBUG(x) cerr << #x << " = " << (x) << " (l" << __line__ << ")" << " " << __file__ << endl

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

	ll N;
	cin >> N;

	set<ll> res;
	ll q = N - 1;
	for (ll i = 1; i * i <= q; ++i) {
		if (q % i == 0) {
			res.insert(i);
			res.insert(q / i);
		}
	}

	map<ll, ll> prime_to_count;
	vector<bool> is_prime(sqrt(N) + 1, true);
	q = N;
	for (ll p = 2; p * p <= q; ++p) {
		if (!is_prime[p]) continue;
		for (ll i = 2; p * i < is_prime.size(); ++i) is_prime[p * i] = false;

		while (q % p == 0) {
			if (prime_to_count.count(p) == 0) prime_to_count[p] = 0;
			++prime_to_count[p];
			q /= p;
		}
	}
	if (q != 1) {
		if (prime_to_count.count(q) == 0) prime_to_count[q] = 0;
		++prime_to_count[q];
	}

	ll divisor_count = 1;
	for (auto iter = prime_to_count.begin(); iter != prime_to_count.end(); ++iter) {
		divisor_count *= iter->second + 1;
	}

	ll divisor, idx, mult_count;
	for (ll i = 1; i < divisor_count; ++i) {
		idx = i;
		divisor = 1;
		for (auto iter = prime_to_count.begin(); iter != prime_to_count.end(); ++iter) {
			mult_count = idx % (iter->second + 1);
			for (ll j = 0; j < mult_count; ++j) {
				divisor *= iter->first;
			}
			idx /= iter->second + 1;
		}

		q = N;
		while (q % divisor == 0) {
			q /= divisor;
		}
		if (q % divisor == 1) {
			res.insert(divisor);
		}
	}

	if (res.count(1)) res.erase(1);
	cout << res.size() << endl;

	return 0;
}


Measured memory_bytes: 384
import std.stdio;
import std.string;
import std.conv;
import std.range;
import std.array;
import std.algorithm;

void main(){
  auto a=readln.chomp.to!int;
  auto b=readln.chomp.to!int;
  auto c=readln.chomp.to!int;
  auto d=readln.chomp.to!int;
  if(a>=b&&c>=d)writeln(b+d);
  else if(a>=b&&c<=d)writeln(b+c);
  else if(a<=b&&c>=d)writeln(a+d);
  else if(a<=b&&c<=d)writeln(a+c);
}    

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



typedef tree<long long, null_type, less<long long>, rb_tree_tag, 
             tree_order_statistics_node_update> 
    new_data_set; 
 
 
//defines
typedef long long ll;
typedef long double ld;

ll a,b,c,n,m,k,t=1;

void solve()
{
  cin>>n>>m;
  priority_queue<ll>p;
  for(ll i=0;i<n;i++)cin>>k,p.push(k);
  for(ll i=1;i<=m;i++)
  {
      c=p.top();
      p.pop();
      p.push(c/2);
  }
  ll ans=0;
  while(!p.empty())
  {
      ans+=p.top();p.pop();
  }
  cout<<ans;
 if(t>0)cout<<"\n";
}

int32_t main()
{
#ifdef ONPC
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

 // cin>>t;
    while(t--)
    {
        solve();
    }
  //cout<<sum;
        
    return 0;
}

Measured memory_bytes: 1400
#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define ll long long

using namespace std;

const int N=1e5+10,M=2e5+10;
int n,m,cnt,head[N],x,y,tot,flag,col[N]; ll a,b,c;
struct edge{int to,nxt;}e[M<<1];

void adde(int x,int y){
	e[++cnt].to=y; e[cnt].nxt=head[x]; head[x]=cnt;
}

void dfs(int u,int c){
	++tot,col[u]=c;
	for (int i=head[u],v;i;i=e[i].nxt){
		v=e[i].to;
		if (col[v]==-1) dfs(v,c^1);
		else if (col[v]==c) flag=1;
	}
}

int main(){
	scanf("%d%d",&n,&m);
	rep (i,1,m) scanf("%d%d",&x,&y),adde(x,y),adde(y,x);
	memset(col,-1,sizeof(col));
	rep (i,1,n) if (col[i]==-1){
		tot=0,flag=0,dfs(i,0);
		if (tot==1) a++;
		else if (flag) b++;
		else c++;
	}
	printf("%lld\n",a*(2*n-1)-a*(a-1)+c*c*2+b*b+b*c*2);
	return 0;
}

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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9;
const ll MOD = 1e9 + 7;

const int MAXN = 1e5 + 5;

void solve(){
	int n;
	scanf("%d", &n);
	ll ans = 1ll;
	REPN(i, 2, n){
		int fl = 0;
		for(int j = 2; j * j <= i; j++){
			if (i % j == 0){
				fl = 1;
				break;
			}
		}
		if (!fl){
			//cout << i << endl;
			int cur = 1;
			for(int v = n; v; v /= i){
				cur += v / i;
			}
			ans = (ans * cur) % MOD;
		}
	}
	printf("%lld\n", ans);
}   

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}


Measured memory_bytes: 256
#include<iostream>
    using namespace std;
     
    int main()
    {
       int A,B;
       cin >> A >> B ;
       if(A%3==0 || B%3==0){
           cout << "Possible"<< endl;
       }
       else if((A+B)%3==0){
           cout << "Possible"<< endl;
       }
       else{
           cout << "Impossible"<< endl;
       }
       return 0;
    }

Measured memory_bytes: 256
H, W, K = map(int, input().split())
board = []
for _ in range(H):
    board.append(list(input()))
ans = 0
for bh in range(1 << H):
    for bw in range(1 << W):
        num = 0
        for y in range(H):
            if (bh >> y) & 1 == 0:
                continue
            for x in range(W):
                if (bw >> x) & 1 == 0:
                    continue
                if board[y][x] == '#':
                    num += 1
        if num == K:
            ans += 1
print(ans)

Measured memory_bytes: 9196
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <cstdlib>

using namespace std;

int main(void)
{
    int n;
    cin >>n;

    vector<long long> a;
    long long sum = 0;
    for(int i = 0; i < n; i++){
        long long tmp;
        cin >>tmp;
        a.push_back(tmp);
        sum += tmp;
    }

    long long csum = 0;
    long long ans = LLONG_MAX;
    for(int i = 0; i < n-1; i++){
        csum += a[i];
        ans = min(ans, abs(sum - csum * 2));
    }

    printf("%lld\n", ans);

    return 0;
}

Measured memory_bytes: 2420
import java.util.Scanner;

public class Main {
	static int mod = 1_000_000_007;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		
		int n = N-K+1;
		for (int i=1; i<K+1; i++){
			
			if (n>0){
				long blue = nCr(N-K+1,i);
				long red = nCr(K-1,i-1);
			
				System.out.println(blue*red%mod);
			}
			else 
				System.out.println(0);
			
			n--;
		}
		
		sc.close();
	}
	
	public static long factorial(int n) {
		long tmp = 1;
		for (int i=n; i>0; i--) {
			tmp = (tmp*i)%mod;
		}
		return tmp;
	}
	
	public static long pow(long a,int n) {
	    long res=1;
	    while (n>0) {
	        if ((n-n/2*2)==1) {
	            res=(res*a)%mod;
	        }
	        a=(a*a)%mod;
	        n>>=1;
	    }
	    return res;
	}
 
	public static long modinv(long n) {
		return pow(n, mod-2);
	}
 
	public static long nCr(int n, int r) {
		return factorial(n) * modinv(factorial(n-r)) % mod * modinv(factorial(r)) % mod;
	}
}

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

#define rep(i, a, n)  for(ll i=a; i<n; i++)
#define per(i, a, n)  for(ll i=n-1; i>=a; i--)
#define fill0(n)  setfill('0') << right << setw(n)
#define all(x)  (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define LONGMAX 1e18
#define INTMAX 1000000000
using namespace std;
typedef long long ll;
typedef pair<int,int> p;

int a,b,c,d,e,f;
int water, sugar;

int main(){
  cin >> a >> b >> c >> d >> e >> f;
  int a100 = 100*a;
  int b100 = 100*b;
  double temp_dense = 0.0;
  double temp_sugar = 0;
  double temp_water = a100;
  rep(i,0,31){
    rep(j,0,31){
      rep(k,0,100){
        rep(l,0,100){
          double water = a100*i+b100*j;
          double sugar = k*c+l*d;
          if(water==0||water+sugar > f||e * water/100 < sugar)break;
          double dense = double(100*sugar/(water+sugar));
          if(dense > temp_dense){
            temp_dense = 100*sugar/(water+sugar);
            temp_sugar = sugar;
            temp_water = water;
          }
        }
      }
    }
  }
  std::cout << temp_water+temp_sugar <<' '<<temp_sugar << '\n';
}


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

int main() {
  int H, W, K, sum;
  sum = 0;
  
  cin >> H >> W >> K;
  
  vector<vector<char>> vec(H, vector<char>(W)), copy(H, vector<char>(W));
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      cin >> vec.at(i).at(j);
    }
  }
  copy = vec;

  bool ans = false;
 
  // すべての選び方を試して、総和がKになるものがあるかを調べる
  for (int tmp = 0; tmp < (1 << H); tmp++) {
    bitset<6> s(tmp);  // 最大20個なので20ビットのビット列として扱う
    for (int tmpr = 0; tmpr < (1 << W); tmpr++) {
      bitset<6> t(tmpr);  // 最大20個なので20ビットのビット列として扱う
 
    // ビット列の1のビットに対応する整数を選んだとみなして総和を求める
    
      for (int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
          if(s.test(i)||t.test(j)){
            copy.at(i).at(j)='0';
          }
        }
      }
      int cnt = 0;
      for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
          if(copy.at(i).at(j)=='#') cnt++;
        }
      }
      if(cnt==K) sum++;
      copy = vec;

    }
  }
  cout << sum;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int inf = INT_MAX;
const ll INF = LLONG_MAX;
const ll MOD = 1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b, const ll mod=MOD) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b, const ll mod=MOD) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b, const ll mod=MOD) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b, const ll mod=MOD) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    string in; cin >> in;
    in[3] = '8';
    cout << in << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
using namespace std;
#define int long long
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
#define endl '\n'
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll inf=1e9+7;
const ll mod=1e9+7;
vector<vector<ll> >G(100010);
vector<vector<ll> >dp(100010,vector<ll>(11,0));
void solve(ll i,ll d,ll c){
    if(dp[i][d]){
        return;
    }
    dp[i][d]=c;
    if(d==0){
        return;
    }
    if(dp[i][d-1]==0)solve(i,d-1,c);
    for(auto e:G[i]){
        if(dp[e][d-1])continue;
        solve(e,d-1,c);
    }
    return;
}
signed main(){
    ll n,m;
    cin>>n>>m;
    rep(i,m){
        ll a,b;cin>>a>>b;
        a--;b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    ll q;cin>>q;
    vector<ll>v(q),d(q),c(q);
    rep(i,q){
        cin>>v[i]>>d[i]>>c[i];
        v[i]--;
    }
    for(int i=q-1;i>=0;i--){
        solve(v[i],d[i],c[i]);
    }
    rep(i,n){
        cout<<dp[i][0]<<endl;
    }
}

Measured memory_bytes: 20980
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
constexpr LL MOD = 1'000'000'007LL;
char G[1001][1001];
LL mpow(LL a, LL n) {
    LL r = 1;
    if (a <= -MOD || a >= MOD) a %= MOD;
    while (n > 0) {
        if (n % 2) r = r * a % MOD;
        n /= 2, a = a * a % MOD;
    }
    return r < 0 ? r + MOD : r;
}
void mul(LL a[2][2], const LL b[2][2]) {
    LL c[2][2];
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            c[i][j] = (a[i][0] * b[0][j] + a[i][1] * b[1][j]) % MOD;
        }
    }
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            a[i][j] = c[i][j];
        }
    }
}
LL solve(LL n, LL c, LL v, LL K) {
    K--;
    LL M[2][2] = {{1, 0}, {0, 1}}, T[2][2] = {{n, c}, {0, v}};
    while (K > 0) {
        if (K % 2) mul(M, T);
        K /= 2, mul(T, T);
    }
    LL r = (M[0][0] - M[0][1]) % MOD;
    return r < 0 ? r + MOD : r;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int H, W;
    LL K;
    cin >> H >> W >> K;
    if (K <= 1) return cout << "1\n", 0;

    for (int i = 0; i < H; i++) cin >> G[i];

    LL cb = 0, ch = 0, cw = 0, vh = 0, vw = 0;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (G[i][j] == '#') {
                cb++;
                if (G[i + 1][j] == '#') ch++;
                if (G[i][j + 1] == '#') cw++;
            }
        }
    }
    for (int i = 0; i < H; i++) if (G[i][0] == '#' && G[i][W - 1] == '#') vw++;
    for (int j = 0; j < W; j++) if (G[0][j] == '#' && G[H - 1][j] == '#') vh++;
    if (vw == 0 && vh == 0) {
        cout << mpow(cb, K - 1) << '\n';
    } else if (vw > 0 && vh > 0) {
        cout << 1 << '\n';
    } else {
        cout << solve(cb, vw > 0 ? cw : ch, vw > 0 ? vw : vh, K) << '\n';
    }
    return 0;
}


Measured memory_bytes: 1280
#include"bits/stdc++.h"
using namespace std;
using ll=long long;
template<typename T=ll>inline T in(istream&is=cin){T ret;is>>ret;return ret;}
template<typename T>inline auto vec2(typename vector<T>::size_type h,typename vector<T>::size_type w,T v=T()){return vector<vector<T>>(h,vector<T>(w,v));}

int main()
{
    ll a=in(),b=in();
    for(int i=1;i<2000;++i){
        if(i*8/100==a&&i*10/100==b){
            cout<<i<<endl;
            return 0;
        }
    }
    cout<<-1<<endl;
}


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

using namespace std;

using ll = long long;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, y;
    cin >> n >> y;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; i + j <= n; j++) {
            int cost = 10000 * i + 5000 * j;
            if (y - cost == (n - i - j) * 1000) {
                cout << i << " " << j << " " << n - i - j << endl;
                return 0;
            }
        }
    }
    cout << "-1 -1 -1" << endl;
    return 0;
}

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

using namespace std;

int main() {
  size_t taro = 0;
  size_t hanako = 0;

  int n;
  cin >> n;

  string a, b;
  for (int i = 0; i < n; ++i) {
    cin >> a >> b;
    if (a > b) {
      taro += 3;
    } else if (a < b) {
      hanako += 3;
    } else {
      ++taro;
      ++hanako;
    }
  }

  cout << taro << " " << hanako << endl;
  return 0;
}

Measured memory_bytes: 1204
import sys
def input():
  return sys.stdin.readline().rstrip()

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

ans=0
right=0
while True:
  if ans==0:
    right+=K
  else:
    right+=K-1
  ans+=1
  if N<=right:
    break;

print(ans)


Measured memory_bytes: 83920
#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;

typedef long long ll;
template <typename T>
    using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <char cmp = '<'>
    bool icmp(ll a, ll b){ if(cmp=='>') return a > b; else return a < b;}
namespace enhanced_pair{
    typedef pair<ll,ll> pll;
    ostream& operator << (ostream& o, const pll a){
        o<<a.first<<" "<<a.second;
        return o;
    }
    istream& operator >> (istream& i, pll& p){
        i>>p.first>>p.second;
        return i;
    }
    template <char cmp1 = '<', char cmp2 = '<'>
        bool pcmp(pll a, pll b){ return icmp<cmp1> (a.first,b.first) || (a.first==b.first && icmp<cmp2> (a.second,b.second));}
} using namespace enhanced_pair;
const size_t NMAX = 200009;
const ll MOD = 1e9+7;
ll lastbit(ll num){
    return num & -num;
}
ll binPow(ll num, ll p, ll mod = MOD){
    if(!p) return 1;
    ll aux = binPow(num,p/2);
    return aux*aux%mod*(p%2?num:1)%mod;
}

void tc()
{

}
ll sum[NMAX],s=0;
int main()
{
    ll n,m,t=0,cnt=0,x;
    cin>>n>>m>>t;
    for(ll i=0;i<n;i++){
        cin>>x;
        sum[i]=(i?sum[i-1]:0)+x;
        if(sum[i]<=t)
            cnt=max(cnt,i+1);

    }
    for(ll i=0;i<m;i++){
        cin>>x;
        if(s<=t) cnt=max(cnt,i);
        s+=x;
        if(s<=t){
            ll total=i+(upper_bound(sum,sum+n,t-s)-sum)+1;
            cnt=max(cnt,total);
        }
    }
    cout<<cnt;
    return 0;
}



Measured memory_bytes: 5128
#include <iostream>
int main()
{
    int a, b, c;
    std::cin >> a;
    std::cin >> b;
    std::cin >> c;

    if (a < b && b < c)
    {
        std::cout <<"Yes\n";
    }
    else
    {
        std::cout <<"No\n";
    }
    return 0;
}


Measured memory_bytes: 3100
#include<stdio.h>

int main(void)
{
int i,j,n,max,min,t,ii,a,k;
int num[8];
int tem[8];

scanf("%d",&n);
for(k=0;k<n;k++){

max=0;
min=0;
ii=1;

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

for(i=0;i<8;i++){
tem[i]=num[i];
}
for(i=0;i<8;i++){
for(j=0;j<7-i;j++){
if(tem[j]>tem[j+1]){
t=tem[j];
tem[j]=tem[j+1];
tem[j+1]=t;
}
if(9-num[j]>9-num[j+1]){
t=num[j];
num[j]=num[j+1];
num[j+1]=t;
}
}
}

for(i=0;i<8;i++){
max+=tem[i]*ii;
min+=num[i]*ii;
ii*=10;
}

printf("%d\n",max-min);
}

return 0;
}

Measured memory_bytes: 600
#! python3
# ring.py

sent = input()
pat = input()

len_sent = len(sent)
len_pat = len(pat)

flag = False
for i in range(len_sent):
    sent_pat = ''
    if i+len_pat <= len_sent:
        sent_pat = sent[i:i+len_pat]
    else:
        sent_pat = sent[i:len_sent] + sent[0:len_pat - (len_sent - i)]
    if sent_pat == pat:
        flag = True

if flag:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 5560
//#include <tourist>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = 1e9;
const ll LINF = ll(1e18);
const int MOD = 1000000007;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define rep(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()
#define debug(v)          \
    cout << #v << ":";    \
    for (auto x : v)      \
    {                     \
        cout << x << ' '; \
    }                     \
    cout << endl;
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;
}
//cout<<fixed<<setprecision(15);有効数字15桁
//-std=c++14
//-std=gnu++17
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll n, m;
vector<vector<int>>v;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    v.resize(n);
    for (int i = 0; i < m; i++)
    {
        int temp,temp1;
        cin >> temp>>temp1;
        temp--;
        temp1--;
        v[temp].push_back(temp1);
        v[temp1].push_back(temp);
    }
    rep(i,n){
        cout<<v[i].size()<<"\n";
    }
}


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

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

        void Solve(ConsoleInput cin)
        {
            int n = cin.ReadInt;
            int w = cin.ReadInt;

            int[] w_n = new int[n];
            long[] v_n = new long[n];

            for (int i = 0; i < n; i++)
            {
                w_n[i] = cin.ReadInt;
                v_n[i] = cin.ReadLong;
            }

            long[,] dp = new long[n + 1, w + 1];
            for (int j = 0; j < w; j++)
            {
                dp[0, j] = 0;
            }

            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j <= w; j++)
                {
                    long tmp1 = 0;
                    if (j >= w_n[i])
                    {
                        tmp1 = dp[i, j - w_n[i]] + v_n[i];
                    }

                    dp[i + 1, j] = Math.Max(tmp1, dp[i, j]);
                }
            }

            Console.WriteLine(dp[n, w]);
        }

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

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

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

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


Measured memory_bytes: 89696
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vout(x) rep(i,x.size()) cout << x[i] << " "
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll,int>;
const int inf = 1e9;
const ll inf_l = 1e18;
const int MAX = 1e5;

int main() {
    int n; cin >> n;
    vvint g(n);
    rep(i,n) {
        int x; cin >> x;
        x--;
        g[i].push_back(x);
    }
    int ct = 0;
    for (int i = 0; i != 1; i = g[i][0]) {
        ct++;
        if (ct > 1e5) {cout << -1 << endl; return 0;}
    }
    cout << ct << endl;
}

Measured memory_bytes: 5760
#include<bits/stdc++.h>
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false) ;
#define endl '\n'
#define ll long long
using namespace std ;

int main() {
    fast ;
    int n,k ;
    cin >> n >> k ;
    int arr[n] ;
    for(int i=0;i<n;i++) cin >> arr[i] ;
    sort(arr,arr+n) ;
    ll ans=0 ;
    for(int i=0;i<k;i++) ans+=arr[i] ;
    cout << ans << endl ;
}

Measured memory_bytes: 3604
N, K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
suc = 1
suc_list = []
for i in range(N-1):
    if A[i] == A[i+1]:
        suc += 1
    else:
        suc_list.append(suc)
        suc = 1
suc_list.append(suc)

suc_list.sort()

kind = len(suc_list) - K

ans = sum(suc_list[0:kind])
print(ans)



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

int main(){
    int n;
    cin >> n;
    auto f = [](int x)->int{
        int ret = 0;
        while(x)    ret += x%10, x/=10;
        return ret;
    };
    int ans = 1<<30;
    for(int i = 1; i < n; i++){
        ans = min(ans, f(i)+f(n-i));
    }
    cout << ans << endl;
    return 0;
}

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

#define ll long long
#define all(it) it.begin(), it.end()
#define FOR(i, n) for(int i = 0; i < n; i++)
#define FORU(i, a, b, s) for(int i = a; i < b; i += s)
#define FORD(i, a, b, s) for(int i = a; i > b; i -= s)
#define endl "\n"

ll INF = 2e18;
ll MOD = 1e9 + 7;
int i, j, k, t;

int main() {
    string s;
    cin >> s;
    int N = s.size();

    int ans = 999;
    FOR(i, N - 2) { ans = min(ans, abs(753 - atoi(s.substr(i, 3).c_str()))); }
    cout << ans << endl;
}

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

const int MX = 100100;
int res = 0;
int N, K;
vector<int> up;
vector<vector<int>> upup;
vector<int> down[MX];
vector<int> dep;
vector<bool> done;

void dfs(int cur, int d) {
    dep[cur] = d;
    for (auto& nxt: down[cur]) dfs(nxt, d + 1);
}

void cut(int cur) {
    if (done[cur]) return;
    done[cur] = true;
    for (auto& nxt: down[cur]) cut(nxt);
}

signed main() {
    cin >> N >> K;
    up.resize(N);
    REP(i, N) cin >> up[i], --up[i];
    if (up[0] != 0) ++res;
    up[0] = -1;
    upup.assign(N, vector<int>(32, -1));
    REP(i, N) upup[i][0] = up[i];
    REP(i, 31) {
        REP(j, N) {
            int idx = upup[j][i];
            if (idx != -1) idx = upup[idx][i];
            upup[j][i + 1] = idx;
        }
    }
    for (int i = 1; i < N; ++i) down[up[i]].emplace_back(i);
    dep.assign(N, -1);
    dfs(0, 0);
    // [dep, idx]
    priority_queue<pair<int, int>> pq;
    REP(i, N) if (dep[i] > K) pq.emplace(dep[i], i);
    done.assign(N, false);
    while (not pq.empty()) {
        auto [dep, idx] = pq.top();
        pq.pop();
        if (done[idx]) continue;
        for (int i = 0; i < 31; ++i) {
            assert(idx != -1);
            if ((K - 1) >> i & 1) idx = upup[idx][i];
        }
        cut(idx);
        ++res;
    }
    cout << res << endl;
}


Measured memory_bytes: 30016
#define _GLIBCXX_DEBUG//TLEの原因になるので注意！！！！！！！！！！！
#include<cmath>
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<int> arr;
stack<int> st;
queue<int> qu;
queue<pair<int,int> > qu2;
priority_queue<int> pq;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define rep2(i,n) for(int i=1; i<=(int)(n); i++)
#define mins(x,y) x=min(x,y)
#define maxs(x,y) x=max(x,y)
typedef set<int> set_t;
typedef set<string> set_g;
typedef complex<double> xy_t;
static const int NIL = -1;
static const int INF = 1000000007;
#define mp make_pair
#define sz(x) int(x.xise())
#define mod 1000000007
#define reps(i,s,n) for(int i = s; i < n; i++)
//#define int long long

//cerrはコメントアウトしなくても通る//ただしTLEを引き起こすことがある

int main(){
    int a,b;
    cin >> a>> b;
    if(0<a&&a<10&&0<b&&b<10){
        cout<<a*b<<endl;
    }else{
        cout<<-1<<endl;
    }
    return 0;
}


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

int main() {
  int a, b, c, x, y;
  cin >> a >> b >> c >> x >> y;
  long long ans = 1ll << 55;
  for (int i = 0; i <= 100000; i++) {
    int an = max(0, x - i);
    int bn = max(0, y - i);
    ans = min(ans, (long long)i * 2 * c + an * a + bn * b);
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
import sys
N = int(sys.stdin.readline())
a_list = list(map(int, sys.stdin.readline().split()))

result = 0
for index in range(N):
    if (index + 1) % 2 == 1:
        if a_list[index] % 2 == 1:
            result += 1
        
print(result)
        



Measured memory_bytes: 9152
s = input()
i = 0
ans = 0
atcg = "ACGT"
for i in range(len(s)):
    for j in range(i, len(s)):
        t = s[i: j + 1]
        cnt = 0
        for n in range(4):
            cnt += t.count(atcg[n])
        
        if cnt == len(t):
            ans = max(ans, cnt)
        
    
print(ans)

Measured memory_bytes: 3064
fun main(args : Array<String>) {
    var (a, b, c) = readLine()!!.split(" ").map { it.toInt() }

    if (a % 2 == 1 || b % 2 == 1 || c % 2 == 1) {
        println(0)
        return
    }

    if (a == b && b == c) {
        println(-1)
        return
    }

    var cnt = 0
    while (a % 2 == 0 && b % 2 == 0 && c % 2 == 0) {
        val ta = a
        val tb = b
        a = (b + c) / 2
        b = (ta + c) / 2
        c = (ta + tb) / 2
        cnt++
    }

    println(cnt)
}

Measured memory_bytes: 35980