akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;
 
public class Solution
{
    public static void Main()
    {
      int N = int.Parse(Console.ReadLine());
      string str1 = Console.ReadLine();
      string str2 = Console.ReadLine();
      string[] strV = str1.Split(' ');
      string[] strC = str2.Split(' ');

      int ans = 0;
      for (int i = 0; i < N; i++)
      {
        int VminusC = int.Parse(strV[i]) - int.Parse(strC[i]);
        if (VminusC > 0) ans += VminusC;
      }

      Console.WriteLine($"{ans}");
    }
}

Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
using i64 = int_fast64_t;
using ui64 = uint_fast64_t;
#define REP(i, n)    for (i64 (i) = 0;   (i) < (n); ++(i))
#define FOR(i, a, b) for (i64 (i) = (a); (i) < (b); ++(i))

int N;
vector<int> A;
bitset<4004004> dp;

signed main() {

    cin >> N;

    A.resize(N);
    REP(i, N) cin >> A[i];

    dp[0] = 1;
    REP(i, N) dp |= dp << A[i];

    ui64 sum = 0;
    REP(i, N) sum += A[i];

    // 中央値はsumの半分(切り上げ)以上
    FOR(i, (sum + 1) / 2, sum + 1) {
        if (dp[i]) {
            cout << i << endl;
            return 0;
        }
    }

}

Measured memory_bytes: 1664
full_num = int(input())     
A = list(map(int, input().split()))  
move = 0
A_result = ""
for i in range(full_num-1):
   if  A[i] >= A[i+1]:
       A_result =A_result+"1"
   else:
       A_result =A_result+"0"
B = list(A_result.split("0"))
C = []
for i in B:
    C.append(len(i))
print(max(C))

Measured memory_bytes: 14224
[a,b,c,x]=require('fs').readFileSync('/dev/stdin','utf8').split('\n').map(n=>n|0)
r=0
Array(a+1).fill().map((_,i)=>
Array(b+1).fill().map((_,j)=>
Array(c+1).fill().map((_,k)=>
	i*500+j*100+k*50==x&&r++
)))
console.log(r)

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

#define forn(i,n) for(int i=0;i<(int)(n);i++)
#define si(c) ((int)(c).size())
#define forsn(i,s,n) for(int i = (int)(s); i<((int)n); i++)
#define dforsn(i,s,n) for(int i = (int)(n)-1; i>=((int)s); i--)
#define all(c) (c).begin(), (c).end()
#define D(a) cerr << #a << "=" << a << endl;
#define pb push_back
#define eb emplace_back
#define mp make_pair

typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> pii;

const int N = 555;

int n, total, col[N], row[N];
string a[N];

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

    cin >> n;
    forn(i,n) cin >> a[i];

    int needCols = n;
    forn(i,n) forn(j,n) {
        bool black = a[i][j] == '#';
        row[i] += black;
        col[j] += black;
        if (col[j] == n) needCols--;
        total += black;
    }

    if (total == 0) cout << -1 << endl;
    else {
        int needRow = n;
        forn(i,n) needRow = min(needRow, n - row[i] + (col[i] == 0));
        cout << needRow + needCols << endl;
    }
    return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const int maN = 1e6+5;

int main() {
    int n, k, t;
    cin >> n >> k >> t;
    int rem = n%k;
    int quo = n/k;
    int ans;
    if(rem > 0)
    {
        ans = t*(quo+1); 
    }
    else
    {
        ans = t*quo;
    }
    cout << ans;
    
	return 0;
}


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

void main()
{
    auto s = readln.chomp;

    string ret;

    foreach (c; s) {
        switch (c) {
            case 'B':
                if (!ret.empty)
                    ret = ret[0..$-1];
                break;
            default:
                ret ~= c;
        }
    }

    writeln(ret);
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);

		int R = scan.nextInt();

		if (R < 1200){
			System.out.println("ABC");
		}else if (R < 2800){
			System.out.println("ARC");
		}else {
			System.out.println("AGC");
		}
	}
}

Measured memory_bytes: 21844
from operator import itemgetter
N = int(input())
A = []
for i in range(N):
  a,b = map(int, input().split())
  A.append([a+b,a,b])
  
A.sort(key=itemgetter(0),reverse=True)

ans = 0
for i in range(N):
  if i%2 == 0:
    ans += A[i][1]
  else:
    ans -= A[i][2]
    
print(ans)


Measured memory_bytes: 24460
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int[] a = new int[3];
    a[0] = sc.nextInt();
    a[1] = sc.nextInt();
    a[2] = sc.nextInt();
    Arrays.sort(a);
    System.out.println(a[0]+" "+a[1]+" "+a[2]);
  }
}

Measured memory_bytes: 26188
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  long long ans = 0;
  int rem = 0;
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    ans += a / 2;
    if (a == 0) {
      rem = 0;
      continue;
    }
    if (rem == 0) {
      rem = a % 2;
    } else {
      if (a % 2 == 1) {
        ans++;
        rem = 0;
      } 
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000000000000000



int main(){
	
	int N;
	cin>>N;
	
	long long X;
	cin>>X;
	
	vector<long long> x(N);
	for(int i=0;i<N;i++)cin>>x[i];
	
	vector<long long> S(N+1,0);
	for(int i=0;i<N;i++){
		S[i+1] = x[i];
		S[i+1] += S[i];
	}
	
	long long ans = Inf;
	
	for(int i=1;i<=N;i++){
		long long t = X*i;
		t += S[N] - S[N-i];
		long long p = 2;
		long long now = 4;
		for(int j=N;j>=1;j-=i){
			if(j-i>=0)t += now * (S[j] - S[j-i]);
			else t += now*S[j];
			if(t>=Inf)break;
			p++;
			now = p*p - (p-1)*(p-1);
		}

		ans = min(ans,t);
	}
	
	cout<<ans+X*N<<endl;
	
	return 0;
}


Measured memory_bytes: 6436
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
 
 
public class Main {
 
    private static final int BIG_NUM  = 2000000000;
 
    public static void main(String[] args) {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        long sum = 0;
        int minimum = BIG_NUM,maximum = -BIG_NUM;
 
        try {
 
            int N = Integer.parseInt(br.readLine());
 
            String first[] = br.readLine().split("[\\s]+");
            int array[] = new int[first.length];
 
            for(int i = 0; i < first.length; i++){
 
                array[i] = Integer.parseInt(first[i]);
                minimum = Math.min(minimum, array[i]);
                maximum = Math.max(maximum, array[i]);
                sum += array[i];
            }
 
            System.out.printf("%d %d %d\n",minimum,maximum,sum);
 
        } catch (IOException e) {
            e.printStackTrace();
        }
 
    }
}


Measured memory_bytes: 31768
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int k = sc.nextInt();
        for (int i=0;i<k;i++){
            if (a>=b){
                b*=2;
            }else {
                c*=2;
            }
        }
        if (a<b&&b<c)System.out.println("Yes");
        else System.out.println("No");
    }
}


Measured memory_bytes: 35636
#!/usr/bin/perl

$line = 0;
while (<>) {
    chomp;
    if($line == 0) {
        @n = split //, $_;
    } else {
        @a = split /\s+/, $_;
    }
    $line++;
}

if($n[0] == $n[2]) {
    print "Yes\n";
} else {
    print "No\n";
}


Measured memory_bytes: 384
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007


#define MAX_N 30000
class Dinic {
public:
  struct Edge { int to, cap, rev; };
  vector<Edge> G[MAX_N];
  int level[MAX_N], iter[MAX_N];

  void add_edge(int from, int to, int cap) {
    G[from].pb((Edge) { to, cap, (int)G[to].size() });
    G[to].pb((Edge) { from, 0, (int)G[from].size() - 1 });
  }

  void bfs(int s) {
    memset(level, -1, sizeof(level));
    queue<int> q;
    level[s] = 0;
    q.push(s);
    while (!q.empty()) {
      int x = q.front(); q.pop();
      for (Edge e : G[x]) {
        if (e.cap > 0 && level[e.to] < 0) {
          level[e.to] = level[x] + 1;
          q.push(e.to);
        }
      }
    }
  }

  int dfs(int x, int t, int f) {
    if (x == t) return f;
    for (int &i=iter[x]; i<G[x].size(); i++) {
      Edge &e = G[x][i];
      if (e.cap > 0 && level[x] < level[e.to]) {
        int d = dfs(e.to, t, min(f, e.cap));
        if (d > 0) {
          e.cap -= d;
          G[e.to][e.rev].cap += d;
          return d;
        }
      }
    }
    return 0;
  }

  int max_flow(int s, int t) {
    int flow = 0;
    while (true) {
      bfs(s);
      if (level[t] < 0) return flow;
      memset(iter, 0, sizeof(iter));
      int f;
      while (true) {
        f = dfs(s, t, INF);
        if (f <= 0) break;
        flow += f;
        if (flow >= INF) return INF;
      }
    }
  }
};

int W, H;
int SX, SY, TX, TY;
char A[100][100];

int WI[100], HI[100];
int IN[100][100], OUT[100][100];

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> H >> W;
  rep(y, H) {
    rep(x, W) {
      cin >> A[x][y];
      if (A[x][y] == 'S') SX = x, SY = y;
      if (A[x][y] == 'T') TX = x, TY = y;
    }
  }
  rep(i, W) WI[i] = 2*W*H + i;
  rep(i, H) HI[i] = 2*W*H + W + i;
  rep(x, W) {
    rep(y, H) {
      IN[x][y] = 2*(y*W+x);
      OUT[x][y] = 2*(y*W+x)+1;
    }
  }

  Dinic dinic;
  rep(x, W) {
    rep(y, H) {
      if (A[x][y] == '.') continue;
      // (x,y) <-> WI[x]
      dinic.add_edge(OUT[x][y], WI[x], INF);
      dinic.add_edge(WI[x], IN[x][y], INF);
      // (x,y) <-> HI[x]
      dinic.add_edge(OUT[x][y], HI[y], INF);
      dinic.add_edge(HI[y], IN[x][y], INF);

      // in -> out
      dinic.add_edge(IN[x][y], OUT[x][y], 1);
    }
  }
  int ans = dinic.max_flow(OUT[SX][SY], IN[TX][TY]);
  if (ans == INF) cout << -1 << "\n";
  else cout << ans << "\n";
  return 0;
}


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

int main() {
  int x,tmp,tmp2;
  double n;
  cin >> n;
  x=n/1.08;
  tmp=(double)x*1.08;
  tmp2=(double)(x+1)*1.08;
  if(tmp==n)  cout << (ll)x << endl;
  else if(tmp2==n) cout << (ll)(x+1) << endl;
  else puts(":(");
}


Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
#include <iostream>

using namespace std;

int main() {
  int n;
  cin >> n;
  int as[n];
  long long sum = 0;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    sum += x;
    as[i] = x;
  }
  sort(as, as + n);
  cout << as[0] << " " << as[n - 1] << " " << sum << endl;
  return 0;
}


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

int main() {

  long long int n;
  cin >> n;

  long long int a[100][100];

  for ( long long int i = 0; i < n; i++ ) {
    for ( long long int j = 0; j < n; j++ ) {
      cin >> a[j][i];
    }
  }

  long long int cnt[100][100] = {0};
  for ( long long int x0 = 0; x0 < n; x0++ ) {
    long long int k = 0;
    for ( long long int y0 = 0; y0 < n; y0++ ) {
      k += a[x0][y0];
      if ( x0 == 0 ) {
	cnt[x0][y0] = k;
      }else {
	cnt[x0][y0] = k + cnt[x0-1][y0];
      }
    }
  }

  long long int ans = -10000000;
  for ( long long int x0 = 0; x0 < n; x0++ ) {
    for ( long long int y0 = 0; y0 < n; y0++ ) {
      for ( long long int x1 = x0; x1 < n; x1++ ) {
	for ( long long int y1 = y0; y1 < n; y1++ ) {
	  long long int k = cnt[x1][y1];
	  if ( x0 > 0 ) {
	    k -= cnt[x0-1][y1];
	  }
	  if ( y0 > 0 ) {
	    k -= cnt[x1][y0-1];
	  }
	  if ( x0 > 0 && y0 > 0 ) {
	    k += cnt[x0-1][y0-1];
	  }
	  ans = max( ans, k );
	}
      }
    }
  }

  cout << ans << endl;

  return 0;

}

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

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP0(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define RREP0(i, n) for (int i = (n)-1; i >= 0; --i)
#define REP1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define RREP1(i, n) for (int i = (n); i >= 1; --i)

typedef long long LL;
typedef pair<int, int> pii;

const int INTINF = int(1e9) + 1;
const LL LLINF = LL(1e18) + 1;
long double eps = 1.0E-14;
#define pow10(n) int(1e##n + n)

void solve()
{
    int N;
    cin >> N;
    // 「全て偶数個である状態」:E
    //「奇数個のりんごがある状態」:O
    // が移り合うことを考えると、
    // 最初にEを踏んだほうが最後までEを押しつけられて負ける
    bool second = true;
    REP1 (i, N)
    {
        int a;
        cin >> a;
        second = second and a % 2 == 0;
    }

    std::cout << (second ? "second" : "first") << endl;
}

int main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(20);
    solve();
    return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<map>
#include<vector>
using namespace std;
int main(){
    int a,b,N=0,M=0,tmp=0;
    cin>>N>>M;
    int road[55]={};

    for(int i=0;i<M;i++){
        cin>>a>>b;
        road[a]++;
        road[b]++;
    }

    for(int i=1;i<=N;i++){ 
        cout<<road[i]<<endl;
    }
}

Measured memory_bytes: 256
#include <string>
#include <iostream>
using namespace std;
 
int main(){
    string str;
     
    while(true){
        int sum = 0;
        cin >> str;
        if(str=="0") break;
        for(int i = 0 ; i < str.size() ; i++){
            sum += str[i]-'0';
        }
        cout << sum << endl;
    }
     
    return 0;
}



Measured memory_bytes: 3232
#coding:utf-8

N = int(input())
buff = [y for x in range(N) for y in [input().split()]]
data = [(x[0], int(x[1])) for x in buff]
S = [x for x in data if x[0]=="S"]
H = [x for x in data if x[0]=="H"]
D = [x for x in data if x[0]=="D"]
C = [x for x in data if x[0]=="C"]

ansS = [("S", x) for x in range(1,14) if ("S", x) not in S]
ansH = [("H", x) for x in range(1,14) if ("H", x) not in H]
ansD = [("D", x) for x in range(1,14) if ("D", x) not in D]
ansC = [("C", x) for x in range(1,14) if ("C", x) not in C]

ans = ansS + ansH + ansC + ansD
[print(str(x[0]) + " " + str(x[1])) for x in ans]

Measured memory_bytes: 7728
N = int(input())
A = []
B = []
C = []
D = []
for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
for i in range(N):
    c, d = map(int, input().split())
    C.append(c)
    D.append(d)

G = [[] for i in range(2 * N + 10)]
for i in range(N):
    for j in range(N):
        if A[i] < C[j] and B[i] < D[j]:
            G[i].append(N + j)
            G[N + j].append(i)

used = [False for i in range(2 * N + 10)]
match = [-1 for i in range(2 * N + 10)]

def dfs(v):
    used[v] = True
    for i in range(len(G[v])):
        u = G[v][i]
        w = match[u]
        if w < 0 or not used[w] and dfs(w):
            match[v] = u
            match[u] = v
            return True
    return False

ans = 0
for v in range(N):
    if match[v] < 0:
        for i in range(2 * N + 10):
            used[i] = False
        if dfs(v):
            ans += 1
print(ans)


Measured memory_bytes: 3188
#include<stdio.h>
#define M 100000

int partition(int A[], int n, int p, int r){
  int x, i, j, k;
  x = A[r];
  i = p - 1;
  for ( j = p; j < r; j++ ){
    if ( A[j] <= x ){
      i++;
      k = A[i]; A[i] = A[j]; A[j] = k;
    }
  }
  k = A[i+1]; A[i+1] = A[r]; A[r] = k;
  return i+1;
}

main(){
  int A[M], n, i, q;
  scanf("%d", &n);
  for ( i = 0; i < n; i++ ) scanf("%d", &A[i]);
  q = partition(A, n, 0, n-1);

  for ( i = 0; i < n; i++ ) {
    if ( i ) printf(" ");
    if ( i == q ) printf("[");
    printf("%d", A[i]);
    if ( i == q ) printf("]");
  }
  printf("\n");

  return 0;
}



Measured memory_bytes: 2112
#include <bits/stdc++.h>
using namespace std;
int die[6];
int dice[6]={1,3,4,2,3,6};
void S(){
  int a[6];
  for(int i=0;i<6;i++) a[i]=die[i];
  die[0]=a[1];
  die[1]=a[5];
  die[5]=a[4];
  die[4]=a[0];
}

void W(){
int a[6];
 for(int i=0;i<6;i++) a[i]=die[i];
 die[0]=a[3];
 die[3]=a[5];
 die[5]=a[2];
 die[2]=a[0];
}

void N(){ S(),S(),S();}
void E(){W(),W(),W();}


int main(){



  while(1){
    int n;
    cin>>n;
    if(!n) break;
    for(int i=0;i<6;i++) die[i]=i+1;
      
    while(n--){
      string a;
      cin>> a;
      if(a=="north") N();
      if(a=="east") E();
      if(a=="south")S();
      if(a=="west")W();
    }
    cout << die[0]<<endl;
  }
  return 0;
}

Measured memory_bytes: 1212
#include <bits/stdc++.h>
    using namespace std;
    #define endl "\n"
    #define pb push_back
    typedef long long ll;
    queue<int>q;
    int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        string s;
        cin>>s;
        ll sum=0;
        for(int i=0;i<s.length();++i){
            sum=sum+(int)s[i]-48;
        }
        if(sum%9==0)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }

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

#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FORd(i, a, b) for (int i = (a) - 1; i >= (b); i--)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define present(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<ll> vi;
typedef vector<pi> vii;
const int MOD = (int) 1e9 + 7;
const int MOD2 = MOD + 2; //1007681537;
const int INF = (int) 1e9;
const ll LINF = (ll) 1e18;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;
inline ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
inline ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
inline ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
template<class T> inline int chkmin(T& a, const T& val) {return val < a ? a = val, 1 : 0;}
template<class T> inline int chkmax(T& a, const T& val) {return a < val ? a = val, 1 : 0;}
inline ll isqrt(ll k) {ll r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline void addmod(int& a, int val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
inline void submod(int& a, int val, int p = MOD) {if ((a = (a - val)) < 0) a += p;}
inline int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}
inline int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}
inline int sign(ld x) {return x < -EPS ? -1 : x > +EPS;}
inline int sign(ld x, ld y) {return sign(x - y);}
#define db(x) cerr << #x << " = " << (x) << " ";
#define endln cerr << "\n";


int main() 
{
  ll x,i=0;
  cin>>x;
  ll curamt=100;
  while(curamt<x)
  {
    curamt=curamt*(1.01);
    i++;
  }
  cout<<i<<endl;
  return 0;
}




























Measured memory_bytes: 3596
n,x,y=map(int,input().split())
ans=[0]*n
for i in range(1,n):
    for j in range(i+1,n+1):
        distance=min(j-i,abs(x-i)+1+abs(j-y))
        ans[distance]+=1
for i in range(1,n):
    print(ans[i])

Measured memory_bytes: 46300
#[allow(unused_imports)]
use std::cmp::{Ordering};

#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};

#[allow(unused_imports)]
use std::io::{stdin, stdout, BufWriter, Write};

#[allow(unused_imports)]
use std::iter::FromIterator;

#[allow(unused_macros)]
macro_rules! min {
    ($x: expr) => ($x);
    ($x: expr, $($z: expr),+) => {{
        std::cmp::min($x, min!($($z),*))
    }}
}

#[allow(unused_macros)]
macro_rules! max {
    ($x: expr) => ($x);
    ($x: expr, $($z: expr),+) => {{
        std::cmp::max($x, max!($($z),*))
    }}
}

#[allow(unused_macros)]
macro_rules! get { 
    ([$t: ty]) => { 
        { 
            let mut line = String::new(); 
            stdin().read_line(&mut line).unwrap(); 
            line.split_whitespace().map(|t|t.parse::<$t>().unwrap()).collect::<Vec<_>>()
        }
    };
    ([$t: ty];$n: expr) => {
        (0..$n).map(|_|get!([$t])).collect::<Vec<_>>()
    };
    ($t: ty) => {
        {
            let mut line = String::new();
            stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t: ty),*) => {
        { 
            let mut line = String::new();
            stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            ($(iter.next().unwrap().parse::<$t>().unwrap(),)*)
        }
    };
    ($t: ty; $n: expr) => {
        (0..$n).map(|_|get!($t)).collect::<Vec<_>>()
    };
    ($($t: ty),*; $n: expr) => {
        (0..$n).map(|_|get!($($t),*)).collect::<Vec<_>>()
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*).unwrap();
    }
}

const BIG_STACK_SIZE: bool = true;

#[allow(dead_code)]
fn main() {
    use std::thread;
    if BIG_STACK_SIZE {
        thread::Builder::new()
            .stack_size(32 * 1024 * 1024)
            .name("solve".into())
            .spawn(solve)
            .unwrap()
            .join()
            .unwrap();
    } else {
        solve();
    }
}

fn solve() {
    let (h,w,a,b) = get!(usize, usize, usize, usize);

    for i in 0..b {
        for j in 0..a {
            print!("0");
        }
        for j in a..w {
            print!("1");
        }
        println!("");
    }
    for i in b..h {
        for j in 0..a {
            print!("1");
        }
        for j in a..w {
            print!("0");
        }
        println!("");
    }
}


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

typedef long long ll;
typedef long double ld;
const ll M=1e9+7;
const ll MAXN=1e6+7;
const ld pi=acos(-1);

#define gi(n) ll n=read()
#define endl '\n'
#define rep(i,a,b) for(ll i=a; i<b; ++i)
#define per(i,a,b) for(ll i=b-1; i>=a; --i)

typedef vector<ll> V;
typedef vector<V> VV;
typedef set<ll> S;
typedef pair<ll,ll> pl;
typedef vector<pl> Vp;

#define all(v) v.begin(),v.end()
#define pb push_back
#define fs first
#define sc second

inline ll read(){
	ll x=0,ff=1;
	char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();}
	while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*ff;
}
ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
ll pow1(ll p,ll d, ll P){return d?(pow1(p*p%P,d>>1,P)*(d&1?p:1))%P:1;}

V prime;
bool is_composite[MAXN];
void sieve (ll n){
	std::fill (is_composite, is_composite + n, false);
	rep(i,2,n){
		if(!is_composite[i]) prime.pb(i);
		for(ll j = 0; j < prime.size() && i*prime[j] < n; ++j){
			is_composite[i*prime[j]] = true;
			if(i % prime[j] == 0) break;
		}
	}
}
ll modInverse(ll a, ll m){
	ll m0=m,y=0,x=1;
	if(m==1) return 0;
	while(a>1){
		ll q=a/m,t=m;
		m=a%m;
		a=t; 
		t=y;

		y = x-q*y; 
		x = t;
	}
	if(x<0) x += m0;
	return x; 
}

void doit(){
	gi(n); gi(k);
	ll a[n],s=0;
	rep(i,0,n) a[i]=read();
	sort(a,a+n);
	rep(i,0,k) s+=a[i];
	cout<<s;
}
int main(){
//	for(gi(t);t--;cout<<endl)
		doit();
	return 0;
}

Measured memory_bytes: 3648
unittest
{
	assert( [ "6 2" ].parse.expand.solve == 2 );
	assert( [ "14 3" ].parse.expand.solve == 2 );
	assert( [ "20 4" ].parse.expand.solve == 3 );
}



import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto nd = input.front.split.to!( long[] );
	return tuple( nd[ 0 ], nd[ 1 ] );
}

auto solve( long n, long d )
{
	return cast( long )( n / ( d * 2.0L + 1 ) ).ceil;
}


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

int main()
{
	string S;
	cin >> S;

	vector<int> L,R;
	for(int i=0;i<S.size();i++)
	{
		if(S[i]=='L')
			L.push_back(i);
		else
			R.push_back(i);
	}

	int ans[100010]={};
	for(int i=0;i<S.size();i++)
	{
		int pos;
		if(S[i]=='L')
		{
			auto itr=lower_bound(R.begin(),R.end(),i);
			--itr;
			pos=*itr+((i-*itr)%2);
		}
		else
		{
			auto itr=lower_bound(L.begin(),L.end(),i);
			pos=*itr-((*itr-i)%2);
		}
		ans[pos]++;
	}

	for(int i=0;i<S.size();i++)
	{
		cout << ans[i];
		if(i==S.size()-1)
			cout << endl;
		else
			cout << " ";
	}
	return 0;
}



Measured memory_bytes: 1532
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define per(i,a,b) for(int i=(b)-1;i>=a;i--)
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define de(x) cout << #x << "=" << x << endl
#define dd(x) cout << #x << "=" << x << " "
#define pw(x) (1ll<<(x))
#define pq priority_queue
#define endl "\n"
const ll maxn=1e5+100;
ll a[maxn],up[maxn],cnt[maxn];
int main()
{
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    for(int i=0;i<=n;i++)
    	cin >> a[i];
	ll now=0,flag=0;
	for(int i=n;i>=0;i--){
		now+=a[i];
		cnt[i]=now;
	}
	cnt[0]=1;
	ll ans=0;
	for(int i=1;i<=n;i++){
		if((cnt[i-1]-a[i-1])*2<cnt[i])
			cnt[i]=(cnt[i-1]-a[i-1])*2;
		if(cnt[i]<a[i]){
			cout<<"-1";
			return 0;
		} 
		ans+=cnt[i];
	}
	if(cnt[n]!=a[n]){
		cout <<"-1";
		return 0;
	}
	cout << ans+1 << endl;
    return 0;
}


Measured memory_bytes: 5216
#include <bits/stdc++.h>
using namespace std;
int N;
vector<vector <int> > p;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
bool isFind = false;
int safe(int i, int j) {
    return (0 <= i && i < 100000) && (0 <= j && j < 100000);
}
void f(int i, int j, int cnt, int index) {
    
    if (i < 0 || j < 0)
        return;
    if (cnt == p[index][0]) {
        if (i == p[index][1] && j == p[index][2])
            isFind = true;
        return;
    }

    f(i+1, j, cnt+1, index);
    f(i-1, j, cnt+1, index);
    f(i, j+1, cnt+1, index);
    f(i, j-1, cnt+1, index);

}

//x , y, time, postion
void g(int i, int j, int cnt, int index) {
    queue <vector<int> > q;
    int t, x, y;
    q.push({i, j, cnt});

    while (!q.empty()) {
        x = q.front()[0];
        y = q.front()[1];
        t = q.front()[2];
        q.pop();

        if (t == p[index][0]) {
            if (x == p[index][1] && y == p[index][2]) {
                isFind = true;
                break;
            }
        } else {

            q.push({x+1, y, t+1});
            q.push({x-1, y, t+1});
            q.push({x, y+1, t+1});
            q.push({x, y-1, t+1});
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin >> N;

    for (int i = 0; i < N; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        p.push_back({a,b,c});
    }

    int x, y, time;
    x = y = time = 0;
    for (int i = 0; i < p.size(); i++) {
        isFind = false;
        int dist = (abs(x-p[i][1]) + abs(y-p[i][2]));
        int t = p[i][0] - time;
        if (dist <= t) {
            if (dist % 2 == t % 2)
                continue;//f(x, y, time, i);
            else {
                cout << "No\n";
            return 0;
            }
                
            x = p[i][1];
            y = p[i][2];
            time = p[i][0];
        }
        else {
            cout << "No\n";
            return 0;
        }
        if (isFind == false) {
            cout << "No\n";
            return 0;
        }

    }
    cout <<"Yes\n";
    return 0;
}




Measured memory_bytes: 6068
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long lli;
typedef vector<lli> vll;

lli partition(vll& a,lli p,lli r){
	lli x = a[r];
	lli i = p-1;
	for(lli j = p;j < r;j++){
		if(a[j] <= x){
			i++;
			swap(a[j],a[i]);
		}
	}
	swap(a[i+1],a[r]);
	return i+1;
}

lli n;
vll a;

int main(){
	cin >> n;
	a = vll(n);
	for(lli i = 0;i < n;i++) cin >> a[i];
	lli p = partition(a,0,n-1);
	for(lli i = 0;i < n;){
		if(i == p) cout << "[";
		cout << a[i];
		if(i == p) cout << "]";
		if(++i < n) cout << " ";
		else cout << endl;
	}
	return 0;
}

Measured memory_bytes: 3536
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int main() {
    string s= "abcdefghijklmnopqrstuvwxyz";
    string a;
    long long n;
    cin >> n;
    while (n) {
        n--;
        a += s[n%26];
        n /= 26;
    }
    
    for (int i = a.size()-1; i >= 0; i--) cout << a[i];
    //system("pause");
}

Measured memory_bytes: 3100
import sys

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

""" Input
N, A, B = map(int, input().split())
A = list(map(int, input().split()))
A = np.array(input().split(), dtype=np.float64)
D = [int(input()) for _ in range(N)]
AB = [[int(x) for x in input().split()] for _ in range(N)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]
"""

K = int(input())
S = input().rstrip()

if len(S) <= K:
    print(S)
else:
    print(S[:K] + '...')

Measured memory_bytes: 9052
#include <stdio.h>
int main(){
    int n,i,num,max,min;
    long int sum;
    scanf("%d",&n);
    scanf("%d",&num);
    max = num;
    sum = num;
    min = num;
    for(i = 2;i<=n;i++){
        scanf("%d",&num);
        sum = sum + num;
        if(max<num){
            max = num;
        }
        if(num<min){
            min = num;
        }
    }
    printf("%d %d %ld\n",min,max,sum);
    return 0;
}


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

int main() {
  int a,b;
  cin>>a>>b;
  if(a%3==0||b%3==0||(a+b)%3==0) {
    cout<<"Possible"<<endl;
  }
  else {
    cout<<"Impossible"<<endl;
  }
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
	int h[10];
	int i, j;
	int M, idx;
	char buf[8];
	
	for(j = 0; j < 10; j++) {
		fgets(buf, 8, stdin);
		h[j] = strtol(buf, NULL, 10);
	}

	for(i = 0; i < 3; i++) {
		M = 0;
		for(j = 0; j < 10; j++) {
			if (h[j] > M) {
				M = h[j];
				idx = j;
			}
		}
		printf("%d\n", M);
		h[idx] = 0;
	}
	return 0;
}

Measured memory_bytes: 0
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,k=map(int,input().split())
    s=(n-1)*(n-2)//2-k
    if(s<0):
        print(-1)
        return
    print(s+n-1)
    from itertools import product
    E=[(u,v) for u,v in product(range(2,n+1),repeat=2) if u<v]
    for i in range(n-1):
        print(1,i+2) # 1-rooted
    for i in range(s):
        print(*E[i])
resolve()

Measured memory_bytes: 42864
n,m,c=map(int,input().split())
b=list(map(int,input().split()))
a=[list(map(int,input().split())) for _ in range(n)]

count,sum=0,c
for i in range(n):
  sum=c
  for j in range(m):
    sum+=a[i][j]*b[j]
  if sum>0:
    count+=1
    
print(count)

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

#define all(v) v.begin(), v.end()
#define V vector
#define P pair
typedef long long ll;
const int INT_INF = 1e9;
const ll INF = 1LL << 30;

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

    if(m.size() <= k){
        cout << 0 << endl;
        return 0;
    }

    V<P<int, int> > v;
    for(auto p : m){
        v.push_back(make_pair(p.second, p.first));
    }
    sort(all(v));

    int ans = 0;
    for(int i = 0; i < m.size() - k; i++){
        ans += v[i].first;
    }
    cout << ans << endl;

}



Measured memory_bytes: 11768
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <functional>
#include <math.h>
#include <stdlib.h>
#include <map>
#include <deque>
#include <sys/timeb.h>
#include <fstream>

using namespace std;

#define repr(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repr(i,0,n)
#define reprrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) reprrev(i,0,n)
#define repi(itr,ds) for(auto itr=ds.begin();itr!=ds.end();itr++)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define mp make_pair
#define mt make_tuple
#define INF 1050000000
#define INFL 1100000000000000000LL
#define EPS (1e-10)
#define MOD 1000000007
#define PI 3.1415926536
#define RMAX 4294967295

typedef long long ll;
typedef pair<int, int> Pi;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<Pi> vPi;
typedef vector<vector<int> > vvi;
typedef vector<vector<bool> > vvb;
typedef vector<vector<ll> > vvll;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<double> > vvd;
typedef vector<vector<Pi> > vvPi;
typedef priority_queue<int, vector<int>, greater<int> > pqli;
typedef priority_queue<ll, vector<ll>, greater<ll> > pqlll;
typedef priority_queue<Pi, vector<Pi>, greater<Pi> > pqlP;
struct Edge {
	int from, to, cost;
	bool operator<(Edge e) {
		return cost < e.cost;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
template <class T>
using vec = vector<T>;
template<class T>
using pql = priority_queue<T, vector<T>, greater<T>>;
string debug_show(Pi a) {
	return "(" + to_string(a.first) + "," + to_string(a.second) + ")";
}

template<class T>
struct augEdge {
	T from, to;
	int cost;
	bool operator<(augEdge e) { return cost < e.cost; }
	bool operator>(augEdge e) { return cost > e.cost; }
};
template<class T>
using augGraph = vector<augEdge<T>>;



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

	string s;
	cin >> s;
	string t[] = { "dream" , "dreamer" ,"erase" ,"eraser" };
	rep(i, 4) {
		reverse(t[i].begin(), t[i].end());
	}
	reverse(s.begin(), s.end());

	bool f = true;
	while (s.size() > 0) {
		string a = s.substr(0, 5);
		if (a == t[0] || a == t[2]) {
			s = s.substr(5, s.size() - 1);
		}
		else {
			a = s.substr(0, 6);
			if (a == t[3]) {
				s = s.substr(6, s.size() - 1);
			}
			else {
				a = s.substr(0, 7);
				if (a == t[1]) {
					s = s.substr(7, s.size() - 1);
				}
				else {
					cout << "NO" << endl;
					return 0;
				}
			}
		}

	}

	cout << "YES" << endl;

	return 0;
}


Measured memory_bytes: 620
import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as BS
import Data.List

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

main = do
    n <- getInt
    as <- getIntList
    let rs = scanr g 0 as
    let zs = zipWith f as (tail rs)
    let ans = foldl' g 0 zs
    print ans
 
f a b = (a * b) `mod` 1000000007
g a b = (a + b) `mod` 1000000007

Measured memory_bytes: 46560
#include <cstdio>
#include <vector>

typedef long long ll;

using namespace std;

int main() {
    ll n, c = 0;
    scanf("%lld", &n);
    vector<ll> a(n), b(n);
    for (int i = 0; i < n; ++i) scanf("%lld%lld", a.begin() + i, b.begin() + i);
    for (int i = n - 1; i >= 0; --i) if ((a.at(i) += c) % b.at(i)) c += b.at(i) - (a.at(i) % b.at(i));
    printf("%lld\n", c);
    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;
int n,q,a,b; 
ll x[222222];

struct node
{
	ll lazy;
	ll ans;
};

node st[2][800111];

void build(int ty, int id, int l, int r)
{
	st[ty][id].lazy=0;
	if(r-l<2)
	{
		st[ty][id].ans=ll(1e14);
		if(l==a)
		{
			st[ty][id].ans=abs(x[0] - b);
		}
		if(ty==0) st[ty][id].ans-=l;
		else st[ty][id].ans+=l;
		return ;
	}
	int mid=(l+r)>>1;
	build(ty,id*2,l,mid); build(ty,id*2+1,mid,r);
	st[ty][id].ans=min(st[ty][id*2].ans,st[ty][id*2+1].ans);
}

void push(int ty, int id, int l, int r)
{
	if(st[ty][id].lazy!=0)
	{
		st[ty][id].ans+=st[ty][id].lazy;
		if(r-l>=2)
		{
			st[ty][id*2].lazy+=st[ty][id].lazy;
			st[ty][id*2+1].lazy+=st[ty][id].lazy;
		}
		st[ty][id].lazy=0;
	}
}

void update(int ty, int id, int l, int r, int pos, ll v)
{
	push(ty,id,l,r);
	if(pos>=r||pos<l) return ;
	if(r-l<2)
	{
		st[ty][id].ans=min(v,st[ty][id].ans);
		return ;
	}
	int mid=(l+r)>>1;
	update(ty,id*2,l,mid,pos,v); update(ty,id*2+1,mid,r,pos,v);
	st[ty][id].ans=min(st[ty][id*2].ans,st[ty][id*2+1].ans);
}

void add(int ty, int id, int l, int r, int ql, int qr, ll v)
{
	push(ty,id,l,r);
	if(ql>=r||l>=qr) return ;
	if(ql<=l&&r<=qr)
	{
		st[ty][id].lazy+=v;
		push(ty,id,l,r);
		return ;
	}
	int mid=(l+r)>>1;
	add(ty,id*2,l,mid,ql,qr,v); add(ty,id*2+1,mid,r,ql,qr,v);
	st[ty][id].ans=min(st[ty][id*2].ans,st[ty][id*2+1].ans);
}

ll query(int ty, int id, int l, int r, int ql, int qr)
{
	push(ty,id,l,r);
	if(ql>=r||l>=qr) return ll(1e15);
	if(ql<=l&&r<=qr) return st[ty][id].ans;
	int mid=(l+r)>>1;
	return min(query(ty,id*2,l,mid,ql,qr), query(ty,id*2+1,mid,r,ql,qr));
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n>>q>>a>>b; a--; b--;
	for(int i=0;i<q;i++) {cin>>x[i]; x[i]--;}
	ll ans=ll(1e18);
	for(int z=0;z<2;z++)
	{
		for(int ty=0;ty<2;ty++) build(ty,1,0,n);
		for(int i=1;i<q;i++)
		{
			ll real = min(query(0,1,0,n,0,x[i]) + x[i], query(1,1,0,n,x[i],n) - x[i]);
			for(int j=0;j<2;j++) add(j,1,0,n,0,n,abs(x[i-1]-x[i]));
			update(0,1,0,n,x[i-1],real-x[i-1]);
			update(1,1,0,n,x[i-1],real+x[i-1]);
		}
		for(int i=0;i<n;i++)
		{
			ans=min(ans,query(0,1,0,n,i,i+1)+i);
		}
		swap(a,b);
	}
	cout<<ans<<'\n';
}


Measured memory_bytes: 22784
#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
#define F first
#define S second
const ll mod = 1e9 + 7;
const ll INF = 922337203685477;
#define pb push_back
#define deb(x) cout << '>' << #x << ':' << x << endl;
#define fastio ios_base::sync_with_stdio(false); cin.tie(0);
#define maxN 200007
using namespace std;
int main() {
  fastio;
  ll d = 0, t = 0, s = 0;
  cin >> d >> t >> s;
  if (t * s >= d)
    cout << "Yes";
  else
    cout << "No";
}

Measured memory_bytes: 3584
//https://atcoder.jp/contests/dp/tasks/dp_d

#include <bits/stdc++.h>
#include <limits.h>
#include <algorithm>  


#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;


using namespace std;

typedef long long int ll;

const int precision = 16;
const int modulo =  1000000007; // 10^9 + 7
using ll = long long;
const double EPS = 1e-9;


// ll recKS1(int ind, const vector<int> & w, const vector<int> & c, int W) 
// {
// 	if(ind >= (int)w.size()) return 0;
// 	if(W <= 0) return 0;

// 	if(w[ind] > W) {
// 		return recKS1(ind + 1, w, c, W);
// 	}

// 	auto r1 = c[ind] + recKS1(ind + 1, w, c, W - w[ind]);
// 	auto r2 = recKS1(ind + 1, w, c, W);
// 	return max(r1, r2);
// }

// auto h = std::hash<ll>();
// auto _hash = [&h](pair<int, int> p) ->ll {
// 	return h((ll)p.first | ((ll)p.second << 32));
// };



// ll recKS2(int ind, const vector<int> & w, const vector<int> & c, int W, gp_hash_table<pair<int, int>, ll,decltype(_hash)>  & memo) 
// {
// 	if(memo.find({ind, W}) != memo.end()) return memo[{ind, W}];
// 	if(ind >= (int)w.size()) return 0;
// 	if(W <= 0) return 0;
	
// 	if(w[ind] > W) {
// 		auto ret = recKS2(ind + 1, w, c, W, memo);
// 		memo[{ind, W}] = ret;
// 		return memo[{ind, W}];
// 	}

// 	auto r1 = c[ind] + recKS2(ind + 1, w, c, W - w[ind], memo);
// 	auto r2 = recKS2(ind + 1, w, c, W, memo);
// 	auto r = max(r1, r2);
// 	memo[{ind, W}]  = r;
// 	return r;
// }

// ll recKS3(int ind, const vector<int> & w, const vector<int> & c, int W, vector<vector<ll>> & memo) 
// {
// 	if(memo[ind][W] != -1) return memo[ind][W];
// 	if(ind >= (int)w.size()) return 0;
// 	if(W <= 0) return 0;
	
// 	if(w[ind] > W) {
// 		auto ret = recKS3(ind + 1, w, c, W, memo);
// 		memo[ind][W] = ret;
// 		return memo[ind][W];
// 	}

// 	auto r1 = c[ind] + recKS3(ind + 1, w, c, W - w[ind], memo);
// 	auto r2 = recKS3(ind + 1, w, c, W, memo);
// 	auto r = max(r1, r2);
// 	memo[ind][W]  = r;
// 	return r;
// }


ll itKS4(const vector<int> & wA, const vector<int> & c, int C) 
{
	int n = wA.size();

	vector<vector<ll>> dp(n + 1, vector<ll> (C + 1, 0));

	for(auto i = 1; i <= n; ++i) {
		for(auto w = 1; w <= C; ++w) {
			if(wA[i - 1]  <= w) {
				dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - wA[i - 1]] + c[i - 1]);
			} else {
				dp[i][w] = dp[i - 1][w];
			}
		}
	}

	// ll ret = 0;
	// for(auto it : dp[n]) {
	// 	ret = max(ret, it);
	// }

	return dp[n][C];
}

void solveKS1()
{
	int n, W; cin >> n >> W;
	vector<int> w(n), c(n);
	for(auto i = 0; i < n; ++i) {
		cin >> w[i] >> c[i];
	}

	//auto ret = recKS1(0, w, c, W);

	// gp_hash_table<pair<int, int>, ll, decltype(_hash)> memo(_hash);
	// auto ret = recKS2(0, w, c, W, memo);

	// vector<vector<ll>> memo(n + 1, vector<ll> (W + 1, -1));
	// auto ret = recKS3(0, w, c, W, memo);

	auto ret = itKS4(w, c, W);
	cout << ret <<endl;

}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cout.precision(precision);
	cout.setf(ios_base::fixed);

	solveKS1();
	return 0;
}



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

double kitai(double x){
  double sum = 0;
  for(int i = 1; i<x+1; i++){
  	sum += i * (1/x);
  }
  return sum;
}

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



Measured memory_bytes: 256
/*
ID: anonymo14
TASK: wormhole
LANG: C++                 
*/
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<pair<int,int>> vpii;

#define F first
#define S second
#define PU push
#define PUF push_front
#define PUB push_back
#define PO pop
#define POF pop_front
#define POB pop_back

#define REP(i,a,b) for(int i=a; i<=b; i++)

#define MOD 1000000007

void solve(int test_case) {
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	a = max(a,c);
	b=min(b,d);
	if(a<=b)cout<<b-a;
	else cout<<0;
			
}

int main() {
	
	////// FILE BASED IO////
	//freopen("wormhole.in", "r", stdin);
	//freopen("wormhole.out", "w", stdout);
	///////////////
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin>>t;
	REP(i,1,t) {
		solve(i);
	}
	return 0;
}	


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

int Baseball()
{
    const u_int num_of_event = 100;
    int num_of_runner = 0, num_of_out = 0, point = 0;
    std::string event;
    
    for(u_int i = 0; i < num_of_event; ++i){
        std::cin >> event;
        if(event == "HIT"){
            if(num_of_runner == 3)
                ++point;
            else
                ++num_of_runner;
        }
        else if(event == "HOMERUN"){
            point += 1 + num_of_runner;
            num_of_runner = 0;
        }
        else{
            ++num_of_out;
            if(num_of_out == 3)
                break;
        }
    }
    
    return point;
}

int main()
{
    u_int num_of_inning;
    std::cin >> num_of_inning;
    
    for(u_int i = 0; i < num_of_inning; ++i){
        std::cout << Baseball() << std::endl;
    }
    
    return 0;
}

Measured memory_bytes: 1208
#include <iostream>

using namespace std;

int main(void){
		string s;
	cin>>s;
	if(s[0] == 'a' || s[0]=='i' ||s[0]=='u' ||s[0]=='e' ||s[0]=='o' ){
		cout<<"vowel"<<endl;
	}else{
		cout<<"consonant"<<endl;
	}

	return 0;

}

Measured memory_bytes: 256
#include <bits/stdc++.h> //stdのインクルード
using namespace std; //std::を省略する
#define rep(i, n) for(int i = 0; i < n; ++i)
#include <vector>

const int INF = 1001001001;
vector<int> to[100005];

int main() {
  int N, M;
  cin >> N >> M;
  
  rep(i, M) {
    int a, b;
    cin >> a >> b;
    --a; --b;
    to[a].push_back(b);
    to[b].push_back(a);
  }
  
  queue<int> q;
  vector<int> dist(N, INF);
  vector<int> pre(N, -1);
  dist[0] = 0;
  q.push(0);
  
  while(!q.empty()) {
    int s = q.front(); q.pop();
    for(int t : to[s]) {
      if(dist[t] != INF) continue;
      dist[t] = dist[s] + 1;
      pre[t] = s;
      q.push(t);
    }
  }
  
  cout << "Yes" << endl;
  
  rep(i, N) {
    if(i == 0) continue;
    cout << pre[i] + 1 << endl;
  }
  return 0;
}

Measured memory_bytes: 10588
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_A main
#include "bits/stdc++.h" 
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LLONG_MAX/2)
const int MGN = 8;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using psi = pair<string, int>;
// functions

#endif


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

    string S; cin >> S;

    string ans = "No";
    
    sort(S.begin(), S.end());

    if (S[0] == S[1] && S[1] != S[2] && S[2] == S[3]) ans = "Yes";

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()
using ll = long long;
const ll mod = 1000000007;
const ll INF = 100000000000000000LL;
signed main(){
    int a,b;
    cin>>a>>b;
    cout<<(a-1)*(b-1)<<endl;
}

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

#define rep(i, n) for (int i = 0; i < (n); i++)
#define contains(v, t) (find(v.begin(), v.end(), t) != v.end())
#define MOD 1000000007
typedef long long ll;
typedef unsigned long long ull;

int main() {
  int d, n;
  cin >> d >> n;
  if (n == 100) n = 101;
  if (d == 0) {
    cout << n;
    return 0;
  }
  if (d == 1) {
    cout << n * 100;
    return 0;
  }
  if (d == 2) {
    cout << n * 10000;
    return 0;
  }
}


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

#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl

typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
const int inf = 1000000001;
const ll INF = 1e18 * 4;
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout<<setprecision(15)<<fixed<<p<<endl;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };

int main() {
	vl a(3);
	cin >> a[0] >> a[1] >> a[2];
	if (!(a[0] % 2) || !(a[1] % 2) || !(a[2] % 2)) {
		cout << 0 << endl;
	}
	else {
		sort(a.begin(), a.end());
		cout << a[0] * a[1] << endl;
	}
}

Measured memory_bytes: 256