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

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

for k in range(K):
  light = [0] * N
  for i in range(N):
    start = max(0,i-A[i])
    end = min(N-1, i+A[i])
    for j in range(start, end+1):
      light[j] += 1
  if light[0] == N and light[N-1] == N:
    break
    
  A = light

print(" ".join(map(str,light)))

### FIXED CODE ###

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

import math
K = min(K, 43)
for k in range(K):
  light = [0] * (N+1)
  for i in range(N):
    start = max(0,i-A[i])
    end = min(N-1, i+A[i])
    light[start] += 1
    light[end+1] -= 1
  for i in range(1,N):
    light[i] += light[i-1]
    
  A = light

light.pop()
print(" ".join(map(str,light)))
### BUGGY CODE ###

k,s=map(int,input().split())
t=0

for i in range(k+1):
    for j in range(k+1):
        for l in range(k+1):
            if i+j+l==s:
                t+=1
print(t)


### FIXED CODE ###

k,s=map(int,input().split())
t=0

for i in range(k+1):
    for j in range(k+1):
        l=s-i-j
        if 0<=l<=k:
            t+=1
print(t)
### BUGGY CODE ###

n = int(input())
nun_list = list(map(int, input().split()))
count=0
hoge = len(nun_list) - 1
for i in range(1,n+1):
    tmp = 0
    for j in range(1,n+1):
        if i != j:
            if nun_list[i-1] % nun_list[j-1]  == 0:
                break
            else :
                tmp+=1
    if tmp == hoge:
        count+=1
print(count)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
cnt = Counter(A)
A.sort()
ans = 0
P = [0] * (10 ** 6 + 1)
for a in A:
    if P[a] == 0:
        for i in range(10 ** 7):
            x = a * i
            if x > 10 ** 6:
                break
            P[x] = 1
        if cnt[a] == 1:
            ans += 1
print(ans)
### BUGGY CODE ###

N=int(input())
import math

def make_divisors(n):
    number=0

    i = 1
    while i*i <= n:
        if n % i == 0:
            number+=1
            if i != n // i:
                number+=1
        i += 1
    return number

answer=0
for n in range(1,N+1):
    answer+=n*make_divisors(n)

print(answer)


### FIXED CODE ###

N = int(input())

ans = 0
for x in range(1, N + 1):
    n = N // x
    ans += n * (2 * x + (n - 1) * x) // 2

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

import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n = I()
    s = S()
    rgb = [None for _ in range(n)]
    rgb_acc = [None for _ in range(n)]
    rgb_st = {"R","G","B"}
    rgb_lst = ["R","G","B"]
    for i, char in enumerate(s):
        if char == "R":
            rgb[i] = [1,0,0]
        elif char == "G":
            rgb[i] = [0,1,0]
        else:
            rgb[i] = [0,0,1]
    
    rgb_acc[0] = rgb[0]
    for i in range(1, n):
        rgb_acc[i] = rgb_acc[i-1][:]
        rgb_acc[i][rgb[i].index(1)] += 1
    
    ans = 0
    for i in range(n-2):
        for j in range(i+1,n-1):
           if s[i]!=s[j]:
                ex = rgb_st - {s[i], s[j]}
                ex = ex.pop()
                index = rgb_lst.index(ex)
                cnt = rgb_acc[n-1][index]-rgb_acc[j][index]
                if j+1 <= 2*j-i < n:
                    if s[2*j-i] == ex:
                        cnt -= 1
                ans += cnt

    print(ans)
main()

### FIXED CODE ###

import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n = I()
    s = S()
    rgb = [None for _ in range(n)]
    rgb_acc = [None for _ in range(n)]
    rgb_st = {"R","G","B"}
    rgb_lst = ["R","G","B"]
    for i, char in enumerate(s):
        if char == "R":
            rgb[i] = [1,0,0]
        elif char == "G":
            rgb[i] = [0,1,0]
        else:
            rgb[i] = [0,0,1]
    
    rgb_acc[0] = rgb[0]
    for i in range(1, n):
        rgb_acc[i] = rgb_acc[i-1][:]
        rgb_acc[i][rgb[i].index(1)] += 1
    
    ans = 0
    for i in range(n-2):
        for j in range(i+1,n-1):
           if s[i]!=s[j]:
                ex = rgb_st - {s[i], s[j]}
                ex = ex.pop()
                index = rgb_lst.index(ex)
                cnt = rgb_acc[n-1][index]-rgb_acc[j][index]
                if j+1 <= 2*j-i < n:
                    if s[2*j-i] == ex:
                        cnt -= 1
                ans += cnt

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

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

from math import factorial as kj

d = 0
ans = 0

for i in range(1, n):
  d = (d * i + kj(i-1)) % mod
  ans = (ans * i + (lx[i] - lx[i-1]) * d) % mod

print(ans)

### FIXED CODE ###

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

d = 0
ans = 0

for i in range(1, n):
  f = 1 if i == 1 else f * (i-1) % mod
  d = (d * i + f) % mod
  ans = (ans * i + (lx[i] - lx[i-1]) * d) % mod

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

n = int(input())
s = list(input())
m = n
for i in range(n + 1):
    if m > s[:i].count("#") + s[i:].count("."):
        m = s[:i].count("#") + s[i:].count(".")
        
print(m)

### FIXED CODE ###

n = int(input())
s = list(input())
m = n
counts = s[:].count(".")
m = min(n,counts)
for i in range(n):
    counts += s[i].count("#") - s[i].count(".")
    if m > counts:
        m = counts
        
print(m)
### BUGGY CODE ###

import sys

def binary_search(li, item):
  low = 0
  high = len(li) - 1
  
  while low <= high:
    mid = (low + high) // 2
    guess = li[mid]
    if item == guess:
      return True
    if item < guess:
      high = mid-1
    else:
      low = mid+1
  return False

def main():
  input = sys.stdin.readline
  n = int(input())
  a_li = list(input().split())
  a_li = [int(s) for s in a_li]

  a_li.sort()
  for a in a_li:
    a_li.remove(a)
    if binary_search(a_li, a) == True:
      print("NO")
      sys.exit()
  print("YES")
  
if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys


def main():
  input = sys.stdin.readline
  n = int(input())
  a_li = list(input().split())
  a_li = [int(s) for s in a_li]

  a_li.sort()
  for i in range(n-1):
    if a_li[i] == a_li[i+1]:
      print("NO")
      sys.exit()
  print("YES")
  
if __name__ == "__main__":
  main()
### BUGGY CODE ###

import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]


h,w=map(int,input().split())
a=[list(map(int,input().split())) for i in range(h)]
b=[list(map(int,input().split())) for i in range(h)]

lst=[[0]*w for i in range(h)]

lst[0][0]={abs(a[0][0]-b[0][0]):1}
# print(lst)
d=deque([(0,0)])
while d:
    now=d.popleft()
    tmp=lst[now[0]][now[1]].keys()
    if now[0]+1<h:
        ab=abs(a[now[0]+1][now[1]]-b[now[0]+1][now[1]])
        if lst[now[0]+1][now[1]]==0:
            d.append((now[0]+1,now[1]))
            lst[now[0]+1][now[1]]={}

        for i in tmp:
            lst[now[0]+1][now[1]][i+ab]=1
            lst[now[0]+1][now[1]][abs(i-ab)]=1

    # print(lst)
    if now[1]+1<w:
        ab=abs(a[now[0]][now[1]+1]-b[now[0]][now[1]+1])
        if lst[now[0]][now[1]+1]==0:
            d.append((now[0],now[1]+1))
            lst[now[0]][now[1]+1]={}

        for i in tmp:
            lst[now[0]][now[1]+1][i+ab]=1
            lst[now[0]][now[1]+1][abs(i-ab)]=1
    # print(d)
    # print(lst)
anslst=list(lst[-1][-1].keys())
anslst.sort(key=lambda x: abs(x))
print(abs(anslst[0]))

### FIXED CODE ###

import sys

input = sys.stdin.buffer.readline

h, w = map(int, input().split())
AA = [list(map(int, input().split())) for _ in range(h)]
BB = [list(map(int, input().split())) for _ in range(h)]

kouho = [[0] * (w) for _ in range(h)]
delta = abs(AA[0][0] - BB[0][0])
kouho[0][0] |= 1 << delta
for y in range(h):
    for x in range(w):
        nx = x + 1
        ny = y
        if nx < w:
            delta = abs(AA[ny][nx] - BB[ny][nx])
            temp = 0
            for i in range(1, delta + 1):
                if (kouho[y][x] >> i) % 2:
                    temp |= 1 << (delta - i)
            # print(x,y,kouho[y][x],temp,delta)
            kouho[ny][nx] |= kouho[y][x] << delta
            kouho[ny][nx] |= kouho[y][x] >> delta
            kouho[ny][nx] |= temp

        nx = x
        ny = y + 1
        if ny < h:
            delta = abs(AA[ny][nx] - BB[ny][nx])
            temp = 0
            for i in range(1, delta + 1):
                if (kouho[y][x] >> i) % 2:
                    temp |= 1 << (delta - i)
            # print(x,y,kouho[y][x],temp,delta)
            kouho[ny][nx] |= kouho[y][x] << delta
            kouho[ny][nx] |= kouho[y][x] >> delta
            kouho[ny][nx] |= temp
# print(kouho)
for i in range(81):
    if (kouho[h - 1][w - 1] >> i) % 2:
        print(i)
        exit()
### BUGGY CODE ###

i=1
j=1
while i<10:
        j=1
        while j<10:
                print i,"x",j,"=",i*j

### FIXED CODE ###

x = range(1,10)
for i in x:
  for j in x:
    print u"%dx%d=%d"%(i, j, i*j)
### BUGGY CODE ###

def gcd(p, q) :
	if p % q == 0 :
		return q
	else :
		return gcd(q,p%q)
if __name__ == '__main__':
	ans = 0
	tmp = 0
	k = int(input())
	for i in range(1,k+1) :
		for j in range(1, k+1) :
			tmp = gcd(i,j)
			for l in range(1, k+1) :
				ans += gcd(tmp,l)
	print(ans)


### FIXED CODE ###

def gcd(p, q) :
	if p % q == 0 :
		return q
	else :
		return gcd(q,p%q)
if __name__ == '__main__':
	k = int(input())
	a = []
	ans = 0
	for i in range(1,k+1) :
		for j in range(1,k+1) :
			a.append(gcd(i,j))
	for i in range(1,k+1) :
		for j in a :
			ans += gcd(i,j)
	print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    N, M = LI()
    LR = []
    for _ in range(M):
        LR.append(LI())
    SE = None
    for l, r in LR:
        se = set(range(l, r + 1))
        if SE is None:
            SE = se
        else:
            SE = SE & se
    ans = len(SE)
    return ans

print(main())


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    N, M = LI()
    LR = []
    for _ in range(M):
        LR.append(LI())
    left = 0
    right = INF
    for l, r in LR:
        left = max(left, l)
        right = min(right, r)
    ans = max(right - left + 1, 0)
    return ans

print(main())
### BUGGY CODE ###

k = int(input())
m = 7
if(k%2==0):
  print("-1")
else:
  i = 1
  while True:
    j = m%k
    if(j==0):
      print(i)
      break  
    if(i>k):
      print("-1")
      break
    m *= 10
    m += 7
    i += 1



### FIXED CODE ###

k = int(input())
m = 7
if(k%2==0):
  print("-1")
else:
  i = 1
  while True:
    m = m%k
    if(m==0):
      print(i)
      break  
    if(i>k):
      print("-1")
      break
    m *= 10
    m += 7
    i += 1
### BUGGY CODE ###

MOD = 1e9 + 7

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]

dp = [0] * (n+1)
dp[0] = 1
for i in range(1, n+1):
    if i in a:
        continue
    if i > 1:
        dp[i] = (dp[i-1] + dp[i-2]) % MOD
    else:
        dp[i] = dp[i-1]

print(int(dp[n]))


### FIXED CODE ###

MOD = 1e9 + 7

n, m = map(int, input().split())
a = [False] * (n+1)
for i in range(m):
    b = int(input())
    a[b] = True

dp = [0] * (n+1)
dp[0] = 1
for i in range(1, n+1):
    if a[i]:
        continue
    if i > 1:
        dp[i] = (dp[i-1] + dp[i-2]) % MOD
    else:
        dp[i] = dp[i-1]

print(int(dp[n]))
### BUGGY CODE ###

n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))

sa = sorted(a)
for i in range(n):
    val = a[i]
    idx = sa.index(val)
    sa.pop(idx)
    print(sa[-1])
    sa.insert(idx, val)


### FIXED CODE ###

n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))

sa = sorted(a)
mx = sa[-1]
for val in a:
    if val != mx:
        print(sa[-1])
    else:
        print(sa[-2])
### BUGGY CODE ###

def main():
    from collections import deque
    H, W = (int(i) for i in input().split())
    c = [input() for j in range(H)]
    st = [(h, w) for h in range(H) for w in range(W)]

    def bfs(sy, sx, gy, gx):
        que = deque()
        dist = [[-1]*W for h in range(H)]
        dist[sy][sx] = 0
        que.append((sy, sx))
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        while que:
            uy, ux = que.popleft()
            for dy, dx in d:
                next_y = uy + dy
                next_x = ux + dx
                if not(0 <= next_y < H and 0 <= next_x < W):
                    continue
                if dist[next_y][next_x] != -1:
                    continue
                if c[next_y][next_x] == '#':
                    continue
                dist[next_y][next_x] = dist[uy][ux] + 1
                que.append((next_y, next_x))
        return dist[gy][gx]

    ans = 0
    for s in st:
        for t in st:
            if s == t or c[s[0]][s[1]] == "#" or c[t[0]][t[1]] == "#":
                continue
            ans = max(ans, bfs(s[0], s[1], t[0], t[1]))
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from collections import deque
    H, W = (int(i) for i in input().split())
    c = [input() for j in range(H)]
    st = [(h, w) for h in range(H) for w in range(W)]  # H*W個

    def bfs(sy, sx):
        que = deque()
        dist[sy][sx] = 0
        que.append((sy, sx))
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        while que:
            uy, ux = que.popleft()
            for dy, dx in d:
                next_y = uy + dy
                next_x = ux + dx
                if not(0 <= next_y < H and 0 <= next_x < W):
                    continue
                if dist[next_y][next_x] != -1:
                    continue
                if c[next_y][next_x] == '#':
                    continue
                dist[next_y][next_x] = dist[uy][ux] + 1
                que.append((next_y, next_x))

    ans = 0
    for s in st:
        dist = [[-1]*W for h in range(H)]
        if c[s[0]][s[1]] == "#":
            continue
        bfs(s[0], s[1])
        for t in st:
            if s == t or c[t[0]][t[1]] == "#":
                continue
            ans = max(ans, dist[t[0]][t[1]])
    print(ans)


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

n,m = map(int, input().split())
a = list(map(int,input().split()))
for i in range(m):
    b,c = map(int,input().split())
    a = a + [c for i in range(b)]
a.sort()
a.reverse()
print(sum(a[:n]))

### FIXED CODE ###

from collections import deque

n,m = map(int,input().split())
a = deque(sorted(list(map(int,input().split()))))
bc = [list(map(int,input().split()))[::-1] for i in range(m)]
bc.sort(reverse=True)
def hoge(n,m,a,bc):
    cur_sum = sum(a)
    for x in bc:
        c = x[0]
        for i in range(x[1]):
            prv_sum = cur_sum
            cur_sum -= a.popleft()
            cur_sum += c
            a.append(c)
            if prv_sum >= cur_sum:
                print(prv_sum)
                return
    print(cur_sum)
    return
hoge(n,m,a,bc)
### BUGGY CODE ###

import bisect

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

l.sort()

ans = 0
for i in range(n):
    for j in range(i):
        ans += bisect.bisect_left(l, l[i]+l[j], j+1, i)-bisect.bisect_right(l, l[i]-l[j], j+1, i)

print(ans)


### FIXED CODE ###

import bisect

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

l.sort()

ans = 0
for i in range(n):
    for j in range(i):
        ans += bisect.bisect_left(l, l[i]+l[j], j+1, i)-bisect.bisect_right(l, l[i]-l[j], j+1, i)

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

import sys,math,collections,itertools
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))
B = []
for i,a in enumerate(A):
    B.append([a,i])
B.sort()
cnt = 0
for i in range(N):
    for j in range(i+1,N):
        if B[i][0]+B[j][0]==abs(B[i][1]-B[j][1]):
            cnt +=1
        if B[i][0]+B[j][0]>=N:
            break
print(cnt)



### FIXED CODE ###

import sys,collections
input = sys.stdin.readline
N=int(input())
A=list(map(int,input().split()))
B = []
C = []
for i,a in enumerate(A):
    B.append(i+a)
    C.append(i-a)
cnt = 0
Bc = collections.Counter(B)
Cc = collections.Counter(C)

for key,val in Bc.items():
    cnt += val*Cc[key]
print(cnt)
### BUGGY CODE ###

from math import gcd

n = int(input())

gcd_dic = {}
ans = 0
for i in range(1, n + 1):
    for j in range(1, n + 1):
        for k in range(1, n + 1):
            fs = frozenset({i, j, k})
            if fs not in gcd_dic:
                gcd_dic[fs] = gcd(gcd(i, j), k)
            ans += gcd_dic[fs]
print(ans)

### FIXED CODE ###

answer = [1, 9, 30, 76, 141, 267, 400, 624, 885, 1249, 1590, 2208, 2689, 3411, 4248, 5248, 6081, 7485, 8530, 10248, 11889, 13687, 15228, 17988, 20053, 22569, 25242, 28588, 31053, 35463, 38284, 42540, 46581, 50893, 55362, 61824, 65857, 71247, 76884, 84388, 89349, 97881, 103342, 111528, 120141, 128047, 134580, 146316, 154177, 164817, 174438, 185836, 194157, 207927, 218812, 233268, 245277, 257857, 268182, 288216, 299257, 313635, 330204, 347836, 362973, 383709, 397042, 416448, 434025, 456967, 471948, 499740, 515581, 536073, 559758, 583960, 604833, 633651, 652216, 683712, 709065, 734233, 754734, 793188, 818917, 846603, 874512, 909496, 933081, 977145, 1006126, 1041504, 1073385, 1106467, 1138536, 1187112, 1215145, 1255101, 1295142, 1342852, 1373253, 1422195, 1453816, 1502376, 1553361, 1595437, 1629570, 1691292, 1726717, 1782111, 1827492, 1887772, 1925853, 1986837, 2033674, 2089776, 2145333, 2197483, 2246640, 2332104, 2379085, 2434833, 2490534, 2554600, 2609625, 2693919, 2742052, 2813988, 2875245, 2952085, 3003306, 3096024, 3157249, 3224511, 3306240, 3388576, 3444609, 3533637, 3591322, 3693924, 3767085, 3842623, 3912324, 4027884, 4102093, 4181949, 4270422, 4361548, 4427853, 4548003, 4616104, 4718640, 4812789, 4918561, 5003286, 5131848, 5205481, 5299011, 5392008, 5521384, 5610705, 5739009, 5818390, 5930196, 6052893, 6156139, 6239472, 6402720, 6493681, 6623853, 6741078, 6864016, 6953457, 7094451, 7215016, 7359936, 7475145, 7593865, 7689630, 7886244, 7984165, 8130747, 8253888, 8403448, 8523897, 8684853, 8802826, 8949612, 9105537, 9267595, 9376656, 9574704, 9686065, 9827097, 9997134, 10174780, 10290813, 10493367, 10611772, 10813692]
n = int(input())
print(answer[n - 1])
### BUGGY CODE ###

n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))
cnt = 0
for i in T:
 a = 0
 b = n-1
 while b >= a:
  mid = (a + b) // 2
  if S[mid] == i:
   cnt += 1
   break
  elif S[mid] > i:
   b = mid
   continue
  else:
   a = mid + 1
   continue
print(str(cnt))

### FIXED CODE ###

n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))
cnt = 0
for i in T:
 a = 0
 b = n-1
 while b >= a:
  mid = (a + b) // 2
  if S[mid] == i:
   cnt += 1
   break
  elif S[mid] > i:
   b = mid - 1
   continue
  else:
   a = mid + 1
   continue
print(str(cnt))
### BUGGY CODE ###

a,b = map(int,input().split())
i  = max(a,b)
while i%a+i%b>0:
  i+=1
print(i)

### FIXED CODE ###

import fractions
a,b = map(int,input().split())
print(int(a*b/fractions.gcd(a,b)))
### BUGGY CODE ###

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

MAX = 1000000000000000000
ans = 1

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

if (ans > MAX) :
    print(-1)
else :
    print(ans)


### FIXED CODE ###

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

MAX = 1000000000000000000
ans = 1

for i in range(n) :
    if (a[i] == 0) :
        print(0)
        exit()

for i in range(n) :
    ans *= a[i]
    if (ans > MAX) :
        print(-1)
        exit()

if (ans > MAX) :
    print(-1)
else :
    print(ans)
### BUGGY CODE ###

D, G = map(int, input().split())

Score = []
q_sum = 0
for i in range(D):
    p, c = map(int, input().split())
    q_sum += p
    Score.append([(i+1)*100, p, c])

def Calc(score, num):
    temp = list(filter(lambda x: x[1] < num+1, score))
    if temp == []:
        return score[-1][0] * num
    else:
        cand = []
        if len(score) == 1:
            cand.append(temp[0][0]*temp[0][1] + temp[0][2])
        else:
            copy_score = score.copy()
            for t in temp:
                temp_score = score.copy()
                del temp_score[temp_score.index(t)]
                del copy_score[copy_score.index(t)]
                cand.append(t[0]*t[1] + t[2] + Calc(temp_score, num - t[1]))
            if len(copy_score) > 0:
                cand.append(copy_score[-1][0] * num)
        return max(cand)

    

for i in range(1, q_sum+1):
    res = Calc(Score, i)
    if res >= G:
        print(i)
        exit()


### FIXED CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
import math

s_in = lambda: stdin.readline()[:-1] # s = s_in()
d_in = lambda: int(stdin.readline()) # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split())) # List = ds_in()

D, G = ds_in()

Score = []
for i in range(D):
    p, c = ds_in()
    Score.append([(i+1)*100, p, c])

INF = 10**10

search = []
def SearchMin(search, idx):
    if idx == D:
        score = 0
        num = 0
        res = []
        maxprob = [0, 0, 0]
        for s, i in zip(Score, search):
            num += s[1] * i
            score += (s[0] * s[1] + s[2]) * i
            if i == 0 and s[0] > maxprob[0]:
                maxprob = s.copy()
        if (G > score) and (math.ceil((G - score) / maxprob[0]) <= maxprob[1]):
            return num + max(0, math.ceil((G - score) / maxprob[0]))
        elif G <= score:
            return num
        else:
            return INF

    else:
        s0 = search.copy()
        s0.append(0)
        s1 = search.copy()
        s1.append(1)
        idx += 1
        ans0 = SearchMin(s0, idx)
        ans1 = SearchMin(s1, idx)
        return min(ans0, ans1)

print(SearchMin(search, 0))
### BUGGY CODE ###

# -*- coding: utf-8 -*-


def main():
    x, y, z, k = map(int, input().split())
    a = sorted(list(map(int, input().split())), reverse=True)
    b = sorted(list(map(int, input().split())), reverse=True)
    c = sorted(list(map(int, input().split())), reverse=True)
    count = min(x * z, k)
    ac = list()
    ans = list()

    for ai in a:
        for ci in c:
            ac.append(ai + ci)

    for bi in b:
        for ac_i in sorted(ac, reverse=True)[:count]:
            ans.append(bi + ac_i)

    for j in sorted(ans, reverse=True)[:k]:
        print(j)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-


def main():
    x, y, z, k = map(int, input().split())
    a = sorted(list(map(int, input().split())), reverse=True)
    b = sorted(list(map(int, input().split())), reverse=True)
    c = sorted(list(map(int, input().split())), reverse=True)
    ac = list()

    for ai in a:
        for ci in c:
            ac.append(ai + ci)

    count = min(x * z, k)
    acs = sorted(ac, reverse=True)[:count]
    ans = list()

    for bi in b:
        for ac_i in acs:
            ans.append(bi + ac_i)

    for j in sorted(ans, reverse=True)[:k]:
        print(j)


if __name__ == '__main__':
    main()