Harryxun/stf_run huggingface dataset:
#!/usr/bin/env python3
import sys
#sys.setrecursionlimit(150000)


def solve(H: int, W: int, s: "List[str]"):
    x=y=0
    k=1 if s[y][x]=="#" else 0
    for i in range(H+W-2):
        if y<H-1 and s[y][x]==s[y+1][x]:
            y+=1
        elif x<W-1 and s[y][x]==s[y][x+1]:
            x+=1
        else:
            k+=1
            if x<W-1:
                x+=1
            else:
                y+=1
    print((k+1)//2)
    return
        
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    s = [next(tokens) for _ in range(W)]  # type: "List[str]"
    solve(H, W, s)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
#sys.setrecursionlimit(150000)


def solve(H: int, W: int, s: "List[str]"):
    x=y=0
    k=1 if s[y][x]=="#" else 0
    dt=[[999]*W for _ in range(H)]
    dt[y][x]=1 if s[y][x]=="#" else 0
    for y in range(H):
        for x in range(W):
            if y>0:
                dt[y][x]=min(dt[y][x], dt[y-1][x]+(1 if s[y][x]!=s[y-1][x] else 0))
            if x>0:
                dt[y][x]=min(dt[y][x], dt[y][x-1]+(1 if s[y][x]!=s[y][x-1] else 0))
    print((dt[H-1][W-1]+1)//2)
    #print("#",s,dt)
    """
    for i in range(H+W-2):
        if y<H-1 and s[y][x]==s[y+1][x]:
            y+=1
        elif x<W-1 and s[y][x]==s[y][x+1]:
            x+=1
        else:
            print(x,y,k+1)
            k+=1
            if x<W-1:
                x+=1
            else:
                y+=1
    print(k,(k+1)//2)
    """
    return
        
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    s = [next(tokens) for _ in range(H)]  # type: "List[str]"
    solve(H, W, s)

if __name__ == '__main__':
    main()
import sys
n, m = map(int, input().split())

if m > 0:
  As = set(map(int, sys.stdin))
else:
  As = set()

nums = [0] * (n + 1)
nums[0] = 1
if 1 in As:
  pass
else:
  nums[1] = 1
  
for i in range(2, n + 1):
  if i in As:
    continue
  else:
    nums[i] = (nums[i-1] + nums[i-2]) % 1000000007
    
print(nums[-1])

### FIXED CODE ###

p, q, r = map(int, input().split())

print(p + q + r - max(p, q, r))
n,m=map(int, input().split())
def is_prime(N):
    is_prime=[True]*(N+1)
    is_prime[0:2]=False,False
    for i in range(int(N**0.5)+1):
        if is_prime[i]==False:
            continue
        for j in range(i*2,N+1,i):
            is_prime[j]=False
    return is_prime
def primes(N):
    prime=is_prime(N)
    return [i for i in range(N+1) if prime[i]]
def prime_factorization(n):
    ps=primes(int(n**0.5))
    r=[]
    for i,p in enumerate(ps):
        num=0
        while(True):
            x,y=divmod(n,p)
            if y!=0:
                break
            n=x
            num+=1
        if num>0:
            r.append((p,num))
    if n>1:
        r.append((n,1))
    return r

f=prime_factorization(m)
from scipy.special import perm, comb
ans=1
mod=10**9+7
for p in f:
    ans*=comb(p[1]+n-1,n-1,exact=True)
    ans%=mod
print(ans)


### FIXED CODE ###

n,m=map(int, input().split())
def is_prime(N):
    is_prime=[True]*(N+1)
    is_prime[0:2]=False,False
    for i in range(int(N**0.5)+1):
        if is_prime[i]==False:
            continue
        for j in range(i*2,N+1,i):
            is_prime[j]=False
    return is_prime
def primes(N):
    prime=is_prime(N)
    return [i for i in range(N+1) if prime[i]]
def prime_factorization(n):
    ps=primes(int(n**0.5))
    r=[]
    for i,p in enumerate(ps):
        num=0
        while(True):
            x,y=divmod(n,p)
            if y!=0:
                break
            n=x
            num+=1
        if num>0:
            r.append((p,num))
    if n>1:
        r.append((n,1))
    return r
mod=10**9+7
def add(a,b):
    return (a+b)%mod
def sub(a,b):
    return (a-b)%mod
def mul(a,b):
    return ((a%mod)*(b%mod))%mod
def pow(x,y):
    if y==0:
        return 1
    elif y==1:
        return x%mod
    elif y%2==0:
        return pow(x,y//2)**2 % mod
    else:
        return pow(x,y//2)**2 * x % mod
def div(a,b):
    return mul(a,pow(b,mod-2))
def fac(n):
    a=1
    for i in range(2,n+1):
        a=mul(a,i)
    return a

f=prime_factorization(m)
ans=1
for p in f:
    ans=mul(ans,fac(p[1]+n-1))
    ans=div(ans,fac(p[1]))
    ans=div(ans,fac(n-1))
print(ans)
n=input()
m=n
s=0
while true:
  q,mod=divmod(m,10)
  s+=mod
  m=q
  if q<=0:
    break
if n%s==0:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

n=int(input())
m=n
s=0
while True:
  q,mod=divmod(m,10)
  s+=mod
  m=q
  if q<=0:
    break
if n%s==0:
  print("Yes")
else:
  print("No")
N = int(input())
lis = [(input() + " " + str(i+1)).split() for i in range(N)]
 
lis = [k for k in lis]
 
lis.sort(key=lambda k: int(k[1]). reverse=True)
lis.sort(key=lambda k: k[0])
 
 
for i in lis:
    print(i[2])


### FIXED CODE ###

n=int(input())
l=list()
for i in range(n):
    s,p=input().split()
    l.append([s,int(p),i+1])
l.sort(key=lambda x:(x[0],-x[1]))
[print(k) for i,j,k in l]
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, K = map(int, input().split())
    if N < K:
        print(-1)
    elif K == N:
        edges = [(N, 1)]
        for i in range(1, N):
            edges.append((i, i + 1))
    elif K == N - 1:
        edges = [(N, 1)]
        for i in range(1, N):
            edges.append((i, i + 1))
        edges.append((2, N))
    else:
        cnt = 0
        edges = []
        for i in range(1, N + 1):
            for j in range(i + 1, N + 1):
                if i == 1 and cnt < K:
                    cnt += 1
                    continue
                else:
                    edges.append((i, j))

    print(len(edges))
    for a, b in edges:
        print(a, b)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, K = map(int, input().split())
    if (N - 1) * (N - 2) // 2 < K:
        print(-1)
        return
    else:
        edges = set()
        for i in range(2, N + 1):
            edges.add((1, i))

        cnt = (N - 1) * (N - 2) // 2
        for i in range(1, N):
            for j in range(i, N + 1):
                if i == j:
                    continue

                if cnt == K:
                    print(len(edges))
                    for a, b in edges:
                        print(a, b)
                    return

                if (i, j) not in edges:
                    cnt -= 1
                    edges.add((i, j))

        print(len(edges))
        for a, b in edges:
            print(a, b)
        return


if __name__ == "__main__":
    main()
#もし最初に与えられていたリストが昇順(done)

#1番目とn番目の文字列を消去したリストを作成する。そのリストが昇順ならまずは第一段階クリア
#そして最初に与えられた文字のリストで、(<一番最後の文字> - <一番最初の文字>　+1)なら成立する。

#実装すれば、勝ちなはず。

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



#初期リストを昇順に(done)
ascending_order = P.sort()



#1番目と一番最後を削除したリスト
Test_P = P[1:N-1]

#TestPの昇順
ascending_TestP = Test_P.sort()

Check = (abs((P[-1] + P[0]) +1)) 

if P == ascending_order:
    print("YES")
elif Test_P != ascending_TestP:
    print("NO")
else:
    print("YES")

### FIXED CODE ###

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

 
if (a+b)%2==0:
    print((a+b)//2)
else:
    print("IMPOSSIBLE")
import math
n=int(input())
infy=math.inf
arr=[int(x) for x in input().split()]
arr.append(0)
val=[infy]*(n+1)
val[0]=0
for i in range(0,n-1):
    val[i+1]=min(val[i+1],abs(arr[i+1]-arr[i])+val[i])
    val[i+2]=min(val[i+2],abs(arr[i+2]-arr[i])+val[i])

print(val[n-1])




### FIXED CODE ###

n=int(input())
infy=float('inf')
arr=[int(x) for x in input().split()]
arr.append(0)
val=[infy]*(n+1)
val[0]=0
for i in range(0,n-1):
    val[i+1]=min(val[i+1],abs(arr[i+1]-arr[i])+val[i])
    val[i+2]=min(val[i+2],abs(arr[i+2]-arr[i])+val[i])

print(val[n-1])
h,w,m=map(int,input().split())
lh=[0]*h
lw=[0]*w
l=[[0 for _ in range(w)] for _ in range(h)]
for i in range(m):
  h1,w1=map(int,input().split())
  l[h1-1][w1-1]=1
  lh[h1-1]+=1
  lw[w1-1]+=1
hmax=max(lh)
wmax=max(lw)
lh2=[]
lw2=[]
for i in range(h):
  if lh[i]==hmax:
    lh2.append(i)
for i in range(w):
  if lw[i]==wmax:
    lw2.append(i)
 
s=1
for m in lh2:
  for m2 in lw2:
    if l[m][m2]==0:
      s=0
      
print(hmax+wmax-s)

### FIXED CODE ###

n,x,t=map(int,input().split())
print(((n-1)//x+1)*t)
import sys
a, b, c, d = map(int, sys.stdin.readline().split())
li = [1]*a + [0]*b + [-1]*c
print(sum(li[0:d]))

### FIXED CODE ###

a, b, c, k = map(int,input().split())
if a > k:
  print(k)
elif a+b >= k:
  print(a)
else:
  print(a-(k-a-b))
x, y = map(int, input().split())

ans = "No"
i = 0
while i <= x:
  z = y - 2 * i
  if z == 0:
    ans = "Yes"
    break
  if z % ((x - i) * 4) == 0:
    ans = "Yes"
    break
  i += 1

print(ans)

### FIXED CODE ###

x, y = map(int, input().split())

ans = "No"
crane = 0
while crane <= x:
  turtle = x - crane
  if 2 * crane + 4 * turtle == y:
    ans = "Yes"
  crane += 1

print(ans)
import math

MOD = 1000000007
N = int(input())
A = list(map(int,input().split()))

LCM = A[0]
for i in range(0,N-1,1):
    LCM = LCM*A[i+1]//math.gcd(A[i+1],LCM)

### FIXED CODE ###

def lcm(X,Y):
    x=X
    y=Y
    if y>x:
        x,y=y,x
    while x%y!=0:
        x,y=y,x%y
    return X*Y//y

MOD = 1000000007
N = int(input())
A = list(map(int,input().split()))

LCM = A[0]
for i in range(0,N-1,1):
    LCM = lcm(LCM,A[i+1])
B = [0 for i in range(0,N,1)]
for i in range(0,N,1):
    B[i]= (LCM%MOD)*pow(A[i],MOD-2,MOD)%MOD

ans = 0
for i in range(0,N,1):
    ans = (B[i] + ans)%MOD

print(ans)
n = int(input())
d = {}
for i in range(n - 1):
  u, v, w = map(int, input().split())
  u -= 1
  v -= 1
  if u in d:
    d[u].append([v, w])
  else:
    d[u] = [[v, w]]
  if v in d:
    d[v] = [[u, w]]
  else:
    d[v] = [[u, w]]

rem = {}

for i in range(n):
  rem[i] = 1
  
ans = [0 for _ in range(n)]

def check(p, tmp):
  rem.pop(p)
  for n, w in d[p]:
    if n in rem:
      tmp = (tmp + w) % 2
      ans[n] = tmp
      check(n, tmp)
      
check(0, 0)

for res in ans:
  print(res)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

n = int(input())
d = {}
for i in range(n - 1):
  u, v, w = map(int, input().split())
  u -= 1
  v -= 1
  if u in d:
    d[u].append([v, w])
  else:
    d[u] = [[v, w]]
  if v in d:
    d[v].append([u, w])
  else:
    d[v] = [[u, w]]

rem = {}

for i in range(n):
  rem[i] = 1
  
ans = [0 for _ in range(n)]

def check(p, tmp):
  rem.pop(p)
  for n, w in d[p]:
    if n in rem:
      ntmp = (tmp + w) % 2
      ans[n] = ntmp
      check(n, ntmp)
      
check(0, 0)

for res in ans:
  print(res)
import scipy.special

def combination(n,r):
    return scipy.special.comb(n,r,exact=True)

mod=10**9+7
N,K=map(int,input().split())
B=K
R=N-K

for i in range(1,K+1):
    print(combination(R+1,i)*combination(B-1,i-1)%mod)

### FIXED CODE ###

from scipy.misc import comb

mod=10**9+7
N,K=map(int,input().split())
B=K
R=N-K

for i in range(1,K+1):
    print(comb(R+1,i,exact=True)*comb(B-1,i-1,exact=True)%mod)
n = int(input())
pl = list()
for i in range(n):
    pl.append(list(map(int, input().split())))

import math
lsum = 0
for i in range(n):
    for j in range(n):
        if i != j:
            a, b = pl[i]
            c, d = pl[j]
            lsum += math.sqrt((a-c) ** 2 + (b-d) ** 2)
print(lsum /(n)

### FIXED CODE ###

n = int(input())
pl = list()
for i in range(n):
    pl.append(list(map(int, input().split())))

import math
lsum = 0
for i in range(n):
    for j in range(n):
        if i != j:
            a, b = pl[i]
            c, d = pl[j]
            lsum += math.sqrt((a-c) ** 2 + (b-d) ** 2)
print(lsum /(n))
# D
import numpy as np

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

G = dict()
for i in range(N):
    G[i] = []

for _ in range(M):
    x, y = map(int, input().split())
    G[x].append(y)
    G[y].append(x)
    
res = 0
connec = 0
done_list = [0]*N

st = 0
while True:
    while st < N:
        if done_list[st] == 0:
            break
        st += 1

    if st == N:
        break

    queue = [st]
    conn = [a_list[st]]
    conn_ = [st]
    done_list[st] = 1
    connec += 1

    while len(queue) > 0:
        s = queue.pop()
        for t in G[s]:
            if done_list[t] == 0:
                done_list[t] = 1
                queue.append(t)
                conn.append(a_list[t])
                conn_.append(t)
                
    args = np.argsort(conn)
    res += conn[args[0]]
    a_list[conn_[args[0]]] = 2000000000

a_list.sort()

if connec == 1:
    print(0)
elif len(a_list) < 2*connec - 2:
    print('Impossible')
else:
    print(res + sum(conn_list[:(connec - 2)]))


### FIXED CODE ###

# D
import numpy as np

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

G = dict()
for i in range(N):
    G[i] = []

for _ in range(M):
    x, y = map(int, input().split())
    G[x].append(y)
    G[y].append(x)
    
res = 0
connec = 0
done_list = [0]*N

st = 0
while True:
    while st < N:
        if done_list[st] == 0:
            break
        st += 1

    if st == N:
        break

    queue = [st]
    conn = [a_list[st]]
    conn_ = [st]
    done_list[st] = 1
    connec += 1

    while len(queue) > 0:
        s = queue.pop()
        for t in G[s]:
            if done_list[t] == 0:
                done_list[t] = 1
                queue.append(t)
                conn.append(a_list[t])
                conn_.append(t)
                
    args = np.argsort(conn)
    res += conn[args[0]]
    a_list[conn_[args[0]]] = 2000000000

a_list.sort()

if connec == 1:
    print(0)
elif len(a_list) < 2*connec - 2:
    print('Impossible')
else:
    print(res + sum(a_list[:(connec - 2)]))
s = imput ()
if s [0] == s[1] or s[1] == s[2]:print('No')
else: print('Yes')

### FIXED CODE ###

S = input()
if S[0] == S[1] and S[1] == S[2]:
  print('No')
else: 
  print('Yes')
N, A, B, C, D = [int(i) for i in input().split()]
road = [i for i in list(input())]

for i in range(len(road)-1):
  if (road[i] == '#') & (road[i+1] == '#'):
    judge = 0
    break
  else:
    judge = 1
if judge == 1:
  if C < D:
    judge = 1
  else:
    for i in range(D-B+1):
      if (road[B+i-1] == '.') & (road[B+i] == '.') & (road[B+i+1] == '.'):
        judge = 1
        break
      else:
        judge = 0

if judge == 0:
  print("No")
else:
  print("Yes")

### FIXED CODE ###

N, A, B, C, D = [int(i) for i in input().split()]
road = [i for i in list(input())]

for i in range(D-A):
  if (road[A+i-1] == '#') & (road[A+i] == '#'):
    judge = 0
    break
  else:
    judge = 1
if judge == 1:
  if C < D:
    judge = 1
  else:
    for i in range(D-B+1):
      if (road[B+i-2] == '.') & (road[B+i-1] == '.') & (road[B+i] == '.'):
        judge = 1
        break
      else:
        judge = 0

if judge == 0:
  print("No")
else:
  print("Yes")
N =input()

flag = 0
for i in range(len(N)):
	if N[i] == "7":
		flag = 1
		break

if flag == 1:
	print("Yes")
else:
	print("No"

### FIXED CODE ###

N = input()

flag = 0
for i in range(len(N)):
	if N[i] == "7":
		flag = 1
		break

if flag == 1:
	print("Yes")
else:
	print("No")
l = []
ans_list = []

while True:
    e = int(input())
    if e == 0:
        #print('=========================')
        break
    else:
        l.append(e)

for e in l:
    ans = float('inf')
    for z in range(e):
        r1 = e - z ** 3
        if r1 >= 0:
            for y in range(r1+1):
                x = r1 - y ** 2
                if x >= 0:
                    s = z + y + x
                    ans = min(ans, s)
                else:
                    break
        else:
            break
    ans_list.append(ans)

for ans in ans_list:
    print(ans)


### FIXED CODE ###

while True:
    e = int(input())
    if e == 0:
        break
    z, ans = 0, float('inf')
    while z ** 3 <= e:
        r = e - z ** 3
        y = int(r ** 0.5)
        x = r - y ** 2
        ans = min(ans, x + y + z)
        z += 1
    print(ans)
N=int(input())
As=list(map(int, input().split()))
rejected=false
for A in As:
  if A%2==0:
    if A%3*(A%5)!=0:
      rejected=true
if rejected:
  print("DENIED")
else:
  print("APPROVED")

### FIXED CODE ###

N=int(input())
As=list(map(int, input().split()))
rejected=False
for A in As:
  if A%2==0:
    if A%3*(A%5)!=0:
      rejected=True
if rejected:
  print("DENIED")
else:
  print("APPROVED")
S=input()
money=700
for i in str.count('o'):
  money+=100

### FIXED CODE ###

S=input()
money=700
counter=0
while counter < S.count("o"):
  money+=100
  counter+=1
print(money)
N, M = map(int, input().split())
Hi = list(map(int,input().split(" ")))
path = [list[] for _ in range(M+1)]

for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    path[a].append(b)
    path[b].append(a)
    

goodT = 0
T = range(M+1)

for i, p in zip(T, path):
    good = 1
    if p == []:
        goodT += good
    else:
        for t in p:
            if Hi[i] <= Hi[t]:
                good = 0
        goodT +=good
        
print (goodT)

### FIXED CODE ###

N, M = map(int, input().split())
Hi = list(map(int,input().split(" ")))
#path = [list() for _ in range(M+1)]

Tallest = [0]*N

for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    Tallest[a] = max(Tallest[a], Hi[b])
    Tallest[b] = max(Tallest[b], Hi[a])

goodT = 0

for i in range(N):
    if Hi[i]>Tallest[i]:
        goodT +=1
    
print (goodT)
#coding: utf-8
input = input().split()
r = input[0]
g = input[1]
b = input[2]
x = r+g+b
if x%4==0:
  print('YES')
else:
  print('NO')

### FIXED CODE ###

#coding: utf-8
input = input().split()
r = input[0]
g = input[1]
b = input[2]
x = int(r+g+b)
if x%4==0:
  print('YES')
else:
  print('NO')
import sys
sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def main():
    h, w = [int(i) for i in input().split()]
    c_h, c_w = [int(i) for i in input().split()]
    d_h, d_w = [int(i) for i in input().split()]
    grid = [["#"] * (w + 2)]
    for _ in range(h):
        line = ["#"] + list(input()) + ["#"]
        grid.append(line)
    grid.append(["#"] * (w + 2))
    warp_count = [[float("inf")] * (w + 2) for _ in range(h + 2)]
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))

    def dfs(_h, _w, warp):
        warp_count[_h][_w] = min(warp, warp_count[_h][_w])
        # walk
        for _a, _b in directions:
            if grid[_h + _a][_w + _b] != "#" and warp_count[_h + _a][_w + _b] > warp:
                dfs(_h + _a, _w + _b, warp)
        # warp
        for x in range(-2, 3):
            for y in range(-2, 3):
                if (x, y) in directions:
                    continue
                elif x == 0 and y == 0:
                    continue
                if _h + x < 0 or _h + x > h or _w + y < 0 or _w + y > w:
                    continue
                if grid[_h + x][_w + y] == "#":
                    continue
                if warp_count[_h + x][_w + y] > warp + 1:
                    dfs(_h + x, _w + y, warp + 1)

    dfs(c_h, c_w, 0)
    if warp_count[d_h][d_w] == float("inf"):
        print(-1)
    else:
        print(warp_count[d_h][d_w])
    return


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import deque


def input():
    return sys.stdin.readline().strip()


def main():
    INF = 10**7
    h, w = [int(i) for i in input().split()]
    c_h, c_w = [int(i) for i in input().split()]
    d_h, d_w = [int(i) for i in input().split()]
    grid = [["#"] * (w + 2)]
    for _ in range(h):
        line = ["#"] + list(input()) + ["#"]
        grid.append(line)
    grid.append(["#"] * (w + 2))
    warp_count = [[INF] * (w + 2) for _ in range(h + 2)]
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
    warps = []
    for x in range(-2, 3):
        for y in range(-2, 3):
            if x == 0 and y == 0:
                continue
            if (x, y) not in directions:
                warps.append((x, y))

    stack = deque()
    warp_count[c_h][c_w] = 0
    stack.append((c_h, c_w, 0))

    while stack:
        _h, _w, warp = stack.pop()
        if warp > warp_count[_h][_w]:
            continue
        warp_count[_h][_w] = warp

        # walk
        for _a, _b in directions:
            if grid[_h + _a][_w + _b] != "#" and warp_count[_h + _a][_w + _b] > warp:
                stack.append((_h + _a, _w + _b, warp))

        # warp
        for x, y in warps:
            if _h + x < 0 or _h + x > h or _w + y < 0 or _w + y > w:
                continue
            elif grid[_h + x][_w + y] == "#":
                continue
            if warp_count[_h + x][_w + y] > warp + 1:
                stack.appendleft((_h + x, _w + y, warp + 1))

    if warp_count[d_h][d_w] == INF:
        print(-1)
    else:
        print(warp_count[d_h][d_w])
    return


if __name__ == "__main__":
    main()
a , b , c , k = map(int, input().split())

lst_1 = [1] * a
lst_2 = [0] * b
lst_3 = [-1] * c
lst_1.extend(lst_2)
lst_1.extend(lst_3)

ans = sum(lst_1[0:k])
print(ans)


### FIXED CODE ###

a , b , c , k = map(int, input().split())

if  a > k:
  print(k)
elif a + b >= k:
  print(a)
else:
  print(2*a - k + b)
import math

N = int(input())
ans = 0
mod = 10**9+7

kai = math.factorial(N)
i = 2

while kai == 0:
    if kai % i == 0:


#for i in range(1,kai+1):
#    if kai % i == 0:
#        ans += 1

print(ans % mod)


### FIXED CODE ###

N = int(input())
count = [1]*(N+1)
ans = 1
mod = 10**9+7

for i in range(2,N+1):
    wari = i
    for w in range(2,i+1):
        while wari % w == 0:
            count[w] += 1
            wari /= w

for i in range(N+1):
    ans *= count[i]

print(ans % mod)
N, M = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort()
BC = [0]*M
for i in range(M):
    BC[i] = tuple(map(int, input().split()))

BC.sort(key=lambda x: x[1], reverse=True)

idx, flg = 0, 0
for i in BC:
    B, C = i
    for i in range(B):
        if A[idx] >= C:
            flg = 1
            break
        else:
            A[idx] = C
            idx += 1
            B -= 1
            if B == 0:
                break
    if flg:
        break

print(sum(A))


### FIXED CODE ###

N, M = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort()
BC = [0]*M
for i in range(M):
    BC[i] = tuple(map(int, input().split()))

BC.sort(key=lambda x: x[1], reverse=True)

idx, flg = 0, 0
for i in BC:
    B, C = i
    for i in range(B):
        if idx > N-1:
            flg = 1
            break
        if A[idx] >= C:
            flg = 1
            break
        else:
            A[idx] = C
            idx += 1
            B -= 1
            if B == 0:
                break
    if flg:
        break

print(sum(A))
a, b = map(int, input().split())

if a == b:
  print("H")
else:
  print("D")

### FIXED CODE ###

a, b = map(str, input().split())
 
if a == b:
  print("H")
else:
  print("D")
N = input()
A = list(input())
intA = [int(s) for s in A]
j = 1
c = 0
while j == 1 :
    for i in range(len(intA)):
        if(intA[i]%2==1):
            j = 0
        else:
            c += 1
print(c)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
cau = 0
flag = True
while flag:
    for i in range(N):
        if A[i] % 2 == 1:
            flag = False
            break        
    if flag:
        for i in range(N):
            A[i] = A[i]/2
        cau += 1
print(cau)