akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int M=pow(10,9)+7;
inline ll add(ll a,ll b)
{
	a+=b;
	if(a>M)a-=M;
	return a;
}
int main() {
	
	int n;
	cin>>n;
	vector<vector<bool>> A(n,vector<bool>(n));
	for(int i=0;i<n;i++)
	for(int j=0;j<n;j++)
	{
		int a;
		cin>>a;
		A[i][j]=a;
	}
	vector<ll>dp((1<<n),0);
	dp[0]=1;
		for(int mask=0;mask<(1<<n)-1;mask++)
		{
			int i=__builtin_popcount(mask);
			for(int k=0;k<n;k++)
			{
				if(A[i][k] and  !(mask&(1<<k)) )
				{
					dp[mask^(1<<k)]=add(dp[mask^(1<<k)],dp[mask]);
				}
			}
		}
	printf("%lld\n",dp[(1<<n)-1]);
	
}


Measured memory_bytes: 19528
#include<cstdio>

int n[4],w[4]={0,500,100,50},X,Ans;

void dfs(int x,int sum)
{
	if(x>3&&sum>X) return;
	if(x==3)
	{
		if(sum==X) Ans++;
		return;
	}
	for(int i=0;i<=n[x+1];i++)
		dfs(x+1,sum+i*w[x+1]);
}

int main()
{
	scanf("%d%d%d%d",&n[1],&n[2],&n[3],&X);
	dfs(0,0);
	printf("%d",Ans);
	getchar();
	getchar();
}

Measured memory_bytes: 128
// Snippets
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

macro_rules! stdin {
    () => ({
        use std::io::Read;
        let mut s = String::new();
        std::io::stdin().read_to_string(&mut s).unwrap();
        s
    })
}

macro_rules! test {
    ($($input:expr => $output:expr),* $(,)*) => (
        #[test]
        fn solve_test() {
            $(
                assert_eq!(solve($input.to_string()), $output);
            )*
        }
    )
}

// End Snippets

fn main() {
    println!("{}", solve(stdin!()));
}

fn solve(src: String) -> String {
    input!{
        source = src,
        s: chars
    }
    let mut ans = 0;
    let is_acgt = |x| x == 'A' || x == 'C' || x == 'G' || x == 'T';
    for i in 0..s.len() {
        let mut partial = 0;
        if is_acgt(s[i]) {
            partial = 1;
            for j in i+1..s.len() {
                if !is_acgt(s[j]) {
                    break;
                }
                partial += 1;
            }
        }
        ans = std::cmp::max(ans, partial);
    }
    ans.to_string()
}

test! {
"ATCODER" => "3",
"HATAGAYA" => "5",
"SHINJUKU" => "0",
}


Measured memory_bytes: 4352
n,k = map(int, input().split())
l = [0]+list(map(int, input().split()))

journey = [1]

for i in range(2*n):
    next = l[journey[-1]]
    journey.append(next)
if k <= n+1:
    print(journey[k])
    exit()

end = n
start = n-1

while journey[start] != journey[end]:
    start -= 1

period = end - start
k %= period

while k < n:
    k += period

print(journey[k])

Measured memory_bytes: 32380
n = int(input())
num = [1, 6, 6**2, 6**3, 6**4, 6**5, 6**6, 9, 9**2, 9**3, 9**4, 9**5]
answer = [0]*(n+1)
for i in range(1, n+1):
    answer[i] = min([answer[i-l]+1 for l in num if i-l>=0])
print(answer[n])

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

using namespace std;

vector<int> list;
int dp[100100];

int pow(int x, int n) {
	if (n == 0) {
		return 1;
	}
	int res = pow(x * x, n / 2);
	if (n & 1) {
		res *= x;
	}
	return res;
}

int f(int n, int x) {
	int res = 0;
	int i = 0;
	while (pow(x, i) <= 100000) {
		i++;
	}
	while (i >= 0 || n > 0) {
		res += n / pow(x, i);
		n %= pow(x, i);
		i--;
	}
	return res;
}

int main() {
	int N;
	cin >> N;
	/*
	int sum = 1 << 30;
	for (int i = 0; i <= N; i++) {
		sum = min(sum, f(i, 6) + f(N - i, 9));
	}
	cout << sum << endl;
	*/
	int i = 0;
	int a = 0;
	while ((a = pow(6, i)) <= 100000) {
		list.push_back(a);
		i++;
	}
	i = 1;
	while ((a = pow(9, i)) <= 100000) {
		list.push_back(a);
		i++;
	}
	sort(list.begin(), list.end());

	dp[0] = 0;
	for (int i = 1; i <= N; i++) {
		int mi = 1 << 30;
		for (int x : list) {
			if (i - x >= 0) {
				mi = min(mi, dp[i - x] + 1);
			}
		}
		dp[i] = mi;
	}
	cout << dp[N] << endl;
	//system("pause");
}

Measured memory_bytes: 640
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;

#define LL long long

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	return x*f;
}
const int INF=9999999;
const int MAXN=100000;

int A[MAXN+1],B[MAXN+1];
int N; LL cnta,cntb;

int main(){
    N=read();
    for(int i=1;i<=N;i++) A[i]=read();
    for(int i=1;i<=N;i++) B[i]=read();
    for(int i=1;i<=N;i++){
    	if(A[i]==B[i]) continue;
		if(A[i]<B[i]) cnta+=(B[i]-A[i])/2;
		else cntb+=(A[i]-B[i]);
	}
	if(cntb>cnta){
		puts("No"); return 0;
	}
	puts("Yes");
	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define Speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;

#define st              first
#define nd              second
#define pb              push_back
#define pf              push_front
#define all(a)          (a).begin(), (a).end()
#define lwb             lower_bound
#define upb             upper_bound
#define vvll            vector<vector<ll> >
#define Mset(s, n)      memset(s, n, sizeof(s))
#define Sz(a)           int((a).size())
#define Max(a, b, c)    max(max((ll)(a), (ll)(b)), (ll)(c))
#define Min(a, b, c)    min(min((ll)(a), (ll)(b)), (ll)(c))
#define Unique(a)       sort(all(a)); (a).resize(unique(all(a)) - (a).begin())

typedef long double ld;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;

const ll MOD = 1e9 + 7;
const int oo = 2e9;
const ld PI = acos((ld) -1);
int Getbit(ll x, int k){return (x >> (k - 1)) & 1;}
ll Lcm(ll a, ll b) {return a / __gcd(a, b) * b;}
bool isPrime(ll n){for(ll i = 2; i * i <= n; i++){if(n % i == 0) return 0;} return (n > 1) ? 1 : 0;}
ll Powmod(ll n, ll k, ll p = MOD) {ll r = 1; for(; k; k /= 2, n = n * n % p){if(k & 1) r = r * n % p;} return r;}

const int N = 2e5 + 5;

ll n, m, k;
ll a[N];

void Solve(){
    cin >> n;
    int res = 0;
    ll mn = 2e9;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        if(a[i] < mn) res++;
        mn = min(mn, a[i]);
    }
    cout << res;
}

int main(){
    Speed;
    int query = 1;
//    cin >> query;
    while(query--) Solve();
}


Measured memory_bytes: 1792
#include <stdio.h>

int main(void) {
	int n, i;
	int a[50];

	scanf("%d", &n);

	a[0] = 1;
	a[1] = 1;

	for (i = 2; i < n + 1; i++) {
		a[i] = a[i - 1] + a[i - 2];
	}

	printf("%d\n", a[n]);
	return 0;
}



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

int main() {
  ll N,MOD = 1000000007,sum=0,ans=0;
  cin >> N;
  vector<ll> A(N);
  rep(i,N) {
    cin >> A[i];
    sum+=A[i];
    sum=sum%MOD;
  }
  
  for(int i=0;i<N-1;i++){
    sum = (sum-A[i])%MOD;
    if(sum<0) sum = sum+MOD;
    ans += sum*A[i]%MOD;
    ans = ans%MOD;
    //cout << ans << endl;
  }
  
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 4832
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

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

        scanner.nextLine();

        long ans = 0;
        HashMap<String, Integer> map = new HashMap<>();
        for(int i = 0; i < N; i++) {
            String line = scanner.nextLine();
            char[] c = line.toCharArray();
            Arrays.sort(c);
            String sortedLine = new String(c);

            if(map.containsKey(sortedLine)) {
                ans += map.get(sortedLine);
                map.put(sortedLine, map.get(sortedLine) + 1);
            } else {
                map.put(sortedLine, 1);
            }
        }

        System.out.println(ans);

        scanner.close();
    }
}

Measured memory_bytes: 105248
/////////////////////////////////////////////////
//                                             //
//                 _ooOoo_                     //
//                o8888888o                    //
//                88" . "88                    //
//                (| -_- |)                    //
//             ____/`---'\\____                //
//           .'  \|     |//  `.                //
//           /  \|||  :  |||// \               //
//          /  _||||| -:- |||||- \             //
//          |   | \\  -  /// |   |             //
//          | \_|  ''\---/''  |  |             //
//          \  .-\__  `-`  ___/-. /            //
//         ___`. .'  /--.--\  `. . __          //
//      ."" '<  `.___\_<|>_/___.'  >'"".       //
//     | | :  `- \`.;`\ _ /`;.`/ - ` : | |     //
//     \  \ `-.   \_ __\ /__ _/   .-` /  /     //
//=====`-.____`-.___\_____/___.-`____.-'=======//
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^//
//.............................................//
/////////////////////////////////////////////////

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll modn=998244353;
const ll INF = 0x3f3f3f3f;
char str[10001000];
int main(){
    int n;
    scanf("%d",&n);
    scanf("%s",str);
    if(n%2==0 && strncmp(str,str+n/2,n/2)==0)
        printf("Yes\n");
    else
        printf("No\n" );
    return 0;
}
/*
5
1 2 3 4 5
5 3 2 1 4
*/


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vin=vector<int>;
using vll=vector<long long>;
using vdo=vector<double>;
using vvin=vector<vector<int>>;
using vvll=vector<vector<long long>>;
using vvdo=vector<vector<double>>;
using vstr=vector<string>;
using vvstr=vector<vector<string>>;
using pqin=priority_queue<int>;
using pqsin=priority_queue<int,vector<int>,greater<int>>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,s,n) for(int i=(s);i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define decp(n) cout<<fixed<<setprecision((int)n)
#define _GLIBCXX_DEBUG
int main()
{
    string s;
    cin>>s;
    int a,b,c,d;
    a=s[0]-'0';
    b=s[1]-'0';
    c=s[2]-'0';
    d=s[3]-'0';
    vin x(3);
    bool can=false;
    rep(i,1<<3){
        bitset<3> e(i);
        int sum=0;
        if(e.test(0))sum+=b;
        else sum-=b;
        if(e.test(1))sum+=c;
        else sum-=c;
        if(e.test(2))sum+=d;
        else sum-=d;
        if(sum==7-a){
            can=true;
            x[0]=e[0];
            x[1]=e[1];
            x[2]=e[2];
            break;
        }
    }
    if(can){
        cout<<a;
        if(x[0]==1)cout<<'+';
        else cout<<'-';
        cout<<b;
        if(x[1]==1)cout<<'+';
        else cout<<'-';
        cout<<c;
        if(x[2]==1)cout<<'+';
        else cout<<'-';
        cout<<d<<'='<<7<<endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <set>
#include <string>
using namespace std;

int main(){
    int a,b,c,d;
    cin >> a >> b >> c >> d;

    int ans = min(a,b) + min(c,d);
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
 
int main(void) {
 
	// ??°????????\???????????°?????????
	int num;
	scanf("%d", &num);
	int sequence[num];
 
	// ??\?????????????¨???????????????\??????
	for(int cnt = 0; cnt < num; cnt++) {
		
		scanf("%d", &sequence[cnt]);
		
	}
	
	// ????°????????????§??????????¨??????\???????????°
	int min = sequence[0];
	int max = sequence[0];
	long sum = 0;
	
	// ????°????????????§??????????¨?????¨????
	for(int cnt = 0; cnt < num; cnt++) {
		
		if(min >= sequence[cnt]) {
			
			min = sequence[cnt];
		}
	
		if(max <= sequence[cnt]) {
			
			max = sequence[cnt];
		}
		
		sum += sequence[cnt];
	
	}
	
	// ???????????????
	printf("%d %d %ld\n", min, max, sum);
	
 	return 0;
}

Measured memory_bytes: 1884
from collections import deque
n = int(input())

que = deque()
for _ in range(n):
    cmd = input()

    if cmd == 'deleteFirst':
        try:
            que.popleft()
        except:
            pass
    elif cmd == 'deleteLast':
        try:
            que.pop()
        except:
            pass
    else:
        cmd, x = cmd.split()
        if cmd == 'insert':
            que.appendleft(x)
        elif cmd == 'delete':
            try:
                que.remove(x)
            except:
                pass

print(*que)


Measured memory_bytes: 69736
import java.lang.*;
import java.io.*;
import java.util.*;


public class Main {

	public static void main(String[] args) throws java.lang.Exception {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskA solver = new TaskA();
		solver.solve(in, out);
		out.close();
	}
}

class TaskA {

	public void solve(InputReader in, PrintWriter out) {
		int a = in.nextInt(), b = in.nextInt();
		int c = comp(a, b);

		if (c == 0)
			out.println("Draw");
		else if (c > 0)
			out.println("Alice");
		else
			out.println("Bob");
	}

	private int comp(int a, int b) {
		if (a == b) return 0;
		if (a == 1) return 1;
		if (b == 1) return -1;
		return a-b;
	}
}

class InputReader {
	public BufferedReader reader;
	public StringTokenizer tokenizer;

	public InputReader(InputStream stream) {
		reader = new BufferedReader(new InputStreamReader(stream), 32768);
		tokenizer = null;
	}

	public String next() {
		while (tokenizer==null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(reader.readLine());
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public long nextLong() {
		return Long.parseLong(next());
	}
}


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

using namespace std;

using ll = long long;

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

    int a, b;

    cin >> a >> b;
    if (a <= 8 && b <= 8) cout << "Yay!\n";
    else cout << ":(\n";

    return 0;
}


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

int main() {
    const int MAX = 50100;
    bool isPrime[MAX];
    fill_n(isPrime, MAX, true);
    for (int i = 4; i < MAX; i += 2) {
        isPrime[i] = false;
    }
    for (int i = 3; i * i <= MAX; i += 2) {
        if (isPrime[i]) {
            for (int j = 2 * i; j < MAX; j += i) {
                isPrime[j] = false;
            }
        }
    }
    int n;
    while (cin >> n) {
        for (int i = n - 1; ; i--) {
            if (isPrime[i]) {
                cout << i << " ";
                break;
            }
        }
        for (int i = n + 1; ; i++) {
            if (isPrime[i]) {
                cout << i << endl;
                break;
            }
        }
    }
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <algorithm>
#include <utility>
#include <functional>
#include <queue>
#include <cmath>
#include <numeric>
#include <map>
#define REP(i, N) for(int i=0; i<N; i++)
using namespace std;

int gcd(int a, int b) {
	return b ? gcd(b, a % b) : a;
}

int main() {
	int A;

	cin >> A;

	cout << A *A *3 << endl;

	return 0;
}


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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a, b, c;
    cin >> a >> b >> c;
    string res = "NO";
    for (int i = 0; i < b; i++) {
        if (a * i % b == c) {
            res = "YES";
            break;
        }
    }
    cout << res << "\n";
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <set>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int main()
{
	
	int N; cin >> N;
	vector<int> A(N * 3);
	for (int i = 0; i < A.size(); ++i) {
		cin >> A[i];
	}
	sort(A.begin(), A.end(), greater<int>());

	ll sum = 0;
	for (int i = 0; i < N; ++i) {
		sum += A[i * 2 + 1];
	}
	cout << sum << endl;
}

Measured memory_bytes: 3920
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

struct node
{
    int l;
    int r;
}num[110];

int n,clen,cal,ans,flag;
char c[110];

bool cmp(node a,node b)
{
    if(a.l<=a.r)
    {
        if(b.l<=b.r)return a.l<b.l;
        else return 1;
    }
    else
    {
        if(b.l<=b.r)return 0;
        else return a.r>b.r;
    }
}

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%s",c);
        clen=strlen(c);
        cal=0;
        for(int j=0;j<clen;j++)
        {
            if(c[j]=='(')cal++;
            else
            {
                cal--;
                if(cal<0){num[i].l++;cal=0;}
            }
        }
        cal=0;
        for(int j=clen-1;j>=0;j--)
        {
            if(c[j]==')')cal++;
            else
            {
                cal--;
                if(cal<0){num[i].r++;cal=0;}
            }
        }
    }
    sort(num,num+n,cmp);
    for(int i=0;i<n;i++)
    {
        ans=ans-num[i].l;
        if(ans<0)
        {
            flag=1;
            break;
        }
        ans=ans+num[i].r;
    }
    if(ans!=0 || flag==1)printf("No\n");
    else printf("Yes\n");
    return 0;
}

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

int main(){
  int h,w;
  cin>>h>>w;
  string bo[h];
  const int dx[8]={1,0,-1,0,1,-1,-1,1};
  const int dy[8]={0,1,0,-1,1,1,-1,-1};
  for (int i=0;i<h;i++) cin>>bo[i];
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(bo[i][j]=='#') continue;
      int sum=0;
      for(int k=0;k<8;k++){
        const int ni=i+dx[k];
        const int nj=j+dy[k];
        if(ni<0||ni>=h) continue;
        if(nj<0||nj>=w) continue;
        if(bo[ni][nj]=='#') sum++;
      }
      bo[i][j]=char(sum+'0');
    }
  }
  for (int i=0;i<h;i++) cout<<bo[i]<<endl;
}

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

class Program
{
    static void Main(string[] args)
    {
        if(ConsoleUtil.IntReadLine() < 1200)
        {
            Console.WriteLine("ABC");
        }
        else
        {
            Console.WriteLine("ARC");
        }
    }
}

static class MathUtil
{
    static IEnumerable<int> EnumeratePrimeNumbers()
    {
        List<int> primes = new List<int>() { 2 };
        yield return 2;

        for (int i = 3; i < int.MaxValue; i++)
        {
            bool isPrime = true;
            int Sqrt = (int)Math.Sqrt(i) + 1;

            foreach (var prime in primes)
            {
                if (prime > Sqrt)
                {
                    break;
                }
                if (i % prime == 0)
                {
                    isPrime = false;
                    break;
                }
            }

            if (isPrime)
            {
                primes.Add(i);
                yield return i;
            }
        }
    }
}

static class ConsoleUtil
{
    public static string[] StrArrayReadLine(char sepalator)
    {
        string str = Console.ReadLine();
        return str.Split(sepalator).ToArray();
    }
    public static string[] StrArrayReadLine()
    {
        string str = Console.ReadLine();
        if (str.Contains(','))
        {
            return str.Split(',').ToArray();
        }
        {
            return str.Split(' ').ToArray();
        }
    }
    public static int[] IntArrayReadLine()
    {
        return StrArrayReadLine().Select(s => int.Parse(s)).ToArray();
    }
    public static int[] IntArrayReadLine(char sepalator)
    {
        return StrArrayReadLine(sepalator).Select(s => int.Parse(s)).ToArray();
    }
    public static int IntReadLine() => int.Parse(Console.ReadLine());
}

Measured memory_bytes: 11092
#include<algorithm>
#include<climits>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<list>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<utility>
#include<vector>
 
#define lint long long
#define VI vector<int>
#define VL vector<lint>
#define VB vector<bool>
#define VC vector<char>
#define VS vector<string>
#define VVI vector<VI>
#define VVL vector<VL>
#define REP(i, x, n) for(int i = x ; i < n ; i++)
#define REPR(i, x, n) for(int i = n - 1 ; i >= x ; i--)
#define rep(i, n) REP(i, 0, n)
#define repr(i, n) REPR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define SORT_INV(c) sort((c).begin(), (c).end(), greater<int>())
#define IINF INT_MAX
#define LLINF LLONG_MAX

using namespace std;

int main(){
    int n;
    cin >> n;
    pair<lint, lint> p = make_pair(0, 0);
    rep(i, n){
        lint t, a;
        cin >> t >> a;
        lint k = max({(p.first+p.second-1)/(t+a)+1, (p.first-1)/t+1, (p.second-1)/a+1});
        p = make_pair(t*k, a*k);
    }
    cout << p.first + p.second << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

// (?????????,??????,??????)
struct edge{ int to,cap,rev; };

const int MAX_V = 202; // TODO:initialize
const int F_INF = 1010101010; // TODO:initialize
vector<edge> G[MAX_V];
int level[MAX_V]; // s??????????????¢
int iter[MAX_V]; // ???????????§??????????????£??????

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

void dinic_bfs(int s){
    memset(level,-1,sizeof(level));
    queue<int> que;
    level[s]=0;
    que.push(s);
    while(!que.empty()){
        int v = que.front();
        que.pop();
        rep(i,G[v].size()){
            edge &e = G[v][i];
            if(e.cap>0 && level[e.to]<0){
                level[e.to] = level[v]+1;
                que.push(e.to);
            }
        }
    }
}

// ?¢?????????????dfs??§??¢???
int dinic_dfs(int v, int t, int f){
    if(v==t) return f;
    for(int &i=iter[v]; i<G[v].size(); ++i){
        edge &e=G[v][i];
        if(e.cap>0 && level[v]<level[e.to]){
            int d = dinic_dfs(e.to,t,min(f,e.cap));
            if(d>0){
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

// s??????t???????????§???
int max_flow(int s, int t){
    int flow = 0;
    while(1){
        dinic_bfs(s);
        if(level[t]<0) return flow;
        memset(iter,0,sizeof(iter));
        int f;
        while((f=dinic_dfs(s,t,F_INF))>0) flow+=f;
    }
}

const int INF = 123456789;

int main()
{
    int n,m,L;
    while(cin >>n >>m >>L)
    {
        rep(i,MAX_V) G[i].clear();

        int d[100][100];
        fill(d[0],d[100],INF);
        rep(i,m)
        {
            int a,b,cost;
            scanf(" %d %d %d", &a, &b, &cost);
            --a;
            --b;
            d[a][b] = d[b][a] = cost;
        }

        rep(i,n) d[i][i]=0;
        rep(k,n)rep(i,n)rep(j,n) d[i][j] = min(d[i][j], d[i][k]+d[k][j]);

        int S = 2*n, T = S+1;
        rep(i,n)
        {
            int p;
            scanf(" %d", &p);
            add_edge(S,i,p);
        }
        rep(i,n)
        {
            int k;
            scanf(" %d", &k);
            add_edge(n+i,T,k);
        }

        rep(i,n)rep(j,n)
        {
            if(d[i][j]<L)
            {
                add_edge(i,n+j,INF);
                add_edge(j,n+i,INF);
            }
        }

        printf("%d\n", max_flow(S,T));
    }
    return 0;
}

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

typedef long long ll;

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

    int n,ans=0,i,j,k;
    cin >> n;
    int a[2][110];
    for(i=0;i<2;i++){
        for(j=0;j<n;j++){
            cin >> a[i][j];
        }
    }
    for(i=0;i<n;i++){
        int sum = 0;
        for(j=0;j<i+1;j++){
            sum += a[0][j];
        }
        for(k=i;k<n;k++){
            sum += a[1][k];
        }
        ans = max(ans,sum);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define rep2(i,a,n) for(int i=(a); i<(n); i++)
#define all(vec) vec.begin(),vec.end()
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
int main() {
  int a, b, h; cin >> a >> b >> h;
  int ans = (a+b)*h/2; 
  cout << ans << endl;
  return 0;
}
  

Measured memory_bytes: 3568
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;
 
const int N = 51;
const int M = 51;
 
int a[N+1];
int b[N+1];
bool vis[111];
 
bool checksingle(int s, int e, vi &vec) //can i get from s to e using only stuff from vec?
{
	memset(vis,0,sizeof(vis));
	queue<int> q;
	vis[s] = 1;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front(); q.pop();
		for(int v:vec)
		{
			if(!vis[u%v])
			{
				vis[u%v] = 1;
				q.push(u%v);
			}
		}
	}
	return vis[e];
}
 
bool check(int n, vi &vec)
{
	for(int i=0;i<n;i++)
	{
		if(!checksingle(a[i], b[i], vec))
		{
			return false;
		}
	}
	return true;
}
 
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n; int m = 0;
	for(int i=0;i<n;i++) {cin>>a[i]; m = max(m, a[i]);}
	for(int i=0;i<n;i++) cin>>b[i];
	ll ans = 0; vi V;
	for(int i = m + 1; i > 0; i--)
	{
		vi ch;
		for(int j = i - 1; j > 0; j--) ch.pb(j);
		for(int v: V) ch.pb(v);
		if(!check(n,ch))
		{
			if(i==m+1){cout<<-1<<'\n'; return 0;}
			ans+=(1LL<<i); V.pb(i);
		}
	}
	cout<<ans<<'\n';
}

Measured memory_bytes: 256
n, k = map(int, input().split())
p = list(map(int, input().split()))

max_mean = 0
for i in range(k):
    max_mean += 0.5 * (p[i] + 1)

cur = max_mean
for l in range(k, n):
    cur += 0.5 * (p[l] - p[l-k])
    max_mean = max(max_mean, cur)

print(max_mean)


Measured memory_bytes: 25060
s = input()
length = len(s)

# 場合の数 2^(l-1)

# bit全探索
# https://drken1215.hatenablog.com/entry/2019/12/14/171657
# https://qiita.com/gogotealove/items/11f9e83218926211083a

ans = 0
for bit in range(1<<(length-1)):  # for bit in range(2 ** (length-1)):
  # print(bin(bit))
  p = []
  f = s[0]
  sub_ans = 0
  for i in range(length-1):
    if bit & (1 << i):   # if ((bit >> i) & 1):
      p.append(i)
      f += "+"
    f += s[i + 1]
  sub_ans = sum(map(int, f.split("+")))
  ans += sub_ans
  # print('sub',p,sub_ans)
print(ans)
      
      

  

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		
		String s = in.next();
		
		if(s.endsWith("s")) {
			System.out.println(s+""+"es");
		}
		else {
			System.out.println(s+""+"s");
		}

	}

}


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

int main(){
  int n;
  cin >> n;
  vector<P> jobs;
  rep(i,n) {
    int a, b;
    cin >> a >> b;
    jobs.emplace_back(make_pair(b, a));
  }
  bool ok = true;
  ll cnt = 0;
  sort(jobs.begin(), jobs.end());
  for (int i = 0; i < n; i++) {
    cnt += jobs[i].second;
    ok &= (cnt <= jobs[i].first);
  }
  if (ok) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3444
# Your code here!


n = gets.to_i

arr = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
arr2 = Array.new(15,0)

i = 1
n.times{
    key = i
    
    s = 0
    15.times{
        
        
        loop{
            if key%arr[s] == 0
                key/=arr[s]
                arr2[s]+=1
                
            else
                break
            end
        }
        
        
       s+=1 
    }
    
    
    i+=1
}



answer = 0

if arr2[0]>=74
    answer+=1
end

count14 = 0
count4 = 0
count24 = 0
count2 = 0

k = 0
15.times{
    
   if arr2[k]>=24
       count24+=1
   end
   
   if arr2[k]>=14
       count14+=1
   end
   
   if arr2[k]>=2 
       count2+=1
   end
   
   if arr2[k]>=4
       count4+=1
   end

    
  k+=1
}



answer+=count14*(count14-1)+count14*(count4-count14)

answer+=count24*(count24-1)+count24*(count2-count24)


answer+=count4*(count4-1)*(count4-2)/2
answer+=count4*(count4-1)*(count2-count4)/2


p answer



Measured memory_bytes: 1788
N = int(input())
x = [0]*N
y = [0]*N
h = [0]*N
for i in range(N):
    x[i],y[i],h[i] = map(int,input().split())

import sys

for cx in range(0,101):
    for cy in range(0,101):
        H = [0]*N
        for i in range(N):
            H[i] = h[i] + abs(x[i]-cx) + abs(y[i]-cy)
        for i in range(N):
            if h[i] == 0:
                H[i] = min(H)
        if max(H) == min(H):
            print(cx,cy,max(H))
            sys.exit()

Measured memory_bytes: 3064
#include <bits/stdc++.h>//Carefully Crafted by hetp111
using namespace std;
#define int long long
#define double long double
#define all(v) (v).begin(),(v).end()
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vii vector<pii>
#define MOD 1000000007
#define eps 1e-8
#define FASTER ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
template<class A,class B>ostream&operator<<(ostream&out,const pair<A,B>&a){return out<<"("<<a.first<<","<<a.second<<")";}
template<class A>ostream&operator<<(ostream&out,const vector<A>&a){for(const A &it:a)out<<it<<" ";return out;}
template<class A,class B>istream&operator>>(istream&in,pair<A,B>&a){return in>>a.first>>a.second;}
template<class A>istream&operator>>(istream&in,vector<A>&a){for(A &i:a)in>>i;return in;}
//ifstream cinn("input.txt");ofstream coutt("output.txt");

signed main(){
    FASTER;
    int n;cin>>n;
    vi v(n);cin>>v;
    sort(all(v));
    int cnt=0;
    for(int i=n-1; i>=1;i--){ 
        int l=0,r=i-1;
        while(l<r){
            if(v[l]+v[r]>v[i]){ 
                cnt+=r-l;
                r--;   
            } else l++;
        }
    } 
    cout<<cnt;
    
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
int n,m,val[100100],col[100100],root[100100],tsz,dis[100100];
int dfn[100100],rev[100100],fa[100100],dep[100100],son[100100],top[100100],sz[100100],head[100100],cnt,tot;
struct node{
	int to,next,val,col;
}edge[200100];
void ae(int u,int v,int c,int w){
	edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,edge[cnt].col=c,head[u]=cnt++;
	edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=w,edge[cnt].col=c,head[v]=cnt++;
}
void dfs1(int x,int Fa){
	fa[x]=Fa,dep[x]=dep[Fa]+1,sz[x]=1;
	for(int i=head[x],y;i!=-1;i=edge[i].next){
		if((y=edge[i].to)==fa[x])continue;
		dis[y]=dis[x]+edge[i].val,dfs1(y,x),sz[x]+=sz[y],val[y]=edge[i].val,col[y]=edge[i].col;
		if(sz[son[x]]<sz[y])son[x]=y;
	}
}
void dfs2(int x){
	if(son[x])top[son[x]]=top[x],dfn[son[x]]=++tot,rev[tot]=son[x],dfs2(son[x]);
	for(int i=head[x],y;i!=-1;i=edge[i].next){
		y=edge[i].to;
		if(y==fa[x]||y==son[x])continue;
		top[y]=y,dfn[y]=++tot,rev[tot]=y,dfs2(y);
	}
}
struct SegTree{
	int lson,rson,sum,sz;
	SegTree(){lson=rson=sum=sz=0;}
	friend SegTree operator +(const SegTree &x,const SegTree &y){
		SegTree z;
		z.sum=x.sum+y.sum;
		z.sz=x.sz+y.sz;
		return z;
	}
}seg[20001000];
void modify(int &x,int l,int r,int P,int val){
	if(!x)x=++tsz;
	seg[x].sum+=val,seg[x].sz++;
	if(l==r)return;
	if(mid>=P)modify(seg[x].lson,l,mid,P,val);
	else modify(seg[x].rson,mid+1,r,P,val);
}
SegTree query(int x,int l,int r,int L,int R){
	if(!x)return SegTree();
	if(l>R||r<L)return SegTree();
	if(L<=l&&r<=R)return seg[x];
	return query(seg[x].lson,l,mid,L,R)+query(seg[x].rson,mid+1,r,L,R);
}
int ask(int x,int y,int c,int w){
	int X=x,Y=y;
	SegTree res;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		res=res+query(root[c],1,n,dfn[top[x]],dfn[x]),x=fa[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	if(x!=y)res=res+query(root[c],1,n,dfn[x]+1,dfn[y]);
	return dis[X]+dis[Y]-2*dis[x]+w*res.sz-res.sum;
}
int main(){
	scanf("%d%d",&n,&m),memset(head,-1,sizeof(head));
	for(int i=1,a,b,c,d;i<n;i++)scanf("%d%d%d%d",&a,&b,&c,&d),ae(a,b,c,d);
	dfs1(1,0),dfn[1]=rev[1]=tot=top[1]=1,dfs2(1);
	for(int i=2;i<=n;i++)modify(root[col[i]],1,n,dfn[i],val[i]);
	for(int i=1,a,b,c,d;i<=m;i++)scanf("%d%d%d%d",&a,&b,&c,&d),printf("%d\n",ask(c,d,a,b));
	return 0;
}

Measured memory_bytes: 325760
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
using P = pair<int,int>;
using pq = priority_queue<int>;
typedef long long ll;

int  main()
{
	int n;
	cin >> n;
	vector <long> a(n);
	rep(i, n)
		cin >> a[i];
	vector <long> b(n, 0);
	ll sum = 0;
	long max = a[0];
	int i = 0;
	while (i < n)
	{
		if (max < a[i])
			max = a[i];
		else if (a[i] < max)
			sum += max - a[i];
		i++;
	}
	cout << sum << endl;
	return (0);
}


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

using namespace std;
typedef long long ll;
typedef unsigned long long ull;

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

    bool ok = true;
    for (int i = 1; i < 4; i++) {
        if (s[i] == s[i-1]) ok = false;
    }
    cout << (ok ? "Good" : "Bad") << endl;
}


Measured memory_bytes: 384
N, M = map(int, input().split())
SC = [list(map(int, input().split())) for _ in range(M)]

A = [-1] * N
ok= True
for s, c in SC:
    i = s-1
    if A[i] != -1 and A[i] != c:
        ok = False
        break
    A[i] = c
if N > 1 and A[0]==0:
    ok = False
if ok:
    for i in range(N):
        if A[i] == -1:
            if i == 0 and N != 1:
                A[i] = 1
            else:
                A[i] = 0
if ok:
    print(''.join(map(str, A)))
else:    
    print(-1)

Measured memory_bytes: 3064
n = gets.to_i

cont = 0
ok = false

n.times do |i|
  d1, d2 = gets.split.map(&:to_i)
  if d1 == d2
    cont += 1
  else
    cont = 0
  end

  if cont >= 3
    ok = true
  end
end

puts(ok ? 'Yes' : 'No')


Measured memory_bytes: 14332
var readline = require('readline');
var rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
  terminal: false
});

rl.on('line', function(S){
   var left = {
   SUN: 7, MON: 6, TUE: 5, WED: 4, THU: 3, FRI:2, SAT: 1
  }
 console.log(left[S]);
})


Measured memory_bytes: 11596
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pt;

bool cmp(pt p, pt q) {
  if (p.second == q.second) return p.first > q.first;
  return p.second > q.second;
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
  int n; cin>>n;
  
  vector<pt> red(n), blue(n);
  for (int i=0; i<n; i++) {
    cin>>red[i].first>>red[i].second;
  }
  for (int i=0; i<n; i++) {
    cin>>blue[i].first>>blue[i].second;
  }
  sort(red.begin(),red.end(),cmp);
  sort(blue.begin(), blue.end());
  
  vector<bool> used(n);
  int res = 0;
  
  for (int j=0; j<n; j++) {
    pt p = blue[j];
    for (int i=0; i<n; i++) {
      pt r = red[i];
      if (r.first < p.first && r.second < p.second && !used[i]) {
	res++;
	used[i]=true;
	break;
      }
    }
  }


  cout<<res<<endl;

  return 0;
}


Measured memory_bytes: 256
n, m = map(int, input().split())

min_l = 0
max_l = 10**6

for _ in range(m):
    L, R = map(int, input().split())
    min_l = max(min_l, L)
    max_l = min(max_l, R)

print(max_l - min_l + 1 if max_l - min_l + 1 > 0 else 0)

Measured memory_bytes: 9008
#define _USE_MATH_DEFIMES
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

const int MOD = 1'000'000'007;
const int INF = 1'000'000'000; //1e9
const int NIL = -1;
const long long LINF = 1'000'000'000'000'000'000; // 1e18
const long double EPS = 1E-10;

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







int main(){
    std::string S; std::cin >> S;
    int n(S.length());
    //dp[i][m] := 先頭i桁で余りmの数
    std::vector<std::vector<int>> dp(n+1, std::vector<int>(13, 0));
    dp[0][0] = 1;

    for(int i(0); i < n; ++i){
        int c(S[i] == '?' ? NIL : S[i] - '0');

        for(int j(0); j < 10; ++j){
            if(c != NIL && c != j) continue;

            for(int k = 0; k < 13; ++k){
                (dp[i+1][(k * 10 + j) % 13] += dp[i][k]) %= MOD;
            }
        }

    }

    std::cout << dp[n][5] << std::endl;
    return 0;
}


Measured memory_bytes: 11980
import numpy as np
INF = 10**9

N, M, X = map(int, input().split())
C = [None]*N
A = [None]*N
for i in range(N):
    line = list(map(int, input().split()))
    C[i] = line[0]
    A[i] = np.array(line[1:])

choose = [True, False]

min_price = INF

for s in range(1 << N):
    price = 0
    knowledge = np.zeros(M)
    for i in range(N):
        if s >> i & 1:
            knowledge += A[i]
            price += C[i]
    if np.any(knowledge < X):
        continue
    if min_price == -1:
        min_price = price
    min_price = min(min_price, price)

if min_price == INF:
    print(-1)
else:
    print(min_price)


Measured memory_bytes: 27224
def check(n):
    x = A[n] + M
    if P == 1:
        B = A[:n] + A[n+1:]
    else:
        B = A[:n] + A[n+1:-(P-1)]
    scores = M * (V - P)
    if x < B[-1]:
        return False
    for b in B:
        if b + M <= x:
            scores -= M
        else:
            scores -= x - b
        if scores <= 0:
            return True
    return False


N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

left = 0
right = N - P
while left < right:
    mid = (left+right) // 2
    if check(mid):
        right = mid
    else:
        left = mid + 1
print(N - left)


Measured memory_bytes: 14964
public class Main{
	public static void main(String[] args) {
		for(int i = 1; i <= 9; i++) {
			for(int j = 1; j <= 9; j++) {
				int t = i * j;
				System.out.printf("%dx%d=%d\n", i, j, t);
			}
		}
	}
}


Measured memory_bytes: 24564
N=int(input())
X=list(map(int,input().split()))
def D(x,a):
	ans=0
	for i in range(len(a)):
		ans+=(x-a[i])**2
	return ans
for i in range(0,101):
	if D(i,X)<D(i+1,X):
		print(D(i,X))
		break

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

using namespace std;

typedef long long ll;

const ll MOD = 998244353;
const int MX = 500005;

template<typename T> void cmax(T &x, const T &y)
{
	if(y > x) x = y;
}

template<typename T> void read(T &x)
{
	x = 0;
	char c = getchar();
	bool f = 0;
	while(!isdigit(c) && c!='-') c = getchar();
	if(c == '-') f = 1, c = getchar();
	while(isdigit(c)) x = x*10+c-'0', c = getchar();
	if(f) x = -x;
}

int n, k;
ll fac[MX+5], faci[MX+5];

ll qpow(ll x, ll t)
{
	ll ret = 1;
	while(t)
	{
		if(t & 1) ret = ret * x % MOD;
		x = x * x % MOD;
		t >>= 1;
	}
	return ret;
}

ll inv(ll x)
{
	return qpow(x, MOD-2);
}

void init()
{
	fac[0] = 1;
	for(int i=1; i<=MX; i++) fac[i] = fac[i-1] * i % MOD;
	faci[MX] = inv(fac[MX]);
	for(int i=MX; i>=1; i--) faci[i-1] = faci[i] * i % MOD;
}

ll C(int x, int y)
{
	if(x<0 || y<0 || y>x) return 0;
	return fac[x] * faci[y] % MOD * faci[x-y] % MOD;
}

void work()
{
	read(n), read(k);
	ll ans = 0;
	for(int i=(k+1)/2; i<=k; i++)
	{
		int r = i, b = k-i;
		int t = max(0, n-(r-b));
		if(t*2+(n-t) > k) continue;
		if(t == n) ans = (ans + C(k-1, r) - C(k-1, r+b-t+1) + MOD) % MOD;
		else ans = (ans + C(k, r) - C(k, r+b-t+1) + MOD) % MOD;
	}
	printf("%lld\n", ans);
}

int main()
{
	init();
	work();
	return 0;
}

Measured memory_bytes: 8064
# coding: utf-8

N = int(input())
#H = list(map(int, input().split()))
s = [int(input()) for i in range(N)]
#print(s)
max=0
a=0
for i in range(N):
  if s[i]>max:
    max=s[i]
    a=i

for i in range(N):
  if i==a:
    s.sort()
    s.reverse()
    print(s[1])
  else:
    print(max)
  
  
  

Measured memory_bytes: 69080
fn main() {
    let nm = read_vec::<usize>();
    let n = nm[0];
    let m = nm[1];
    let v = read_vec2::<usize>(m);

    let mut mi = 0;
    let mut ma = 100001;
    for lr in v.iter() {
        let l = lr[0];
        if mi < l { mi = l; }

        let r = lr[1];
        if ma > r { ma = r; }
    }

    let ret = if mi > ma {
        0
    } else if n < mi {
        0
    } else if mi <= n && n < ma {
        n - mi + 1
    } else {
        ma - mi + 1
    };
    println!("{}", ret);
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}

fn read_vec2<T: std::str::FromStr>(n: usize) -> Vec<Vec<T>> {
    let mut v2 = Vec::new();
    for _ in 0..n {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).ok();
        let v = s.trim().split_whitespace().map(|e| e.parse().ok().unwrap()).collect();
        v2.push(v);
    }
    v2
}


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

typedef long long int ll;

int main(){

    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        // freopen("output.txt", "w", stdout);
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    string str1, str2;

    cin >> str1 >> str2;

    int n = str1.length();
    int m = str2.length();

    int dp[n+1][m+1];

    for (int i=0; i<n+1; i++){
        for (int j=0; j<m+1; j++){

            if (i==0 || j==0)
                dp[i][j] = 0;
            else if (str1[i-1]==str2[j-1])
                dp[i][j] = 1 + dp[i-1][j-1]; 
            else
                dp[i][j] = max( dp[i-1][j], dp[i][j-1] ); 

            // cout << dp[i][j] << " ";
        }
        // cout << endl;
    }

    // cout << dp[n][m] << endl;

    int i=n, j=m;
    string result = "";

    while(i>0 && j>0){
        
        if (str1[i-1]==str2[j-1]){
            result += str1[i-1]; 
            i--;
            j--;
        }
        else if ( dp[i-1][j] >  dp[i][j-1]){
            i--;
        }
        else{
            j--;
        }


    }

    reverse(result.begin(), result.end());

    cout << result << endl;

   return 0;
}


Measured memory_bytes: 38672
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		int X = sc.nextInt();
		int Y = sc.nextInt();
		int sum = 0;
		for(int i = 0; i < N; i++) {
			if(i < K) {
				sum += X;
			} else {
				sum += Y;
			}
		}
		System.out.println(sum);
	}
}

Measured memory_bytes: 27020
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int main()
{
	int a[1001];
	cin>>a[1]>>a[2]>>a[3];
	sort(a+1,a+4);
	int sum=a[3]*10+a[2]+a[1];
	cout<<sum;
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <utility>
#include <map>
#include <set>
#include <algorithm>

#define REP(i, a, b) for (int i=a; i <b; i++)
#define F first
#define S second
#define N 16010

using namespace std;

typedef long long ll;
typedef vector< int > vi;

int main() {
    string s;
    int x, y;

    cin >> s;
    cin >> x >> y;

    int xs[N] = {0};
    int ys[N] = {0};

    int num = 0;
    int ind_x = 0, ind_y = 0;
    int value = 0;
    int max = -1;
    REP(i, 0, s.size()) {
        if (s[i] == 'F') {
            value++;
        }
        if (s[i] == 'T') {
            if (num % 2 == 0) {
                xs[ind_x] = value;
                ind_x++;
            } else {
                ys[ind_y] = value;
                ind_y++;
            }
            if (value >= max) {
                max = value;
            }
            num++;
            value = 0;
        }
        if (i == s.size() -1) {
            if (num % 2 == 0) {
                xs[ind_x] = value;
                ind_x++;
            } else {
                ys[ind_y] = value;
                ind_y++;
            }
            if (value >= max) {
                max = value;
            }
            num++;
            value = 0;
        }
     }
    int mid = 8005 + max;
        if (ind_y == 0) {
        ind_y++;
    }
    if (ind_x == 0) {
        ind_x++;
    }

    vector < vector < int > > dpx(ind_x+1), dpy(ind_y+1);

    REP(i, 0, ind_x+1) {
        dpx[i].resize(N+2*max);
    }
    REP(i, 0, ind_y+1) {
        dpy[i].resize(N+2*max);
    }

    for (int i=0; i<ind_x+1; i++) {
        for (int j=0; j<N+2*max; j++) {
            dpx[i][j] =0;
        }
    }

    for (int i=0; i<ind_y+1; i++) {
        for (int j=0; j<N+2*max; j++) {
            dpy[i][j] =0;
        }
    }

    dpx[0][xs[0]+mid] = 1; dpy[0][ys[0]+mid] = 1;
    dpy[0][mid-ys[0]] = 1;
    for (int i=1; i<ind_x; i++) {
        for (int j=0; j< N+2*max; j++) {
            if (dpx[i-1][j- xs[i]] == 1 || dpx[i-1][j+ xs[i]] == 1) {
                dpx[i][j] = 1;
            }
        }
    }

    for (int i=1; i<ind_y; i++) {
        for (int j=0; j< N+2*max; j++) {
            if (dpy[i-1][j- ys[i]] == 1 || dpy[i-1][j+ ys[i]] == 1) {
                dpy[i][j] = 1;
            }
        }
    }
    
    //cout << "ind: " << ind_x << " " << ind_y << "\n";
    //cout << "result: " << dpx[ind_x-1][x+mid] << " " << dpy[ind_y-1][y+mid] << "\n";
    //cout << "aaaaa: " << dpx[0][2] << "\n";
    //cout << "b: " << xs[1] << "\n";
    if (dpx[ind_x-1][x+mid] == 1 && dpy[ind_y-1][y+mid] == 1) {
        cout << "Yes" << '\n';
    } else {
        cout << "No" << '\n';
    }

    return 0;
}


Measured memory_bytes: 497024
#include<bits/stdc++.h>
#define pb push_back 
 #define fo(i,n) for(int i=0;i<n;i++)
#define ll long long 
#define int long long 
#define Mod 10000000000007 
#define maxn 200005
#define MAX 4294967296  // 2^32
const int M=1e9+7;
#define ip pair<int,int>
#define test(t) ll t;cin>>t;while(t--)
  
using namespace std;

long long gcd(int x,int y){
    if(y>x)swap(x,y);
    if(y==0)return x;
    return gcd(y,x%y);
}


void solve(){
vector<pair<int,int>>v;
int n,k;
cin>>n>>k;
int t=n;
for(int i=0;i<k;i++){
    int a,b;
    cin>>a>>b;
    b++;
    v.push_back({a,b});
}
int dp[n+1]={0};
dp[0]=1;
dp[1]=-1;
for(int i=0;i<n;i++){
    if(i>0)dp[i]+=dp[i-1];
        for(int j=0;j<k;j++){
            if(i+v[j].first<n)dp[i+v[j].first]=(dp[i+v[j].first]+dp[i])%998244353;
            if(i+v[j].second<n)dp[i+v[j].second]-=dp[i];
        }


}

cout<<dp[n-1]%998244353;


}

signed main(){


    // std::string binary = std::bitset<8>(n).to_string();
    ios::sync_with_stdio(0);
    cin.tie(0);
   
solve();


  


}

Measured memory_bytes: 5212