akhauriyash/Code-Regression huggingface dataset:
////////////////いろいろあるよ//////////////////////////////////
//include,namespace
 #include<bits/stdc++.h>
 #include<iostream>
 #include<bitset>
 using namespace std;
//REPmacro
 #define all(x) (x).begin(),(x).end()             //ソート
 #define FOR(i,x,n)for(int i=(x);i<(n);i++)
 #define FOR_R(i,x,n) for(int i=(n-1);i>=(x);i--)
 #define REP(i, n) FOR(i, 0, n)
 #define REP_R(i, n) FOR_R(i, 0, n)
//long long(define)
 using ll = long long;
 typedef long long ll;
 typedef long long int64;
 typedef long long lint;
 typedef long long lli;
 
//bit
 /*
 const unsigned int BIT_FLAG_0 = (1 << 0); // 0000 0000 0000 0001
 const unsigned int BIT_FLAG_1 = (1 << 1); // 0000 0000 0000 0010
 const unsigned int BIT_FLAG_2 = (1 << 2); // 0000 0000 0000 0100
 const unsigned int BIT_FLAG_3 = (1 << 3); // 0000 0000 0000 1000
 const unsigned int BIT_FLAG_4 = (1 << 4); // 0000 0000 0001 0000
 const unsigned int BIT_FLAG_5 = (1 << 5); // 0000 0000 0010 0000
 const unsigned int BIT_FLAG_6 = (1 << 6); // 0000 0000 0100 0000
 const unsigned int BIT_FLAG_7 = (1 << 7); // 0000 0000 1000 0000 
 */
 
//variable
 //const int INF = 1000000;
 //int dp[INF][INF];
 //int ans=0;
 
 //int dx[4]={1,0,-1,0};
 //int dy[4]={0,1,0,-1};
 
int N=0;
int M=0;
////////////////いろいろあるよ//////////////////////////////////
 
int main(){
 	int a,b,c;
  cin >> a >> b >> c;
  int maxn=0;
  maxn = max(a,b);
  if(c%maxn == 0)cout << c/maxn << endl;
  else cout << (c/maxn)+1 << endl;
 
 	return 0;
}

Measured memory_bytes: 256
/* ex 9_1
   yumizmiz */

#include <stdio.h>
#include <stdlib.h>
//スタックに格納するデータの最大数
#define SIZE 1000

//スタックの定義
typedef struct stack{
    int size;
    int count;
    char data[SIZE];
    char *top;
} stack;

//スタックの初期化
void initialize_stack(stack *stk){
    stk->count = 0;
    stk->size = SIZE;
    stk->top = &(stk->data[SIZE]);
}

//データの追加
void push(stack *stk, char elem){
    if(stk->count >= stk->size){
        fprintf(stderr, "Error: stack overflow. (x=%c)\n", elem);
        exit(1);
    }
    else{
        stk->top--;
        *(stk->top) = elem;
        stk->count++;
    }
}

//データの取り出し
char pop(stack *stk){
    char latest;
    
    if(stk->count <= 0){
        fprintf(stdout, "Error: stack underflow.\n");
        exit(1);
    }
    else{
        latest = *(stk->top);
        stk->top++;
        stk->count--;
        return latest;
    }
}

int main(void){
    //スタック
    stack stk;
    initialize_stack(&stk);

    //入力文字列の配列（最大文字数10）
    char input[11], *ptr1;
    //出力文字列の配列（最大文字数10）
    char output[11], *ptr2;
    scanf("%s", input);

    ptr1 = input;
    while(*ptr1){
        //'B'だったらその前の文字を消す（取り出す）．消せる文字がなければ消さない
        if(*ptr1 == 'B'){
            if(stk.count>0)
                pop(&stk);
        }else{
            push(&stk, *ptr1);
        }
        ++ptr1;
    }
    //スタックを逆順に取り出す
    //文字数はstk.count
    ptr2 = &output[stk.count];
    //ヌル文字を入れて
    *ptr2 = '\0';
    //後ろから文字を入れていく
    while(stk.count>0){
        --ptr2;
        *ptr2 = pop(&stk);
    }
    printf("%s", output);
    return 0;
}

Measured memory_bytes: 1708
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
#define  rep(i,n) for(ll i = 0; i < (n); ++i)
#define  red(i,n) for(ll i = (n)-1; i >= 0; --i)
#define  all(a)   begin(a),end(a)
#define  pb(a)    push_back(a)
#define  yn(a)    cout << ( (a)?"Yes\n":"No\n" )
inline ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; }
ll INF = 1e9+9, LINF = 1e18;

int main() 
{
    ll a,b,c;
    cin>>a>>b>>c;
    cout<<c<<" "<<a<<" "<<b<<endl;
}


Measured memory_bytes: 256
N = int(input())
A = [list(map(int, input().split())) for _ in range(2)]

U = [0] * N
D = [0] * N
U[0] = A[0][0]
D[0] = A[1][0]

for i in range(1, N):
  U[i] = U[i - 1] + A[0][i]
  D[i] = D[i - 1] + A[1][i]

ans = U[0] + D[N - 1]
for i in range(1, N):
  ans = max(ans, U[i] + D[N - 1] - D[i - 1])

print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <iostream>
 using namespace std;
 int main()
 {
     int N,X;
     cin>>N>>X;
     int i=0,b,bounce=0,count=1;
     while(i<N)
     {
         b=0;
         cin>>b;
         bounce+=b;
         if(bounce<=X)
            count++;

         i++;
     }
     cout<<count;
     return 0;
 }


Measured memory_bytes: 256
import itertools
import math

d, g = map(int, input().split())
ls = [[100 * (i + 1)] + list(map(int, input().split())) for i in range(d)]
s0 = [a * p for a, p, _ in ls]
s1 = [a * p + c for a, p, c in ls]

res = float('inf')
for indices in itertools.permutations(range(d)):
    count = 0
    s = 0
    for i in indices:
        if s + s0[i] >= g:
            count += math.ceil((g - s) / (100 * (i + 1)))
            break
        else:
            count += ls[i][1]
            if count >= res:
                break
            s += s1[i]
            if s >= g:
                break
    res = min(res, count)
print(res)

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

using namespace std;

int main(void) {
    int n;
    cin >> n;
    vector<int> odd(200000), even(200000);
    for(int i=0; i<n; i++) {
        int v;
        cin >> v;
        if(i%2) {
            odd[v]++;
        } else {
            even[v]++;
        }
    }

    auto m = max_element(odd.begin(), odd.end());
    int odd_max_pos = distance(odd.begin(), m);
    int odd_max_val = *m;
    *m = 0;
    m = max_element(odd.begin(), odd.end());
    int odd_sec_pos = distance(odd.begin(), m);
    int odd_sec_val = *m;

    m = max_element(even.begin(), even.end());
    int even_max_pos = distance(even.begin(), m);
    int even_max_val = *m;
    *m = 0;
    m = max_element(even.begin(), even.end());
    int even_sec_pos = distance(even.begin(), m);
    int even_sec_val = *m;

    if(odd_max_pos == even_max_pos) {
        cout << n - max(odd_max_val + even_sec_val, odd_sec_val + even_max_val) << endl;
    } else {
        cout << n - odd_max_val - even_max_val << endl;
    }
    return 0;
}


Measured memory_bytes: 1792
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::HashMap;
#[allow(unused_imports)]
use std::collections::VecDeque;
#[allow(unused_imports)]
use std::io::*;
#[allow(unused_imports)]
use std::mem::*;
#[allow(unused_imports)]
use std::str::*;
#[allow(unused_imports)]
use std::usize;

#[allow(unused_macros)]
macro_rules! read_cols {
    ($($t:ty),+) => {{
        let mut line = String::new();
        stdin().read_line(&mut line).unwrap();

        let mut it = line.trim()
            .split_whitespace();

        ($(
            it.next().unwrap().parse::<$t>().ok().unwrap()
        ),+)
    }}
}

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let mut line = String::new();
    stdin().read_line(&mut line).unwrap();
    line.trim().to_string().parse().ok().unwrap()
}

#[allow(dead_code)]
fn read_vec<T: FromStr>() -> Vec<T> {
    let mut line = String::new();
    stdin().read_line(&mut line).unwrap();

    line.trim()
        .split_whitespace()
        .map(|s| s.parse().ok().unwrap())
        .collect()
}

fn main() {
    let (a, b, c, d) = read_cols!(i64, i64, i64, i64);

    println!("{}", max(max(a * c, a * d), max(b * c, b * d)));
}


Measured memory_bytes: 2152
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.NoSuchElementException;

public class Main {

	static int N;

	public static void main(String[] args) {

		FastScanner sc = new FastScanner();
		N = sc.nextInt();

		int[] L = new int[N];
		for (int i = 0; i < N; i++)
			L[i] = sc.nextInt();
		int ans = 0;

		Arrays.sort(L);

		for (int i = 0; i < N - 2; i++)
			for (int j = i + 1; j < N - 1; j++)
				for (int k = j + 1; k < N; k++)
					if (L[k] < L[j] + L[i])
						ans++;
		System.out.println(ans);

	}
}

class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}

	private int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}

	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
			ptr++;
		return hasNextByte();
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	public long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
			throw new NumberFormatException();
		return (int) nl;
	}

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


Measured memory_bytes: 22228
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [[0]]
limit = 0
for i in range(N-1):
    B = []
    for j in range(limit + 2):
        for x in A:
            if max(x) + 1 < j:
                continue
            y = x + [j]
            B.append(y)
    A = B
    limit += 1

A = [tuple(x) for x in A]
A = sorted(set(A))
for x in A:
    x = [chr(y + ord('a')) for y in x]
    print(''.join(x))


Measured memory_bytes: 44872
#include <fstream>
#include <algorithm>
#include <deque>
#include <iostream>

// BE CAREFUL WITH HASH TABLE & UNORDERED MAP
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
using namespace std;

#define MOD 998244353
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define F0R(i,b) FOR(i,0,b)
#define RFO(i,a,b) for (int i = (b-1); i >= (a); i--)
#define RF0(i,b) RFO(i,0,b)
#define lli long long int
#define pii pair<lli,lli>
#define add(a,b) ((int) (((lli) (a) + (b))%MOD))
#define mul(a,b) ((int) (((lli) (a) * (b))%MOD))
#define PB emplace_back
#define F first
#define S second

// ifstream cin ("cinput.in");
// ofstream cout ("coutput.out");

lli N, D, A, x, h;
deque<pii> msts;
deque<pii> ev; // location, subtract
// Helper Functions

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> D >> A;
    F0R(i,N) {
        cin >> x >> h;
        msts.PB(make_pair(x,h));
    }
    sort(msts.begin(), msts.end());

    lli ans = 0;
    lli dam = 0;
    while (!msts.empty()) {
        if (ev.empty() || msts[0].first <= ev[0].first) {
            pii cur = msts[0];
            msts.pop_front();
            if ((lli) cur.second - dam > 0) {
                lli num = (cur.second - dam + A - 1) / A;
                ans += num;
                ev.PB(make_pair(cur.first+2*D, num*A));
                dam += num*A;
            }
        } else {
            pii cur = ev[0];
            ev.pop_front();
            dam -= cur.second;
        }
    }
    cout << ans << '\n';
}

Measured memory_bytes: 6716
#include <iostream>

using namespace std;

int main(){
	int a;
	int b;
	int c;
	int d;
	int e;
	int f;
	int g;
	int h;
	cin>>a>>b>>c>>d;
	cin>>e>>f>>g>>h;
	if(a+b+c+d>e+f+g+h)
	{
	    cout<<a+b+c+d<<endl;
	}
	if(e+f+g+h>a+b+c+d)
	{
        cout<<e+f+g+h<<endl;	
	}
	if(e+f+g+h==a+b+c+d)
	{
	    cout<<a+b+c+d<<endl;
	}

	return 0;
}

Measured memory_bytes: 1160
#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
#define INF 1e18

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef vector < pair<int, int> > vii;
typedef long double ld;
typedef tree<pair<int,int>, null_type, less<pair<int,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;

ll n, k, x, ans, a[222222], t;
vi b;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> k;
	for(int i = 0; i < n; i++){
		cin >> x;
		a[x]++; 
	}
	for(int i = 0; i < 200001; i++){
		if(a[i]){
			b.pb(a[i]);
			t++;
		}
	}
	sort(b.begin(),b.end());
	for(int i = 0; i < b.size(); i++){
		if(t<=k){
			cout<<ans<<'\n';
			return 0;
		}
		else{
			t--;
			ans+=b[i];
		}
	}
	return 0;
}


Measured memory_bytes: 2936
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

a, b, c, d = rl()

ans = max(a*c, a*d, b*c, b*d)
print(ans)


Measured memory_bytes: 68012
from sys import stdin
readline = stdin.readline


from collections import namedtuple
Point = namedtuple('Point', ['x', 'y'])
Block = namedtuple('Block', ['color', 'direction', 'x', 'y'])


def occupation_point(block):
    x, y = block.x, block.y
    d = [(0, 0), (1, 0), (0, 1), (1, 1)]
    for dx, dy in d:
        yield x + dx, y + dy
    if block.direction:
        y += 2
    else:
        x += 2
    for dx, dy in d:
        yield x + dx, y + dy

def paintout(board, start, value):
    color = board[start.y][start.x]
    if color == 0:
        return
    que =[(start.x, start.y)]
    while que:
        x,y = que.pop()
        if board[y][x] == color:
            board[y][x] = value
            que.extend([(x + dx, y + dy) for dx, dy in [(-1, 0), (0, -1), (1, 0), (0, 1)]])


def is_reachable(size, start, goal, blocks):
    board = [[0] * (size.x + 2) for _ in range(size.y + 2)]
    for bi in blocks:
        for x, y in occupation_point(bi):
            board[y][x] = bi.color
    paintout(board, start, -1)
    return board[goal.y][goal.x] == -1


while True:
    size = Point(*map(int, readline().split()))
    if size.x == 0:
        break
    start = Point(*map(int, readline().split()))
    goal = Point(*map(int, readline().split()))
    blocks = []
    for _ in range(int(readline())):
        blocks.append(Block(*map(int, readline().split())))
    print('OK' if is_reachable(size, start, goal, blocks) else 'NG')

Measured memory_bytes: 6832
#include<iostream>
#include<cmath>
#include<vector>
#include<set>
#include<algorithm>
#include<tuple>
#include<utility>
#include<cctype>
#include<climits>
#include<map>
#include<queue>
#include<functional>

using namespace std;

#define REP(i,a,n) for(int i=a;i<n;++i)
#define REPE(i,a,n) for(int i=a;i<=n;++i)
#define RUP(a,b) ((a+b-1)/(b))
#define ENT "\n"
#define SRTVG(v) sort(v.begin(),v.end(),greater<>())
#define SRTAG(a,n) sort(a,a+n,greater<>())
#define MOD 1000000007

typedef long long ll;
typedef tuple<int,int,bool> Tb;

template<class T> void chmax(T& a, T b) {if(a < b){a=b;}}
template<class T> void chmin(T& a, T b) {if(a > b){a=b;}}
template<class T> void YesNo(T& a) {if(a){cout << "Yes" << ENT;}else{cout << "No" << ENT;}}
template<class T> void YESNO(T& a) {if(a){cout << "YES" << ENT;}else{cout << "NO" << ENT;}}

int atcoder(){
    //入力
    ll n;
    cin >> n;
    ll a[110];
    REP(i,0,n) cin >> a[i];
    ll ans=LLONG_MAX;
    
    REP(i,-100,101){
        ll tmp=0;
        REP(j,0,n) tmp += pow((i-a[j]),2);
        chmin(ans,tmp);
    }
    
    cout << ans;
    
    return 0;
}

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


Measured memory_bytes: 256
function myin(){return require("fs").readFileSync("/dev/stdin", "utf8").trim();}
function myout(text){console.log(text);}//standard output
//[no]param
//0:noConvert	1:singleNum	2:spaceList	3:newLineList	4:spaceNumList	5:newLineNumList
function myconv(i,no){switch(no){case 0:return i;case 1:return parseInt(i);case 2:return i.split(" ");case 3:return i.split("\n");case 4:return i.split(" ").map((a)=>Number(a));case 5:return i.split("\n").map((a)=>Number(a));}}

function Main(input) {
  input = myconv(input,3);
  var N = myconv(input[0],1);
  var list1 = myconv(input[1],4);
  var list2 = myconv(input[2],4);
  var output = 0;
  
  var list3 = [];
  var list4 = [];
  
  for(var i = 0; i < N; i++){
    if(i == 0){
    	list3.push(list1[0]);
  	}else{
      	list3.push(list3[i-1] + list1[i]);
    }
  }
  for(var i = 0; i < N; i++){
    if(i == 0){
    	list4.push(list2[N - 1]);
  	}else{
      	list4.push(list4[i-1] + list2[N - (i + 1)]);
    }
  }
  list4.sort(function(a,b){
  	return b - a;
  });
  //myout(list3);
  //myout(list4);
  for(var i = 0; i < N; i++){
    output = Math.max(output,list3[i] + list4[i]);
  }
  myout(output);
}

Main(myin());

Measured memory_bytes: 7500
"""
左右の累積gcdをもたせて置く

i番目を除く(i=1)
R : acc[i-1]
L : racc[n-i-1] 
"""

n = int(input())
As = list(map(int, input().split()))

def gcd(n, m):
    a = max(n,m)
    b = min(n,m)
    while b:
        a, b = b, a % b
    return a


acc = [As[0]]
racc = [As[-1]] #(右から)i番目の累積gcd
for i in range(1,n):
    acc.append(gcd(acc[i-1],As[i]))
    racc.append(gcd(racc[i-1],As[-i-1]))

racc = racc[::-1] #i番目以降のgcd
ans = 0
for i in range(n):
    if i == 0:
        ans = max(ans, racc[i+1])
    elif i == n-1:
        ans = max(ans, acc[i-1])
    else:
        ans = max(ans, gcd(acc[i-1],racc[i+1]))
    
print(ans)

Measured memory_bytes: 71660
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
/*
//#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
*/

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
/*
//#if __cplusplus >= 201103L
#include <array>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
*/
using namespace std;
#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl

#define uni(x) x.erase(unique(all(x)),x.end())
template<class T,class U>inline void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>inline void chmax(T &t,U f){if(t<f)t=f;}
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) > (b) ? (b) : (a))

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;

#define INF INT_MAX/3
#define MAX_N 1000
#define M_INF 1000000000
int n,m,v,i;
void solve(){
   cin.tie(0);
  ios::sync_with_stdio(false);
  string s;ll k;
  cin>>s>>k;
  ll i = 0;
  while(s.size()>i) {
    if(s[i]=='1') i++;
    else break;
  }
  if(k<=i) cout<<1<<endl;
  else if(s.size()==1) cout<<s[0]<<endl;
  else if(s[0] != '1') cout<<s[0]<<endl;
  else if(i == s.size()) cout<<1<<endl;
  else cout<<s[i]<<endl;
}

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


Measured memory_bytes: 256
#ABC113C-ID.py

from sys import stdin

input = stdin.readline

N, M = list(map(int, input().split()))

Info = []

for i in range(M):
    s = input().split()
    Info.append([i, int(s[0]), int(s[1]), s[0], 'a'])
    while len(Info[i][3]) < 6:
        Info[i][3] = '0' + Info[i][3]

Info.sort(key=lambda x: (x[1],x[2]))

j = 0
k = Info[0][1]
for i in range(M):
    if k == Info[i][1]:
        j += 1
        Info[i][4] = str(j)
        while len(Info[i][4]) < 6:
            Info[i][4] = '0' + Info[i][4]
    else:
        k = Info[i][1]
        j = 1
        Info[i][4] = str(j)
        while len(Info[i][4]) < 6:
            Info[i][4] = '0' + Info[i][4]

Info.sort()

for i in range(M):
    print(Info[i][3] + Info[i][4])


Measured memory_bytes: 41792
import java.util.Scanner;

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

		int min = 999999999;
		for (int i = 0; i < N; i++) {
			A[i] = sc.nextInt();
			int count = 0;
			while (A[i] % 2 == 0) {
				A[i] /= 2;
				count++;
			}
			min = Math.min(min, count);
		}

		sc.close();
		System.out.println(min);
	}
}


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

int main() {
  int a, P = 0, W = 0, G = 0, Y = 0;
  string b;
  cin >> a;
  for(int i = 0; i < a; i++) {
  	cin >> b;
    if(b == "P") {
      P++;
    }else if(b == "W") {
      W++;
    }else if(b == "G") {
      G++;
    }else{
      Y++;
    }
  }
  
  if(P && W && G && Y) {
	cout << "Four" << endl;
  }else{
    cout << "Three" << endl;
  }
}

Measured memory_bytes: 256
n=int(input())
s=input()
l=["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"]
new=""

for i in range(len(s)):
    if(l.index(s[i])+n >=26):
        num=l.index(s[i])+n-26
    else:
        num=l.index(s[i])+n
    new=new[:]+ l[num]
print(new)


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

using namespace std;


int main(){
    int N=0;
    long ans=0;
    cin>>N;
    vector<long> Avec(N);
    vector<long> Bvec(N);

    for(int i=0;i<N;++i){
        cin>>Avec[i];
        cin>>Bvec[i];

    }

long tmp=0;

    for(int i=N-1;i>=0;--i){

        if((tmp+Avec[i])%Bvec[i]==0){
            continue;
        }else{
        ans+=Bvec[i]-(tmp+Avec[i])%Bvec[i];
        tmp+=Bvec[i]-(tmp+Avec[i])%Bvec[i];
        }

        
    
    }


    cout<<ans<<endl;

}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define _GLIBCXX_DEBUG
const ll MOD = 1000000007;
const ll Mod = 998244353;
const int MAX = 510000;
const double PI = 3.14159265358979;
const vector<int> dx = {1, 0};
const vector<int> dy = {0, 1};

int main() {
  int A, B, C, K;
  cin >> A >> B >> C >> K;
  for (int i=0; i<K; i++) {
    if (A<B&&B<C) {
      cout << "Yes" << endl;
      return 0;
    }
    if (A>=B) B *= 2;
    else if (B>=C) C *= 2;
  }
  if (A<B&&B<C) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 3624
S=gets.chomp
s1=S[0..1].to_i
s2=S[2..3].to_i

a=false
b=false
if s1<=12 && s1>0 then
  a=true
end
if s2<=12 && s2>0 then
  b=true
end

if a && b then
  puts 'AMBIGUOUS'
elsif !a && b
  puts 'YYMM'
elsif a && !b
  puts 'MMYY'
else
  puts 'NA'
end

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

int main() {
 int N,L;
  cin>>N>>L;
  vector<string> s(N);
  for(string &x: s) cin>>x;
  sort(s.begin(),s.end());
  for(int i=0;i<N;i++)
  cout<<s[i];
}
  

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
 
int main() {
  int N = 0;
  int A = 0;
  
  cin >> N;
  cin >> A;
  if ((( 0 <= N ) && ( N <= 100 )) &&
      (( 0 <= A ) && ( A <= pow(N,2) )))
  {
    cout << pow(N,2) - A << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll minCost(vector<vector<ll> > &cost, ll m, ll n)
{
     ll i, j;

     // Instead of following line, we can use ll tc[m+1][n+1] or
     // dynamically allocate memoery to save space. The following line is
     // used to keep te program simple and make it working on all compilers.
     vector<vector<ll> > tc(m+1,vector<ll>(n+1,0));

     tc[0][0] = cost[0][0];

     /* Initialize first column of total cost(tc) array */
     for (i = 1; i <= m; i++)
        tc[i][0] = tc[i-1][0] + cost[i][0];

     /* Initialize first row of tc array */
     for (j = 1; j <= n; j++)
        tc[0][j] = tc[0][j-1] + cost[0][j];

     /* Construct rest of the tc array */
     for (i = 1; i <= m; i++)
        for (j = 1; j <= n; j++)
            tc[i][j] = max(tc[i-1][j-1],max(tc[i-1][j],tc[i][j-1])) + cost[i][j];

     return tc[m][n];
}
int main()
{
    ll m,n;
    cin>>m;
    n=2;
    vector<vector<ll> > v(n+1,vector<ll>(m+1,0));
    for(ll i=1;i<=n;i++)
    {
        for(ll j=1;j<=m;j++)
        {
            cin>>v[i][j];
        }
    }
    ll ans=minCost(v,n,m);
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#define _GLIBCXX_DEBUG //エラーを出すためのおまじない
#include <bits/stdc++.h>
using namespace std;
#define coYES cout << "YES" << endl
#define coNO cout << "NO" << endl
#define coYes cout << "Yes" << endl
#define coNo cout << "No" << endl
#define coyes cout << "yes" << endl
#define cono cout << "no" << endl
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) {
    int num;
    cin >> num;
    a.at(i) = num;
  }
  bool flag = true;
  int count = 0;
  while(flag) {
    rep(i, n) {
      if (a.at(i) % 2 == 1) {
        flag = false;
        break;
      }
      a.at(i) /= 2;
    }
    if (flag == false) {
      break;
    }
    count++;
  }
  cout << count << endl;
}


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

#define int long long

#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)a, i##_len=(b); i<i##_len; i++)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

using namespace std;

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

const long long INF = LLONG_MAX/3;

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

struct UnionFind{
	std::vector<int> par,siz;
	void init(int n){
		par.resize(n);
		for(int i=0;i<n;i++)par[i]=i;
		siz.resize(n,1);
	}
	UnionFind(int n){
		init(n);
	}
	int root(int n){
		if(par[n]==n)return n;
		else return par[n]=root(par[n]);
	}
	bool issame(int x,int y){
		return (root(x)==root(y));
	}
	bool marge(int a,int b){
		if(issame(a,b))return false;
		else{
			a=root(a),b=root(b);
			if(siz[a]<siz[b])swap(a,b);
			siz[a]+=siz[b];
			par[a]=par[b];
			return true;
		}
	}
	int size(int n){
		return siz[root(n)];
	}
};

long long gcd(long long a,long long b){
    if(b==0)return a;
    return gcd(b,a%b);
}
long long lcm(long long i,long long j){
    return i*(j/gcd(i,j));
}
const int MOD=1e9+7;
signed main(){
	int n;
	cin>>n;
	int memo1=-1,memo2=-1;
	int ans=true;
	int cnt=0;
	rep(i,n){
		int a;
		cin>>a;
		if(memo1==-1)memo1=a;
		else if(memo1!=-1&&a!=memo1&&memo2==-1)memo2=a;
		else if(memo1!=-1&&memo2!=-1&&a!=memo1&&a!=memo2){
			ans=false;
		}
		if(a==memo1)cnt++;
	}
	if(memo2==-1){
		if(!(memo1+1>=n||memo1*2<=n))ans=false;
	}
	else {
		if(memo1>memo2){
			swap(memo1,memo2);
			cnt=n-cnt;
		}
		if(!(cnt<=memo2&&(memo2-cnt)>=1&&(n-cnt)>=(memo2-cnt)*2)||memo2-memo1>1)ans=false;
	}
	cout<<(ans?"Yes":"No")<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
int str_length(const char s[]) {
  int len = 0;
  
  while (s[len])
    len++;
  return len;
}

int main(void){
  char S[200001];
  char T[200001];

  scanf("%s%s", S, T);
  

  int n = str_length(S);
  int wa = 0;
  for(int i = 0; i < n; i++) {
    if(S[i] == T[i]){ wa++; }
  }
  printf("%d", n - wa);
  return 0;
}


Measured memory_bytes: 2116
n,k = map(int, input().split())
a = list(map(int,input().split()))
ans = 1
c = [1]
d = [0]*(n+5)
d[1] = 1
for j in range(1,2*n):
    i = a[c[-1]-1]
    if d[i] == 1:
        g = i
        break
    # if i in set(c):
    #     g = i
    #     break
    d[i] = 1
    c.append(i)
s = c.index(g)
r = len(c)-s
if k <=s:
    print(c[k])
else:
    b = (k-s)%r
    print(c[s+b])

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

int main(){
  int n, a, b[100009]={}, ans=0;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a;
    b[a]++;
  }
  
  for(int x=0;x<100007;x++){
    ans=max(ans, b[x]+b[x+1]+b[x+2]);
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define MA(i,j) make_pair(i,j)
#define PA pair<int,int>
#define PB push_back
#define PQ priority_queue<int>
#define PGQ priority_queue<int,vector<int>,greater<int> >
#define VE vector<int>
#define VP vector<PA>
#define MOD 1000000007
#define INF 1000000007
using namespace std;
//
int N,K;
int A[200000];
int CNT[200001];
int ans;
set<int> S;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin>>N>>K;
  FOR(i,0,N){
    cin>>A[i];
    CNT[A[i]]++;
    S.insert(A[i]);
  }
  sort(CNT,CNT+200000);
  int i=0;
  while(CNT[i]==0){
    i++;
  }
  if((int)S.size()<=K){
    cout<<"0"<<endl;
    return 0;
  }else{
    FOR(j,0,(int)S.size()-K){
      ans+=CNT[i];
      i++;
    }
  }
  cout<<ans<<endl;
  return 0;
}


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

int main(){
    int N;
    std::map<int,int>m;
    std::cin>>N;
    for(int i=0;i<N-1;++i){
        int buf;
        std::cin>>buf;
        m[buf-1]++;
    }
    for(int i=0;i<N;++i){
        std::cout<<m[i]<<std::endl;
    }
}

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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

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

void Main()
{
	vector<string> s(3);
	rep(i,3){
		cin >> s[i];
		cout << s[i][i];
	}
	cout << endl;
	return;
}

int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
	return 0;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc, wr = bufio.NewScanner(os.Stdin), bufio.NewWriter(os.Stdout)

func scanString() string { sc.Scan(); return sc.Text() }
func scanInt() int { a,_ := strconv.Atoi(scanString()); return a }
func scanInt64() int64 { a,_ := strconv.ParseInt(scanString(),10,64); return a }
func scanFloat64() float64 { a,_ := strconv.ParseFloat(scanString(),64); return a }

func scanInts(n int) []int {
	res := make([]int, n); for i := 0; i < n; i++ { res[i] = scanInt() }; return res
}

func abs(a int) int { if a<0 { return -a }; return a }
func min(a,b int) int { if a<b { return a }; return b }
func max(a,b int) int { if a>b { return a }; return b }

//•*¨*•.¸¸♪Main•*¨*•.¸¸♪(　-ω-)ノ　(　・ω・)

func main() {
	defer wr.Flush()
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 10000), 1001001)

	n := scanInt()

	a := make([]int, n)
	b := make([]int, n)
	c := make([]int, n)
	d := make([]int, n)

	for i := 0; i < n; i++ {
		a[i] = scanInt()
		b[i] = scanInt()
	}

	for i := 0; i < n; i++ {
		c[i] = scanInt()
		d[i] = scanInt()
	}

	pair := make([][]int, n*2)
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if a[i] < c[j] && b[i] < d[j] {
				pair[i] = append(pair[i], n+j)
				pair[n+j] = append(pair[n+j], i)
			}
		}
	}

	ans,_ := bipartiteMatching(pair)

	fmt.Fprintln(wr, ans)
}

func bipartiteMatching(g [][]int) (int, []int) {
	used := make([]bool, len(g))
	match := make([]int, len(g))
	for i := 0; i < len(g); i++ { match[i] = -1 }

	var fn func(v int) bool
	fn = func(v int) bool {
		if used[v] { return false }
		used[v] = true
		for _, to := range g[v] {
			if match[to] == -1 || fn(match[to]) {
				match[v], match[to] = to, v
				return true
			}
		}
		return false
	}

	res := 0

	for i := 0; i < len(g); i++ {
		used = make([]bool,len(g))
		if match[i] == -1 && fn(i) { res++ }
	}

	return res, match
}


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

typedef unsigned long long ull;

int main() {
    ull x,count = 0,ans = 100;
    cin >> x;
    for (;;) {
        if (ans >= x) {
            cout << count;
            return 0;
        }
        ans *= 1.01;
        ++count;
    }
    return 0;
}


Measured memory_bytes: 3644
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC137A
{
    class Program
    {
        static void Main(string[] args)
        {
            int a, b,m,n,l;
            var word = Console.ReadLine().Split(' ');
            a = int.Parse(word[0]);
            b = int.Parse(word[1]);
            m = a + b;
            n = a - b;
            l = a * b;
            if (m >= n && m >= l)
            {
                Console.WriteLine(m);
            }
            else if (n >= m && n >= l)
            {
                Console.WriteLine(n);
            }
            else if (l >= m && l >= n)
            {
                Console.WriteLine(l);
            }
            Console.ReadKey();
        }
    }
}


Measured memory_bytes: 13140
// ABC001C.cpp : コンソール アプリケーションのエントリ ポイントを定義します。
//
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <map>

using namespace std;




int main()
{
	string str;
	cin>>str;
	int length = str.length();
	//cout << "length : " << length <<endl;
	int min = 999;
	for(int i = 0; i <= length - 3; i++){
		int diff = abs( 753 - stoi(str.substr(i,3)));
		if(diff < min){
			min = diff;
		}
		//cout << i <<" : stoi->"<<stoi(str.substr(i,3)) << ", min->"<<min<<endl;
	}
	cout<<min<<endl;
	return 0;
}



Measured memory_bytes: 384
#define _USE_MATH_DEFINES
#include<iostream>
#include<iomanip>
#include<algorithm>	
#include<string>
#include<math.h>
#include <vector>
using namespace std;
int main() {
	string S;
	string fire;
	char f[100];
	int a = 0;
	int N = 0;
	int T = 0;
	int l = 0;
	int A[100000] = { 0 };
	int r = 0;
	int c = 0;
	int p = 0;
	int sum = 0;
	double ans = 0;


	cin >> a >> S;
	if (3200 <= a) {
		cout << S << endl;
	}
	else {
		cout << "red" << endl;
	}
}

Measured memory_bytes: 256
/**
 *    author:  FromDihPout
 *    created: 2020-08-14
**/

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


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    vector<int> r1(n), r2(n);
    for (int i = 0; i < n; i++) {
        cin >> r1[i];
        r1[i] += r1[i-1];
    }
    for (int i = 0; i < n; i++) {
        cin >> r2[i];
    }
    for (int i = n-2; i >= 0; i--) {
        r2[i] += r2[i+1];
    }
    
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, r1[i] + r2[i]);
    }
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 3620
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i = 0; i < (ll)(n); i++)
#define inf 1000000000000000000
#define mod 1000000007
#define mod2 998244353
#define pi acos(-1)
#define all(x) (x).begin(),(x).end()
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

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

  ll n; cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];

  map<tuple<ll, ll, ll>, ll> dp;
  dp[{0, 0, 0}] = 0;

  for (ll i = 1; i < n + 1; i++) {
    ll maxj = (i % 2 == 0)? i/2 : i/2 + 1;
    ll minj = ((n - i) % 2 == 0)? n/2 - (n - i)/2 : n/2 - ((n - i)/2 + 1);
    for (ll j = minj; j < maxj + 1; j++) {
      if (dp.count(make_tuple(i - 1, j, 0)) == 0) dp[{i - 1, j, 0}] = -inf;
      if (dp.count(make_tuple(i - 1, j, 1)) == 0) dp[{i - 1, j, 1}] = -inf;
      if (dp.count(make_tuple(i - 1, j - 1, 0)) == 0) dp[{i - 1, j - 1, 0}] = -inf;
      dp[{i, j, 0}] = max(dp[{i - 1, j, 0}], dp[{i - 1, j, 1}]);
      dp[{i, j, 1}] = dp[{i - 1, j - 1, 0}] + a[i - 1];
    }
  }
  cout << max(dp[{n, n/2, 0}], dp[{n, n/2, 1}]) << endl;
}


Measured memory_bytes: 90728
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <numeric>
#include <cmath>

#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
using P = pair<ll, ll>;

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

const ll MOD = 1000000007;
const int INF = 1<<30;
//const ll INF = (ll)1e18 + 1;

int gcd(int x, int y){
  return y == 0 ? x : gcd(y, x % y);
}

int main(){
  int N; cin >> N;
  vector<int> a(N); rep(i, N) cin >> a[i];

  int g = a[0];
  for (int i = 1; i < N; ++i){
    g = gcd(g, a[i]);
  }
  cout << g << endl;
}


Measured memory_bytes: 3736
//#include <bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<numeric>
#include<cstdio>
#include<cmath>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<ctype.h>
#include <fstream>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
using namespace std;
typedef long long ll;//int64
typedef unsigned long long ull;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int dy[4]={0,1,0,-1};
//----------program from here----------

int main(){
  int N=0,c=0;
  
  cin >> N;
  while(N){
    c += N;
    --N;
  }
  cout << c << endl;

  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
int main(){
  int i, H, W;
  for (; ;) {
    scanf("%d %d", &H, &W);
    if (H==0 && W==0) break;
    char s[W+1]={""};
    for (i=0; i<W; i++) {
      s[i] = '#';
    }
    s[i] = '\0';
    for (i=0; i<H; i++) {
      printf("%s\n", s);
    }
    printf("\n");
  }
}


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

using namespace std;

#define INF (1ll << 62)
#define pb push_back
#define ii pair<int,int>
#define OK cerr <<"OK"<< endl
#define debug(x) cerr << #x " = " << (x) << endl
#define ff first
#define ss second
#define int long long
#define tt tuple<int, int, int>
#define endl '\n'

int dp[105][100005]; 
int moc(int q,int p,vector<ii> vec) {
  for(int i = 1; i <= q; i++)
  {
    for(int j = 1; j <= p;j++) {
      if(j >= vec[i-1].ff)
        dp[i][j] = max(dp[i-1][j],vec[i-1].ss + dp[i-1][j-vec[i-1].ff]);
      else 
        dp[i][j] = dp[i-1][j];
    }
  }
  return dp[q][p];
}
signed main(signed argc, char *argv[])
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int p,q;
  vector<ii> vec;
  cin >> q >> p;
  int x,y;
  for(int i = 0; i < q; i++) {
       cin >> x >> y;
       vec.push_back(make_pair(x,y)); 
  }
  for(int i = 0; i <= p; i++)
    dp[0][i] = 0;
  for(int i = 1; i <= q; i++)
    dp[i][0] = 0;
  sort(vec.begin(),vec.end());
  cout << moc(q,p,vec) << endl;
}



Measured memory_bytes: 80128
#include<bits/stdc++.h>
using namespace std;
#define LL long long int

LL H, W, mul;

int main() {
    cin >> H >> W;
    mul = H * W;

    if (H == 1 || W == 1)
        cout << 1 << endl;
    else
        cout << mul/2 +(mul%2 == 0 ? 0 : 1) << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <stack>
#include <set>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define INF (int)(1123456789)
#define LINF (long long int)(112345678901234567)
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define all(v) v.begin(), v.end()

const int N = (int)3e5;

ll mpow(ll a, ll b){
	if(b==0) return 1;
	else if(b%2==0){ll memo = mpow(a,b/2); return memo*memo%MOD;}
	else return mpow(a,b-1) * a % MOD;
}
ll gcd(ll a, ll b){
	if(b==0) return a;
	else return gcd(b, a%b);
}
vector<ll> kaijo_memo;
ll kaijo(ll n){
	if(kaijo_memo.size() > n) return kaijo_memo[n];
	if(kaijo_memo.size() == 0) kaijo_memo.push_back(1);
	while(kaijo_memo.size() <= n) kaijo_memo.push_back(kaijo_memo[kaijo_memo.size()-1] * kaijo_memo.size() % MOD);
	return kaijo_memo[n];
}
ll nCr(ll n, ll r){
	if(n < r || r < 0) return 0;
	ll ret = 1;
	ret *= kaijo(n); ret %= MOD;
	ret *= mpow(kaijo(r), MOD-2); ret %= MOD;
	ret *= mpow(kaijo(n-r), MOD-2); ret %= MOD;
	return ret;
}

int main(void){
	int n;cin>>n;
	string s;cin>>s;
	vector<int> S;
	rep(i,s.size()){
		if(s[i] == 'B'){
			S.push_back(1);
		}else{
			S.push_back(0);
		}
	}
	ll ans = 1;
	ll count = 0;
	ll remain = n;
	rep(i,2*n){
		cerr<<i<<" "<<ans<<endl;
		if(count == 2*n-i){
			if((S[i]+count)%2 == 1){
				cout<<0<<endl;
				return 0;
			}
			ans *= count;
			ans %= MOD;
			count--;
			continue;
		}

		if((S[i] + count)%2 == 1){
			ans *= remain;
			ans %= MOD;
			remain--;
			count++;
		}else{
			ans *= count;
			ans %= MOD;
			count--;
		}
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 1532
#include <stdio.h>

int main(void) 
{
  int n;
  int a, b, c, d;
  int combination;

  while (scanf("%d", &n) != EOF) {

    combination = 0;

    for (a = 0; a <= 9; a++) 
      for (b = 0; b <= 9; b++) 
	for (c = 0; c <= 9; c++) 
	  for (d = 0; d <= 9; d++) 
	    if (a + b + c + d == n) 
	      combination++;

    printf("%d\n", combination);
  }

  return 0;
}

Measured memory_bytes: 596
n,m=map(int,input().split())
a=[int(i) for i in input().split()]
t=sum(a)/(4*m)
for i in range(n):
    if m==0:
        break
    else:
        if a[i]>=t:
            m-=1
if m==0:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define USE_MATH_DEFINES
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;

int main() {
    int n;
    cin >> n;
    int d[n];
    rep(i, n) cin >> d[i];
    sort(d, d + n);
    printf("%d\n", d[n / 2] - d[n / 2 - 1]);
}

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

using namespace std;

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

    int ml[n+1];
    ml[0] = 0;
    for (int i = 0; i < n; i++) {
        ml[i+1] = max(ml[i], a[i]);
    }

    int mr[n+1];
    mr[n] = 0;
    for (int i = n - 1; i >= 0; i--) {
        mr[i] = max(mr[i+1], a[i]);
    }

    for (int i = 0; i < n; i++) {
        cout << max(ml[i], mr[i+1]) << endl;
    }

    return 0;
}


Measured memory_bytes: 3968
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define range(i,a,n) for(int i=(a);i<(n);i++)

#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI 3.1415926535897932384

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

template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S acm(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
void YN(bool b){cout<<(b?"YES":"NO")<<"\n";}
void Yn(bool b){cout<<(b?"Yes":"No")<<"\n";}
void yn(bool b){cout<<(b?"yes":"no")<<"\n";}
int sgn(const double&r){return (r>EPS)-(r<-EPS);} // a>0  : sgn(a)>0
int sgn(const double&a,const double&b){return sgn(a-b);} // b<=c : sgn(b,c)<=0

ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s;a=0;} return os;}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll a,b,c;
	cin>>a>>b>>c;
	cout<<max(0ll,c-(a-b))<<endl;
}


Measured memory_bytes: 256
fn main() {
    proconio::input! {
        s: proconio::marker::Chars,
        t: proconio::marker::Chars,
    }
    let len = t.len() - 1;
    let ans = if t.into_iter().take(len).collect::<Vec<_>>() == s {
        "Yes"
    } else {
        "No"
    };
    println!("{}", ans);
}


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

using namespace std;

int main() {
	int n;

	scanf("%d", &n);

	if (n % 2 == 0) {
		printf("%d\n", (n / 2) - 1);
	}
	else {
		printf("%d\n", (n - 1) / 2);
	}

	return 0;
}

Measured memory_bytes: 256
/*------------------------- Bism Allah Alruhmin Alrahim -------------------------------*/
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < n; i++)
#define ford(i, n) for (int i = n - 1; i > -1; i--)
#define forl(i, l, r) for (int i = l; i <= r; i++)
#define vc vector
#define f first
#define s second
#define pb(i) push_back(i)
#define mx(ar, n) (*max_element(ar, ar + n))
#define mn(ar, n) (*min_element(ar, ar + n))

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
const long double pi = acos(-1);

int main()
{
	int n , q ; string s ;
	cin >> n >> q >> s ; 
	int x[n] = {0}  , c = 0;

	for (int i = 0; i < s.size()-1; ++i)
	{
		// cout << s[i] << " " << s[i+1] << endl ;
		if(s[i] == 'A' and s[i+1] == 'C'){
			x[i] = c ;
			c++ ;
			x[i+1] = c ; 
		}
		else{
			x[i+1] = c ; 
			x[i] = c ; 
		}
	}

	while(q--){
		int a , b ; cin >> a >> b ;
		cout << x[b-1] - x[a-1] << endl ;
	}	
	return 0 ;
}


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

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

    int N;
    string S;
    cin >> N >> S;

    int all_wnum = 0;
    for (int i = 0; i < N; i++)
    {
        if (S[i] == '.')
        {
            all_wnum++;
        }
    }
    int ans = min(all_wnum, N - all_wnum);
    int bnum = 0, wnum = 0;
    for (int i = 0; i < N; i++)
    {
        if (S[i] == '#')
        {
            bnum++;
        }
        else
        {
            wnum++;
        }
        ans = min(ans, bnum + (all_wnum - wnum));
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 720
S=list(input())
T=list(input())
ans=len(T)
c,count=0,0
for i in range(len(S)-ans+1):
    a=S[i:i+ans+1]
    for j in range(ans):
        if a[j]==T[j]:
            count+=1
    c=max(c,count)
    count=0
print(ans-c)


Measured memory_bytes: 9040