Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

# 2019-11-14 10:01:24(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

mod = 10 ** 9 + 7
def main():
    n, m, *broken_treads = [int(x) for x in sys.stdin.read().split()]
    safe = sorted((set(range(1, n+1)) - set(broken_treads)))

    pattern_for_each_section = []
    ans = 1
    p = [0, 1]
    continuous_broken_count = 0
    for i in range(1, n+1):
        if i in safe:
            continuous_broken_count = 0
            p.append(p[-1] + p[-2])
        else:
            continuous_broken_count += 1
            if continuous_broken_count == 1:
                pattern_for_each_section.append(p[-1])
                p = [1, 0]
            else:
                print(0)
                sys.exit()
    
    if continuous_broken_count == 0:
        pattern_for_each_section.append(p[-1])
    

    for c in pattern_for_each_section:
        ans = ans * c % mod
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

mod = 10 ** 9 + 7
n, m, *a = [int(x) for x in sys.stdin.read().split()]

safe = sorted(set(range(1,n+1)) - set(a))
dp = [0] * (n + 2)
dp[0] = 0
dp[1] = 1
for i in safe:
    dp[i+1] = (dp[i] + dp[i-1]) % mod

print(dp[-1])
### BUGGY CODE ###

import numpy as np
from numba import jit

N, K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
a = np.array(A)

fin = np.array([N] * N)


@jit(nopython=True)
def calc_b(a):
    b = np.array([0] * N)
    for i in range(N):
        if a[i] == N:
            b[i] = a[i]
        else:
            l = max(0, i - a[i])
            r = min(N - 1, i + a[i])

            for j in range(l, r + 1):
                b[j] += 1
    return b


for k in range(K):
    a = calc_b(a)

    if (a == fin).all():
        break

a = [str(_) for _ in a]
print(' '.join(a))


### FIXED CODE ###

import numpy as np
from numba import njit

N, K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
a = np.array(A, dtype=int)


fin = [N] * N

@njit(cache=True)
def calc_b(a):
    b = np.zeros(N, dtype=np.int64)
    for i, _a in enumerate(a):
        l = max(0, i - _a)
        r = min(N - 1, i + _a)

        # imos hou
        b[l] += 1
        if r + 1 < N:
            b[r + 1] -= 1

    b = np.cumsum(b)
    # print('b_sum', b)
    return b


for k in range(min(K,100)):
    # print('a', a)
    a = calc_b(a)
    # if all(a == fin):
    #     break

a = [str(_) for _ in a]
print(' '.join(a))
# print('step=', k)
### BUGGY CODE ###

from collections import deque

s = input()
N = int(input())

S = []
for i in range(len(s)):
    S.append(s[i])
    
back_count = 0
for i in range(N):
    Q = list(map(str, input().split()))
    Q[0] = int(Q[0])
    if Q[0] == 1:
        if back_count == 0:
            back_count = 1
        else:
            back_count = 0
    else:
        Q[1] = int(Q[1])
        if back_count == 0:
            if Q[1] == 1:
                d = deque(S)
                d.appendleft(Q[2])
                S = list(d)
            else:
                S.append(Q[2])
        else:
            if Q[1] == 1:
                S.append(Q[2])
            else:
                d = deque(S)
                d.appendleft(Q[2])
                S = list(d)

if back_count == 0:
    print("".join(S))
else:
    S = S[::-1]
    print("".join(S))

### FIXED CODE ###

from collections import deque

s = input()
N = int(input())

S = []
for i in range(len(s)):
    S.append(s[i])

d = deque(S)
    
back_count = 0
for i in range(N):
    Q = list(map(str, input().split()))
    Q[0] = int(Q[0])
    if Q[0] == 1:
        if back_count == 0:
            back_count = 1
        else:
            back_count = 0
    else:
        Q[1] = int(Q[1])
        if back_count == 0:
            if Q[1] == 1:
                d.appendleft(Q[2])
            else:
                d.append(Q[2])
        else:
            if Q[1] == 1:
                d.append(Q[2])
            else:
                d.appendleft(Q[2])

S = list(d)
if back_count == 0:
    print("".join(S))
else:
    S = S[::-1]
    print("".join(S))
### BUGGY CODE ###

def gcd(x, y):
    while y:
        amari = x % y
        x = y
        y = amari
    return x
 
def main():
    n = int(input())
    a = [int(a) for a in input().split()]
 
    maxv = 0
    for i in range(n):
        a_ = a[:i] + a[i+1:]
        gcdv = a_[0]
        for j in range(1, n-1):
            gcdv = gcd(gcdv, a_[j])
        if maxv < gcdv:
            maxv = gcdv
    print(maxv)
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import math
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def input(): return sys.stdin.readline()[:-1]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def MAT(h): return [list(map(int, input().split())) for _ in range(h)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N = INT()
    A = LIST()
    L = [0] * N
    R = [0] * N
    M = [0] * N
    for i in range(N - 1):
        L[i + 1] = gcd(L[i], A[i])
        R[N - i - 2] = gcd(R[N - i - 1], A[N - i - 1])
    maxv = 0
    for i in range(N):
        M[i] = gcd(L[i], R[i])
        if maxv < M[i]:
            maxv = M[i]
    print(maxv)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

def div(n, m):
  if n > m:
    n = m
  d = []
  for i in range(1, n+1):
    if n % i == 0 and m % i == 0:
      d.append(i)
  return d

a, b = map(int, input().split())
lc = div(a,b)
la = []
for i in lc:
  if la:
    for j in la:
      if j != 1 and i % j == 0:
        break
    else:
      la.append(i)
  else:
    la.append(i)
print(len(la))


### FIXED CODE ###

import math
def gcd(a, b):
  while b > 0:
    a, b = b, a % b
  return a
def div(a):
  r = []
  i = 2
  k = int(math.sqrt(a))
  while i <= k:
    if a % i == 0:
      r.append(i)
      while a % i == 0:
        a //= i
      k = math.sqrt(a)
    i += 1
  if a > 1:
    r.append(a)
  return r

a, b = map(int, input().split())
if a > b:
  a, b = b, a
c = gcd(a,b)
print(len(div(c))+1)
### BUGGY CODE ###

a,b,x=map(int,input().split())
ans = 0
for i in range(a,b+1):
  if i%x == 0:
    ans += 1
print(ans)

### FIXED CODE ###

a, b, x = map(int, input().split())
ans = int(b//x) - int(a//x)
if a%x ==0:
    ans += 1
print(ans)
### BUGGY CODE ###

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

ans=1

for i in range(n):
    ans *= a[i]

if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

b = sorted(a, reverse=True)


ans=1

if min(b) == 0:
    print(0)
    exit(0)

for i in range(n):
    ans *= b[i]
    if ans > 10 ** 18:
        print(-1)
        exit(0)



print(ans)
### BUGGY CODE ###

N,M=map(int, input().split())
f=[]
for _ in range(M):
    a,b = map(int, input().split())
    for i in f:
        if a in i or b in i:
            i.add(a)
            i.add(b)
            break
    else:
        f.append(set((a,b)))

x = 0
for i in f:
    x=max(x,len(i))
if M == 0:
    x = 1
print(x)


### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

N,M=map(int, input().split())
mx=0
uf = UnionFind(N+1)
for i in range(M):
	a,b = map(int, input().split())
	uf.union(a,b)
for i in uf.parents:
	mx = max(mx, uf.size(i))
if M == 0:
	mx = 1
print(mx)
### BUGGY CODE ###

import collections

H, W, M = map(int, input().split())

h, w = [0]*M, [0]*M
for i in range(M):
    h[i], w[i] = map(int, input().split())

counter = collections.Counter(h)
h_max = max(counter.values())
mode_h = [key for key , value in counter.items() if value == h_max]
counter = collections.Counter(w)
w_max = max(counter.values())
mode_w = [key for key , value in counter.items() if value == w_max]

ans = 0
for i in mode_h:
    for j in mode_w:
        if ans < h.count(i) + w.count(j):
            ans = h.count(i) + w.count(j)
            for k in range(M):
                if h[k] == i and w[k] == j:
                    ans -= 1
            if ans == H + W - 1 or ans == M or ans == h_max + w_max:
                print(ans)
                exit()

print(ans)

### FIXED CODE ###

import collections
H, W, M = map(int, input().split())

h, w = [0]*M, [0]*M
dic = set()
for i in range(M):
    h[i], w[i] = map(int, input().split())
    dic.add((h[i],w[i]))

counter = collections.Counter(h)
h_max = max(counter.values())
mode_h = [key for key , value in counter.items() if value == h_max]
counter = collections.Counter(w)
w_max = max(counter.values())
mode_w = [key for key , value in counter.items() if value == w_max]

for i in mode_h:
    for j in mode_w:
        if (i,j) not in dic:
            print(h_max+w_max)
            exit()

print(h_max+w_max-1)
### BUGGY CODE ###

import sys
from operator import mul
from functools import reduce


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


n = int(input())
l = [int(x) for x in input().split()]

cl = [0 for i in range(n)]
ll = [x for x in set(l) if l.count(x) > 1]

if not ll:
    for i in range(n):
        print(0)
    sys.exit()

sum = 0
for i in ll:
    m = l.count(i)
    nc = combinations_count(m, 2)
    sum += nc
    # print(nc)
    if m < 3:
        cl[i-1] = nc
    else:
        cl[i - 1] = nc - combinations_count(m-1, 2)

# print(sum)
# print(cl)
for i in l:
    print(sum - cl[i - 1])

### FIXED CODE ###

import collections

def combinations_count(n, r):
    return n * (n-1) // r


n = int(input())
l = [int(x) for x in input().split()]

l1 = []
l2 = []
c = collections.Counter(l)

total = sum([combinations_count(i, 2) for i in c.values()])

for a in l:
    print(total-combinations_count(c[a], 2)+combinations_count(c[a]-1, 2))
### BUGGY CODE ###

import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

def add_sentinel(t: list, v: list):
    t = [0] + [0] + t + [t[-1]]
    v = [0] + v + [0]
    return t,v
    
def find_max_vel(ti: int, v: list, intervals: list):
    ret = float('inf')
    for inti, interval in enumerate(intervals):
        st, ed = interval
        
        if ti < st:
            ret = min(ret, v[inti] + (st - ti))
        elif st <= ti <= ed:
            ret = min(ret, v[inti])
        else:
            ret = min(ret, v[inti] + (ti - ed))
            
    return ret

n = ni()
t = list(li())
v = list(li())

t,v = add_sentinel(t, v)
t = list(accumulate(t))
intervals = [(st, ed) for st, ed in zip(t[:-1], t[1:])]

vels = []
for ti in range(2*max(t)+1):
    timestamp = ti/2
    vels.append(find_max_vel(timestamp, v, intervals))
    
ans = 0
for left, right in zip(vels[:-1], vels[1:]):
    ans += (left + right) * 0.5 * 0.5
    
print(ans)

### FIXED CODE ###

N = int(input())
T = list(map(int, input().split()))
V = list(map(int, input().split()))

V = [0] + V + [0]

# 0.前処理
# N+2個の条件をつくる
left = [0]
right = [0]

for i in range(N):
    left.append(right[i])
    right.append(left[-1]+T[i])
    
left.append(right[-1])
right.append(right[-1])

INF = float("inf")
vel = [INF]*(2*right[-1]+1)

# 1.各ステップでの許容測度の最大値の最小値を求める
for t in range(2*right[-1]+1):
    for i in range(N+2):
        if (t/2) < left[i]:
            vel[t] = min(vel[t], -(t/2)+(V[i]+left[i]))
        elif left[i] <= (t/2) and (t/2) <= right[i]:
            vel[t] = min(vel[t], V[i])
        elif (t/2) > right[i]:
            vel[t] = min(vel[t], (t/2)+(V[i]-right[i]))
            

# 2.面積を求める
ans = 0
for t in range(2*right[-1]):
    ans += (1/2)*0.5*(vel[t]+vel[t+1])
    
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())  #数字

B=[]
for i in range(N + 1):
    B.append(i)

D = []
import itertools
for i in range(K,len(B)+1):
    for j in itertools.combinations(B, i):
        D.append(j)

E = []
F = []
G = 0
for i in range(K, len(D[-1])+1):
    for j in range(G,len(D)):
        if len(D[j]) == i:
            E.append(sum(D[j]))
        if len(D[j]) > i:
            G = j
            break
    F.append(set(E))
    E = []
        
H = 0
for i in range(len(F)):
    for j in range(len(F[i])):
        H += 1
print(H)

### FIXED CODE ###

N, K = map(int, input().split())  #数字
MOD = 10 ** 9 + 7

ans = 0
for i in range(K, N + 2):
    A = (i - 1) * i // 2
    B = N * (1 + N) // 2 - (N + 1 - i - 1) * (N + 1 - i) // 2
    ans += B - A + 1

print(ans % MOD)
### BUGGY CODE ###

import bisect

n, m = map(int, input().split())
ls = sorted(map(int, input().split()))
ls2 = [list(map(int, input().split())) for _ in range(m)]
ls2.sort(key=lambda x: (x[1], x[0]), reverse=True)
left = 0
res = 0
for b, c in ls2:
    i = bisect.bisect(ls[left:], c)
    i = min(i, b)
    res += c * i
    left += i
print(res + sum(ls[left:]))

### FIXED CODE ###

n, m = map(int, input().split())
ls = sorted(map(int, input().split()))
ls2 = [list(map(int, input().split())) for _ in range(m)]
ls2.sort(key=lambda x: (x[1], x[0]), reverse=True)
left = 0
right = 0
index = 0
res = 0
while left < n:
    if index == len(ls2):
        break
    b, c = ls2[index]
    if c <= ls[left]:
        break
    right = left + 1
    while right <= n:
        if right == n:
            res += c * (right - left)
            break
        if ls[right] <= c and right - left < b:
            right += 1
        else:
            res += c * (right - left)
            break
    left = right
    index += 1

print(res + sum(ls[left:]))
### BUGGY CODE ###

import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    s = list(input())
    l = len(s)
    dp = [[0 for _ in range(13)] for __ in range(l + 1)]
    dp[0][0] = 1

    for i, si in enumerate(s):
        keta = pow(10, l - i - 1)
        base = keta % 13

        if si == "?":
            for k in range(10):
                tmp = base * k % 13
                for j in range(13):
                    dp[i + 1][(j + tmp) % 13] += dp[i][j]
                    dp[i + 1][(j + tmp) % 13] %= MOD
        else:
            si = int(si)
            tmp = base * si % 13
            for j in range(13):
                dp[i + 1][(j + tmp) % 13] += dp[i][j]
                dp[i + 1][(j + tmp) % 13] %= MOD

    print(dp[l][5])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    s = list(input())
    l = len(s)
    dp = [[0 for _ in range(13)] for __ in range(l + 1)]
    dp[0][0] = 1

    for i, si in enumerate(s):
        base = pow(10, l - i - 1, 13)

        if si == "?":
            for k in range(10):
                tmp = base * k % 13
                for j in range(13):
                    dp[i + 1][(j + tmp) % 13] += dp[i][j]
                    dp[i + 1][(j + tmp) % 13] %= MOD
        else:
            si = int(si)
            tmp = base * si % 13
            for j in range(13):
                dp[i + 1][(j + tmp) % 13] += dp[i][j]
                dp[i + 1][(j + tmp) % 13] %= MOD

    print(dp[l][5])


if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
N,M = map(int, input().strip().split(' '))
broken = [int(line.strip()) for line in sys.stdin]
p = [0]*(N+2)
p[0] = 1
for i in range(N):
  # 今i段目にいる
  if i in broken:
    continue
  p[i+1] += p[i]
  p[i+2] += p[i]
print(p[N]%1000000007)

### FIXED CODE ###

import sys
N,M = map(int, input().strip().split(' '))
broken = set(int(line.strip()) for line in sys.stdin)
p = [0]*(N+2)
p[0] = 1
for i in range(N):
  # 今i段目にいる
  if i in broken:
    continue
  p[i+1] += p[i]
  p[i+2] += p[i]
print(p[N]%1000000007)
### BUGGY CODE ###

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

cnt = 0
before_hairetsu = [N+1] * N

#i_before = N + 1
before_hairetsu[0] = N + 1
for i in range(N):
  if(min( min(before_hairetsu) , P[i]) >= P[i]):
    cnt += 1
  #i_before = P[i]
  before_hairetsu.append( P[i] )
  
print(cnt)
      

### FIXED CODE ###

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

cnt = 0

maxmax = max(P) + 1

for i in range(N):
  if( maxmax > P[i]):
    cnt += 1
    maxmax = P[i]
  
print(cnt)
### BUGGY CODE ###

n, m = map(int, input().split())
tree = [[] for _i in range(m+1)]
k = []
for i in range(n):
    x = list(map(int, input().split()))
    for j in x[1:]:
        tree[j].append(i)
    k.append(x[1:])

visit = [0 for _ in range(n)]
from collections import deque
q = deque([0])
while q:
    p = q.pop()
    if visit[p]==1:
        continue
    visit[p] = 1
    for i in k[p]:
        for j in tree[i]:
            if visit[j]==0:
                q.appendleft(j)
if sum(visit)==n:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

n, m = map(int, input().split())
tree = [[] for _i in range(m+n+1)]
for i in range(n):
    x = list(map(int, input().split()))
    tree[i].extend([i+n for i in x[1:]])
    for j in x[1:]:
        tree[j+n].append(i)

from collections import deque
q = deque([1])
visit = [0 for _i in range(m+n+2)]
visit[1] = 1
while q:
    p = q.pop()
    for j in tree[p]:
        if visit[j]==0:
            visit[j] = 1
            q.appendleft(j)
if sum(visit[:n]) == n:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]

def lcm(x, y):
    if x > y:
        big = x
    else:
        big = y

    while(True):
        if((big % x == 0) and (big % y == 0)):
            lcm = big
            break
        big += 1
    return lcm

ans = a[0]
for i in a:
    ans = lcm(ans, i)
    
print(ans)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]

def gcd(x, y):
    while(y):
        x, y = y, x%y
    return x

def lcm(x, y):
    lcm = (x*y)//gcd(x,y)
    return lcm

ans = 1
for i in a:
    ans = lcm(ans, i)
    
print(ans)
### BUGGY CODE ###

from collections import Counter


def main():
    N = int(input())
    A = list(map(int, input().split(' ')))
    counter = Counter(A)
    A.sort()
    one_num = len(list(filter(lambda a: a == 1, A)))
    if one_num == 1:
        print(1)
        return
    elif one_num >= 2:
        print(0)
        return
    nums = list()
    for a in A:
        is_target = True
        for n in nums:
            if a % n == 0:
                is_target = False
                break
            if a // 2 < n:
                break
        if is_target:
            nums.append(a)
    print(len(list(filter(lambda n: counter[n] == 1, nums))))


if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import Counter


def main():
    N = int(input())
    A = list(map(int, input().split(' ')))
    counter = Counter(A)
    searched = [0 for _ in range(10 ** 6 + 1)]
    ans = 0
    for i in range(1, 10 ** 6 + 1):
        if counter[i] == 0:
            continue
        if searched[i] == 0 and counter[i] == 1:
            ans += 1
        for j in range(1, ((10 ** 6) // i) + 1):
            searched[i * j] = 1
    print(ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

import numpy as np
N, M, Q = map(int, input().split())

check = np.array([[0] * (N+1) for i in range(N+1)])

for i in range(M):
    l, r = map(int, input().split())
    check[r][l] += 1

# print(check)
for i in range(1, N+1):
    check[i] += check[i-1]
for i in range(1, N+1):
    check[:,i] += check[:,i-1]
# print(check)

for i in range(Q):
    p, q = map(int, input().split())
    print(check[q][q] - check[q][p-1] - check[p-1][q] + check[p-1][p-1])


### FIXED CODE ###

# import sys
import numpy as np
# input = sys.stdin.readline

def main():
    N, M, Q = map(int, input().split())

    check = np.zeros((N+1, N+1))

    for i in range(M):
        l, r = map(int, input().split())
        check[r][l] += 1

    # print(check)
    for i in range(1, N+1):
        check[i] += check[i-1]
    for i in range(1, N+1):
        check[:,i] += check[:,i-1]
    # print(check)

    for i in range(Q):
        p, q = map(int, input().split())
        print(int(check[q][q] - check[q][p-1] - check[p-1][q] + check[p-1][p-1]))

if __name__ == "__main__":
    main()
### BUGGY CODE ###

A,B,C,K = map(int,input().split())

s=-1*K*C

lc=[]
lc_=[]
for i in range(A+1):
  for j in range(min(K-i+1,B+1)):
    lc.append([i,j,K-i-j])

#print(lc)

for i in range(len(lc)):
  if lc[i][0]<=A and lc[i][1]<=B and lc[i][2]<=C:
    # print(lc[i])
    s=max(s, lc[i][0]-lc[i][2])

print(s)


### FIXED CODE ###

A,B,C,K = map(int,input().split())

if A+B<K:
  print(A-(K-A-B))
else:
  print(min(A, K))
### BUGGY CODE ###

from collections import defaultdict as d
s=d(int)
s[0]=0
n,w=map(int,input().split())
for i in range(n):
    q,v=map(int,input().split())
    c=s.copy()
    for p,r in c.items():
        if p+q<=w:
            s[p+q]=max(s[p+q],r+v)
print(max(s.values()))


### FIXED CODE ###

import numpy as np
n,a=map(int,input().split())
s=np.full(n*1000+1,a+1)
s[0]=0
for i in range(n):
    w,v=map(int,input().split())
    s[v:]=np.minimum(s[v:],s[:-v]+w)
print(np.max(np.where(s<=a)))