Harryxun/stf_run huggingface dataset:
import bisect
import collections
import itertools


def getint(): return int(input())
def getints(): return list(map(int, input().split()))
def getint2d(rows): return [getints() for _ in range(rows)]
def getgrid(rows): return [input() for _ in range(rows)]
def array1d(n, value): return [value for _ in range(n)]
def array2d(n, m, value): return [array1d(m, value) for _ in range(n)]

class Graph:
    def __init__(self, node_count, edge_count):
        self.node_count = node_count
        self.lst = [-1 for _ in range(node_count)]
        self.nxt = [0 for _ in range(edge_count)]
        self.to = [0 for _ in range(edge_count)]
        self.m = 0

    def add_edge(self, u, v, w):  # bidirection weight
        m = self.m
        self.nxt[m], self.lst[u], self.to[m] = self.lst[u], m, (v, w)
        self.m += 1

    def traverse(self, u):
        m = self.lst[u]
        while m != -1:
            yield self.to[m]
            m = self.nxt[m]


n,q=getints()
values = [0]*n
gr = Graph(n,2*n)

for _ in range(n-1):
    a,b=getints()
    a,b=a-1,b-1
    gr.add_edge(a,b,1)
    gr.add_edge(b,a,1)

for _ in range(q):
    u, p=getints()
    values[u-1] += p

def distribute(u, par, prev):
    values[u] += prev
    for v, _ in gr.traverse(u):
        if v == par: continue
        distribute(v, u, values[u])

distribute(0, -1, 0)
print(" ".join(map(str, values)))

### FIXED CODE ###


import bisect
import collections
import itertools


def getint(): return int(input())
def getints(): return list(map(int, input().split()))
def getint2d(rows): return [getints() for _ in range(rows)]
def getgrid(rows): return [input() for _ in range(rows)]
def array1d(n, value): return [value for _ in range(n)]
def array2d(n, m, value): return [array1d(m, value) for _ in range(n)]

class Graph:
    def __init__(self, node_count, edge_count):
        self.node_count = node_count
        self.lst = [-1 for _ in range(node_count)]
        self.nxt = [0 for _ in range(edge_count)]
        self.to = [0 for _ in range(edge_count)]
        self.m = 0

    def add_edge(self, u, v, w):  # bidirection weight
        m = self.m
        self.nxt[m], self.lst[u], self.to[m] = self.lst[u], m, (v, w)
        self.m += 1

    def traverse(self, u):
        m = self.lst[u]
        while m != -1:
            yield self.to[m]
            m = self.nxt[m]


n,q=getints()
values = [0]*n
gr = Graph(n,2*n)

for _ in range(n-1):
    a,b=getints()
    a,b=a-1,b-1
    gr.add_edge(a,b,1)
    gr.add_edge(b,a,1)

for _ in range(q):
    u, p=getints()
    values[u-1] += p

def distribute(u, par, prev):
    stk = []
    stk.append((u, par, 0))
    while stk:
        u,par,prev=stk[-1]
        stk.pop()
        values[u] += prev
        for v, _ in gr.traverse(u):
            if v == par: continue
            stk.append((v,u,values[u]))

distribute(0, -1, 0)
print(" ".join(map(str, values)))
N = int(input())
num_list = list(map(int, input().split()))
num_list = sorted(num_list)

for i in range(len(num_list)):
  if num_list[i] == num_list[i+1]:
    print('NO')
    exit()
print('YES')

### FIXED CODE ###

N = int(input())
num_list = list(map(int, input().split()))
num_list = sorted(num_list)

for i in range(len(num_list)):
  if i == N-1:
    print('YES')
  elif num_list[i] == num_list[i+1]:
    print('NO')
    exit()
import math

n = int(input())
ans = []
for x in range(1, math.ceil(n**(1/2))+1):
    for y in range(1, math.ceil(n**(1/2))+1):
        for z in range(1, math.ceil(n**(1/2))+1):
            ans.append(x**2 + y**2 + z**2 + x*y + y*z + z*x)
ans.sort()
for i in range(1, n+1):
    tmp = 0
    for x in ans:
        if x == i:
            tmp += 1
        elif x > i:
            print(tmp)
            break

### FIXED CODE ###

L, R, d = map(int, input().split())
ans = 0
for x in range(L, R+1):
    if x % d == 0:
        ans += 1

print(ans)
n,m=map(int, input().split()) 
s=list(input())

# dp[i]=iに行くのに最短の手数
dp=[0]*(n+1)
ans=0
now=n
count=0
flag=True
ans=[]
for i in range (n+1):
    if flag==False:
        break
    for j in range(m,0,-1):

        if s[now-j]!='1':
            if now-j<=0:
                ans.append(now)
                flag=False
                break
            else:
                ans.append(j)
                count+=1
                now-=j
                break
        else:
            if j==1:
                print(-1)
                exit()
            continue
        

ans.reverse()

print(*ans)
        

                
            
        
        
        

### FIXED CODE ###

n,m=map(int, input().split()) 
s=list(input())

# dp[i]=iに行くのに最短の手数
dp=[0]*(n+1)
ans=0
now=n
count=0
flag=True
ans=[]
for i in range(10**11):
    if flag==False:
        break
    for j in range(m,0,-1):
        if now-j<=0:
            ans.append(now)
            flag=False
            break
        elif s[now-j]!='1':
            ans.append(j)
            count+=1
            now-=j
            break
        else:
            if j==1:
                print(-1)
                exit()
            continue
        

ans.reverse()

print(*ans)
import sys
sys.setrecursionlimit(100000)
H,N = (int(x) for x in input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
mem = [0] * H
def dp(rem):
    global mem
    if mem[rem-1]:
        return mem[rem-1]
    elif rem <= 0:
        return 0
    else:
        a = min([dp(rem-AB[i][0]) + AB[i][1] for i in range(N)])
        mem[rem-1] = a
        return a
print(dp(H))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
H,N = (int(x) for x in input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
mem = [0] * H
def dp(rem):
    global mem
    if rem <= 0:
        return 0
    elif mem[rem-1]:
        return mem[rem-1]
    else:
        a = min([dp(rem-AB[i][0]) + AB[i][1] for i in range(N)])
        mem[rem-1] = a
        return a
print(dp(H))
i = input()
sp = i.spint()

multid = sp[0] * sp[1]

if multid % 2 == 0:
    print("Even")
else:
    print("Odd")


### FIXED CODE ###

i = input()
sp = i.split()

multid = int(sp[0]) * int(sp[1])

if multid % 2 == 0:
    print("Even")
else:
    print("Odd")
N, M = [int(x) for x in input().split()]

print(M * 1900+(N-M)*100)*(2**M)




### FIXED CODE ###

N, M = [int(x) for x in input().split()]

print((M * 1900+(N-M)*100)*(2**M))
n = int(input())
ar = list(map(int, input().split()))

assert 3 <= n <= 10
assert len(ar) == n
assert (1 <= min(ar)) and (max(ar) <= 100)

if max(ar) < sum(ar) - max(ar):
  print("Yes")
else:
  print("No")



### FIXED CODE ###

T, X = map(int, input().split())

print(float(T)/X)
L = []
for i in range(int(input)):
  l.append(input())
for j in ['AC','WA','TLE','RE']:
  print(L.count(j))

### FIXED CODE ###

L = []
for i in range(int(input())):
  L.append(input())
for j in ['AC','WA','TLE','RE']:
  print(j,'x',L.count(j))
N = input()
a = N - N//2
print(a / N)

### FIXED CODE ###

N = float(input())
a = N - N//2
print(a / N)
from collections import Counter
n = int(input())
v = list(map(int,input().split()))
odd = v[::2 ]
even = v[1::2]
# def count(aaa):
#     if len(set(aaa))!=1:
#         aaa_max = Counter(aaa).most_common(1)[0][1]
#         aaa_min = len(aaa)-aaa_max
#         most_aaa = Counter(aaa).most_common(1)[0][0]
#     else:
#         aaa_min = 0
#         most_aaa = set(aaa)[0]
#     return int(aaa_min),most_aaa
if len(set(v))==1:
    print(int(n/2))
else:
    if len(set(even))!=1:
        even_max = Counter(even).most_common(1)[0][1]
        even_min = len(even)-even_max
        even_most = Counter(even).most_common(1)[0][0]
    else:
        aaa_min = 0
        even_most = even[0]
    if len(set(odd))!=1:
        odd_most = Counter(odd).most_common()
        for key in odd_most:
            if key[0]!=even_most:
                odd_max = key[1]
                odd_min = len(odd)-odd_max
                break
    else:
        odd_most = odd[0]
        if odd_most != even_most:
            odd_min = 0
        else:
            odd_min = len(odd)
    print(even_min+odd_min)

### FIXED CODE ###

from collections import Counter
 
n = int(input())
v = list(map(int,input().split()))
ac = Counter(v[::2]).most_common(2)
bc = Counter(v[1::2]).most_common(2)


if ac[0][0] != bc[0][0]:           
    ans =  n - ac[0][1] - bc[0][1] 
else:                               
    if len(bc) == 1 or len(ac) == 1:
        ans = n // 2
    else: 
        ans = n - max(ac[0][1] + bc[1][1], ac[1][1] + bc[0][1])
print(ans)
N=int(input())
S=['x']*N
for i in range(N):
    S[i]=input()
poll=[]
S_set=list(set(S))
for i in range(len(S_set)):
    poll.append((S.count(S_set[i]),S_set[i]))
poll=sorted(poll)[::-1]
x=poll[0][0]
i=0
ans=[]
while True:
    if x==poll[i][0]:
        ans.append(poll[i][1])
        i+=1
    else:
        break
ans=sorted(ans)
for i in range(len(ans)):
    print(ans[i])

### FIXED CODE ###

N=int(input())
S=[input() for i in range(N)]
S=sorted(S)
cnt=1
max_cnt=1
ans=[S[0]]
for i in range(N-1):
    if S[i]==S[i+1]:
        cnt+=1
    else:
        cnt=1
    if cnt==max_cnt:
        ans.append(S[i+1])
    if cnt>max_cnt:
        max_cnt=cnt
        ans=[S[i+1]]
ans=sorted(ans)
for i in ans:
    print(i)
A,B = map(int,input().split())

k = (A + B) / 2

answer = 0
if A - k >= 0 and -B + k <=0 :
	answer = 1
    
elif -A + K <=0 and B - k >= 0 :
	answer = 1 
    
if anaswer == 1 and (A + B) % 2 == 0  :
	print(k)
else :
	print("IMPOSSIBLE")

### FIXED CODE ###

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

k = (A + B) / 2

answer = 0

if A != B and (A + B) % 2 == 0 and (A - k) * (B - k) < 0:
	print(int(k))
else:
	print("IMPOSSIBLE")
n=int(input())
a=list(map(int,input().split()))
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
a.sort()
a=a[::-1]
res=[a[0]]
for i in range(1,n):
    for t in res:
        x=gcd(t,a[i])
        if x!=t:
            res.append(x)
res.sort()
print(res[1])

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
a.sort()
x=[a[0]]
for i in range(1,n):
    x.append(gcd(x[-1],a[i]))
y=[a[-1]]
for i in range(2,n+1):
    y.append(gcd(y[-1],a[-i]))
y=y[::-1]
res=[x[-2],y[1]]
for i in range(n-2):
    res.append(gcd(x[i],y[i+2]))
print(max(res))
N = int(input())
l = list()

for i in range(N):
  n = int(input())
  l.append(n)
 
m = max(l)
SUM = sum(l) - m
 
if m > SUM:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

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

m = max(l)
SUM = sum(l) - m

if m < SUM:
  print('Yes')
else:
  print('No')
import sys

import numba as nb

input = sys.stdin.readline
INF = float("inf")


@nb.njit
def solve(N, K, h):
    dp = [0] * N
    for i in range(1, N):
        min_cost = INF
        for k in range(1, min(K + 1, i + 1)):
            cost = dp[i - k] + abs(h[i] - h[i - k])
            if cost < min_cost:
                min_cost = cost
        dp[i] = min_cost
    return dp[-1]


def main():
    N, K = map(int, input().split())
    h = tuple(map(int, input().split()))

    ans = solve(N, K, h)
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline
INF = float("inf")


def main():
    N, K = map(int, input().split())
    h = list(map(int, input().split()))

    dp = [0] * N
    for i in range(1, N):
        min_cost = INF
        for k in range(1, min(K + 1, i + 1)):
            cost = dp[i - k] + abs(h[i] - h[i - k])
            if cost < min_cost:
                min_cost = cost
        dp[i] = min_cost

    ans = dp[-1]
    print(ans)


if __name__ == "__main__":
    main()
S = int(input())

A = [0,0,1]
for i in range(3,S):
  A += [A[i-1] + A[i-3]]
print(A[i])

### FIXED CODE ###

S = int(input())
 
A = [0,0,1]
if S == 1 or S == 2:
  print(0)
elif S == 3:
  print(1)
else:
  for i in range(3,S):
    A += [A[i-1] + A[i-3]]
  print(A[i] % (10 ** 9 + 7))
N, T = map(int, input().split())
ct = [[] for _ in range(N)]
for i in range(N):
    ct[i] = list(map(int, input().split()))
cost =[]
for v in ct:
    if v[1] <= T:
        cost.append(v)
for i, v in enumerate(cost):
    if i == 0:
        least = v[0]
    else:
        if v[0] <= least:
            least = v[0]
if least <= T:
    print(least)
else:
    print('TLE')

### FIXED CODE ###

N, T = map(int, input().split())
ct = [[] for _ in range(N)]
for i in range(N):
    ct[i] = list(map(int, input().split()))
cost =[]
for v in ct:
    if v[1] <= T:
        cost.append(v)
if len(cost) <1:
    print('TLE')
else:
    for i, v in enumerate(cost):
        if i == 0:
            least = v[0]
        else:
            if v[0] <= least:
                least = v[0]
    print(least)
import math
input1 = list(map(int, (input().split())))

a = input1[0]
b = input1[1]

a1 = math.ceil(a / 0.08)
a2 = math.ceil((a+1) / 0.08)
b1 = math.ceil(b / 0.1)
b2 = math.ceil((b+1) / 0.1)
# alist = list(range(a1, a2))
# blist = list(range(b1, b2))

# print(alist)
# print(blist)
for i in range(a1, a2):
    for j in range(b1, b2):
        if i == j:
            print(i)
            # print(i * 0.08)
            # print(i * 0.1)
            exit(1)
print(-1)


### FIXED CODE ###

import math
input1 = list(map(int, (input().split())))

a = input1[0]
b = input1[1]

a1 = math.ceil(a / 0.08)
a2 = math.ceil((a+1) / 0.08)
b1 = math.ceil(b / 0.1)
b2 = math.ceil((b+1) / 0.1)
# alist = list(range(a1, a2))
# blist = list(range(b1, b2))

# print(alist)
# print(blist)
for i in range(a1, a2):
    for j in range(b1, b2):
        if i == j:
            print(i)
            # print(i * 0.08)
            # print(i * 0.1)
            exit(0)
print(-1)
n,m=map(int, input().split())
ac,wa=0,0
if m==0:
    print(ac,wa)
else: #一度飛ばして新たな問題を解いたうえで戻ってくる場合があるのか？
    l=[0]*n #正解処理の配列
    r=[0]*n #誤答カウンター
    for i in range(m):
        pa,s=map(str, input().split())
        p=int(pa)
        if l[p-1]==0 and s=='AC': #初正解時の処理
            l[p-1]=1
            ac+=1
        elif s=='WA': #誤答時の処理
            r[p-1]+=1
        else:
            continue
    for i in range(n):
        if l[i]==1:
            wa+=w[i]
        else:
            continue
    print(ac,wa)

### FIXED CODE ###

n,m=map(int, input().split())
ac,wa=0,0
if m==0:
    print(ac,wa)
else: #一度飛ばして新たな問題を解いたうえで戻ってくる場合があるのか？
    l=[0]*n #正解処理の配列
    r=[0]*n #誤答カウンター
    for i in range(m):
        pa,s=map(str, input().split())
        p=int(pa)
        if l[p-1]==0 and s=='AC': #初正解時の処理
            l[p-1]=1
            ac+=1
        elif l[p-1]==0 and s=='WA': #誤答時の処理
            r[p-1]+=1
        else:
            continue
    for i in range(n):
        if l[i]==1:
            wa+=r[i]
        else:
            continue
    print(ac,wa)
n, d = map(int, input().split())
X = []
for _ in range(n):
    X.append([int(x) for x in input().split()])
ans = 0
for i in range(n - 1):
  for j in range(i + 1, n):
    s = sum((X[i][d] - X[j][d])**2 for d in range(d))
      if (s ** .5).is_integer():
        ans += 1
print(ans)


### FIXED CODE ###

n, d = map(int, input().split())
X = []
for _ in range(n):
    X.append([int(x) for x in input().split()])
ans = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        s = sum((X[i][d] - X[j][d])**2 for d in range(d))
        if any(k**2 == s for k in range(1000)):
            ans += 1
print(ans)
N = int(input())
A = int(input())
B = int(input())

if N == 1:
    print('Hello World')
else:
    print(A+B)

### FIXED CODE ###

N = int(input())

if N == 1:
    print('Hello World')
else:
    A = int(input())
    B = int(input())
    print(A+B)
n=int(input())
arr=[int(x) for x in input().split()]
pairs = []
for i in range(n):
    for j in range(i+1, n):
        if arr[i] > arr[j]:
            pairs.append([arr[i], arr[j]])
        else:
            pairs.append([arr[j], arr[i]])
print(pairs)
m = 0
max_index = -1
for index, pair in enumerate(pairs):
    cur = comb(pair[0], pair[1])
    print(cur)
    if cur > m:
        m = cur
        max_index = index
res = pairs[max_index]
print(res[0], res[1])

### FIXED CODE ###

input()
arr=sorted(int(x)for x in input().split())
m=arr[-1]
print(m,min(arr,key=lambda x:abs(m-x*2)))
N = 0
try:
  N = int(input())
except:
  pass
if N == 0:
  print(0)
else:
  print(((N - 1) / 1000) + 1) * 1000 - N)

### FIXED CODE ###

N = 0
try:
  N = int(input())
except:
  pass
if N == 0:
  print(0)
else:
  print((((N - 1) // 1000) + 1) * 1000 - N)
from collections import Counter
n = input()
s = [''.join(sorted(input())) for i in range(n)]
d = Counter(s)
count = 0
for i in d.values():
  if i !=1:
    count+=i
print(count)

### FIXED CODE ###

n = int(input())
d = dict()
for i in range(n):
  S = ''.join(sorted(list(input())))
  if S in d.keys():
    d[S] +=1
  else:
    d[S] = 1
 
ans = 0
for i in d.values():
  ans += i*(i-1)//2
print(ans)
weeks = {'MON': '1', 'TUE': '2',
          'WED': '3', 'THU': '4',
          'FRI': '5', 'SAT': '6',
          'SUN': '0'
         }
  s = input()
  print(7-int(weeks.get(s)))

### FIXED CODE ###

weeks = {'MON': '1', 'TUE': '2', 'WED': '3', 'THU': '4', 'FRI': '5', 'SAT': '6', 'SUN': '0'}
s = input()
print(7-int(weeks.get(s)))
import sys,collections

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[list(S()) for _ in range(h)]

  ans=0
  _visited=[[-1 for __ in range(w)] for _ in range(h)]
  q=collections.deque()
  for i in range(h):
    for j in range(w):
      if field[i][j]=='#':
        continue
      q.append((i,j,0))
      visited=copy.deepcopy(_visited)
      while len(q)>0:
        y,x,c=q.popleft()
        visited[y][x]=c

        for dy,dx in ((-1,0),(0,1),(1,0),(0,-1)):
          ny=y+dy
          nx=x+dx
          if 0<=ny<h and 0<=nx<w:
            if field[ny][nx]=='#':
              continue
            if visited[ny][nx]!=-1:
              continue
            q.append((ny,nx,c+1))
      ans=max(ans,c)
  return ans

# main()
print(main())


### FIXED CODE ###

import sys,collections

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  visited=[[-1 for __ in range(w)] for _ in range(h)]
  q=collections.deque()
  for i in range(h):
    for j in range(w):
      if field[i][j]=='#':
        continue
      q.append((i,j))
      for _i in range(h):
        for _j in range(w):
          visited[_i][_j]=-1
      visited[i][j]=0
      _ans=0
      while q:
        y,x=q.popleft()

        for dy,dx in ((-1,0),(0,1),(1,0),(0,-1)):
          ny=y+dy
          nx=x+dx
          if not 0<=ny<h:
            continue
          if not 0<=nx<w:
            continue
          if field[ny][nx]=='#':
            continue
          if visited[ny][nx]!=-1:
            continue
          _ans=visited[y][x]+1
          visited[ny][nx]=_ans
          q.append((ny,nx))
      ans=max(ans,_ans)
  return ans

# main()
print(main())
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))


#処理内容
def main():
	N, T = getlist()
	K = []
	for i in range(N):
		A, B = getlist()
		K.append([A, B])
	DP = [[0 for i in range(T)] for j in range(N + 1)]
	for i in range(N):
		W, V = K[i][0], K[i][1]
		for j in range(T):
			if j < W:
				DP[i + 1][j] = DP[i][j]
			else:
				DP[i + 1][j] = max(DP[i][j], DP[i][j - W] + V)
	ans = DP[-1][-1]
	use = [0] * N
	Y = T - 1
	for i in range(N):
		if DP[N - i][Y] != DP[N - i - 1][Y]:
			use[N - 1 - i] = 1
			Y -= K[-1 - i][0]
	lis = []
	for i in range(N):
		if use[i] == 0:
			lis.append(K[i][1])
	lis = sorted(lis)
	ans += lis[-1]
	print(ans)



if __name__ == '__main__':
	main()

### FIXED CODE ###

#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))


#処理内容
def main():
	N, T = getlist()
	K = []
	for i in range(N):
		A, B = getlist()
		K.append([A, B])
	DP = [[0 for i in range(T)] for j in range(N + 1)]
	for i in range(N):
		W, V = K[i][0], K[i][1]
		for j in range(T):
			if j < W:
				DP[i + 1][j] = DP[i][j]
			else:
				DP[i + 1][j] = max(DP[i][j], DP[i][j - W] + V)
	ans = DP[-1][-1]
	use = [0] * N
	Y = T - 1
	for i in range(N):
		if DP[N - i][Y] != DP[N - i - 1][Y]:
			use[N - 1 - i] = 1
			Y -= K[-1 - i][0]
	lis = []
	for i in range(N):
		if use[i] == 0:
			lis.append(K[i][1])
	lis = sorted(lis)
	if len(lis) >= 1:
		ans += lis[-1]
	print(ans)

if __name__ == '__main__':
	main()
A,B,C,K = map(int,input().split())

L = [1] * A + [0] * B + [-1] * C

ans = 0

AB = A + B

if AB > K:
  print(A)
else:
  print(A + (K - AB) * -1)

### FIXED CODE ###

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

aa = min(a,k)
bb = min(b,k - aa)
cc = min(c,k - aa - bb)

print(aa - cc)
#!/usr/bin/env python3
from collections import defaultdict

(n, ), *p = [[*map(int, i.split())] for i in open(0)]
d = defaultdict(int)
for i in range(n):
    for j in range(n):
        if i != j:
            d[(p[i][0] - p[j][0], p[i][1] - p[j][1])] += 1
print(n - max(d.values()))


### FIXED CODE ###

#!/usr/bin/env python3
from collections import defaultdict

(n, ), *p = [[*map(int, i.split())] for i in open(0)]
d = defaultdict(int)
for i in range(n):
    for j in range(n):
        if i != j:
            d[(p[i][0] - p[j][0], p[i][1] - p[j][1])] += 1
print(n*(n<2) or n - max(d.values()))
n, m = map(int, input().split())

d={}

for i in range(m):
    s, c = map(int, input().split())
    if s == 1 and c == 0:
        print(-1)
        eixt()
    elif s not in d:
        d[s] = c
    else:
        if d[s] != c:
            print(-1)
            exit()
if 1 not in d:
    d[1] = 1
for i in range(2, n+1):
    if i not in d:
        d[i] = 0
ans = 0
for i in range(1, n+1):
    ans += d[i] * pow(10, n-i)
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())

d={}

for i in range(m):
    s, c = map(int, input().split())
    if s == 1 and c == 0 and n != 1:
        print(-1)
        exit()
    elif s not in d:
        d[s] = c
    else:
        if d[s] != c:
            print(-1)
            exit()
if 1 not in d and n != 1:
    d[1] = 1
if 1 not in d and n == 1:
    d[1]=0
    
for i in range(2, n+1):
    if i not in d:
        d[i] = 0
ans = 0
for i in range(1, n+1):
    ans += d[i] * pow(10, n-i)
print(ans)
a = int(input())
# スペース区切りの整数の入力
b = map(int, input().split())


//a = 4
//b=[5, 6, 8, 10]

c = len(b)
d = 0


while c == len(b):
  c=0
  for i in b:
    if b %2 == 0:
      c +=1
  if(c == len(a)):
    d += 1
    b = [b /2 for i in b]
print (d)
   




### FIXED CODE ###


a = int(input())
# スペース区切りの整数の入力
b = input().split()
b = [int(i) for i in b]

c = len(b)
d = 0


while c == len(b):
  c=0
  for i in b:
    if i %2 == 0:
      c +=1
  if(c == len(b)):
    d += 1
    b = [i/2 for i in b]
print (d)
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
 

N, Q = map(int, input().split())

T = [[]for i in range(N)]

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

X = [0 for i in range(N)]
for i in range(Q):
    p, x = map(int, input().split())
    X[p-1] += x

ans = [X[i] for i in range(N)]

def dfs(x, p):
    for j in range(len(T[x])):
        if j == p:
            continue
        ans[T[x][j]] += ans[x]
        dfs(T[x][j])

dfs(0)

for i in range(N):
    print(ans[i], end =" ")


### FIXED CODE ###

N, Q = map(int, input().split())

F = [0 for i in range(N)]
T = [[]for i in range(N)]

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

X = [0 for i in range(N)]
for i in range(Q):
    p, x = map(int, input().split())
    X[p-1] += x

ans = [X[i] for i in range(N)]
for i in range(N):
    F[i] = 1
    for j in range(len(T[i])):
        if F[T[i][j]] == 1:
            continue
        ans[T[i][j]] += ans[i]

for i in range(N):
    print(ans[i], end =" ")