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

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

tmp = []
MA = 0
for i in range(N - K + 1):
    M = 0
    t = []
    for j in range(K):
        M += P[i + j]
        t.append(P[i + j])
    
    if M > MA:
        tmp = t
        MA = M
    # elif M == MA:
    #     tmp.append(t)
    #     MA = M


    # print(M)
    # print(i)
# print(tmp)
ans = 0
for t in tmp:
    ans += t * (t + 1) / (2 * t)
print("{:.12f}".format(ans))

### FIXED CODE ###

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

INDEX = 0
total = 0
for i in range(K):
    total += P[i]

tmp = total
for i in range(N - K):
    tmp = tmp - P[i] + P[i + K]
    
    if tmp > total:
        total = tmp
        INDEX = i+1


# MA = 0
# for i in range(N - K + 1):
#     M = 0
#     for j in range(K):
#         M += P[i + j]
    
#     if M > MA:
#         MA = M
#         INDEX = i

ans = 0
for i in range(K):
    ans += P[i+INDEX] * (P[i+INDEX]+1) / (2*P[i+INDEX])

print("{:.12f}".format(ans))
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort()
def binary_search(list, item):
    low = 0
    high = len(list) - 1
    mid = (low + high) //2
    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            #return mid
            break
        if guess > item:
            high = mid -1
        else:
            low = mid + 1

    if mid < len(list):
      while item >= list[mid]:
        mid += 1
        if mid == len(list):
          break
    #return None
    return len(list) - mid

from bisect import insort
bit = [L[0]+L[1]]
ans = 0
for k in range(2, N):
  ans += binary_search(bit, L[k])
  for j in range(k):
    insort(bit, L[j]+L[k])

print(ans)  

### FIXED CODE ###

# Binary Indexed Tree (Fenwick Tree)
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)


N = int(input())
L = list(map(int, input().split()))
L.sort()
bit = BIT(L[-1]*2+1)
bit.add(L[0]+L[1], 1)
total = 1
ans = 0
for k in range(2, N):
  ans += total - bit.sum(L[k])
  for j in range(k):
    bit.add(L[j]+L[k], 1)
    total += 1

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

R, G, B, N = map(int, input().split())

cnt = 0

for r in range(3001):
    if r*R > N:
        break
    for g in range(3001):
        if r*R + g*G > N:
            break
        diff = N - (r*R + g*G)
        if divmod(diff, B)[1] == 0:
            cnt += 1

print(cnt)


### FIXED CODE ###

R, G, B, N = map(int, input().split())

cnt = 0
r, g, b = 0, 0, 0

while r*R <= N:
    tank = N - r*R
    while True:
        if divmod(tank, B)[1] == 0:
            cnt += 1
        tank -= G
        if tank < 0:
            break
    r += 1

print(cnt)
### BUGGY CODE ###

N,Q = list(map(int,input().split()))
S = input()
for i in range(Q):
	f,t = list(map(int,input().split()))
	print(S[f-1:t].count('AC'))


### FIXED CODE ###

N,Q = list(map(int,input().split()))
S = input()
sums = [0]
for i in range(len(S)):
	if i == 0:
		continue
	sums.append(sums[i-1])
	if S[i-1]+S[i] == 'AC':
		sums[i] += 1

for i in range(Q):
	f,t = list(map(int,input().split()))
	print(sums[t-1]-sums[f-1])
### BUGGY CODE ###

import copy
def calc(n):
    d = copy.deepcopy(h)
    d = [dd - (b * n) for dd in d if (dd - (b*n)) > 0]
    a_num = sum([dd // (a - b) if (dd % (a - b) == 0) else (dd // (a - b)) + 1 for dd in d])
    if a_num <= n:
        return True
    return False

n, a, b = map(int, input().split())
h = []
for _ in range(n):
    h.append(int(input()))
ans = 0


left = 1
right = (max(h) + 1) // (b)
middle = (left + right) // 2
middle_1 = middle - 1
calc_middle = calc(middle)
calc_middle_1 = calc(middle_1)
while not ((calc_middle) & (not calc_middle_1)):
    if not calc_middle:
        left = middle
        middle = (left + right) // 2
        middle_1 = middle - 1
    else:
        right = middle
        middle = (left + right) // 2
        middle_1 = middle - 1
    calc_middle = calc(middle)
    calc_middle_1 = calc(middle_1)
print(middle)

### FIXED CODE ###

def calc(n):
    damage = (b * n)
    d = [max(dd - damage, 0) for dd in h]
    a_num = 0
    for i in range(len(d)):
        a_num += max(0, 1 + (d[i]-1) // (a - b))
    if a_num <= n:
        return True
    return False

n, a, b = map(int, input().split())
h = []
for _ in range(n):
    h.append(int(input()))
ans = 0
h.sort()

left = 0
right = 10000000000

while (right - left) > 1:
    middle = (left + right) // 2
    if calc(middle):
        right = middle
    else:
        left = middle
print(right)
### BUGGY CODE ###

import collections

n = int(input())
a = list(map(int,input().split()))
s = sum([i*(i-1)//2 for i in collections.Counter(a).values()])

for j in a:
    print(s-a.count(j)+1) 

### FIXED CODE ###

import collections

n = int(input())
a = list(map(int,input().split()))
d = collections.Counter(a)
s = sum([i*(i-1)//2 for i in d.values()])

for j in a:
    print(s-d[j]+1)
### BUGGY CODE ###

def chmax(dp, i, x):
  if dp[i] < x:
    dp[i] = x
    return True
  return False

n, W = map(int, input().split())
dp = [-10**9]*(W+1)
dp[0] = 0
for i in range(n):
  w, v = map(int, input().split())
  for i in range(W-w,-1,-1):
    dp[i+w] = max(dp[i+w], dp[i] + v) 
print(max(dp))

### FIXED CODE ###

n,W = map(int, input().split())
l = [dict() for i in range(n+1)]
l[0][0] = 0
for i in range(1,n+1):
  w,v = map(int, input().split())
  l[i] = l[i-1].copy()
  l[i][w] = max(l[i].get(w,0),v)
  for x in l[i-1]:
    if x+w <= W:
      l[i][x+w] = max(l[i].get(x+w,0),l[i-1][x] + v)
print(max(l[n].values()))
### BUGGY CODE ###

#??????????????????
import heapq
def SME(start,end):
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        if None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    D.add(idx)
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in C.difference(D):
        if i < L:
            ANS[i] = min(Whole[:i+1])
        else :
            ANS[i] = min(Whole[i+1-L:i+1])
    return ANS
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
A = []
C = set([i for i in range(N)])
D = set([])
parameter = 0.99
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

s = input()
t = input()

inf = pow(10, 4)
dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
key = [[0]*(len(t)+1) for _ in range(len(s)+1)]
for i in range(len(s)+1):
  for j in range(len(t)+1):
    if i == 0 and j == 0:
      continue
    if i == 0:
      dp[i][j] = dp[i][j-1]
      continue
    if j == 0:
      dp[i][j] = dp[i-1][j]
      continue
    if s[i-1] == t[j-1]:
      dp[i][j] = dp[i-1][j-1] + 1
      key[i][j] = (i-1)*inf+(j-1)
    else:
      if dp[i-1][j] > dp[i][j-1]:
        dp[i][j] = dp[i-1][j]
        key[i][j] = key[i-1][j]
      else:
        dp[i][j] = dp[i][j-1]
        key[i][j] = key[i][j-1]

ans = []
i, j = key[len(s)][len(t)]//inf, key[len(s)][len(t)]%inf
while True:
  if s[i] == t[j]:
    ans.append(s[i])
  if i == 0 or j == 0:
    break
  i, j = key[i][j]//inf, key[i][j]%inf

ans.reverse()
print("".join(ans))

### FIXED CODE ###

s = input()
t = input()

inf = pow(10, 4)
dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
key = [[0]*(len(t)+1) for _ in range(len(s)+1)]
for i in range(len(s)+1):
  for j in range(len(t)+1):
    if i == 0 and j == 0:
      continue
    if i == 0:
      dp[i][j] = dp[i][j-1]
      continue
    if j == 0:
      dp[i][j] = dp[i-1][j]
      continue
    if s[i-1] == t[j-1]:
      dp[i][j] = dp[i-1][j-1] + 1
      key[i][j] = (i-1)*inf+(j-1)
    else:
      if dp[i-1][j] > dp[i][j-1]:
        dp[i][j] = dp[i-1][j]
        key[i][j] = key[i-1][j]
      else:
        dp[i][j] = dp[i][j-1]
        key[i][j] = key[i][j-1]

ans = []
i, j = key[len(s)][len(t)]//inf, key[len(s)][len(t)]%inf
while True:
  if s[i] == t[j]:
    ans.append(s[i])
  if i == 0 or j == 0:
    break
  i, j = key[i][j]//inf, key[i][j]%inf

ans.reverse()
print("".join(ans))
### BUGGY CODE ###

from functools import reduce
import functools
import fractions
 
@functools.lru_cache(maxsize=128)
def gcd(*numbers):
  return reduce(gcd_, numbers)
  # return reduce(fractions.gcd, numbers)

@functools.lru_cache(maxsize=128)
def gcd_(a, b):
  if (b == 0):
    return a
  return gcd(b, a % b)
 
sum = 0
K = int(input())
 
for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      sum += gcd(i,j,k)
      
print(sum)


### FIXED CODE ###

from functools import reduce
import functools
import fractions
 
@functools.lru_cache(maxsize=None)
def gcd(*numbers):
  return reduce(gcd_, numbers)

@functools.lru_cache(maxsize=None)
def gcd_(a, b):
  if (b == 0):
    return a
  return gcd(b, a % b)
 
sum = 0
K = int(input())
 
for i in range(1,K+1):
  for j in range(i,K+1):
    for k in range(j,K+1):
      if (i == j) & (j == k):
        sum += gcd(i,j,k)
      elif (i == j) & (j != k):
        sum += gcd(i,j,k)*3
      elif (i != j) & (j == k):
        sum += gcd(i,j,k)*3
      elif (i != j) & (j != k):
        sum += gcd(i,j,k)*6

print(sum)
### BUGGY CODE ###

from functools import cmp_to_key
import math
import bisect

n = int(input())
s = input()
k = 1
rank = [0] * (n+1)
tmp = [0] * (n+1)
sa = [''] * (n+1)
"""
def compare_sa(i,j):
	if rank[i] != rank[j]:
		return -1 if rank[i] < rank[j] else 1
	else:
		if i + k <= n:
			ri = rank[i+k]
		else:
			ri = -1
		if j + k <= n:
			rj = rank[j+k]
		else:
			rj = -1
		return -1 if ri < rj else 1


for i in range(n+1):
	sa[i] = i
	if i < n:
		rank[i] = ord(s[i])
	else:
		rank[i] = -1

while k <= n:

	sa = sorted(sa,key=cmp_to_key(compare_sa))

	tmp[sa[0]] = 0

	for i in range(1,n+1):
		if compare_sa(sa[i-1],sa[i]) == -1:
			tmp[sa[i]] = tmp[sa[i-1]] + 1
		else:
			tmp[sa[i]] = tmp[sa[i-1]]

	for i in range(n+1):
		rank[i] = tmp[i]

	k *= 2

#saはインデックス、sorted_listは実際の文字列
sorted_list = []
for i in range(n+1):
	sorted_list.append(s[sa[i]:])
print(sa)
print(sorted_list)

#文字列検索
T = ['ab','abra','abc','abracadabra','abracadabraaa','brabra','bra']
for t in T:
	start = bisect.bisect_left(sorted_list,t)
	end = bisect.bisect_left(sorted_list,t[:-1]+chr(ord(t[-1])+1))
	if start == end:
		print(t+'は存在しません')
	else:
		print(t+'は存在します')
"""

#lcp配列の作成
def getLCP(i,j):
	h = 0
	while i+h < n and j+h < n:
		if s[j+h] != s[i+h]:
			break
		h+=1
	return h

#lcp配列の最大値=最長の共通部分文字列のインデックス
#ans = sorted_list[ lcp.index(max(lcp)) ]
#ans = ans[:max(lcp)]
#print(ans)

ans = 0
for i in range(0,n):
	for j in range(i+1,n):
		lcp = min(getLCP(i,j),j-i)
		ans = max(ans,lcp)

print(ans)


### FIXED CODE ###

n = int(input())
s = input()

def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
        	j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A
ans = 0
for i in range(n-1):
	tmp = z_algo(s[i:])
	for j,zj in enumerate(tmp):
		if j+1 > zj:
			ans = max(ans,zj)

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

N=int(input())
S=input()

def lcs(s,t):
  a=len(s)
  b=len(t)
  dp=[[0]*(b+1) for i in range(a+1)]
  for i in range(a):
    for j in range(b):
      if s[i]==t[j]:
        dp[i+1][j+1]=dp[i][j]+1
      else:
        dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
  return dp[-1][-1]

ans=0
for i in range(1,N):
  s=S[:i]
  t=S[i:]
  a=lcs(s,t)
  ans=max(a,ans)
print(ans)

### FIXED CODE ###

N=int(input())
S=input()
ans=0

def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N

    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg

ans=0  
for i in range(N):
  d=S[i:]
  D=Z_algorithm(d)
  for j in range(N-i):
    ans=max(ans,min(j,D[j]))
print(ans)
### BUGGY CODE ###

n = int(input())
check = []

for _ in range(n):
  s = list(input())
  s.sort()
  s = "".join(s)
  #print(s)
  check.append(s)
  
cnt=0
check_set = set(check)
for c in check_set:
  temp_cnt = check.count(c)
  if c==1:
    pass
  else:
    cnt +=  temp_cnt*(temp_cnt-1)/2
print(int(cnt))

### FIXED CODE ###

n = int(input())
check = {}
lst = []

for _ in range(n):
  s = list(input())
  s.sort()
  s = "".join(s)
  lst.append(s)
  try:
    check[s]+=1
  except:
    check.update({s:1})
  
cnt=0
check_set = set(lst)
for c in check_set:
  temp_cnt = check[c]
  cnt +=  temp_cnt*(temp_cnt-1)/2
print(int(cnt))
### BUGGY CODE ###

from collections import deque
import sys
a,b=map(int,input().split())
List=[list(map(int,input().split())) for i in range(b)]
l=[0]*(a+1)
line=deque([1])
while line:
  i=line.popleft()
  bye=[]
  for j in range(len(List)):
    x,y=List[j]
    if x==i:
      if l[y]==0:
        l[y]=i
        bye+=[j]
        line.append(y)
    if y==i:
      if l[x]==0:
        l[x]=i
        bye+=[j]
        line.append(x)
  for p in range(len(bye)):
    List.pop(bye[p]-p)
print("Yes")
for h in range(a-1):
  print(l[h+2])

### FIXED CODE ###

import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a,b=mi()
l=[[] for i in range(a)]
for j in range(b):
  x,y=mi()
  l[x-1].append(y-1)
  l[y-1].append(x-1)
lst=[-1]*a
q=deque([0])
while q:
  s=q.popleft()
  for j in l[s]:
    if lst[j]==-1:
      lst[j]=s
      q.append(j)
print("Yes")
for k in range(a-1):
  print(lst[k+1]+1)
### BUGGY CODE ###

n, k = list(map(int, input().split()))
p = list(map(int, input().split()))
s = []
for i in range(0, n - k + 1):
    v = [(1 + p[j])/2 for j in range(i, i + k)]
    s.append(sum(v))
print(max(s))


### FIXED CODE ###

n, k = list(map(int, input().split()))
p = list(map(int, input().split()))
q = [(1 + p[0]) / 2]
for i in range(1, n):
    q.append(q[i - 1] + ((1 + p[i]) / 2))
s = [q[k - 1]]
for i in range(k, n):
    s.append(q[i] - q[i - k])
print(max(s))
### BUGGY CODE ###

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

ticket_list = []
total_price_list = []
total_m = 0

def discount(price_list, ticket_num):
    total_ticket =0

    while total_ticket < ticket_num:
        temp_num = int(sorted(price_list)[-1]/2)
        price_list.sort()
        price_list[-1] = temp_num 
        total_ticket += 1

    return price_list



# total_price  += int(price_list[n] / (2 ** m))
# break
res = discount(price_list, M)
# print(res)
print(sum(res))

### FIXED CODE ###

import heapq as hp
N, M = [int(item) for item in input().split()]
price_list = sorted([-1 * int(item) for item in input().split()])

total_m = 0

def discount(price_list, ticket_num):
    total_ticket =0
    hp.heapify(price_list)

    while total_ticket < ticket_num:
        temp = hp.heappop(price_list)
        hp.heappush(price_list, -1* (-1*temp//2))
        total_ticket += 1

    return price_list

res = discount(price_list, M)
print(-1 * sum(res))
### BUGGY CODE ###

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [float('inf') for _ in range(n)]
    dp[0] = 0

    for i in range(n):
        for j in range(1, min(k+1, n-i)):
            num0 = h[i]-h[i+j]
            if num0 < 0:
                num0 *= -1
            num = dp[i]+num0
            if num < dp[i+j]:
                dp[i+j] = num
    print(dp[-1])

main()


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [float('inf')]*n
    dp[0] = 0
    for i in range(n):
        a = h[i]
        for j in range(1, min(k+1, n-i)):
            num = dp[i]+abs(a-h[i+j])
            if num < dp[i+j]:
                dp[i+j] = num
    print(dp[-1])

main()
### BUGGY CODE ###

import numpy as np
from collections import deque

H, W = map(int, input().split())
maze = np.array([input() for _ in range(H)])


def bfs(sty, stx):
    visited = np.array([[-1]*W for _ in range(H)])
    q = deque()
    q.append((sty, stx, 0))


    def is_ok(y, x):
        if not 0 <= y <= H - 1:
            return False
        if not 0 <= x <= W - 1:
            return False
        if visited[y][x] != -1:
            return False
        if maze[y][x] == '#':
            return False
        return True


    while q:
        y, x, lv = q.popleft()
        visited[y][x] = lv
        for i in (-1, 1):
            if is_ok(y+i, x):
                q.append((y+i, x, lv+1))
            if is_ok(y, x+i):
                q.append((y, x+i, lv+1))

    return np.max(visited)

res = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            steps = bfs(i, j)
            if steps > res:
                res = steps

print(res)


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
maze = [input() for _ in range(H)]


def bfs(sty, stx):
    visited = [[-1]*W for _ in range(H)]
    q = deque()
    visited[sty][stx] = 0
    q.append((sty, stx, 0))


    def is_ok(y, x):
        if not 0 <= y <= H - 1:
            return False
        if not 0 <= x <= W - 1:
            return False
        if visited[y][x] != -1:
            return False
        if maze[y][x] == '#':
            return False
        return True


    while q:
        y, x, lv = q.popleft()
        for i in (-1, 1):
            if is_ok(y+i, x):
                visited[y+i][x] = lv+1
                q.append((y+i, x, lv+1))
            if is_ok(y, x+i):
                visited[y][x+i] = lv + 1
                q.append((y, x+i, lv+1))

    return max(max(r) for r in visited)

res = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            res = max(res, bfs(i, j))

print(res)
### BUGGY CODE ###

N=int(input())
s=[input() for i in range(N)]
S=sorted(s)
a=1
num=[]
st=[]
for i in range(N-1):
  if S[i+1]==S[i]:
    a+=1
    if i == (N-2):
        num.append(a)
        st.append(S[-1])
  elif S[i+1]!=S[i]:
    num.append(a)
    st.append(S[i])
    a=1
if S[-1]!=S[-2]:
    num.append(1)
    st.append(S[-1])

d=max(num)
x=[]
if num.count(d)==1:
    print(st[num.index(max(num))])
else:
    ind=[i for i, v in enumerate(num) if v == max(num)]# 複数の最大値のインデックスを全て取得
    st2=[]
    for i in range(len(ind)):
        st2.append(st[ind[i]])
    [print(i) for i in st2]

### FIXED CODE ###

import collections
N=int(input())
s=[input() for i in range(N)]
#S=sorted(s)
a=1
num=[]
st=[]
c = collections.Counter(s)#要素数が大きい順に辞書型ですべての要素を返す
#print(c)
max_c = max(c.values())#最も多い要素の数
#print(max_c)
st=[]
for k,v in c.items():
    if v==max_c:
        st.append(k)
st2=sorted(st)
[print(i) for i in st2]
### BUGGY CODE ###

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


result = 0

for i in range(k):
    if a > 0:
        a = a-1
        result += 1

    elif b > 0:
        b = b-1
        result += 0

    else:
        result -= 1


print(result)


### FIXED CODE ###

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

if k <= a:
    print(k)
elif k <= a+b:
    print(a)
else:
    print(a-(k-(a+b)))
### BUGGY CODE ###

from math import ceil

n, k = [int(_) for _ in input().split()]

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

a.sort()


l, r = 0, 10**9

while r-l > 1:

    m = (l+r)//2
    c = 0
    for i in range(n):
        if a[i] < m:
            continue
        c += a[i]//m-(a[i] % m == 0)
    # print(c, l, r, m)
    if c > k:
        l = m
    else:
        r = m

print(r)


### FIXED CODE ###

from math import ceil

n, k = [int(_) for _ in input().split()]

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

# a.sort()


l, r = 0, 10**9

while r-l > 1:

    m = (l+r)//2
    c = 0
    for i in range(n):
        if a[i] < m:
            continue
        c += a[i]//m-(a[i] % m == 0)
    # print(c, l, r, m)
    if c > k:
        l = m
    else:
        r = m

print(r)
### BUGGY CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**8
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,M,R = LI()
    r = _LI()
    root = [[] for _ in range(N)]
    for _ in range(M):
        a,b,c = LI()
        root[a-1].append((b-1,c))
        root[b-1].append((a-1,c))

    memo = [[0] * N for _ in range(N)]

    min_r = INF
    for x in itertools.permutations(r):
        it = 0
        s = x[0]
        for t in x[1:]:
            if memo[s][t]:
                it += memo[s][t]
            else:
                node = [INF] * N
                q = [(s,0)]
                while q:
                    u,l = q.pop()
                    node[u] = l
                    for v,m in root[u]:
                        if node[v] > l + m:
                            q.append((v,l+m))
                memo[s][t] = node[t]
                #memo[t][s] = node[t]
                it += node[t]
            s = t
        min_r = min(min_r,it)
    print(min_r)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**8
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,M,R = LI()
    r = _LI()
    root = [[] for _ in range(N)]
    for _ in range(M):
        a,b,c = LI()
        root[a-1].append((b-1,c))
        root[b-1].append((a-1,c))

    memo = [[0] * N for _ in range(N)]

    min_r = INF
    for x in itertools.permutations(r):
        it = 0
        s = x[0]
        for t in x[1:]:
            if memo[s][t]:
                it += memo[s][t]
            else:
                node = [INF] * N
                q = collections.deque()
                q.append((s,0))
                node[s] = 0
                while q:
                    u,l = q.popleft()
                    for v,m in root[u]:
                        if node[v] > l + m:
                            node[v] = l + m
                            q.append((v,l+m))
                memo[s][t] = node[t]
                memo[t][s] = node[t]
                it += node[t]
            s = t
        min_r = min(min_r,it)
    print(min_r)

if __name__ == '__main__':
    main()