akhauriyash/Code-Regression huggingface dataset:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.StringTokenizer;

public class Main 
{

	public static void main(String[] args) 
	{
		FastReader sc = new FastReader();
		int n = sc.nextInt();
		StringBuilder sb = new StringBuilder();
		int curs = 0;
		LinkedList<Integer> l = new LinkedList<Integer>();
		ListIterator<Integer> lit = l.listIterator();
		lit.add(-1000000001);
		lit.previous();
//		System.out.println(lit + " " + lit.previous());
		
		for(int i = 0; i < n; i++)
		{
//			System.out.println(l);
			int com = sc.nextInt();
			if(com == 0)
			{ //insert
//				l.add(curs, sc.nextInt());
				lit.add(sc.nextInt());
				lit.previous();
			}
			else if(com == 1)
			{ //move
//				curs += sc.nextInt();
				int arg = sc.nextInt();
				if(arg > 0)
				{
					for(int k = 0; k < arg && lit.hasNext(); k++)
					{
						lit.next();
					}
				}
				else
				{
					for(int k = 0; k < -arg && lit.hasPrevious(); k++)
					{
						lit.previous();
					}
				}
				
				if(!lit.hasNext() && lit.hasPrevious())lit.previous();
			}
			else
			{ //erase
//				System.out.println("Removing " + lit.previous());
				if(lit.hasNext())
				{
					lit.next();
					lit.remove();
				}
				else
				{
				}
//				System.out.println(l);
//				curs = Math.min(curs, l.size());
//				if(curs < 0)curs = 0;				
//				l.remove(curs);
			}
			
		}
		
//		System.out.println("TOT " + l.size());
		int ii = 0;
		
		
		for(int i : l)
		{
			if(i >= -1000000000)
			{
				if(ii > 0)sb.append("\n");
				sb.append(i);
				ii++;
			}
		}
		
		
		/*
		while(!l.isEmpty())
		{
			if(ii > 0)sb.append("\n");
			sb.append(l.poll());
			ii++;
		}
		*/

		System.out.println(sb);
		// TODO Auto-generated method stub

	}
    static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 

}



Measured memory_bytes: 124232
while(True):

    val1=input().split(" ")
    val2=[int(n) for n in val1]
    
    if val2 ==[0,0]:
        break
    else:
        for i in range(val2[0]):
            for j in range(val2[1]):
                if i>0 and j>0 and i < val2[0]-1 and j < val2[1]-1:
                    print(".",end="")
                else:
                    print("#",end="")
            print()
    print()


Measured memory_bytes: 7016
#include <stdio.h>
int main(void)
{
    int N, minb;
    scanf("%d", &N);
    int A[N], B[N - 1];
    for (int i = 0; i < N - 1; i++)
    {
        scanf("%d", &B[i]);
    }
    A[0] = B[0];
    A[N - 1] = B[N - 2];
    for (int i = 1; i < N - 1; i++)
    {
        minb = B[i];
        if (B[i] > B[i - 1])
        {
            minb = B[i - 1];
        }
        A[i] = minb;
    }
    int max = 0;
    for (int i = 0; i < N; i++)
    {
        max += A[i];
    }
    printf("%d", max);
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;

int main(void)
{

	int x, y;
	cin >> x >> y;

	if (x == 2 || y == 2) {
		printf("No\n");
		return 0;
	}

	if (x == 4 || x == 6 || x == 9 || x == 11) {
		x = 0;
	}

	if (y == 4 || y == 6 || y == 9 || y == 11) {
		y = 0;
	}

	if (x == y) {
		printf("Yes\n");
	}
	else if (x == 0 || y == 0) {
		printf("No\n");
	}
	else {
		printf("Yes\n");
	}

	return 0;
}

Measured memory_bytes: 256
from itertools import accumulate
import collections
N,M = map(int,input().split())
A = list(map(int,input().split()))
dic = collections.defaultdict(int)
P = list(accumulate(A))
for p in P:
    dic[p%M] += 1
ans = 0
for key,val in dic.items():
    if key==0: ans += val # あまり0の時はそれ自体もカウント
    ans += val*(val-1)//2
print(ans)

Measured memory_bytes: 17624
H, W, K = map(int, input().split())
c = []
cnt = [0] * H
num = 0
A = [[0] * W for _ in range(H)]

for i in range(H):
    row = list(input())
    c.append(row)
    cnt[i] = row.count("#")


def solve(cl, cr):
    global num
    P = []
    for i in range(cl, cr + 1):
        for j in range(W):
            if c[i][j] == "#":
                P.append(j)
    P = sorted(P)
    for i in range(len(P)):
        v1 = 0
        v2 = W - 1
        if (i >= 1):
            v1 = P[i - 1] + 1
        if (i < len(P) - 1):
            v2 = P[i]
        num += 1
        for j in range(cl, cr + 1):
            for k in range(v1, v2 + 1):
                A[j][k] = num


vec = []
for i in range(H):
    if cnt[i] >= 1:
        vec.append(i)
for i in range(len(vec)):
    v1 = 0
    v2 = H - 1
    if (i >= 1):
        v1 = vec[i - 1] + 1
    if (i < len(vec) - 1):
        v2 = vec[i]
    solve(v1, v2)
for i in range(H):
    print(*A[i])


Measured memory_bytes: 8272
s = int(input())

def f(n):
    if n % 2 == 0:
        return n // 2
    else:
        return 3*n + 1

l = [s]
i = 0
while True:
    g = f(l[i])
    if g in l:
        print(i+2)
        break
    l.append(g)
    i += 1


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

int main() {
	int  n; cin >> n;
	if(n < 105) cout << 0 << endl;
	else if(n < 135) cout << 1 << endl;
	else if(n < 165) cout << 2 << endl;
	else if(n < 189) cout << 3 << endl;
	else if(n < 195) cout << 4 << endl;
	else cout << 5 << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define FAST_IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main(){
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    string str;
    while(cin>>str){
        string st="YAKI";
        int flag=1;
        for(int i=0;i<4;i++){
            if(str[i]!=st[i]){
                flag=0;
                break;
            }
        }
        cout<<(flag?"Yes":"No")<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
  int n,m; cin >> n >> m; vector<ll> A(n+1,0); int a;
  for (int i=0;i<m;i++)
  {  cin >> a;
  	A[a]=-1;
  }
  vector<ll> dp(n+1,0);
  ll mod=1e9+7;
  dp[0]=1; dp[1]=(A[1]==0);
  for (int i=2;i<=n;i++)
  {
    if (A[i]==-1) dp[i]=0;
    else
    {
      dp[i]=(dp[i-1]+dp[i-2])%mod;
    }
  }
  cout << dp[n];
  return 0;
}


Measured memory_bytes: 1792
import java.util.*;
import java.io.*;
public class Main {

	static Scanner inp= new Scanner(System.in);
	static PrintWriter out= new PrintWriter(System.out);
	public static void main(String args[]) {		    	
	   	Main g=new Main();
	   	g.main();
	   	out.close();
	}

	
	
	//Main
	void main() {
		
		String s=inp.next();
		int n=s.length();
		int gg=0;
		for(int i=0;i<n;i++) {
			gg+=(s.charAt(i)-'0');
		}
		System.out.println(gg%9==0?"Yes":"No");
		
	}
    
    
		
}


Measured memory_bytes: 40348
my $N = <STDIN>;

my $s = <STDIN>;
my @dat = split(/ /,$s);

my $count = 0;
my $max   = 0; 
for(my $i=1;$i<=$#dat;$i++){
  #print "$i $dat[$i] \n";
  if($dat[$i-1] >= $dat[$i]){
    $count++;
    if( $max < $count ){
      $max = $count ;
    }
  }else{
    $count = 0;
  }
}

print "$max";

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

using namespace std;


int main(void){

  int size,min_diff;
  while(true){
    cin>>size;
    if(size==0) break;
    vector<int> vec(size);
    for(int i=0;i<size;i++){
      cin>>vec.at(i);
  //    vec.push_back(temp);
    }
    sort(vec.begin(),vec.end());
    min_diff=vec.at(1)-vec.at(0);
    for(int i=1;i<size-1;i++){
      int nowdiff=vec.at(i+1)-vec.at(i);
      if(min_diff>nowdiff) min_diff=nowdiff;
    }
    cout<<min_diff<<endl;
  }
  return 0;
}



Measured memory_bytes: 3092
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int k = Integer.parseInt(sc.next());
        int[] a = new int[n];
        int count = 0;        
        for(int i=0; i<n; i++) {
            a[i] = Integer.parseInt(sc.next());
            if(1 == a[i]) count++;
        }
        if((n-count) % (k-1) == 0) System.out.println((n-count)/(k-1));
        else System.out.println(((n-count)/(k-1)) +1);
    }
}


Measured memory_bytes: 48880
#include <iostream>
#include <set>

using namespace std;

int main(int argc, char* argv[])
{
    string S; cin >> S;

    set<char> s;
    for (int i = 0; i < S.size(); i++) {
        s.insert(S[i]);
    }

    cout << ((S.size() == s.size()) ? "yes" : "no") << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <numeric>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

#define rep(i, N) for(int i = 0; i < N; ++i)

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

#define IN(l, r, x) ((l) <= (x) && (x) < (r))

int n, m;
vs64 x, y, z;

s64 solve(int i)
{
    static const s64 sign[2] = {1, -1};

    s64 ret = 0;
    int a, b, c;
    a = (i >> 2) & 1;
    b = (i >> 1) & 1;
    c = (i >> 0) & 1;
    vs64 cand(n);
    rep (i, n)
    {
        cand[i] = sign[a] * x[i] + sign[b] * y[i] + sign[c] * z[i];
    }
    sort(cand.begin(), cand.end(), greater<s64>());

    rep (i, m)
    {
        ret += cand[i];
    }

    return ret;
}

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

    cin >> n >> m;

    x.resize(n);
    y.resize(n);
    z.resize(n);
    rep (i, n)
    {
        cin >> x[i] >> y[i] >> z[i];
    }

    s64 ans = 0;
    rep (i, 8)
    {
        ans = MAX(ans, solve(i));
    }

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



Measured memory_bytes: 256
// atcoder/abc169/F/main.cpp
// author: @___Johniel
// github: https://github.com/johniel/

#include <bits/stdc++.h>

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; for (auto& i: v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { for (auto& i: v) is >> i; return is; }
template<typename T> ostream& operator << (ostream& os, set<T> s) { os << "#{"; for (auto& i: s) os << i << ","; os << "}"; return os; }
template<typename K, typename V> ostream& operator << (ostream& os, map<K, V> m) { os << "{"; for (auto& i: m) os << i << ","; os << "}"; return os; }

template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }

using lli = long long int;
using ull = unsigned long long;
using point = complex<double>;
using str = string;
template<typename T> using vec = vector<T>;

constexpr array<int, 8> di({0, 1, -1, 0, 1, -1, 1, -1});
constexpr array<int, 8> dj({1, 0, 0, -1, 1, -1, -1, 1});
constexpr lli mod = 998244353;

int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.setf(ios_base::fixed);
  cout.precision(15);

  int n, s;
  while (cin >> n >> s) {
    vec<lli> a(n);
    cin >> a;

    const int N = 3000 + 5;
    static lli dp[N][N];
    fill(&dp[0][0], &dp[N - 1][N - 1] + 1, 0);
    dp[0][0] = 1;
    for (int i = 0; i < a.size(); ++i) {
      for (int j = 0; j < N; ++j) {
        if (j + a[i] <= s) (dp[i + 1][j + a[i]] += dp[i][j]) %= mod;
        (dp[i + 1][j] += dp[i][j] * 2) %= mod;
      }
    }
    cout << dp[a.size()][s] << endl;
  }

  return 0;
}


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

int main(){
    int N;
    cin >> N;
    map<string, int> mp;
    for(int i=0; i<N; i++){
        string s;
        cin >> s;
        sort(s.begin(), s.end());
        mp[s]++;
    }
    int64_t ans = 0;
    for(auto& p : mp){
        int64_t num = p.second;
        ans += num*(num-1)/2;
    }
    cout << ans << endl;
    return 0;
}


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

int main(){
    long int N, x;
    cin >> N >> x;
    vector<long int> a(N);
    for (int i = 0; i < N; i++) {
        long int t;
        cin >> t;
        a[i] = t;
    }
    sort(a.begin(), a.end());
    int cnt = 0;
    for(int i = 0; i < N; i++) {
        x -= a[i];
        if (x >= 0) cnt++;
        else break;
        if (i == N-1 && x != 0) {
            cnt--;
        }
    }
    cout << cnt << "\n";
}

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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
using ll = long long;

int need_cnt(char c) {
    if(c == 'a') return 0;
    return 26 - (c - 'a');
}

char rot(char c, int k) {
    int n = ((c - 'a') + k) % 26;
    return (char) n + 97;
}

int main() {
    string s;
    int K;
    cin >> s >> K;
    string ans;
    rep(i, s.size()) {
        char c = s[i];

        if (i == s.size() - 1) {
            ans += rot(c, K);
        } else {
            int cnt = need_cnt(c);
            if (cnt <= K) {
                K -= cnt;
                ans += rot(c, cnt);
            } else {
                ans += c;
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 640
# -*- coding: utf-8 -*-
"""
Created on Wed Feb 27 02:28:19 2019

@author: yuta
"""

def dornut(nx,m):
    nx2 = list(map(int,nx))
    m2 = list(map(int,m))
    m2 = sorted(m2)
    rest = nx2[1] - sum(m2)
    if rest >= m2[0]:
        add = int(rest/m2[0])
    else:
        add = 0
    print(add + nx2[0])

x = input().split()

y = []
for i in range(int(x[0])):
    y.append(int(input()))
    
dornut(x,y)

Measured memory_bytes: 3064
/*************************************
 * @contest:      AtCoder ABC156.
 * @user_id:      63720.
 * @user_name:    Jomoo.
 * @time:         2020-02-22.
 * @language:     C++.
 * @upload_place: Luogu.
*************************************/ 

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

typedef signed char          int8;
typedef unsigned char       uint8;
typedef short                int16;
typedef unsigned short      uint16;
typedef int                  int32;
typedef unsigned            uint32;
typedef long long            int64;
typedef unsigned long long  uint64;

template <typename Int>
inline Int read()       
{
    Int flag = 1;
    char c = getchar();
    while ((!isdigit(c)) && c != '-') c = getchar();
    if (c == '-') flag = -1, c = getchar();
    Int init = c & 15;
    while (isdigit(c = getchar())) init = (init << 3) + (init << 1) + (c & 15);
    return init * flag;
}

template <typename Int>
inline Int read(char &c)       
{
    Int flag = 1;
    c = getchar();
    while ((!isdigit(c)) && c != '-') c = getchar();
    if (c == '-') flag = -1, c = getchar();
    Int init = c & 15;
    while (isdigit(c = getchar())) init = (init << 3) + (init << 1) + (c & 15);
    return init * flag;
}

template <typename Int>
inline void write(Int x)
{
    if (x < 0) putchar('-'), x = ~x + 1;
    if (x > 9) write(x / 10);
    putchar((x % 10) | 48);
}  

template <typename Int>
inline void write(Int x, char nextch)
{
    write(x);
    putchar(nextch);
}

int n;
int x[107];
int minn = INT_MAX, pos;
int now = 0;

int main()
{
    n = read<int>();
    for (int i = 1; i <= n; i++) x[i] = read<int>();
    for (int i = 1; i <= 100; i++) {
        now = 0;
        for (int j = 1; j <= n; j++) now += (x[j] - i) * (x[j] - i);
        if (now < minn) {
            minn = now;
            pos = i;
        }
    }
    write(minn, 10);
    return 0;
}

Measured memory_bytes: 256
def inlt():
    return(list(map(int, input().split())))


def invr():
    return(map(int, input().split()))


n, m, c = invr()
B = inlt()
A = []
for t in range(n):
    A.append(inlt())
# print(A)
# print(B)

correct = 0
for i in range(n):
    s = 0
    for j in range(m):
        s += A[i][j]*B[j]
    s += c
    if s > 0:
        correct += 1
print(correct)


Measured memory_bytes: 3064
#include <cstdio>
#include <algorithm>
#include <vector>

const int MN = 100005;

int N, deg[MN], del[MN];
int col[MN], Cnt;
std::vector<int> G[MN];
int que[MN], lp, rp;
int root, num, sum, ans;

int DFS(int u, int fz) {
	int xv1 = 0, xv2 = 0;
	for (auto v : G[u]) {
		if (del[v] || v == fz) continue;
		int d = DFS(v, u);
		if (d > xv2) xv2 = d;
		if (xv2 > xv1) std::swap(xv2, xv1);
	}
	ans = std::max(ans, xv1 + xv2 + col[u]);
	return xv1 + col[u];
}

int main() {
	scanf("%d", &N);
	for (int i = 1, x, y; i < N; ++i)
		scanf("%d%d", &x, &y),
		G[x].push_back(y),
		G[y].push_back(x),
		++deg[x], ++deg[y];
	for (int i = 1; i <= N; ++i) {
		char s[2];
		scanf("%1s", s);
		col[i] = *s == 'W';
		Cnt += col[i];
	}
	if (Cnt == 0) return puts("0"), 0;
	if (Cnt == 1) return puts("1"), 0;
	lp = 1, rp = 0;
	for (int i = 1; i <= N; ++i)
		if (deg[i] == 1 && !col[i])
			que[++rp] = i;
	while (lp <= rp) {
		int u = que[lp++];
		del[u] = 1;
		for (auto v : G[u])
			if (!del[v] && --deg[v] == 1 && !col[v])
				que[++rp] = v;
	}
	for (int i = 1; i <= N; ++i) if (!del[i]) {
		col[i] ^= deg[i] & 1;
		++num;
		sum += col[i];
		root = i;
	}
	sum += 2 * (num - 1);
	DFS(root, 0);
	printf("%d\n", sum - 2 * ans);
	return 0;
}

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

class Program
{
    public Program() { }


    Scanner cin;

    void myon()
    {
        cin = new Scanner();

        int d = cin.nextInt();
        Console.Write("Christmas");

        for (int i = d; i < 25; i++)
        {
            Console.Write(" Eve");
        }
        Console.WriteLine();
    }

    static void Main(string[] args)
    {
        new Program().myon();
    }
}


class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        i = 0;
        return next();
    }

    public int nextInt()
    {
        return int.Parse(next());
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }

}


Measured memory_bytes: 11092
#include <iostream>

using namespace std;
int table[300010];
int main(){
  int i,j,k,n;
  while(1){
    for(i=0;i<300010;i++)table[i]=1;
    cin >> n;
    if(n == 1)break;
    cout << n << ':';
    for(i=2;i*i<=n;i++){
      if(i%7!=1 && i%7!=6)continue;
      if(n%i==0 && ((n/i)%7==1 || (n/i)%7==6)){
        for(j=2*i;j<300010;j+=i)table[j]=0;
      }
    }
    for(i=2;i<=n;i++){
      if(i%7!=1 && i%7!=6)continue;
      if(table[i] && (n%i==0 && ((n/i)%7==1 || (n/i)%7==6)))cout << ' ' << i;
    }
    cout << endl;
  }
  return 0;
}



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

int main(){
	int i,j;
	int num;

	for(int i=1; i<10; i++){
		for(int j=1; j<10; j++){
			cout << i << "x" << j <<"=" << i*j << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1116
import Data.Maybe

main = do
  n <- readLn :: IO Int
  s <- readLn :: IO Int
  let rN = floor . sqrt . realToFrac $ n
      rN' = if rN^2 == n then rN - 1 else rN
      ans1 = filter (/=Nothing) $ map (solve n s) [2..rN]
  if n < s
    then print (-1)
    else if length ans1 > 0
           then print $ fromJust $ head ans1
           else let ans2 = map fromJust . filter (/=Nothing) $ map (solve' n s) [1..rN']
                in if length ans2 > 0 && n > s
                     then print $ minimum ans2
                     else if n == s
                            then print $ s+1
                            else print (-1)

f :: Int -> Int -> Int
f b n
  | n < b = n
  | otherwise = (f b $ div n b) + mod n b

solve :: Int -> Int -> Int -> Maybe Int
solve n s b = let ans = f b n
              in if ans == s then Just b
                             else Nothing

solve' :: Int -> Int -> Int -> Maybe Int
solve' n s p = let b = (+1) $ div (n - s) p
               in if b == 1
                    then Nothing
                    else let ans = f b n
                         in if ans == s then Just b
                                        else Nothing


Measured memory_bytes: 508
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String sa = scanner.next();
        String sb = scanner.next();
        String sc = scanner.next();

        int currentPlayer = 0; // 0 = A, 1 = B, 2 = C
        while (true) {
//            System.out.print("currentPlayer : " + currentPlayer);
//            System.out.print("sa : " + sa);
//            System.out.print("sb : " + sb);
//            System.out.print("sc : " + sc);

            char nextPlayer = 'a';
            switch (currentPlayer) {
                case 0: {
                    if (sa.isEmpty()) {
                        // A is win
                        System.out.print("A");
                        return;
                    }
                    nextPlayer = sa.charAt(0);
                    sa = sa.substring(1);
                    break;
                }
                case 1: {
                    if (sb.isEmpty()) {
                        // A is win
                        System.out.print("B");
                        return;
                    }
                    nextPlayer = sb.charAt(0);
                    sb = sb.substring(1);
                    break;
                }
                case 2: {
                    if (sc.isEmpty()) {
                        // A is win
                        System.out.print("C");
                        return;
                    }
                    nextPlayer = sc.charAt(0);
                    sc = sc.substring(1);
                    break;
                }
            }

            if (nextPlayer == 'a') {
                currentPlayer = 0;
            } else if (nextPlayer == 'b') {
                currentPlayer = 1;
            } else if (nextPlayer == 'c') {
                currentPlayer = 2;
            }
        }
    }
}


Measured memory_bytes: 20948
N = int(input())
YMD = [[0,0,0] for i in range(N)]
ans = [[[0 for i in range(20)] for j in range(10)] for k in range(1000)]
for i in range(N):
    line = input().split(" ")
    YMD[i] = [int(line[0])-1, int(line[1])-1, int(line[2])-1]

#print(YMD)
count = 0
for y in range(1000):
    if (y+1)%3 == 0:
        for m in range(10):
            for d in range(20):
                ans[y][m][d] = count
                count+=1
    else:
        for m in range(10):
            if m%2 == 0:
                for d in range(20):
                    ans[y][m][d] = count
                    count+=1
            else:
                for d in range(19):
                    ans[y][m][d] = count
                    count+=1
            
mile = ans[999][0][0]
for i in range(N):
    tmpYMD = YMD[i]
    tage = ans[tmpYMD[0]][tmpYMD[1]][tmpYMD[2]]
    diff = mile - tage
    print(diff)


Measured memory_bytes: 14492
#include <stdio.h>
#include <string.h>

int main(int argc, char const* argv[])
{
	int n, i;
	float a[100];
	float ans=0;
	scanf("%d",&n);
	for(i=0; i<n; i++) {
		scanf("%f",a+i);
		ans += 1/a[i];
	}
	printf("%f",1/ans);

	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr long long MOD = 1000000007;
constexpr long long INF = 1LL << 60;
const long double PI = acosl(-1.0);
constexpr long double EPS = 1e-11;
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;
}
int main(){
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    for (ll i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());
    ll ok = 1e9;
    ll ng = 0;
    while(abs(ok-ng)>1){
        ll mid = (ok + ng) / 2;
        ll tmp = 0;
        for (ll i = 0; i < n;i++){
            tmp += (a[i] + mid - 1) / mid;
            tmp--;
        }
        if (tmp > k) {
            ng = mid;
        } else
            ok = mid;
    }
    cout << ok << endl;
}

Measured memory_bytes: 4828
#include<bits/stdc++.h>
using namespace std;
int n,k;
int l[51];
int main(){
    int ans=0;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>l[i];
    }
    sort(l,l+n);
    for(int i=n;i>=n-k;i--){
        ans+=l[i];
    }
    cout<<ans<<endl;
    return 0;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int ans = 0, k;
    cin >> k;
    for(int i = 1; i <= k; i++)
        for(int j = 1; j <= k; j++)
            for(int l = 1; l <= k; l++)
                ans += __gcd(i, __gcd(j, l));
    cout << ans << "\n";

	return 0;
}


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

using namespace std;

int N, M;
int a[3] = {-1, -1, -1};

bool check(int n) {
    string s = to_string(n);
    if (s.length() != N) return false;
    for (int i = 0; i < s.length(); ++i) {
        if (a[i] == -1) {
            continue;
        } else if (s[i] - '0' != a[i]) {
            return false;
        }
    }
    return true;
}

bool check0() {
    return N == 1 and a[0] == 0 and a[1] == -1 and a[2] == -1;
}

int main() {
    cin >> N >> M;

    if (N == 1 and M == 0) {
        cout << 0 << '\n';
        return 0;
    }

    for (int i = 0; i < M; ++i) {
        int x, y;
        cin >> x >> y;
        x--;
        if (a[x] != -1 and a[x] != y) {
            cout << -1 << '\n';
            return 0;
        } else {
            a[x] = y;
        }
    }

    for (int i = 1; i < 1000; ++i) {
        if (check(i)) {
            cout << i << '\n';
            return 0;
        }
    }

    if (check0()) {
        cout << 0 << '\n';
    } else {
        cout << -1 << '\n';
    }
    return 0;
}



Measured memory_bytes: 256
#include<stdio.h>

#define MAX 100005
#define NIL -1

struct Node_struct{int p, l, r;}; /*p: 親(parent), l: 一番左の子(left child), r:右の兄弟(right sibling)*/
typedef struct Node_struct Node;
Node T[MAX];
int D[MAX];

void print(int u){
  int i, c;
  printf("node %d: parent = %d, depth = %d, ", u, T[u].p, D[u]);

  if(T[u].p == NIL) printf("root, ");
  else if(T[u].l == NIL) printf("leaf, ");
  else printf("internal node, ");

  printf("[");
  for (i=0, c = T[u].l; c != NIL; i++, c = T[c].r){
    if(i) printf(", ");
    printf("%d", c);
  }
  printf("]\n");

}

void calcDepth(int u, int p){
  D[u] = p;
  if(T[u].l != NIL) calcDepth(T[u].l, p+1);
  if(T[u].r != NIL) calcDepth(T[u].r, p);
}

int main(){
  int i, j, k;
  int n;
  int id, sib, child;
  int root = NIL;
  scanf("%d", &n);
  for(i=0; i<n; i++) T[i].p = T[i].l = T[i].r = NIL;

  for(i=0; i<n; i++){
    scanf("%d %d", &id, &k);
    for(j = 0, sib = NIL; j<k; j++){ //子を入力する (input children)
      scanf("%d", &child);
      T[child].p = id;
      if(j == 0) T[id].l = child; //idの一番左の子 (the most left child of id)
      else T[sib].r = child; //左の兄弟に繋げる (connect to left sibling)
      sib = child;//次の子供の左の兄弟 (the left sibling of the next child)
    }
  }

  //根を求める (find the root)
  for(i=0; i<n; i++){
    if(T[i].p == -1) root = i;
  }

  //それぞれのノードの深さを求める (find depth of each node)
  calcDepth(root, 0);

  //出力 (output)
  for(i=0; i<n; i++) print(i);

  return 0;
}


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

int main() {
    int N;
    cin >> N;
    int ans = 0;
    rep(i, N) {
        int tmp = i + 1;
        int digits = 0;
        while (tmp > 0) {
            tmp /= 10;
            digits += 1;
        }
        if (digits % 2 == 1) {
            ans += 1;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

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

        Integer[] A = new Integer[N];
        Integer[] B = new Integer[N];

        for(int i = 0; i < N; i++){
            A[i] = scan.nextInt();
            B[i] = scan.nextInt();
        }

        Integer[] idx = new Integer[N];
        Arrays.setAll(idx, i -> i);
        Arrays.sort(idx, Comparator.comparingInt(i -> A[i]));

        long count = 0, sum = 0;
        for(int i = 0; i < N; i++){
            count += B[idx[i]];
            sum += (long)A[idx[i]] * B[idx[i]];
            if(count > M){
                sum -= (long)(count - M) * A[idx[i]];
                break;
            }
        }

        System.out.println(sum);
    }
}

Measured memory_bytes: 93456
#include<cstdio>
int n,x[210];
struct edge{int to,cap;edge*rev,*next;}E[40010],*ne=E,*fir[210],*cur[210];
void link(int a,int b,int c){
	*ne=(edge){b,c,ne+1,fir[a]};fir[a]=ne++;
	*ne=(edge){a,0,ne-1,fir[b]};fir[b]=ne++;
}
int Q[210],D[210];
int dfs(int i,int c){
	if(i==1||!c)return c;
	int fl=0,f;
	for(edge*&e=cur[i];e&&c;e=e->next)
		if(e->cap&&D[e->to]==D[i]-1&&(f=dfs(e->to,c<e->cap?c:e->cap)))
			fl+=f,e->cap-=f,e->rev->cap+=f,c-=f;
	return fl;
}
int mf(){
	for(int f=0;;f+=dfs(0,1<<30)){
		for(int i=0;i<=n+1;i++)D[i]=0,cur[i]=fir[i];
		for(int*h=Q,*t=Q+(D[*Q=1]=1);h<t;h++)
			for(edge*e=fir[*h];e;e=e->next)
				if(e->rev->cap&&!D[e->to])D[*t++=e->to]=D[*h]+1;
		if(!*D)return f;
	}
}
int pr[10000010],pc;
bool com[10000010];
int dif(int x,int y){return x>y?x-y:y-x;}
int main(){
	int N;scanf("%d",&N);
	while(N--){
		int v;scanf("%d",&v);
		if(n&&x[n-1]+1==v)++x[n-1];
		else x[n++]=v-1,x[n++]=v;
	}
	com[1]=1;
	for(int i=2;i<=x[n-1];i++){
		if(!com[i])pr[pc++]=i;
		for(int j=0;j<pc&&i*pr[j]<=x[n-1];j++){
			com[i*pr[j]]=1;
			if(i%pr[j]==0)break;
		}
	}
	int lc=0,rc=0;
	for(int i=0;i<n;i++){
		if(x[i]&1)link(i+2,1,1),rc++;
		else{
			link(0,i+2,1),lc++;
			for(int j=0;j<n;j++)if((x[j]&1)&&!com[dif(x[i],x[j])])link(i+2,j+2,1);
		}
	}
	int s=mf();
	lc-=s;rc-=s;
	printf("%d\n",s+lc/2*2+rc/2*2+lc%2*3);
}

Measured memory_bytes: 16640
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
ll gcd(ll a, ll b);
int main(){
cin.tie(0);
ll n,temp_x,temp_y,x_diff,y_diff,result;
cin>>n;
vector<ll> x,y;
for(ll i=0;i<n;i++){
    cin>>temp_x>>temp_y;
  //cout<<temp_x+temp_y<<endl;
    x.push_back(temp_x-temp_y);
    y.push_back(temp_x+temp_y);
}

sort(x.begin(),x.end());
sort(y.begin(),y.end());

 // cout<<y[0]<<endl;
  //cout<<y[n-1]<<endl;
 // cout<<x[0]<<endl;
 // cout<<x[n-1]<<endl;
x_diff=x[n-1]-x[0];
y_diff=y[n-1]-y[0];
  //cout<<*y.begin()<<endl;
  //cout<<*y.end()<<endl;
result=max(x_diff,y_diff);
if(result<0)result*=-1;
cout<<result;
return 0;
}






ll gcd(ll a, ll b){

   if (a%b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a%b));
   }

}

Measured memory_bytes: 6576
#!/usr/bin/env python3
import sys


def solve(N: int, M: int, H: "List[int]", A: "List[int]", B: "List[int]"):
    ok = [True]*N

    for i in range(M):
        if H[A[i]-1]< H[B[i]-1]:
            ok[A[i]-1] = False
        elif H[A[i]-1]> H[B[i]-1]:
            ok[B[i]-1] = False
        else:
            ok[A[i]-1] = False
            ok[B[i]-1] = False
    
    answer = 0
    for i in range(N):
        if ok[i]:
            answer += 1
    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    H = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, H, A, B)

if __name__ == '__main__':
    main()


Measured memory_bytes: 22776
import java.util.*;
import java.util.Map.Entry;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        TreeMap<String, Integer> map = new TreeMap<String, Integer>();
        for (int i=0;i<N;i++) {
            String S = sc.next();
            if (map.containsKey(S)) {
                map.put(S, map.get(S)+1);
            } else {
                map.put(S, 1);
            }
        }
        ArrayList<Entry<String, Integer>> list = new ArrayList<Entry<String, Integer>>(map.entrySet());

        Collections.sort(list, (o1, o2)->Integer.compare(o2.getValue(), o1.getValue()));
        // System.out.println(list);

        int max = list.get(0).getValue();
        for (Entry<String, Integer> entry : list) {
            if (entry.getValue()==max) {
                System.out.println(entry.getKey());
            } else {
                break;
            }
        }
    }
}

Measured memory_bytes: 86004
N = int(input())
S = []
for i in range(N):
    s = str(input())
    S.append(s)
    
count_AB = 0
for s in S:
    count_AB += s.count("AB")
# print(count_AB)

count_BA = 0
count_A = 0
count_B = 0
for s in S:
    if s[0] == 'B' and s[-1] == 'A':
        count_BA += 1
    if s[0] != 'B' and s[-1] == 'A':
        count_A += 1
    if s[0] == 'B' and s[-1] != 'A':
        count_B += 1
# print(count_BA, count_A, count_B)

if count_BA >= 1:
    count_AB += count_BA -1
if count_BA >= 1:
    if count_A >= 1:
        count_A -= 1
        count_AB += 1
    if count_B >= 1:
        count_B -= 1
        count_AB += 1
count_AB += min(count_A, count_B)
print(count_AB)

Measured memory_bytes: 3956
n=int(input())
inf=[list(map(int,input().split())) for i in range(n)]
for a,b,c in inf:
    if c>0:
        x,y,h=a,b,c
        break
def hei(a,b):
    return h+abs(a-x)+abs(b-y)
for i in range(101):
    for j in range(101):
        flag=True
        H=hei(i,j)
        # if i==2 and j==2:
        #     print(H)
        for k in range(n):
            # if i==2 and j==2:
            #     print(max(H-abs(inf[k][0]-i)-abs(inf[k][1]-j),0),inf[k][2])
            if max(H-abs(inf[k][0]-i)-abs(inf[k][1]-j),0)!=inf[k][2]:
                flag=False
                break
        if flag:
            print(i,j,H)
            exit()

Measured memory_bytes: 3064
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(){
	string s[110];
	int n, l; cin >> n >> l;
	for (int i = 0; i < n; i++){
		cin >> s[i];
	}
	sort(s, s + n);
	for (int i = 0; i < n; i++){
		cout << s[i];
	}
	cout << endl;
}

Measured memory_bytes: 256
a = input().split()
a = [int(i) for i in a]
count_1 = a[1]
count_2 = 0

while (True):
    if a[0] < a[1]:
        count_2 += 1
        break
    a[0] -= (a[1] * 2 + 1)
    count_2 += 1
    if a[0] < 0 or a[0] == 0:
        break

print(count_2)


Measured memory_bytes: 3060
#!/usr/bin/env python3
import sys
INF = float("inf")


def argmin(a):
    m, n = INF, -1
    for i, v in enumerate(a):
        if m > v:
            m, n = v, i
    return m, n


def solve(N: int, T: int, A: int, H: "List[int]"):
    print(argmin([abs(T-h*0.006-A) for h in H])[1]+1)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    H = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, T, A, H)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

vector<int> people;

// int root(int a) {
//     for (;;) {
//         if (people[a] == a) return a;
//         a = people[a];
//     } 
// }

int root(int a) {
    if (people[a] == a) return a;
    else {
        int r = root(people[a]);
        people[a] = r;
        return r;
    }
}

int main(int argc, char const *argv[])
{
    int n, m;
    cin >> n >> m;
    people = vector<int>(n);

    for (int i = 0; i < n; ++i) people[i] = i;

    vector<bool> flg(n, false);

    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        --a, --b; 
        people[root(b)] = root(a);
    }

    int max = 1;
    unordered_map<int, int> mp;

    for (auto e: people) {
        int tmp = 0;
        int r = root(e);
        auto itr = mp.find(r);

        if (itr == mp.end()) mp[r] = 1;
        else tmp = ++(itr->second);

        if (tmp > max) max = tmp;
    }

    cout << max;
    
    return 0;
}


Measured memory_bytes: 11328
using System;
using System.Linq;

namespace abc147_a
{
    static class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine();
            var a = input.ToIntArray();
            Console.WriteLine($"{(a.Sum() >= 22 ? "bust" : "win")}");
        }

        static int ToInteger(this string s)
        {
            return int.Parse(s);
        }

        static int[] ToIntArray(this string s, char separator = ' ')
        {
            var items = s.Split(separator);
            var ret = new int[items.Length];
            for (int i = 0; i < items.Length; i++)
            {
                ret[i] = items[i].ToInteger();
            }
            return ret;
        }

    }
}


Measured memory_bytes: 13268
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 200005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 +c - '0';
	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
	out(x / 10);
    }
    putchar('0' + x % 10);
}
int64 A,B,C,S;
void Solve() {
    read(A);read(B);read(C);
    S = A + B + C;
    int cnt = 0;
    while(1) {
	
	if((A & 1) || (B & 1) || (C & 1)) {out(cnt);enter;return;}
	if(A == B && B == C) {puts("-1");return;}
	A = (S - A) / 2;
	B = (S - B) / 2;
	C = (S - C) / 2;
	++cnt;
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
}


Measured memory_bytes: 256
/*
	  Author : @evenbao
	  Created : 2020 / 07 / 27
*/

#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

#define pii pair<int , int>
#define mp make_pair
#define fi first
#define se second

const int MN = 3005;
const int mod = 1e9 + 7;
const int Inv2 = (mod + 1) / 2;

int N , Q , Coef;
int a[MN] , dp[MN][MN] , p1[MN] , p2[MN];

template <typename T> inline void chkmax(T &x , T y) { x = max(x , y); }
template <typename T> inline void chkmin(T &x , T y) { x = min(x , y); }
template <typename T> inline void read(T &x) {
    T f = 1; x = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0';
    x *= f;
}

inline void inc(int &x , int y) {
		x = x + y < mod ? x + y : x + y - mod;
}
inline void dec(int &x , int y) {
		x = x - y >= 0 ? x - y : x - y + mod;
}

int main() {
		
		read(N); read(Q); Coef = 1;
		for (int i = 1; i <= N; ++i) read(a[i]);
		for (int i = 1; i <= Q; ++i) {
				read(p1[i]) , read(p2[i]);
				if (p1[i] > p2[i]) swap(p1[i] , p2[i]);
		}
		for (int i = 1; i <= N; ++i)
				for (int j = 1; j <= N; ++j)
						dp[i][j] = a[i] > a[j];
		for (int i = 1; i <= Q; ++i) {
				static int tmp[MN][MN];
				for (int x = 1; x <= N; ++x)
						if (x != p1[i] && x != p2[i]) {
								tmp[x][p1[i]] = (LL) Inv2 * (dp[x][p1[i]] + dp[x][p2[i]]) % mod;
								tmp[p1[i]][x] = (LL) Inv2 * (dp[p1[i]][x] + dp[p2[i]][x]) % mod;
								tmp[x][p2[i]] = (LL) Inv2 * (dp[x][p2[i]] + dp[x][p1[i]]) % mod;
								tmp[p2[i]][x] = (LL) Inv2 * (dp[p2[i]][x] + dp[p1[i]][x]) % mod;
						}
				for (int x = 1; x <= N; ++x) 
						if (x != p1[i] && x != p2[i]) {
								dp[x][p1[i]] = tmp[x][p1[i]];
								dp[p1[i]][x] = tmp[p1[i]][x];
								dp[x][p2[i]] = tmp[x][p2[i]];
								dp[p2[i]][x] = tmp[p2[i]][x];
						}
				dp[p1[i]][p2[i]] = dp[p2[i]][p1[i]] = (LL) Inv2 * (dp[p1[i]][p2[i]] + dp[p2[i]][p1[i]]) % mod;
				Coef = 2LL * Coef % mod;
		}
		int ans = 0;
		for (int x = 1; x < N; ++x)
				for (int y = x + 1; y <= N; ++y)
						inc(ans , dp[x][y]);
		printf("%d\n" , (LL) ans * Coef % mod);
	  return 0;
}



Measured memory_bytes: 74212
// Author: πα

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

#define FastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define long int64_t

const int N = 105, M = 1e5 + 5;
long dp[N][M], v[N], w[N];

int main()
{
    FastIO;
    int n, i, j, m;
    cin >> n >> m;
    for(i = 1; i <= n; ++i)
        cin >> w[i] >> v[i];
    for(i = 1; i <= n; ++i)
        for(j = 0; j <= m; ++j)
            dp[i][j] = max((j >= w[i] ? dp[i-1][j-w[i]]+v[i] : 0), dp[i-1][j]);    
    cout << dp[n][m] << endl;
    return 0;
}


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

const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e18)
#define PI (acos(-1))
#define EPS (1e-7)

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

using Edge = pair<int, ll>;

int main(){
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    --s; --t;
    vector<vector<Edge>> g1(n), g2(n);
    rep(i, m) {
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        --u; --v;
        g1[u].emplace_back(v, a);
        g1[v].emplace_back(u, a);
        g2[u].emplace_back(v, b);
        g2[v].emplace_back(u, b);
    }
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q1, q2;
    vll dist1(n, INF), dist2(n, INF);
    q1.emplace(0, s);
    dist1[s] = 0;
    while (!q1.empty()) {
        auto p = q1.top(); q1.pop();
        ll d = p.first; int v = p.second;
        if (d > dist1[v]) continue;
        for (auto to : g1[v]) {
            ll nd = d + to.second; int nv = to.first;
            if (nd >= dist1[nv]) continue;
            q1.emplace(nd, nv);
            dist1[nv] = nd;
        }
    }
    q2.emplace(0, t);
    dist2[t] = 0;
    while (!q2.empty()) {
        auto p = q2.top(); q2.pop();
        ll d = p.first; int v = p.second;
        if (d > dist2[v]) continue;
        for (auto to : g2[v]) {
            ll nd = d + to.second; int nv = to.first;
            if (nd >= dist2[nv]) continue;
            q2.emplace(nd, nv);
            dist2[nv] = nd;
        }
    }
    vll ans(n, 0);
    ll cost = INF;
    repr(i, n) {
        cost = min(cost, dist1[i]+dist2[i]);
        ans[i] = (ll)(1e15) - cost;
    }
    rep(i, n) cout << ans[i] << endl;
    return 0;
}


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

using namespace std;

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

    int n, k;
    cin >> n >> k;
    int ret = 0;
    for (int i = 0; i < n; ++i) {
        int h;
        cin >> h;
        ret += h >= k;
    }
    cout << ret << '\n';

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <numeric>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rep1(i,n) for (int i = 1; i <= n; ++i)
template<typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> inline T intceil(T a, T b) { return (a + (b - 1)) / b; }
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
const long long MOD = 1e9+7;
#define precout(val) cout << std::fixed << std::setprecision(20) << val;
const string alphabet = "abcdefghijklmnopqrstuvwxyz";
const int dy[4] = { 0, 1, 0, -1 };
const int dx[4] = { 1, 0, -1, 0 };
static const double pi = 3.141592653589793;

const int mod = 998244353;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

// combination mod prime
// https://www.youtube.com/watch?v=8uowVvQ_-Mo&feature=youtu.be&t=1619
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};

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

  int n,m,k; cin >> n >> m >> k;
  combination comb(200005);

  mint ans = 0;
  mint mm = m;
  rep(i, k + 1) {
    ans += mm * (mm - 1).pow(n - i - 1) * (comb(n - 1, i));
  }

  cout << ans.x << endl;
}


Measured memory_bytes: 6364