akhauriyash/Code-Regression huggingface dataset:
;; -*- coding: utf-8 -*-
(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (ql:quickload '(:cl-debug-print :fiveam))
  #-swank (set-dispatch-macro-character #\# #\> (lambda (s c p) (declare (ignore c p)) (read s nil (values) t))))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)
#-swank (disable-debugger) ; for CS Academy

;; BEGIN_INSERTED_CONTENTS
(defmacro dbg (&rest forms)
  #+swank
  (if (= (length forms) 1)
      `(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
      `(format *error-output* "~A => ~A~%" ',forms `(,,@forms)))
  #-swank (declare (ignore forms)))

(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64)

(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  (let ((*read-default-float-format* 'double-float))
    (prog1 (princ obj stream) (terpri stream))))

(defconstant +mod+ 1000000007)

;; Body

(defun main ()
  (let* ((r (read)))
    (println (* 3 r r))))

#-swank (main)


;; For Test
#+swank
(defun io-equal (in-string out-string &optional (func #'main))
  "Passes IN-STRING to *STANDARD-INPUT*, executes FUNC, and returns true if the
string output to *STANDARD-OUTPUT* is equal to OUT-STRING."
  (labels ((ensure-last-lf (s)
             (if (and (> (length s) 0)
                      (eql (char s (- (length s) 1)) #\Linefeed))
                 s
                 (uiop:strcat s uiop:+lf+))))
    (equal (ensure-last-lf out-string)
           (with-output-to-string (out)
             (let ((*standard-output* out))
               (with-input-from-string (*standard-input* (ensure-last-lf in-string))
                 (funcall func)))))))

#+swank
(defun get-clipbrd ()
  (with-output-to-string (out)
    (run-program "C:/msys64/usr/bin/cat.exe" '("/dev/clipboard") :output out)))

#+swank (defparameter *this-pathname* (uiop:current-lisp-file-pathname))
#+swank (defparameter *dat-pathname* (uiop:merge-pathnames* "test.dat" *this-pathname*))

#+swank
(defun run (&optional thing (out *standard-output*))
  (let ((*standard-output* out))
    (etypecase thing
      (null ; Runs #'MAIN with the string on clipboard
       (with-input-from-string (*standard-input* (delete #\Return (get-clipbrd)))
         (main)))
      (string
       (with-input-from-string (*standard-input* (delete #\Return thing))
         (main)))
      (symbol (5am:run! thing))
      (pathname ; Runs #'MAIN with the string in a text file
       (with-open-file (*standard-input* thing)
         (main))))))

#+swank
(defun gen-dat ()
  (uiop:with-output-file (out *dat-pathname* :if-exists :supersede)
    (format out "")))

#+swank
(defun bench (&optional (out (make-broadcast-stream)))
  (time (run *dat-pathname* out)))


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

int main(){
    string s;cin>>s;
    string alphabet = "abcdefghijklmnopqrstuvwxyz";
    int min_acc = 10000000;
    for (int i=0;i<alphabet.size();i++){
        string copied_s = s;
        auto alph = alphabet[i];
        if (find(s.begin(), s.end(), alph) == s.end()){
            continue;
        }
        int acc = 0;
        while (true){
            bool flag = true;
            for (int i=0;i<copied_s.size();i++){
                if (copied_s[i] != alph){
                    flag = false;
                }
            }
            if (flag){
                break;
            }
            string temp_s = "";
            for (int i=0;i<copied_s.size() - 1;i++){
                if (copied_s[i] == alph || copied_s[i+1] == alph){
                    temp_s += alph;
                } else {
                    temp_s += copied_s[i];
                }
            }
            copied_s = temp_s;
            acc++;
        }
        if (min_acc > acc){
            min_acc = acc;
        }
    }
    cout << min_acc << endl;
    return 0;
}

Measured memory_bytes: 256
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
s,t = input().split()
print(''.join([s[i] + t[i] for i in range(n)]))

Measured memory_bytes: 76604
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1001001001LL;
constexpr long long LINF = 1e18 + 10;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define rept(i, j, n) for(int i=(j); i<(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main(){
    int n; cin >> n;
    multiset<int> mst;
    rep(i, n){
        int a; cin >> a;
        mst.insert(a);
    }
    vector<pii> res;
    while(mst.size()> 2){
        auto iter = mst.begin();iter++;
        int tmp = *iter, hasi;
        if(tmp >= 0){
            hasi = *mst.begin();
        }else{
            hasi = *mst.rbegin();
        }
        res.push_back({hasi, tmp});
        mst.erase(mst.find(hasi));
        mst.erase(mst.find(tmp));
        mst.insert(hasi - tmp);
    }

    int a = *mst.rbegin(), b = *mst.begin();
    res.push_back({a, b});
    cout << a-b << ln;
    for(auto p: res){
        cout << p.first << " " << p.second << ln;
    }
}


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

#define L 1000
  
long long getValue(long long x){
  if ( x <= L ) return x +1;
  else return L - x%(L+1);
}
  
main(){
  int n, t;
  long long cnt;

  while( cin >> n){
    cnt = 0;
    for ( int i = 0; i <= 2*L; i++ ){
      t = n - i;
      if ( 0 <= t && t <= 2*L ){
	cnt += getValue(i) * getValue(t);
      }
    }
    
    cout << cnt << endl;
  }
}

Measured memory_bytes: 1156
N = int(input())
L = []
for i in range(N):
  L.append(list(map(int,input().split())))
for j in range(N):
  if L[j][2] != 0:
    karix = L[j][0]
    kariy = L[j][1]
    karih = L[j][2]
    break
for p in range(0,101):
  for q in range(0,101):
    cnt = 0
    kouhoH = karih+abs(karix-p)+abs(kariy-q)
    for r in range(N):
      if  L[r][2] == max(kouhoH-abs(L[r][0]-p)-abs(L[r][1]-q),0):
        cnt += 1
    if cnt == N:
      print(p,q,kouhoH)
      exit()

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

int main() {
    int x,a,b; cin >> x >> a >> b;
    if(a>=b) cout << "delicious" << endl;
    else {
        if(b-a<=x) cout << "safe" << endl;
        else cout << "dangerous" << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define vl vector<ll>
#define pl pair<ll,ll>
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,b) for(ll i=0;i<b;i++)
#define RFOR(i,a,b) for(ll i=b-1;i>=a;i--)
#define rsort(v) sort((v).rbegin(), (v).rend())
#define all(v) (v).begin(),(v).end()
using namespace std;

signed main() {
    ll n,a,ans=1000000;
    cin>>n;
    vl w;
    rep(i,n){
        cin>>a;
        w.push_back(a);
    }
    rep(i,n-1){
        ll sum=0,sum1=0;
        rep(j,i+1) {
            sum += w[j];
        }
        FOR(j,i+1,n){
            sum1+=w[j];
        }
        ans=min(ans,abs(sum-sum1));
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }
    public void solve() {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        Holder[] holders = new Holder[5];
        for (int i = 0; i < 5; i++) {
            holders[i] = new Holder(scan.nextInt());
        }
        int answer = 0;
        Arrays.sort(holders, new HolderComparator());
        for (int i = 0; i < 4; i++) {
            answer += Math.ceil((double) holders[i].need_time / 10) * 10;
        }
        answer += holders[4].need_time;
        System.out.println(answer);
    }
    class Holder {
        int need_time = 0;
        int remain_time = 0;
        Holder(int x) {
            this.need_time = x;
            if (x % 10 != 0) {
                this.remain_time = x % 10;
            } else {
                this.remain_time = 9;
            }
        }
    }
    class HolderComparator implements Comparator<Holder> {
        @Override
        public int compare(Holder o1, Holder o2) {
            if (o1.remain_time != o2.remain_time) {
                return -Integer.compare(o1.remain_time, o2.remain_time);
            } else {
                return Integer.compare(o1.need_time, o2.need_time);
            }
        }
    }
}


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

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] a = new int[4];
		for(int i = 0; i < 4; i++) {
			a[i] = sc.nextInt();
		}
		Arrays.sort(a);
		if(a[0] == 1 && a[1] == 4 && a[2] == 7 && a[3] == 9) {
			System.out.println("YES");
		}else {
			System.out.println("NO");
		}
	}
}

Measured memory_bytes: 23764
#include <stdio.h>

int main(void) {
	int a,b;
	scanf("%d %d",&a,&b);
	if (a>b) {
		printf("a > b\n");
	} else if (a<b) {
		printf("a < b\n");
	} else {
		printf("a == b\n");
	}
	return 0;
}

Measured memory_bytes: 580
public class Main {
    private static java.util.Scanner scanner = new java.util.Scanner(System.in);

    public static void main(String[] args) {
        long a = scanner.nextLong(), b = scanner.nextLong();
        System.out.println(a == 0 ? f(b) : f(b) ^ f(a - 1));
    }

    static long f(long x) {
        return (x & 1) == 1 ? x / 2 % 2 ^ 1 : x + x / 2 % 2;
    }
}

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

Measured memory_bytes: 256
(function main(){
  const lines = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split('\n');
  const n = Number(lines.shift());
  lines.shift().split(' ').map(Number).forEach(function(key, i, a) {
    console.log(`node ${i+1}: key = ${a[i]}, `+(i?`parent key = ${a[Math.floor((i-1)/2)]}, `:'')+(2*i+1<a.length?`left key = ${a[2*i+1]}, `:'')+(2*i+2<a.length?`right key = ${a[2*i+2]}, `:''));
  });
})();



Measured memory_bytes: 17316
#include<iostream>
#include<math.h>
#include<iomanip>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<stdlib.h>
using namespace std;
#define PI 3.14159265358979
typedef unsigned long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
 

 int main(void)
 {
   ll x;
    int r,d;

    cin>>r>>d>>x;
 

for(int i=1;i<=10;i++)
{
    x= x*r-d;
    cout<<x<<endl;
}


 }

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

#define rep(i, n) for(int i=0; i < (n); ++i)
#define ll long long

const int mod = 1000000007;
//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 { return mint(*this) += a;}
    mint operator-(const mint a) const { return mint(*this) -= a;}
    mint operator*(const mint a) const { return mint(*this) *= 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 { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}


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

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

// 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() {
    int A, B, C;
    cin >> A >> B >> C;

    if (A==B && B==C) {
        cout << "No" << endl;
        return 0;
    }

    if (A!=B && B!=C && C!=A) {
        cout << "No" << endl;
        return 0;
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {
            int N = sc.nextInt();
            int[] A = new int[N];
            for (int i = 0; i < N; i++) {
                A[i] = sc.nextInt();
            }

            long sum = 0;
            for (int i = 1; i < N; i++) {
                int diff = A[i] - A[i - 1];
                sum += diff < 0 ? -diff : 0;
                A[i] = Math.max(A[i] + (diff < 0 ? -diff : 0), A[i - 1]);
            }
            System.out.println(sum);
        }
    }
}


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

int main (void){
  long long int a = 0,b = 0,c = 0,k = 0,z = 0;

  cin >> a >> b >> c >> k;
  if(k <= a){
    cout << k << endl;
  }else if(k <= a + b){
    cout << a << endl;
  }else{
    z = k - a-b;
    z = a - z;
    cout << z << endl;
  }
  return 0;
}

Measured memory_bytes: 3636
#include<iostream>
#include<unordered_map>
#include<bitset>
#include<math.h>
#include<vector>
#include<set>
#include<algorithm>
#include<ctype.h>
#include<unordered_set>
#include<string>
#include<iomanip>
#include<queue>
#include<limits>
#include<map>
#include<stack>
#include<iterator>
#include<cstring>
 
#include<deque>
#define pi 3.141592653589793238
#include<chrono>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define MOD 1000000007
#define INF 999999999999999999 
#define pb insert
#define ff first
#define ss second
 
#define mt make_tuple
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
 
 
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
 
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
bool isborder(ll x, ll y, ll r ,ll c){
    
    if(x == 0){
        return true;
    }
    if(y == 0){
        return true;
    }
    if(x == r - 1){
        return true;
    }
    if(y == c - 1){
        return true;
    }
    return false;
} 
int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    fast;
    ll T = 1, i, j;
    
    //cin >> T;
    while (T--) {
        ll r, c, n;
        cin >> r >> c >> n;
        
       
        r++, c++;
        set<pair<ll,ll>> v[4];
        for(ll it = 1; it <= n; it++){
            ll x1, x2 ,y1, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            
            if(!isborder(x1, y1, r, c) || !isborder(x2, y2, r, c)){
                continue;
            }
            ll x, y;
            x = x1, y = y1;
            
            if(x == 0 && y < c - 1){
                v[0].pb({y, it});
            }
            else if(y == c - 1 && x < r - 1){
                v[1].pb({x, it});
            }
            else if(x == r - 1 && y > 0){
                v[2].pb({-(y) , it});
            }
            else{
                v[3].pb({-x , it});
            }
            x = x2, y = y2;
            if(x == 0 && y < c - 1){
                v[0].pb({y, it});
            }
            else if(y == c - 1 && x < r - 1){
                v[1].pb({x, it});
            }
            else if(x == r - 1 && y > 0){
                v[2].pb({-(y) , it});
            }
            else{
                v[3].pb({-x , it});
            }
        }
        stack<ll> st;
        for(i = 0; i < 4; i++){
            for(auto u : v[i]){
                if(st.empty()){
                    st.push(u.ss);
                    continue;
                }
                if(st.top() == u.ss){
                    st.pop();
                    continue;
                }
                st.push(u.ss);
            }
        }
        if(st.size()){
            cout << "NO";
        }
        else{
            cout << "YES";
        }
    }
    return 0;
}

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

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

const int MOD = 1000000007;

int main() {
    ll w, h, n; cin >> w >> h >> n;

    ll w1 = 0, w2 = 0, h3 = 0, h4 = 0;
    rep (i, n) {
        ll x, y, a; cin >> x >> y >> a;
        if (a == 1) {
            w1 = max(w1, x);
        }
        if (a == 2) {
            w2  = max(w2, w-x);
        }
        if (a == 3) {
            h3 = max(h3, y);
        }
        if (a == 4) {
            h4 = max(h4, h-y);
        }
    }

    if ((w-w1-w2) <= 0 || (h-h3-h4) <= 0) cout << 0 << endl;
    else cout << (w-w1-w2)*(h-h3-h4) << endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <map>
#include <queue>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

#define f first
#define s second
#define mp make_pair

using namespace std;

typedef vector<vector<int> > G;

int flow(G &g, int s, int d){
  int n = g.size();
  int ans = 0;

  while(true){
    vector<int> prevs(n,-1);
    queue<int> q;
    bool ok = false;
    
    prevs[s]=n;
    q.push(s);
    while(!q.empty()){
      int now = q.front();
      q.pop();
      if(now == d){
        ok = true;
        break;
      }
      for(int i=0;i<n;i++){
        if(g[now][i]>0){
          if(prevs[i]==-1){
            prevs[i]=now;
            q.push(i);
          }
        }
      }
    }

    if(!ok) return ans;

    int f = 100000;
    int pos = d;
    while(pos != s){
      int pos2 = prevs[pos];
      f = min(f,g[pos2][pos]);
      pos = pos2;
    }
    pos = d;
    while(pos != s){
      int pos2 = prevs[pos];
      g[pos2][pos]-=f;
      g[pos][pos2]+=f;
      pos = pos2;
    }
    ans += f;
  }
}

map<pair<int,int>, int> id;

int main(){
  int n, m;
  scanf("%d%d", &n, &m);

  vector<vector<int> > g(n, vector<int>(n));

  REP(i,m){
    int a, b;
    scanf("%d%d", &a, &b);
    g[a-1][b-1] = 1;
    g[b-1][a-1] = 1;
    id[make_pair(a-1,b-1)] = i;
  }

  int s, t;
  scanf("%d%d", &s, &t);

  //REP(i,n){REP(j,n) printf("%2d ", g[i][j]); puts("");}

  int ans = flow(g, s-1, t-1);
  vector<int> rev;

  //REP(i,n){REP(j,n) printf("%2d ", g[i][j]); puts("");}

  REP(i,n) REP(j,n) if(g[i][j] == 2){
    if(id.count(make_pair(i,j))) rev.push_back(id[make_pair(i,j)] + 1);
  }
  sort(rev.begin(), rev.end());

  printf("%d\n", ans);
  printf("%d\n", rev.size());
  REP(i,rev.size()) printf("%d\n", rev[i]);

  return 0;
}

Measured memory_bytes: 0
from heapq import heappush,heappop

S = input()
slist = "abcdefghijklmnopqrstuvwxyz"

if S == "zyxwvutsrqponmlkjihgfedcba":
    print(-1)
    exit()

lis =[]
T = S
if len(S)<26:
    Sset = set(S)
    for s in slist:
        if s not in Sset:
            print(S+s)
            exit()
else:
    while len(S)>0:
        lis.append(S[-1])
        lis.sort()
        S = S[:-1]
        for s in lis:
            if S + s > T:
                print(S + s)
                exit()


Measured memory_bytes: 9044
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#define ll long long
#define ull unsigned long long
using namespace std;

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

	ll n, w;
	cin >> n >> w;
	vector<ll> V(n);
	vector<ll> W(n);
	ll totalVal = 0;
	for (ll i = 0; i < n; i++){
		cin >> W.at(i) >> V.at(i);
		totalVal += V.at(i);
	}

	vector<vector<ll>> DP(n, vector<ll>(totalVal + 1, INT32_MAX));
	//DP[i][j] is minimum weight needed to get a value j using weight i
	
	DP.at(0).at(V.at(0)) = W.at(0);
	DP.at(0).at(0) = 0;
	for (int i = 1; i < n; i++){
		DP.at(i).at(0) = 0;
		for (int j = 0; j <= totalVal; j++){
			if (V.at(i) <= j) DP.at(i).at(j) = min(DP.at(i).at(j), DP.at(i - 1).at(j - V.at(i)) + W.at(i));
			DP.at(i).at(j) = min(DP.at(i).at(j), DP.at(i - 1).at(j));

		}
	}

	ll ans = 0;
	for (int i = 0; i <= totalVal; i++){
		if (DP.back().at(i) <= w){
			ans = i;
		}
	}	
	cout << ans;
	return 0;
}


Measured memory_bytes: 79488
#include <iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
 
struct pct {
    int x, y;
};
 
const int MOD = 1000000007;
const int N = 500003;
 
int n, m, c, d[N], fact[N], invfact[N];
pct v[N];
 
int comb(int n, int k) {
    int r = (1LL * fact[n] * invfact[k]) % MOD;
    r = (1LL * r * invfact[n - k]) % MOD;
 
    return r;
}
 
int nr(int p1, int p2, int p3, int p4) {
    int sz1 = p3 - p1, sz2 = p4 - p2;
 
    return comb(sz1 + sz2, sz1);
}
int po(int el, int p) {
    int r = 1;
 
    while(p) {
 
        if(p & 1)
            r = (1LL * r * el) % MOD;
 
        el = (1LL * el * el) % MOD;
        p /= 2;
    }
 
    return r;
}
 
bool cmp(pct a, pct b) {
    if(a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}
 
int main()
{int i, j;
 
    cin >> n >> m >> c;
 
    fact[0] = 1;
    for(i = 1; i < N; ++i)
        fact[i] = (1LL * fact[i - 1] * i) % MOD;
    invfact[N - 1] = po(fact[N - 1], MOD - 2);
    for(i = N - 2; i >= 0; --i) {
 
        invfact[i] = (1LL * invfact[i + 1] * (i+ 1)) % MOD;
    }
 
    for(i = 1; i <= c; ++i) {
 
        cin >> v[i].x >> v[i].y;
 
    }
 
    sort(v+  1, v + c + 1, cmp);
 
    //v[0].x = 1; v[0].y = 1;
    v[c + 1].x = n; v[c + 1].y = m;
 
    for(i = 1; i <= c + 1; ++i) {
 
        d[i] = nr(1, 1, v[i].x, v[i].y);
 
        for(j = 1; j < i; ++j) if(v[j].x <= v[i].x && v[j].y <= v[i].y) {
 
            int aa = (1LL * d[j] * nr(v[j].x, v[j].y, v[i].x, v[i].y)) % MOD;
 
            d[i] = (d[i] - aa + MOD) % MOD;
        }
    }
 
    cout << d[c + 1];
 
    return 0;
}


Measured memory_bytes: 6400
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,num,s[13],h[13],c[13],d[13];
  char sign;
  cin >> n;
  for(int i=0;i<13;i++){
    s[i]=0;
    h[i]=0;
    c[i]=0;
    d[i]=0;
  }
  for(int i=0;i<n;i++){
    cin >> sign;
    switch(sign){
      case 'S':
      cin >> num;
      s[num-1] = 1;
      break;
      case 'H':
      cin >> num;
      h[num-1] = 1;
      break;
      case 'C':
      cin >> num;
      c[num-1] = 1;
      break;
      case 'D':
      cin >> num;
      d[num-1] = 1;
      break;
      default:break;
    }
  }
  for(int i=0;i<13;i++){
    if(s[i]==0) cout << "S" << " " << i+1 << endl;
  }
  for(int i=0;i<13;i++){
    if(h[i]==0) cout << "H" << " " << i+1 << endl;
  }
  for(int i=0;i<13;i++){
    if(c[i]==0) cout << "C" << " " << i+1 << endl;
  }
  for(int i=0;i<13;i++){
    if(d[i]==0) cout << "D" << " " << i+1 << endl;
  }
  return 0;
}



Measured memory_bytes: 3036
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <cstdlib>

#define For(i, j, k) for(int i = j; i <= k; i++)
#define Forr(i, j, k) for(int i = j; i >= k; i--)
#define Set(i, v) memset(i, v, sizeof i)
#define pb push_back

using namespace std;

const int N = 1000010;

int n, num[N];
int dp[N], l[N], r[N];
char S[N];

int main(){
	scanf("%d%s", &n, S + 1);
	int ans = 0;
	For(i, 1, n){
		if(S[i] == '0') continue;
		int R = i;
		while(S[R] == '1' || S[R + 1] == '1') ++R;
		int c = 0, m = 0;
		For(j, i, R){
			if(S[j] == '0' || j == R){
				if(c) num[++m] = c;
				c = 0;
			}
			else ++c;
		}
		c = 0;

		dp[0] = 0;
		int s = 0;
		For(j, 1, m - 1){
			For(k, 1, num[j]) r[++c] = s + num[j] + 2, l[c] = s + k - 1;
			s += num[j] + 1;
			For(k, 1, num[j + 1]) r[++c] = s + k, l[c] = s - 2;
		}
		s += num[m];

		m = 0;
		For(j, 1, s){
			dp[j] = dp[j - 1];
			while(m < c && r[m + 1] == j){
				++m;
				dp[j] = max(dp[j], dp[l[m]] + r[m] - l[m] - 2);
			}
		}
		ans += dp[s];

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

Measured memory_bytes: 14080
// Package main provides
//
// File:  main.go
// Author: ymiyamoto
//
// Created on Sat Aug 31 20:17:00 2019
//
package main

import "fmt"

func main() {
	var a int
	var s string
	fmt.Scan(&a)
	fmt.Scan(&s)

	if a >= 3200 {
		fmt.Println(s)
	} else {
		fmt.Println("red")
	}
}


Measured memory_bytes: 512
N, A, B = map(int, input().split())
        
Y = int(B-A)

if Y%2 == 0:
    print(int(Y//2))
else:
    if A-1>=N-B:
        print(N-B+int((B-A+1)//2))
    else:
        print(A-1+int((B-A+1)//2))


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


using namespace std;

using ll = long long;
using ld = long double;

#define mp make_pair

int p = 1000000007;


int mul(int a, int b) {
    return (1LL * a * b) % p;
}

int add(int a, int b) {
    int s = (a+b);
    if (s>=p) s-=p;
    return s;
}

int sub(int a, int b) {
    int s = (a+p-b);
    if (s>=p) s-=p;
    return s;
}

int po(int a, int deg)
{
    if (deg==0) return 1;
    if (deg%2==1) return mul(a, po(a, deg-1));
    int t = po(a, deg/2);
    return mul(t, t);
}

int inv(int n)
{
    return po(n, p-2);
}

struct DSU {
    vector<int> sz;
    vector<int> parent;

    void make_set(int v) {
        parent[v] = v;
        sz[v] = 1;
    }

    int find_set(int v) {
        if (v == parent[v])
            return v;
        return parent[v] = find_set(parent[v]);
    }

    void union_sets(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if (a != b) {
            if (sz[a] < sz[b])
                swap(a, b);
            parent[b] = a;
            sz[a] += sz[b];
        }
    }

    DSU(int n) {
        sz.resize(n);
        parent.resize(n);
        for (int i = 0; i < n; i++) make_set(i);
    }
};

/*const int N = 1200000;

vector<int> facs(N), invfacs(N);

void init()
{
    facs[0] = 1;
    for (int i = 1; i<N; i++) facs[i] = mul(facs[i-1], i);
    invfacs[N-1] = inv(facs[N-1]);
    for (int i = N-2; i>=0; i--) invfacs[i] = mul(invfacs[i+1], i+1);
}

int C(int n, int k)
{
    return mul(facs[n], mul(invfacs[k], invfacs[n-k]));
}*/

vector<pair<int, pair<int, int>>> edges;

int r, c, n;

int process(pair<int, int> a)
{
    if (a.first==0) return a.second;
    if (a.second==c) return c + a.first;
    if (a.first==r) return r + c + (c - a.second);
    if (a.second==0) return c + r + c + (r - a.first);
    return -1;
}

vector<int> pt;
vector<vector<int>> pos;

bool check(int l, int r)
{
    if (l>r) return true;
    int kek = pos[pt[l]][1];
    if (kek<=l || kek>r) return false;
    if (!check(l+1, kek-1)) return false;
    if (!check(kek+1, r)) return false;
    return true;
}

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

    cin>>r>>c>>n;
    vector<pair<int, int>> guys;
    for (int i = 0; i<n; i++)
    {
        int a, b, c1, d;
        cin>>a>>b>>c1>>d;
        if (process(mp(a, b))!=-1 && process(mp(c1, d))!=-1) guys.push_back(mp(process(mp(a, b)), process(mp(c1, d))));
    }

    //for (auto it: guys) cout<<it.first<<' '<<it.second<<endl;
    int m = guys.size();

    vector<pair<int, int>> points;

    for (int i = 0; i<m; i++)
    {
        points.push_back(mp(guys[i].first, i));
        points.push_back(mp(guys[i].second, i));
    }


    sort(points.begin(), points.end());
    for (auto it: points) pt.push_back(it.second);

    /*for (auto it: pt) cout<<it<<' ';
    cout<<endl;*/

    pos.resize(m);
    for (int i = 0; i<2*m; i++) pos[pt[i]].push_back(i);

    if (check(0, 2*m-1)) cout<<"YES"; else cout<<"NO";



}



Measured memory_bytes: 10480
#include<bits/stdc++.h>
#define EM 100000000
using namespace std;
using LL = long long;
using P = pair<LL, LL>;
LL LINF = 1e18;
int INF = 1e9;
LL mod = 1e9+7;
using vint = vector<int>;
using vLL = vector<LL>;
using vvint = vector<vector<int>>;
using vvLL = vector<vector<LL>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
	int N, K;
	cin >> N >> K;
	vint a(N);
	for(int i = 0;i < N;i++){cin >> a[i];}
	sort(a.begin(), a.end());
	vint dp(K, 0);
	int l = -1;
	int r = N;
	while(r-l > 1){
		int m = (l+r)/2;
		if(a[m] >= K){r = m;continue;}
		for(int i = 0;i < N;i++){
			if(i == m)	continue;
			for(int j = K-1;j-a[i] >= 0;j--){dp[j] = max(dp[j-a[i]], dp[j]);}
			if(a[i] < K)	dp[a[i]] = 1;
		}
		int f = 0;
		for(int j = K-a[m];j < K;j++){f = max(f, dp[j]);}
		for(int j = 0;j < K;j++)	dp[j] = 0;
		if(f)	r = m;else 	l = m;
	}

	cout << r << endl;
}

Measured memory_bytes: 256
//
//  main.cpp
//  HelloWorld
//
//  Created by purple on 2020/04/13.
//  Copyright © 2020 Purple. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <string>
#include <fstream>
#include <cmath>

using namespace std;

int main(int argc, const char * argv[]) {

    int tmp;
    int i=1;
    while(1){
        cin >> tmp;
        
        if(tmp==0)
            break;
        else
            cout << "Case " << i << ": " << tmp << endl;
        
        i++;
    }

    return 0;
    
}



Measured memory_bytes: 3020
#include <bits/stdc++.h>
using namespace std;
int n,l[200],a;
int main(){
  cin>>n;
  for(int i=0;i<n*2;i++)cin>>l[i];
  sort(l,l+n*2);
  for(int i=0;i<n;i++)a+=l[i*2];
  cout<<a<<endl;
}

Measured memory_bytes: 256
use std::cmp;
use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(& mut buf).unwrap();
    let mut iter = buf.split_whitespace();

    let n = iter.next().unwrap().parse::<usize>().unwrap();
    let mut segments= (0..n).map(|_| {
        let l = iter.next().unwrap().parse::<i64>().unwrap() - 1;
        let r = iter.next().unwrap().parse::<i64>().unwrap();
        (l, r)
    }).collect::<Vec<(i64, i64)>>();

    let max_l = segments.iter().map(|&(l, _)| l).max().unwrap();
    let min_r = segments.iter().map(|&(_, r)| r).min().unwrap();
    let max_size = segments.iter().map(|&(l, r)| r - l).max().unwrap();
    let mut res = max_size + cmp::max(min_r - max_l, 0);

    segments.sort_by(|p1, p2| if p1.0 != p2.0 {
        return p1.0.cmp(&p2.0);
    } else {
        return p2.1.cmp(&p1.1);
    });
    let mut fl = vec![0; n + 1];
    for i in 0..n {
        fl[i + 1] = cmp::max(fl[i], segments[i].0);
    }
    let mut br = vec![1000_000_000; n + 1];
    for i in 0..n {
        let j = n - 1 - i;
        br[j] = cmp::min(br[j + 1], segments[j].1);
    }

    for i in 1..n {
        res = cmp::max(res, cmp::max(min_r - fl[i], 0) + cmp::max(br[i] - max_l, 0));
    }

    println!("{}", res);
}

Measured memory_bytes: 10492
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N = 200;
int a[N];
int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,ans = 0x3f3f3f3f;
    cin >> n;
    for(int i = 0;i < n ; ++i) {
        cin >> a[i];
    }
    for(int i = 1;i <= 100; ++i) {
        int t = 0;
        for(int j = 0;j < n; ++j) {
            t += (a[j] - i) * (a[j] - i);
        }
        ans = min(ans,t);
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
  char s[205];
  cin >>s;
  int n = strlen(s);
  for(int i = n-2; i; i-=2){
    if(strncmp(s, s+i/2, i/2)==0){
      cout << i << endl;
      return 0;
    }
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    int A =abs(c-a),B = abs(b-a),C = abs(c-b);
    if(A <= d || (B<=d && C<=d)){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fastIO (cin.tie(0), cout.tie(0), ios::sync_with_stdio(false))
#define rep(i, n) for (int i = 0; i < (n); ++i)
using lint = long;
using llint = long long;
using namespace std;

int main() {
    fastIO;

    int idx = 1;
    int input;
    while (cin >> input) {
        if (input == 0)
            break;
        cout << "Case " << idx << ": " << input << endl;
        idx++;
    }
}



Measured memory_bytes: 3096
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        String[] linesp = line.split(" ");
        int nfig = Integer.parseInt(linesp[0]);
        int afig = Integer.parseInt(linesp[1]);
        int bfig = Integer.parseInt(linesp[2]);
        int cfig = Integer.parseInt(linesp[3]);
        int dfig = Integer.parseInt(linesp[4]);

        int xmin=0;
        int ymin=0;

        if(nfig%afig==0) {
        	xmin = (nfig/afig)*bfig;
        }else {
        	xmin = ((nfig/afig)+1)*bfig;
        }

        if(nfig%cfig==0) {
        	ymin = (nfig/cfig)*dfig;
        }else {
        	ymin = ((nfig/cfig)+1)*dfig;
        }

        if(xmin>ymin) {
        	System.out.println(ymin);
        }else {
        	System.out.println(xmin);
        }


    }
}


Measured memory_bytes: 26356
import java.io.*;

class Main {
	public static void main(String args[]) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String buf;

		try {
			while ((buf = br.readLine())!=null) {
				for (int i=0;i<buf.length();i++) {
					if (buf.charAt(i)!='@') System.out.print(buf.charAt(i));
					else {
						i++;
						int k = Character.getNumericValue(buf.charAt(i++));
						for (int j=0;j<k;j++) {
							System.out.print(buf.charAt(i));
						}
					}
				}
				System.out.println("");
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}

Measured memory_bytes: 16876
n = int(input())
for i in range(1, n + 1):
    if i % 3 == 0:
        print(" {}".format(i), end="")
        continue

    x = i
    while x > 0:
        if x % 10 == 3:
            print(" {}".format(i), end="")
            break
        else:
            x //= 10
print()


Measured memory_bytes: 5876
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N;
    cin >> N;

    vector<int> numbers(N);
    for (int i = 0; i < N; i++) {
        cin >> numbers.at(i);
    }

    sort(numbers.begin(),numbers.end());

    bool result = true;
    
    for (int i = 0; i < numbers.size()-1; i++) {
        if(numbers.at(i)==numbers.at(i+1)){
            result = false;
            break;
        }
    }

    if(result){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> VI;
typedef vector<VI> VVI;
typedef pair<ll, ll> P;
#define FOR(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(i,n)  FOR(i,0,n)
#define PRINT(V) for (auto v : (V)) cout << v << " "
#define ALL(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const ll INF = numeric_limits<ll>::max();
int main()
{
    int n; cin >> n;
    string c; cin >> c;
    int cnt = 0;
    int wc = 0, rc = 0;
    int lwc = 0, rrc = 0;
    rep(i, n) {
        if (c[i] == 'R') ++rc;
        else ++wc;
    }
    rep(i, rc) if (c[i] == 'W') ++lwc;
    FOR(i, rc, n) if (c[i] == 'R') ++rrc;
    cout << min(lwc, rrc) <<endl;
    return 0;
}

Measured memory_bytes: 3700
#include <stdio.h>
#include <string.h>
#include <algorithm>
 
using namespace std;
 
int main(void){
    int t, p, r, tid, pid, time, i, j, k, flag[50][10], pena[50][10], max, max_i, sum, count, num[50], solvep[50], solvet[50], head, tail;
    char message[8], c;
    int tmp1, tmp2, tmp3;
    const char correct[8] = {"CORRECT"},wrong[6] = {"WRONG"};
    while(1){
        scanf("%d%d%d",&t,&p,&r);
        if(t == 0 && p == 0 && r == 0)
            break;
        memset(pena,0,sizeof(pena));
        memset(flag,0,sizeof(flag));
        for(i = 0;i < r;i++){
            scanf("%d%d%d%*c",&tid,&pid,&time);
            j = 0;
            while((c = getchar()) != '\n')
                message[j++] = c;
            message[j] = '\0';
            if(!strncmp(correct,message,7))
                flag[tid - 1][pid - 1] = 1200 * pena[tid - 1][pid - 1] + time;
            else if(!strncmp(wrong,message,5))
                pena[tid - 1][pid - 1]++;
        }
        for(i = 0;i < t;i++) // numの計算
            num[i] = i + 1;
        for(i = 0;i < t;i++){ // solvepの計算
            count = 0;
            for(j = 0;j < p;j++){
                if(flag[i][j])
                    count++;
            }
            solvep[i] = count;
        }
        for(i = 0;i < t;i++){
            sum = 0;
            for(j = 0;j < p;j++)
                sum += flag[i][j];
            solvet[i] = sum;
        }
        for(i = 0;i < t - 1;i++){
            max_i = i;
            for(j = i + 1;j < t;j++){
                if(solvep[j] > solvep[max_i])
                    max_i = j;
                else if(solvep[j] == solvep[max_i] && solvet[j] < solvet[max_i])
                    max_i = j;
				else if(solvep[j] == solvep[max_i] && solvet[j] == solvet[max_i] && num[j] < num[max_i])
					max_i = j;
            }
            if(max_i != i){
                tmp1 = num[max_i];
                tmp2 = solvep[max_i];
                tmp3 = solvet[max_i];
                num[max_i] = num[i];
                solvep[max_i] = solvep[i];
                solvet[max_i] = solvet[i];
                num[i] = tmp1;
                solvep[i] = tmp2;
                solvet[i] = tmp3;
            }
        }
        for(i = 0;i < t;i++)
            printf("%d %d %d\n",num[i],solvep[i],solvet[i]);
    }
    return 0;
}

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

using namespace std;

using int64 = long long;

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

  int n, m;
  cin >> n >> m;

  vector<int> count(n, 1);
  vector<int> is_red(n, false);
  is_red[0] = true;

  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    x--;
    y--;
    if (is_red[x]) {
      is_red[y] = true;
    }
    count[x]--;
    count[y]++;
    if (count[x] == 0) {
      is_red[x] = false;
    }
  }

  int ans = 0;
  for (int r : is_red) if (r) ans++;
  cout << ans << endl;
}

Measured memory_bytes: 1024
import itertools

n, a, b = map(int, input().split())
mod = 10 **9 + 7


def ncr(n, r, mod):
    x = 1
    y = 1
    for i in range(1, r+1):
        x = x * (n-i+1) % mod
        y = y * i % mod
    return (x*pow(y, mod-2, mod)) % mod

sumc = pow(2, n, mod)-1
ac = ncr(n, a, mod)
bc = ncr(n, b, mod)

print((sumc - ac - bc)% mod)


Measured memory_bytes: 39952
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{
  int value;
  node *next;
  node(int value,node *next):value(value),next(next){}
};
int INF=1LL<<55LL;
string lcs(string x,string y){
  int n=x.size(),m=y.size();
  map<char,vector<int> > M;
  for(int j=m-1;j>=0;j--) M[y[j]].push_back(j);
  vector<int> xs(n+1,INF);
  xs[0]=-INF;
  vector<node* > link(n+1);
  for(int i=0;i<n;i++){
    if(M.count(x[i])){
      vector<int> ys=M[x[i]];
      for(int j=0;j<(int)ys.size();j++){
	int k=distance(xs.begin(),lower_bound(xs.begin(),xs.end(),ys[j]));
	xs[k]=ys[j];
	link[k]=new node(y[ys[j]],link[k-1]);
      }
    }
  }
  string res;
  int l=distance(xs.begin(),lower_bound(xs.begin(),xs.end(),INF-1))-1;
  for(node *p=link[l];p!=NULL;p=p->next)
    res.push_back(p->value);
  return res;
}
signed main(){
  int q;
  cin>>q;
  while(q--){
    string x,y;
    cin>>x>>y;
    cout<<lcs(x,y).size()<<endl;
  }
  return 0;
}

Measured memory_bytes: 51204
n = int(input())

get_line = lambda: [int(x) for x in input().split()]

A = get_line()

b = sum(map(int, input().split()))

C = get_line()

for i in range(len(A) - 1):
    if A[i] == A[i + 1] - 1:
        b += C[A[i] - 1]

print(b)


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

using namespace std;

int main(){

	int n;
	cin >> n;
	int arr[(2 * n) + 5];
	for(int i = 1; i <= 2 * n; ++i)
	{
		cin >> arr[i];
	}
	sort(arr + 1, arr + 1 + 2*n);
	int ans = 0;
	for(int i = 1; i <= n; ++i)
	{
		ans += arr[(2 * i) - 1];
		//cout << arr[2 * i - 1];
	}
	cout << ans;

	return 0;
}

Measured memory_bytes: 256
# ABC 132 D - Blue and Red Balls
# https://atcoder.jp/contests/abc132/tasks/abc132_d

n, k = gets.split(/ /).map(&:to_i)
mod = 10**9 + 7

def separation_patterns(n, i, i_minus_1_factorial)
  n.downto(n - i + 1).to_a.reduce(1) { |acc, j| acc * j } / i_minus_1_factorial
end

def factorial(n)
  1.upto(n).to_a.reduce(1) { |acc, i| acc * i }
end

class Factorial
  def initialize(n)
    @n = n
    @array = [1, 1]
    2.upto(n).each do |i|
      @array.push(@array.last * i)
    end
  end

  def [](n)
    @array[n]
  end
end

factorial = Factorial.new(k)

1.upto(k).each do |i|
  # puts "i_factorial: #{factorial[i]}"

  blue_patterns = (k - 1).downto(k - i + 1).to_a.reduce(1) { |acc, j| acc * j } / factorial[i - 1]
  # puts "blue_patterns: #{blue_patterns}"
  patterns = (n - k + 1).downto(n - k + 1 - i + 1).to_a.reduce(1) { |acc, j| acc * j } / factorial[i]
  puts (patterns * blue_patterns) % mod
end


Measured memory_bytes: 11288
object Main {

  import java.util.Scanner
  import scala.collection.mutable.ArrayBuffer

  def main(args: Array[String]): Unit = {
    val sc = new Scanner(System.in)
    val writer = new java.io.PrintWriter(System.out)
    writer.println(solve(sc))
    writer.flush()
  }

  def solve(sc: Scanner): String = {
    val (r, d, x) = (sc.nextInt(), sc.nextInt(), sc.nextInt())
    debug(r, d, x)

    val weightBuf = ArrayBuffer.empty[Int]
    (1 to 10).foldLeft(x) { (acc, _) =>
      val w = r * acc - d
      weightBuf += w
      w
    }
    weightBuf.mkString("\n")
  }

  private def debug(x: Any): Unit = {
    if (System.getenv("LOCAL_DEBUG") != null) println(x)
  }
}


Measured memory_bytes: 25784
#include<bits/stdc++.h>
using namespace std;
#define int                 long long
#define FF(i,a,b)           for(int i=a;i<b;i++)
#define BF(i,a,b)           for(int i=a;i>=b;i--)
#define vi                  vector<int>
#define MAP                 map<int,int>
#define pb                  push_back
#define MP                  make_pair
#define F                   first
#define S                   second
#define pi                  pair<int,int>
#define all(v)              v.begin(),v.end()
#define PIE                 3.1415926535897932384626433832795
#define print0(a)           cout<<a<<"\n"
#define print1(a)           cout<<a<<' '
#define print2(a,b)         cout<<a<<" "<<b<<" ";
#define print3(a,b,c)       cout<<a<<" "<<b<<" "<<c<<" ";
#define print4(a,b,c,d)     cout<<a<<" "<<b<<" "<<c<<" "<<d<<" ";
#define FastIO              ios::sync_with_stdio(0); cin.tie(0);cout.tie(0)
/**************************************************************************************/
                       /*Global Variables*/
const int mod = 1e9+7;
const int N = 2e5+10;
const int inf = 3e18;

/**************************************************************************************/
template <typename A>istream& operator>>(istream& input,vector<A>& x) {for(auto& i:x)input>>i;return input;}
template<typename A>ostream& operator<<(ostream& output,vector<A>& x) {for(auto& i:x)output<<i<<' ';return output;}
int add(int a, int b){return (a%mod + b%mod + mod)%mod;}
int sub(int a, int b){return (a%mod - b%mod + mod)%mod;}
int mul(int a, int b){return ((a%mod)*(b%mod) + mod)%mod;}
int Power(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1)res*=a;
        a*=a;
        b>>=1;
    }
    return res;
}

signed main()
{
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    // #endif
    FastIO;
    int T=1;
    //cin>>T;
    while(T--)
    {
        int a,b,c,k;
        cin>>a>>b>>c>>k;
        int sum=0;
        sum+=min(a,k);
        k-=a;
        k=max(k,0LL);
        k-=b;
        k=max(k,0LL);
        sum+=(-1*k);
        cout<<sum<<"\n";
       

    }

}
/*
|| Do what you can with all you have,wherever you are. ||

|| Knowing is not enough, we must apply. Wishing is not enough, we must do. ||

|| A goal is a dream with deadline. ||

|| Whether you think you can or you think you can't, you're right. ||
*/



Measured memory_bytes: 3648