akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define N 500000
#define INF 1000000000
typedef long long ll;
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) int(x.size())
#define IN(a) cin>>(a)
#define OUT(a) cout<<(a)<<endl
typedef pair<int,int> P;
const int MAX = 1000000;
const int MOD = 1000000007;
int main(){
	int n;
    IN(n);
    OUT(n*n*n);
	return 0;
}

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

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 1000000000000000000LL
#define MOD 1000000007
#define writeln(n) cout<<n<<endl
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
//vector<tuple<long long, long long, long long>>vec;

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

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

int dy[] = {0, 0, 1, -1, 0};
int dx[] = {1, -1, 0, 0, 0};


int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    llong x;
    cin>>x;
    llong cnt=x/11;
    llong y=x%11;
    llong ans=cnt*2;
    if(y==0) ans=ans;
    else if(y<7) ans+=1;
    else ans+=2;
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define il inline
#define RG register
#define ll long long
#define N (2000010)

using namespace std;

set<int> S;
set<int>::iterator it;
priority_queue<int> Q;

struct edge{ int nt,to; }g[N];

int head[N],p[N],q[N],d[N],k,n,num;

il int gi(){
  RG int x=0,q=1; RG char ch=getchar();
  while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
  if (ch=='-') q=-1,ch=getchar();
  while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
  return q*x;
}

il void insert(RG int from,RG int to){
  g[++num]=(edge){head[from],to},head[from]=num,++d[to]; return;
}

int main(){
  n=gi(),k=gi();
  for (RG int i=1;i<=n;++i) q[p[i]=gi()]=i;
  for (RG int i=1;i<=n;++i){
    if (i>k) S.erase(p[i-k]);
    it=S.insert(p[i]).first;
    if (++it!=S.end()) insert(i,q[*it]);
  }
  S.clear();
  for (RG int i=n;i;--i){
    if (i+k<=n) S.erase(p[i+k]);
    it=S.insert(p[i]).first;
    if (++it!=S.end()) insert(i,q[*it]);
  }
  for (RG int i=1;i<=n;++i) if (!d[i]) Q.push(-i);
  for (RG int id=1;id<=n;++id){
    RG int x=-Q.top(); Q.pop(); p[x]=id;
    for (RG int i=head[x];i;i=g[i].nt)
      if (!(--d[g[i].to])) Q.push(-g[i].to);
  }
  for (RG int i=1;i<=n;++i) printf("%d\n",p[i]); return 0;
}


Measured memory_bytes: 51456
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b)  for(int i=(a),i##formax=(b);i< i##formax;i++)
#define FORR(i,a,b) for(int i=(a),i##formin=(b);i>=i##formin;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define pcnt __builtin_popcount
#define sz(x) (int)(x).size()
#define maxs(x,y) x=max((x),(y))
#define mins(x,y) x=min((x),(y))
#define show(x) cout<<#x<<" = "<<(x)<<endl;
#define all(a) ((a).begin()),((a).end())
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define bit(n) (1LL<<(n))
typedef long long ll;
typedef __int128_t lll;
template<class T>using V=vector<T>;
template<class T>using VV=V<V<T>>;
template<class T,class Y>using P=pair<T,Y>;
template<class T,class Y>ostream& operator<<(ostream&o,P<T,Y>&p){return o<<"("<<p.fi<<","<<p.se<<")";}
template<class T>ostream& operator<<(ostream&o,V<T>&v){for(T&t:v)o<<t<<",";return o;}
template<class T>void uniq(V<T>&v){sort(all(v));v.erase(unique(all(v)), v.end());}
template<class A,size_t N,class T>void Fill(A(&a)[N],const T&v){fill((T*)a,(T*)(a+N),v);}

const int MOD = 1e9+7; //998244353;

lll gcd(lll a,lll b,lll&x,lll&y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll modInv(ll a,ll m=MOD){lll x,y;gcd(a,m,x,y);return(x%m+m)%m;}
ll modPow(lll a,lll n,ll m=MOD){lll p=1;for(;n;n>>=1,a=a*a%m)if(n&1)p=p*a%m;return p;}
//V<ll>Fac,Rac;void setF(int n,int m=MOD){Fac=Rac=V<ll>(++n);Fac[0]=1;FOR(i,1,n)Fac[i]=Fac[i-1]*i%m;Rac[n-1]=modInv(Fac[n-1],m);FORR(i,n-1,1)Rac[i-1]=Rac[i]*i%m;}
//ll comb(int a,int b,int m=MOD){return a<b||b<0?0:Fac[a]*Rac[b]%m*Rac[a-b]%m;}

const int IINF = 1e9+6;
const ll LINF = 1e18;
const int N = 1e5;
deque<char> q;
bool z;
int n;
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  {
    string s;
    cin >> s;
    for(char c:s) q.pb(c);
  }
  cin >> n;
  FOR(_, 0, n){
    int t;
    char c;
    cin >> t;
    if(t==1){
      z ^= true;
      continue;
    }
    cin >> t >> c;
    if(z^--t) q.pb(c);
    else q.push_front(c);
  }
  V<char> ans;
  while(!q.empty()){
    ans.pb(q.front());
    q.pop_front();
  }
  if(z) reverse(all(ans));
  for(char c:ans) cout << c;
  cout << endl;
}

Measured memory_bytes: 4156
<?php
fscanf(STDIN, "%d", $K);
fscanf(STDIN, "%d %d", $A, $B);
$bool = false;
for ($i = $A; $i <= $B; $i++) {
    if ($i % $K === 0) {
        $bool = true;
    }
}
echo $bool ? "OK" : "NG";


Measured memory_bytes: 16196
using System;
using System.Collections.Generic;
using System.Linq;

namespace ABC
{
    class Program
    {
        static void Main(string[] args)
        {
            ABC067_B();
        }

        static void ABC067_B()
        {
            var NK = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            var ln = Console.ReadLine().Split(' ').Select(int.Parse).OrderByDescending(x => x).ToArray();
            var sum = 0;

            for (var i = 0; i < NK[1]; i++)
                sum += ln[i];
            Console.WriteLine(sum);
        }
    }
}

Measured memory_bytes: 11348
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ

		Scanner scanner = new Scanner(System.in);
		String string = scanner.next();

		int num[] = new int[30];
		Arrays.fill(num, 0);
		for(int i = 0; i < string.length(); i++) {
			char c = string.charAt(i);
			num[c - 'a']++;
		}

		String res = "None";
		for(int i = 0; i < 26; i++) {
			if(num[i] == 0) {
				char c = (char)(i + 'a');
				res = String.valueOf(c);
				break;
			}
		}

		System.out.println(res);
	}

}

Measured memory_bytes: 26384
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;


public class Main {
    private static final PrintStream so = System.out;
    private static final Scanner     sc = new Scanner(System.in);
    private static List<Integer> list;
    private static Map<Integer, Integer> map;
    
    public static void main(String[] args) {
        make();
        
        int n = sc.nextInt();
        if (n == 1) {
            so.println("Yes");
            so.println("2");
            so.println("1 1");
            so.println("1 1");
            return;
        }
        if (!list.contains(n)) {
            so.println("No");
            return;
        }
        
        so.println("Yes");
        int w = map.get(n);
        int h = w + 1;
        int a = 1;
        int b = 1;
        int[][] lists = new int[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (i <= j) {
                    lists[i][j] = a++;
                }
            }
        }
        for (int j = 0; j < w; j++) {
            for (int i = 0; i < h; i++) {
                if (i > j) {
                    lists[i][j] = b++;
                }
            }
        }
        print(lists);
    }
    
    static void print(int[][] list) {
        so.println(list.length);
        for (int i = 0; i < list.length; i++) {
            so.print(list[i].length + " ");
            for (int j = 0; j < list[i].length; j++) {
                so.print(list[i][j]);
                if (j != list[i].length - 1) {
                    so.print(" ");
                }
            }
            so.println();
        }
        so.println();
    }

    static private void make() {
        list = new ArrayList<>();
        map = new HashMap<>();
        
        for (int i = 2; ; i++) {
            if (i * (i + 1) > 200000) {
                break;
            }
            list.add(i * (i+1) / 2);
            map.put(i * (i+1) / 2, i);
        }
    }
    
}


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

struct UnionFind{
    vector<int> par;
    UnionFind(int n) : par(n){
       REP(i, n) par[i] = -1;
    }
    int root(int x){
        if(par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    int size(int x){
        return (-par[root(x)]);
    }
    void unite(int x, int y){
        x = root(x);
        y = root(y);
        if(x == y) return;
        if(x > y) swap(x, y);
        if(size(x) < size(y)) swap(x, y);
        par[x] += par[y];
        par[y] = x;
    }
    bool same(int x, int y){
        return root(x) == root(y);
    }
};

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

    int n, m;
    cin >> n >> m;
    vector<int> A(m), B(m);
    REP(i, m){
        cin >> A[i] >> B[i];
        A[i]--; B[i]--;
    }

    int cnt = 0;
    REP(i, m){
        UnionFind UF(n);
        REP(j, m){
            if(i == j) continue;
            UF.unite(A[j], B[j]);
        }
        set<int> st;
        REP(j, n){
            st.insert(UF.root(j));
        }
        if(st.size() > 1) cnt++;
    }
    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pint;
const int dx[] = {-1, 0, 0, 1, -1, -1, 1, 1};
const int dy[] = {0, -1, 1, 0, -1, 1, -1, 1};
const ll waru = 1e9 + 7;

int main() {
  int n, a, b;
  cin>>n;
  if(n==1){
    cout << "Hello World" << endl;
  }else{
      cin>>a>>b;
      cout << a + b << endl;
  }
}


Measured memory_bytes: 256
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;

procedure Solve is
   K : Integer;
   A : Integer;
   B : Integer;
   flag : Integer;
begin
   Get (K);
   Get (A);
   Get (B);
   flag := 0;
   for I in A .. B loop
      if I/K*K = I then
         if flag = 0 then
            Put_Line ("OK");
         end if;
         flag := 1;
      end if;
   end loop;
   if flag = 0 then
      Put_Line ("NG");
   end if;
end Solve;

Measured memory_bytes: 3656
from queue import Queue
n, m = map(int, input().split())
adj = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)
def bfs():
    queue = Queue()
    queue.put(1)
    distance = [10**6]*(n+1)
    distance[1] = 0
    while not queue.empty():
        u = queue.get()
        if u == n and distance[u] == 2:
            print ("POSSIBLE")
            return
        for a in adj[u]:
            if distance[u] + 1 <= 2 and distance[a] > distance[u] + 1:
                distance[a] = distance[u] + 1
                queue.put(a)
    print ("IMPOSSIBLE")
    return
bfs()

Measured memory_bytes: 43676
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    Main m = new Main(sc);
    m.show(m.solve());
    // m.debug();
  }

  Scanner sc;
  boolean a;
  boolean b;

  // 標準入力用のコンストラクタ
  public Main(Scanner sc) {
    this.sc = sc;
    a = sc.next().equals("H");
    b = sc.next().equals("H");
  }

  // 判定処理
  boolean solve() {
    return a ^ b;
  }

  // 回答の表示
  void show(boolean ans) {
    System.out.println(ans ? "D" : "H");
  }
}


Measured memory_bytes: 35380
/*
 * a.cc: 
 */

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

using namespace std;

/* constant */

const int MAX_N = 100000;

/* typedef */

/* global variables */

int as[MAX_N];

/* subroutines */

/* main */

int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) (cin >> as[i]), as[i]--;

  int ans = max(as[0], n - 1 - as[m - 1]);

  for (int i = 0; i < m - 1; i++) {
    int c = (as[i + 1] - as[i]) / 2;
    if (ans < c) ans = c;
  }

  printf("%d\n", ans);
  return 0;
}

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

int main()
{
    int a[5];
    for(int& i : a) cin >> i;

    int k;
    cin >> k;

    for (int j = 4; j >= 1; --j) {
        for (int i = j; i >= 1; --i) {
            if(a[j] - a[i - 1] > k){
                cout << ":(";
                return 0;
            }
        }
    }
    cout << "Yay!";
    return 0;
}

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

me = []

count = 0

sw = False

for i in range(N):
    d1, d2 = map(int, input().split())

    if d1 == d2:
        count += 1
    else:
        count = 0

    if count >= 3:
        sw = True

if sw:
    print("Yes")
else:
    print("No")


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

int main() {
    using namespace std;
    string s, t;
    cin >> s >> t;
    unsigned long N = s.size(), M = t.size();
    {
        unsigned long n = (s.size() + t.size() - 1) / s.size();
        string sss(s.begin(), s.end());
        while(n){
            if(n & 1)s += sss;
            sss += sss;
            n >>= 1;
        }
    }

    vector<unsigned long> idx(N);
    {
        string Q = t + "_" + s;
        vector<unsigned long> KMP(Q.size() + 1);
        for(unsigned long i = 1, j = 0; i <= Q.size(); ++i){
            while(j > 0 && Q[i - 1] != Q[j - 1])j = KMP[j - 1];
            KMP[i] = ++j;
            if(KMP[i] > M && i >= KMP[i] + M && i < KMP[i] + N + M)idx[i - KMP[i] - M] = ~0UL;
        }
    }

    auto f = [rec = [&idx, &M, &N](auto f, unsigned long i, unsigned long t, unsigned long k) -> unsigned long{
        if(!idx[i])return 0;
        if(i == t && k)idx[i] = 2 * N;
        else if(!~idx[i])idx[i] = f(f, (i + M) % N, t, 1) + 1;
        return idx[i];
    }](unsigned long n){rec(rec, n, n, 0);};
    for(unsigned long i = 0; i < N; ++i)f(i);

    unsigned long ans = *max_element(idx.begin(), idx.end());
    if(ans > N)puts("-1");
    else cout << ans << endl;
    return 0;
}

Measured memory_bytes: 39852
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <climits>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <string>
#include <list>
#include <bitset>
#include <vector>
using namespace std;

#define I64d_OJ

//#ifdef I64d_OJ
//#define LL __int64
//#endif // I64d_OJ
#ifdef I64d_OJ
#define LL long long
#endif // I64d_OJ

typedef unsigned LL ULL;
typedef unsigned uint;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<LL,LL> pLL;
typedef vector<int> vi;

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-f; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}

#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define ls rt<<1
#define rs rt<<1|1
#define MID(a,b) (((LL)(a)+(LL)(b))>>1)
#define absx(a) ((a)<0?-(a):(a))
#define MK(a,b) make_pair(a,b)
#define PB(a) push_back(a)
#define lowbit(x) ((x)&-(x))

#define lc c[x][0]
#define rc c[x][1]

template< typename T >
inline void Max(T &a,T &b){if(a<b) a=b;}
template< typename T>
inline void Min(T &a,T &b){if(a>b) a=b;}

const double pi=(double)acos(-1.0);
const double eps=(double)1e-8;
const int INF = (int) 0x3f3f3f3f;
const int MOD = (int) 998244353;
const int MAXN =(int) 3e3+10;
const int MAXM = (int) 3e6+10;

///--------------------START-------------------------
int N,M;
int sum;

void work(){
    scanf("%d%d",&N,&M);
    sum=0;
    for(int i=1;i<=M;i++){
        int x; scanf("%d",&x);
        sum+=x;
    }
    if(sum>N){
        printf("-1\n");
    }
    else printf("%d\n",N-sum);
}

///--------------------END-------------------------
int main(){
#ifdef NNever
//freopen("data.in","r",stdin);
///freopen("out.txt","w",stdout);
#endif // NNever
    work();
    return 0;
}





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

int main(){
	int n, m;
	cin >> n >> m;
	int A[100][100], b[100], c[100];
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cin >> A[i][j];
		}
	}
	for(int j = 0; j < m; j++){
		cin  >> b[j];
	}
	for(int i = 0; i < n; i++){
		c[i] = 0;
		for(int j = 0; j < m; j++){
			c[i] += A[i][j] * b[j];
		}
		cout << c[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 1196
import java.util.*;

public class Main {

  public static void main(String[] args) {
    Main m = new Main();
    m.exec();
  }

  private void exec() {
    Scanner scan = new Scanner(System.in);
    String s = scan.next();
    String head = s.substring(0, 1);
    String tail = s.substring(s.length() - 1);
    System.out.println(head + String.valueOf(s.length() - 2) + tail);
  }
}

Measured memory_bytes: 20820
#include <iostream>

using namespace std;
#define ll long long

int main(){
    ll N, Y;
    cin >> N >> Y;
    for(int i = 0; i <= N; i++){
        for(int j = 0; j <= N; j++){
            if(i + j <= N && 10000 * i + 5000 * j <= Y){
                if((Y - 10000 * i - 5000 * j) % 1000 == 0){
                    if((Y - 10000 * i - 5000 * j)/1000 == N - i - j){
                        cout << i << " " << j << " " << N - i - j << endl;
                        return 0;
                    }
                }
            }
        }
    }
    cout << -1 << " " << -1 << " " << -1 << endl;
}

Measured memory_bytes: 256
// 2013/07/31 Tazoe

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;

struct dic{
	string ds;
	int di;
};

bool operator<(const dic& left, const dic& right)
{
	return left.di < right.di;
}

bool operator>(const dic& left, const dic& right)
{
	return left.di > right.di;
}

int main()
{
	while(true){
		string N;
		getline(cin, N);

		if(N=="0")
			break;

		istringstream isN(N);
		int n;
		isN >> n;

//		cout << n << endl;

		vector<string> w;

		for(int i=0; i<n; i++){
			string S;
			getline(cin, S);

			istringstream isS(S);
			while(!isS.eof()){
				string s;
				isS >> s;

//				cout << s << endl;

				w.push_back(s);
			}
		}

		sort(w.begin(), w.end());
/*
		for(int i=0; i<w.size(); i++){
			cout << w[i] << endl;
		}
*/
		string K;
		getline(cin, K);

		istringstream isK(K);
		char k;
		isK >> k;

//		cout << k << endl;

		vector<struct dic> D;

		for(int i=0; i<w.size(); i++){
			if(w[i][0]!=k)
				continue;

//			cout << w[i] << endl;

			bool flg = false;

			for(int j=0; j<D.size(); j++){
				if(D[j].ds==w[i]){
					D[j].di++;
					flg = true;
					break;
				}
			}

			if(!flg){
				struct dic tmp;
				tmp.ds = w[i];
				tmp.di = 1;
				D.push_back(tmp);
			}
		}

		stable_sort(D.begin(), D.end(), greater<dic>());
/*
		for(int i=0; i<D.size(); i++){
			cout << D[i].di << ' ' << D[i].ds << endl;
		}
*/
		if(D.size()==0){
			cout << "NA" << endl;
		}
		else{
			int m = D.size();
			if(m>5){
				m = 5;
			}

			for(int i=0; i<m; i++){
				cout << D[i].ds;

				if(i==m-1){
					cout << endl;
				}
				else{
					cout << ' ';
				}
			}
		}
	}

	return 0;
}

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

#define ll long long
#define vvi vector<vector<int>>
#define vec vector
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define uniqueV(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define rep(i, n) for (int (i) = (0); (i) < (n); ++(i))
#define repp(i, m, n) for (int (i) = (m); (i) < (n); ++(i))
#define dbg(x) cerr << #x << ": " << x << endl;
#define dbg2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;
#define dbg3(x, y, z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = "<<"("<<x<<", "<<y<<", "<<z<<")"<<endl;
#define dbgB(value, size) cerr<<#value<<": "<<bitset<size>(value) << endl;
#define line() cerr << "---------------" << endl;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const double PI = 3.14159265358979323846;

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; }

template<typename T>
void printA(vector<T> &printArray, char between = ' ') {
   int paSize = printArray.size();
   for (int i = 0; i < paSize; i++) { cerr << printArray[i] << between;}
   if (between != '\n') {cerr << endl;}
}

// ------------------------------------------------------------------------------------------

string S;
ll K;

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

   int cnt = 0;
   char next = '2';
   for (char c : S) {
      if (c != '1') {
         next = c;
         break;
      }
      cnt++;
   }

   if (S[0] == '1') {
      if (K <= S.size() && K <= cnt) {
         cout << 1 << endl;
      } else {
         cout << next << endl;
      }
   } else {
      cout << S[0] << endl;
   }

   return 0;
}

Measured memory_bytes: 256
def insertionSort(A, N):
    '''list of int, int(=len(A)) -> list of int
    return sorted list(insertion sort)
    '''
    l = N
    outA = A.copy()
    for i in range(l):
        val = outA[i]
        j = i - 1
        while j >= 0 and outA[j] > val:
            outA[j + 1] = outA[j]
            j -= 1
        outA[j + 1] = val
        printlist(outA)
    return outA
def printlist(L):
    '''
    print list with space
    '''
    for item in L[:-1]:
        print(item, end = ' ')
    print(L[-1])

n = int(input())
A = list(map(int,input().split()))
_ = insertionSort(A, n)



Measured memory_bytes: 5996
#include <bits/stdc++.h>
#define dbug(x) cout<<#x<<"="<<x<<endl
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while ('0'>ch||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do {(t*=10)+=ch-'0';ch=getchar();} while ('0'<=ch&&ch<='9'); t*=f;
}
typedef long long ll;
const int maxn=(1e5)+10;
int n,in[maxn],head[maxn],pos;
int tot,nxt[maxn*2],to[maxn*2];
ll a[maxn];
void add(int x,int y) {
	tot++; nxt[tot]=head[x];
	head[x]=tot; to[tot]=y;
}
ll f(ll x,ll y) {
	if (x%2==y%2) return x;
	return x-1;
}
ll dfs(int u,int p) {
	ll res=0,x=0,y=0,tmp,z; vector<int> d;
	for (int i=head[u],v;i;i=nxt[i]) {
		v=to[i]; if (v!=p) tmp=dfs(v,u),d.push_back(tmp),res+=tmp;
	}
	//printf("%d %lld\n",u,res);
	if (in[u]==1) return a[u];
	tmp=res-a[u];
	if (res<a[u]||a[u]<tmp) { printf("NO\n"); exit(0); }
	sort(d.begin(),d.end());
	for (int i=0;i<d.size();i++) {
		if (d[i]>x) z=f(x,y);
		else z=f(d[i],y);
		x+=d[i]; y=d[i]-z;
		//printf("%lld %lld %lld\n",x,y,z);
	}
	if ((res-y)/2<tmp) { printf("NO\n"); exit(0); }
	return a[u]-tmp;
}
int main() {
	//freopen("1.txt","r",stdin);
	read(n); int x,y;
	for (int i=1;i<=n;i++) read(a[i]);
	for (int i=1;i<n;i++) {
		read(x); read(y);
		in[x]++; in[y]++;
		add(x,y); add(y,x);
	}
	for (int i=1;i<=n;i++) if (in[i]!=1) pos=i;
	if (!pos) {
		if (a[1]==a[2]) printf("YES\n");
		else printf("NO\n"); return 0;
	}
	if (dfs(pos,0)==0) printf("YES\n");
	else printf("NO\n");
	return 0;
}

Measured memory_bytes: 13312
#include<bits/stdc++.h>
using namespace std;
#define ALL(obj) (obj).begin(),(obj).end()
#define RALL(obj) (obj).rbegin(),(obj).rend()
#define REP(i, n) for(int i=0;i<(n);++i)
#define RANGE(i, a, b) for(int i=(a);i<(b);++i)
#define RREP(i, n) for(int i=(n)-1;i>= 0;--i)

#define endl '\n'
#define pb push_back
#define eb emplace_back
#define pque priority_queue
#define umap unordered_map
#define uset unordered_set
#define BIG 2000000000
#define VERYBIG 1000000000000000ll
#define dcout cout<<fixed<<setprecision(20)
#define Accepted_MAGIC cin.tie(0);ios::sync_with_stdio(false)

// typedef long long ll;
using Real = long double;
#define int long long

const long long dx[]={1,0,-1,0,1,1,-1,-1}, dy[]={0,-1,0,1,1,-1,1,-1};
const long long MOD = 1e9+7;
constexpr Real eps = 1e-9, pi = acos(-1);

template<typename T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template<typename T> inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template<typename T> inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template<typename T> inline T nHr(T a,T b){return nCr(a+b-1,b);}
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}

typedef pair<int, int> INTP;
typedef vector<int> INTV;
struct edge2 {int to, cost;};
struct edge3 {int from, to, cost;};

signed main(void){
  Accepted_MAGIC;
  
  int N, A[200000]; cin >> N;
  map<int, int> mp;
  REP(i, N) {
    cin >> A[i];
    mp[A[i]]++;
  }
  map<int, int> big, small;
  int cnt = 0;
  for(auto ele : mp){
    int idx = ele.first;
    int num = ele.second;
    big[idx] = num * (num-1) / 2;
    small[idx] = (num-1)*(num-2) / 2;
    cnt += big[idx];
  }
  REP(i, N){
    cout << cnt - (big[A[i]] - small[A[i]]) << endl;    
  }
}

Measured memory_bytes: 28800
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <cmath>
#include <tuple>
#include <sstream>
#include <iomanip>
#include <map>
#include <unordered_map>

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())

using namespace std;
typedef long long ll;

int main(int argc, const char * argv[]) {
    //    ifstream in("input.txt");
    //    cin.rdbuf(in.rdbuf());
    
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int a, b;
    cin >> a >> b;
    
    cout << (a - 1) * (b - 1) << endl;
    
    return 0;
}

Measured memory_bytes: 888
#include<bits/stdc++.h>
using namespace std;
int N,C,i,j,s,t,c,cs[100001],sum,ans,len;
vector<pair<int,int>> vii[31],tmp;
int main(void){
  cin>>N>>C;
  for(i=0;i<N;i++){
    cin>>s>>t>>c;
    vii[c].push_back(make_pair(s,t));
  }
  for(i=1;i<=C;i++){
    sort(vii[i].begin(),vii[i].end());
    tmp.clear();
    len=vii[i].size();
    for(j=0;j<len;j++)
      if(tmp.empty()||tmp.back().second<vii[i][j].first)tmp.push_back(vii[i][j]);
      else tmp.back().second=vii[i][j].second;
    len=tmp.size();
    for(j=0;j<len;j++){
      cs[tmp[j].first]++;
      cs[tmp[j].second+1]--;
    }
  }
  for(i=0;i<100001;i++){
    sum+=cs[i];
    ans=max(ans,sum);
  }
  cout<<ans<<endl;
  return EXIT_SUCCESS;
}


Measured memory_bytes: 1920
#include<bits/stdc++.h>
typedef long long ll;
#define pair<int,int> P
#define sc(N) scanf("%lld",&N);
using namespace std;
int main()
{
    ll A,B,C;
    sc(A);
    sc(B);
    sc(C);
    cout<<max(C-A+B,0ll)<<'\n';
    return 0;
}


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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int a, b, k;
    cin >> a >> b >> k;

    for (int i = min(a, b); i >= 1; i--){
        if (a % i == 0 && b % i == 0)
            k -= 1;

        if (k == 0){
            cout << i << '\n';
            break;
        }
    }

    return 0;
}


Measured memory_bytes: 256
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


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


def main():
    x1, y1, x2, y2 = intin()

    xdiff = x2 - x1
    ydiff = y2 - y1

    x3 = x2 - ydiff
    y3 = y2 + xdiff
    x4 = x3 - xdiff
    y4 = y3 - ydiff

    print(x3, y3, x4, y4)

if __name__ == '__main__':
    main()


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

using namespace std;


int main()
{

        int n, input;
        vector<int> p;
        int high = 0;
        int am = 0;

        cin >> n;

        for (int i=0; i<n; i++) {
                cin >> input;

                if (input > high) {
                        p.push_back(high);
                        high = input;
                } else {
                        p.push_back(input);
                }
        }

        for (auto i : p) {
                am += i;
        }
        am += high / 2;

        cout << am << endl;


        return 0;
}



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

ll tree[1 << 20];
int treeh;
ll query(int u, int v, int root = 1, int s = 0, int e = (1 << treeh) - 1) {
  if (v < s || e < u) return 0;
  if (u <= s && e <= v) return tree[root];
  int mid = (s + e)/2;
  return max(query(u, v, 2*root, s, mid), query(u, v, 2*root + 1, mid + 1, e));
}
void update(int p, ll x) {
  p += (1 << treeh);
  tree[p] = x;
  p /= 2;
  while (p > 0) {
    tree[p] = max(tree[2*p], tree[2*p + 1]);
    p /= 2;
  }
}

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

  int n;
  cin >> n;
  treeh = 0;
  while ((1 << treeh) < n) treeh++;
  memset(tree, 0, sizeof(tree));

  ll dp[200005];
  ll ans = 0;
  int h[200005], a[200005];
  for (int i = 0; i < n; i++) {
    cin >> h[i];
    h[i]--;
  }
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < n; i++) {
    dp[i] = a[i] + query(0, h[i] - 1);
    update(h[i], dp[i]);
    ans = max(ans, dp[i]);
  }
  cout << ans << '\n';

  return 0;
}

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

int main()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int w, a, b;
  cin >> w >> a >> b;
  
  if( (b >= a and b <= a+w) or (b+w >= a and b+w <= a+w))
  {
    cout << 0 << endl;
    return 0;
  }
  
  int mn = min(abs(b+w-a), abs(a+w-b));
  
  cout << mn << endl;
  
  return 0;
}

Measured memory_bytes: 256
n, m = gets.chomp.split.map(&:to_i)
arr1 = []
arr2 = []
n.times{arr1 << gets.chomp.split.map(&:to_i)}
m.times{arr2 << gets.chomp.split.map(&:to_i)}

n.times{|i|
    arr3 = []
    m.times{|j| arr3 << (arr1[i][0] - arr2[j][0]).abs + (arr1[i][1] - arr2[j][1]).abs}
    puts (arr3.index(arr3.min)) + 1
}

Measured memory_bytes: 1916
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<pair<ll, ll> > vp;
typedef vector<string> vs;
typedef vector<char> vc;
typedef list<ll> lst;
typedef pair<ll, ll> P;
const long long INF = numeric_limits<ll>::max();
const long long MOD = 1000000007;
const long double PI = 3.1415926;
template <class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <class T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
ll n, m, k, ans = 0, sum = 0, cnt = 0;
string s;
//char c;
 
#define Endl endl
 
/*--------------------template--------------------*/
 
int main() {
    int A, B, C;
    int K;
    cin >> A >> B >> C;
    cin >> K;
    K = pow(2, K);
    if (A > B) {
        if (A > C) {
            cout << K * A + B + C << endl; 
        } else {
            cout << K * C + A + B << endl;
        }
    } else if (B > C) {
        cout << K * B + A + C << endl; 
    } else {
        cout << K * C + A + B << endl;
    }
    return 0;
}

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

int main()
{
	long long N;
	cin >> N;
	for (long i = sqrt(N); i > 0 ; i--) {
		if (N % i == 0) { cout << (N / i) + i - 2 << endl; 
		goto end;
		}
	}
end:
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>
#include <random>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
//#define int long long

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;
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; }

void solve() {
    int d;
    cin >> d;
    VI c(26);
    VVI s(d,VI(26));
    REP(i,0,26) {
        cin >> c[i];
    }
    REP(i,0,d) REP(j,0,26) cin >> s[i][j];
    int t;
    VI lasts(26, -1);
    int score = 0;
    REP(i,0,d) {
        cin >> t;
        --t;
        score += s[i][t];
        lasts[t] = i;
        REP(j,0,26) score -= c[j] * (i - lasts[j]);
        cout << score << endl;
    }

}

signed main() {
    solve();
    
    return 0;
}

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

int main() {
  int S;
  cin >> S;
  int f, s;
  f = S / 100;
  s = S - f * 100;
  //month test
  string flag;
  if (f == 0 && s == 0) {
    flag = "NA";
  } else if (f > 12 && s > 12) {
    flag = "NA";
  } else if (f > 12 && s == 0) {
    flag = "NA";
  } else if (f == 0 && s > 12) {
    flag = "NA";
  } else if (f > 12 || f == 0) {
    flag = "YYMM";
  } else if (s > 12 || s == 0) {
    flag = "MMYY";
  } else {
    flag = "AMBIGUOUS";
  }
  cout << flag << endl;
}

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

#define rep(i,n) for(ll i=0;i<(n);++i)
using ll = long long;
using pll = pair<ll,ll>;
constexpr ll INF = (1LL<<60);
constexpr ll MOD = (1e9+7);
//constexpr ll MOD = (998244353);
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(a>b){a=b;return 1;}return 0;}
#if loc||debg||local||debug
void dump(){cerr<<endl;}
template<class T,class... Ts> void dump(T&& h, Ts&&... t){cerr<<h<<", ";dump(forward<Ts>(t)...);}
#else
template<class T,class... Ts> void dump(T&& h, Ts&&... t){}
#endif
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<class T> ostream &operator<<(ostream& os,vector<T>const& v){for(auto const& vi:v)os<<vi<<" ";return os;}
template<class T>vector<T> vec(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto vec(size_t a, Ts... ts){return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...));}
template<class T>vector<T> _vec(size_t a,T v){return vector<T>(a,v);}
template<class T, class... Ts>auto _vec(size_t a, Ts... ts){return vector<decltype(_vec<T>(ts...))>(a, _vec<T>(ts...));}

int main(){

  long double a,b,c;
  cin>>a>>b>>c;
  long double d = a+2*sqrt(a)*sqrt(b)+b;
  if(d<c){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

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

  int n;
  cin >> n;
  vector<int> a(n), b(n), c(n);
  rep(i, 0, n) cin >> a[i];
  rep(i, 0, n) cin >> b[i];
  rep(i, 0, n) cin >> c[i];
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  sort(c.begin(), c.end());

  vector<ll> one(n), two(n);
  rep(i, 0, n) {
    auto x = upper_bound(b.begin(), b.end(), a[i]);
    int idx_b = x - b.begin();
    one[i] = n - idx_b;
  }
  rep(i, 0, n) {
    auto y = upper_bound(c.begin(), c.end(), b[i]);
    int idx_c = y - c.begin();
    two[i] = n - idx_c;
  }

  // 逆からの累積に変換
  repr(i, 0, n - 1) two[i] += two[i + 1];

  ll ans = 0;
  rep(i, 0, n) ans += two[n - one[i]];
  cout << ans << endl;
}


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

#define int             long long int
#define ld              long double
#define ff              first
#define ss              second
#define mp              make_pair
#define pb              push_back
#define si              set <int>
#define vi              vector <int>
#define pii             pair <int, int>
#define vpii            vector <pii>
#define vpp             vector <pair<int, pii>>
#define mii             map <int, int>
#define mpi             map <pii, int>
#define msi             map < string, int >
#define loop(i,s,e)     for(int i=s;i<e;i++)
#define rloop(i,e,s)    for(int i=e;i>=s;i--)
#define mset(a,f)       memset(a,f,sizeof(a))
#define spi             set <pii>
#define endl            "\n"
#define sz(x)           ((int) x.size())
#define all(p)          p.begin(), p.end()
#define que_max         priority_queue <int>
#define que_min         priority_queue <int, vi, greater<int>>
#define bug(...)        __f (#__VA_ARGS__, __VA_ARGS__)
#define print(a)        for (auto x : a) cout << x << " "; cout << endl
#define Print(a,x,y)    for (int i=x; i<y; i++) cout<< a[i]<< " "; cout << endl

inline int power(int a, int b)
{
	int x = 1;
	while (b)
	{
		if (b & 1) x *= a;
		a *= a;
		b >>= 1;
	}
	return x;
}

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
	const char* comma = strchr (names + 1, ',');
	cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

const int N = 2000005;
int v[N], w[N], n, maxwt;
int dp[105][100005];

int help(int i, int wt)
{
	if (i >= n) return 0;
	if (dp[i][wt] != -1) return dp[i][wt];
	int op1 = -1, op2 = -1;
	if (w[i] <= wt)
		op1 = v[i] + help(i + 1, wt - w[i]);
	op2 = help(i + 1, wt);
	return dp[i][wt] = max(op1, op2);
}

void solve()
{
	cin >> n >> maxwt;
	loop(i, 0, n)
	cin >> w[i] >> v[i];
	mset(dp, -1);
	cout << help(0, maxwt);

	return;

}

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


	int t = 1;
	//cin >> t;
	while (t--)
	{
		solve();
	}
	
	return 0;
}


Measured memory_bytes: 86272
n,gw=map(int,input().split())

V=[]
W=[]

for i in range(n):
	v,w=map(int,input().split())
	V.append(v)
	W.append(w)

DP=[[0]*(gw+1) for i in range(n+1)]

for i in range(n):
	for j in range(gw+1):
		if j-W[i]<0:
			DP[i+1][j]=DP[i][j]
		else:
			DP[i+1][j]=max(DP[i][j],DP[i+1][j-W[i]]+V[i])

print(DP[n][gw])


Measured memory_bytes: 15688
#include<bits/stdc++.h>
using namespace std;
#define ll long long
 
int main(){
 
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    ll n;
    cin >> n;
 
    ll ans = 0;
    for(ll i=1;i<=n;++i){
    	if(!((i%3 == 0) || (i%5 == 0))){
    		ans+=i;
    	}
    }
    cout << ans << "\n";
 
	return 0;
}

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

typedef long long ll;
#define vec vector<int>
#define vecll vector<ll>
#define vpair vector<pair<int, int>>
#define vpairll vector<pair<ll, ll>>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rep(i,n)   for(int i=(int)0; i<(int)n; i++)
#define llrep(i,n)   for(ll i=(ll)0; i<(ll)n; i++)
#define REP(i,m,n) for(int i=(int)m; i<(int)n; i++)
#define all(var)     (var).begin(), (var).end()
#define prt(var)     cout << var << endl
#define prt_dbl(i,var) cout<<fixed<<setprecision(i)<<var<<endl;
template <typename Val,typename Number>
//use ll or int for gcd
Val gcd(Val a, Val b) {
    if (b==0) return a;
    else return gcd(b, a%b);
}
//count vector and return pair (count,vector item)
template <typename Val,typename Number>
void count_vector(vector<Val>* A,vector<pair<Number,Val>>*R){
  sort(A->begin(),A->end());
  int count = 1;
  rep(i,A->size()){
    if(i<A->size()-1){
      if(A->at(i)==A->at(i+1))count++;
      else{
        R->push_back(make_pair(count,A->at(i)));
        count = 1;
      }
    }else{
      R->push_back(make_pair(count,A->at(i)));
      count = 1;
    }
  }
}

//---------------------------------------------------------------

int main(){
  int N;
  cin>>N;
  vector<ll> X(N);
  vector<ll> T;
  rep(i,N){
    cin>>X.at(i);
  }
  T=X;
  sort(X.begin(),X.end());
  int Med1 = X.at(N/2-1);
  int Med2 = X.at(N/2);
  rep(i,N){
  if(T.at(i)<=Med1){
    cout<<Med2<<endl;
  }else{
    cout<<Med1<<endl;
  }
  }


}


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

ll a[300000];
int main() {
	ll n; scanf("%lld", &n);
	rep(i, n) {
		scanf("%lld", &a[i + 1]);
		a[i + 1 + n] = a[i + 1];
	}
	for (ll i = 1; i <= 2 * n; i++)
		a[i] += a[i - 1];
	ll s = 0, g = 1000000000 * n;
	while (s != g) {
		ll t = (s + g) / 2;
		if (g - s == 1)t = g;
		bool flag = false;
		rep(i, n) {
			ll j = lower_bound(a + i, a + i + n + 1, a[i] + t) - a;
			if (j == n + i + 1)continue;
			ll k = lower_bound(a + j, a + i + n + 1, a[j] + t) - a;
			if (a[j] - a[i] >= t&&a[k] - a[j] >= t&&a[i + n] - a[k] >= t) {
				flag = true;
				break;
			}
		}
		if (flag)s = t;
		else g = t - 1;
	}
	printf("%lld\n", s);
}

Measured memory_bytes: 4780
function main(input) {
    var foods = input.split(/\n/).map(s => ~~s);
    var lastServeIndex = 0;
    foods.reduce((minSurplus, curTime, index) => {
        const curSurplus = curTime % 10;
        if (curSurplus !== 0 && minSurplus > curSurplus) {
            lastServeIndex = index;
            return curSurplus;
        } else {
            return minSurplus;
        }
    }, 10);

    const res = foods.reduce((pre, cur, index) => {
        if (index === lastServeIndex) {
            return pre + cur;
        } else {
            return pre + Math.ceil(cur / 10) * 10;
        }
    }, 0)

    console.log(res);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 7372
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    a,b = LI()
    g = fractions.gcd(a,b)

    return a*b//g


print(main())





Measured memory_bytes: 5464
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
int main(){
    int n,cnt,m;
    cnt=0;
    m=0;
    cin >>n;
    vector<int> h(n);
    rep(i,n) cin >>h[i];
    rep(i,n-1){
        if (h[i]>=h[i+1]) {
        cnt++;
        }else{
        m=max(m,cnt);
        cnt=0;
        }
        m=max(m,cnt);
    }
    cout << m << endl;
}

Measured memory_bytes: 640
import java.io.*;
import java.lang.*;
import java.util.*;
import java.math.*;

class Solver extends Main{
	Solver(){
		
	}
}//Solver_end

@SuppressWarnings("unchecked")
class Main{
	static int imax=Integer.MAX_VALUE;
	static long lmax=Long.MAX_VALUE;
	
	public static void main(String[] args) throws FileNotFoundException{
		
		
		Scanner sc=new Scanner(System.in);
		//Scanner sc=new Scanner(fp);
		
		int[] data=readlnI(sc," ");
		int n=data[0];
		int m=data[1];
		int[] path=new int[200000];
		
		for(int i=0;i<m; i++){
			int[] line=readlnI(sc," ");
			if(line[0]==1){
				path[line[1]-1]+=1;
			}else if(line[1]==n){
				path[line[0]-1]+=1;
			}
		}
		
		boolean fnd=false;
		
		for(int x:path){
			if(x==2)fnd=true;
		}
		
		puts(fnd==true ? "POSSIBLE" : "IMPOSSIBLE");
		
	}//main_end
	
//---------------------------------------------------------------------------
	static int readI(Scanner sc){
		return Integer.parseInt(sc.nextLine().trim());
	}
	static long readL(Scanner sc){
		return Long.parseLong(sc.nextLine().trim());
	}
	static String readS(Scanner sc){
		return sc.nextLine().trim();
	}
	static int[] readlnI(Scanner sc, String dl){
		return Arrays.stream(sc.nextLine().trim().split(dl)).mapToInt(Integer::parseInt).toArray();
	}
	static long[] readlnL(Scanner sc, String dl){
		return Arrays.stream(sc.nextLine().trim().split(dl)).mapToLong(Long::parseLong).toArray();
	}
	static String[] readlnS(Scanner sc, String dl){
		return sc.nextLine().trim().split(dl);
	}
	@SuppressWarnings("unchecked")
	static <T> void puts(T... args){
		for(int i=0; i<args.length-1; i++){
			System.out.printf("%s ",args[i]);
		}
		System.out.println(args[args.length-1]);
	}
	static void puts(int[] ary){
		for(int i=0; i<ary.length-1; i++){
			System.out.printf("%d ",ary[i]);
		}
		System.out.println(ary[ary.length-1]);
	}
	static void puts(long[] ary){
		for(int i=0; i<ary.length-1; i++){
			System.out.printf("%d ",ary[i]);
		}
		System.out.println(ary[ary.length-1]);
	}
	static void bs(){
		System.out.println("");
	}
	static int sum(int[] ary){
		int sum=0;
		for(int i=0; i<ary.length; i++) sum+=ary[i];
		return sum;
	}
	static long sum(long[] ary){
		long sum=0;
		for(int i=0; i<ary.length; i++) sum+=ary[i];
		return sum;
	}
	static void tblSort(int[][] tbl){
		Arrays.sort(tbl, new Comparator<int[]>(){
			@Override
			public int compare(int[] a, int[] b){
				if(a[0]==b[0]){
					return b[1]-a[1];
				}else{
					return b[0]-a[0];
				}
			}
		});
	}
}


Measured memory_bytes: 180204