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

import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())
#

def join(s):
    return ''.join(s)

#iterate macro
def piter(n,m):
    return itertools.permutations(n,m)
def citer(n,m):
    return itertools.combinations(n,m)

#modulo macro
def modc(a,b,m):
    c = 1
    for i in xrange(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c
 
def gcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
def modinv(a, m):
    (inv, q, gcd_val) = gcd(a, m)
    return inv % m

#bisect macro
def index(a, x):
    #Locate the leftmost value exactly equal to x
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

#memoize macro
def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper

@memoize
def nck(a,b,m):
    b = min([a-b,b])
    if (b>a or b<0 or a<0):
        return 0
    elif a == 0:
        return 1
    return (nck(a-1,b-1,m)+nck(a-1,b,m)) % m

nh=zip([1,0,-1,0],[0,1,0,-1])

###########

n,x=ii()
a=ii()

def dp(j,k):
    if k!=0:
        return min(dp(j,k-1),a[(j-k)%n])
    else:
        return a[j]

print min([sum([dp(j,k) for j in range(n)])+k*x for k in range(n)])


### FIXED CODE ###

n,x=map(int,raw_input().split(" "))
a=map(int,raw_input().split(" "))
t=[i for i in a]
s=10**15
for m in range(n):
    t=[min(t[j],a[(j-m)%n]) for j in range(n)]
    s=min(x*m+sum(t),s)
print s
### BUGGY CODE ###

from fractions import gcd

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

ans = 0
tmp = 1
g = gcd(a,b)
while g > 1:
    for i in range(tmp+1,g//2):
        if g%i == 0:
            ans += 1
            tmp = i
            while g%i == 0:
                g //= i
            break
    else:
        # もうgでしか割れないはず
        ans += 1
        break
print(ans+1)

### FIXED CODE ###

from fractions import gcd
from math import sqrt, ceil

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

ans = 0
tmp = 1
g = gcd(a,b)
while g > 1:
    for i in range(tmp+1,ceil(sqrt(g))):
        if g%i == 0:
            ans += 1
            tmp = i
            while g%i == 0:
                g //= i
            break
    else:
        # もうgでしか割れないはず
        ans += 1
        break
print(ans+1)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
ope = [list(map(int, input().split())) for _ in range(m)]
ope = sorted(ope, key=lambda x: x[1], reverse=True)
for i in range(m):
    for j in range(ope[i][0]):
        if min(a) < ope[i][1]:
            a[a.index(min(a))] = ope[i][1]
        else:
            break
print(sum(a))


### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ope = [list(map(int, input().split())) for _ in range(m)]
ope = sorted(ope, key=lambda x: x[1], reverse=True)
j = 0
for i in range(n):
    if a[i] < ope[j][1]:
        a[i] = ope[j][1]
        ope[j][0] -= 1
        if ope[j][0] == 0:
            j += 1
            if j == len(ope):
                break
    else:
        break
print(sum(a))
### BUGGY CODE ###

import math

n, k = map(int, input().split(" "))
li = list(map(int, input().split(" ")))

fk = k
crnt = 1
st = set()
wl = []
key = crnt
cy = 0
mg = 0

for i in range(n):
    if crnt in st:
        key = crnt
        cy = i - wl.index(crnt)
        mg = wl.index(crnt)
        break
    st.add(crnt)
    wl.append(crnt)
    crnt = li[crnt - 1]

k -= mg
if cy != 0:
    k %= cy
crnt = key
if n > k:
    k = fk
    crnt = 1
for i in range(k):
    crnt = li[crnt - 1]

print(crnt)


### FIXED CODE ###

import math

n, k = map(int, input().split(" "))
li = list(map(int, input().split(" ")))

fk = k
crnt = 1
st = set()
wl = []
key = crnt
cy = 0
mg = 0

for i in range(n):
    if crnt in st:
        key = crnt
        cy = i - wl.index(crnt)
        mg = wl.index(crnt)
        break
    st.add(crnt)
    wl.append(crnt)
    crnt = li[crnt - 1]

k -= mg
if cy != 0:
    k %= cy
crnt = key
if n > fk:
    k = fk
    crnt = 1
for i in range(k):
    crnt = li[crnt - 1]

print(crnt)
### BUGGY CODE ###

ans=0
K,S=map(int,input().split())
for i in range(K+1):
  for j in range(K+1):
    for k in range(K+1):
      if i+j+k==S:
        ans+=1
print(ans)

### FIXED CODE ###

ans=0
K,S=map(int,input().split())
for i in range(K+1):
  for j in range(K+1):
    if 0<=S-i-j<=K:
      ans+=1
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
lr = [tuple(map(int, input().split())) for _ in range(k)]

dp = [0] * (n+1);

dp[0] = 1
dp[1] = -1

for i in range(0, n):
    if i>0: dp[i] += dp[i-1]
    for l,r in lr:
        if i+l > n: continue
        dp[i+l] += dp[i]
        dp[min(n, i+r+1)] -= dp[i]

print(dp[n-1] % 998244353)


### FIXED CODE ###

n, k = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(k)]

dp = [0] * (n+1);

dp[0] = 1
dp[1] = -1

for i in range(0, n):
    if i>0: dp[i] += dp[i-1]
    dp[i] %= 998244353
    for l,r in lr:
        if i+l > n: continue
        dp[i+l] += dp[i]
        dp[min(n, i+r+1)] -= dp[i]

print(dp[-2] % 998244353)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
mod = 10**9+7
ans = 0
for i in range(60):
    cnt = 0
    for j in range(n):
        if a[j]>>i & 1 == 0: cnt += 1
    ans = (ans+pow(2,i,mod)*cnt%mod*(n-cnt)%mod)%mod
print(ans)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
ans = 0
mod = 10**9+7
for i in range(60):
    x = 0
    for j in range(n):
        if a[j] >> i & 1: x += 1 # i桁目が1である数の個数
    now = x*(n-x)%mod # 0と1の組み合わせの数(0 xor 1 = 1)
    for _ in range(i): now = now*2%mod # i桁目が1なら*2^i
    ans += now
    ans %= mod
print(ans)
### BUGGY CODE ###

from collections import deque
h,w = map(int,input().split())
grid = [list(input()) for i in range(h)]
que = deque([])
d = [[float('inf')]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if grid[i][j] == '#':
            d[i][j] = 0
            que.append([i,j])
dx = [0,-1,0,1]
dy = [-1,0,1,0]
ans = 0
while que:
    [px,py] = que.popleft()
    for i in range(4):
        nx = px + dx[i]
        ny = py + dy[i]
        if 0<=nx<h and 0<=ny<w and grid[nx][ny] == '.' and d[nx][ny] == float('inf'):
            d[nx][ny] = d[px][py] + 1
            ans = max(d[nx][ny],ans)
            que.append([nx,ny])
print(ans)

### FIXED CODE ###

from collections import deque
h,w = map(int,input().split())
a = []
d = []
que = deque()
for i in range(h):
    a.append(list(input()))
    d.append([1e100]*w)
    for j in range(w):
        if a[i][j] == '#':
            que.append([i,j])
            d[i][j] = 0
di = [-1,0,1,0]
dj = [0,1,0,-1]
ans = 0

while que:
    i,j = que.popleft()
    for k in range(4):
        ni = i + di[k]
        nj = j + dj[k]
        if 0 <= ni < h and 0 <= nj < w and d[ni][nj] == 1e100:
            d[ni][nj] = d[i][j] + 1
            ans = max(ans, d[ni][nj])
            que.append([ni,nj])
print(ans)
### BUGGY CODE ###

A,B=map(int,input().split())
res=A
for a in range(A+1,B+1):
    res=res^a
print(res)

### FIXED CODE ###

A,B=map(int,input().split())
A-=1
if A%4==1:
    A=1
elif A%4==2:
    A+=1
elif A%4==3:
    A=0
if B%4==1:
    B=1
elif B%4==2:
    B+=1
elif B%4==3:
    B=0
print(A^B)
### BUGGY CODE ###

from collections import Counter

class UnionFind:
    def __init__(self, size):
        self.rank = [-1 for _ in range(size)]
        self.number = [1 for _ in range(size)]

    def find(self, x):
        while self.rank[x] >= 0:
            x = self.rank[x]
        return x

    def union(self, s1, s2):
        if s1 == s2:
            return
        if self.rank[s1] == self.rank[s2]:
            self.rank[s1] -= 1
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        elif self.rank[s1] < self.rank[s2]:
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        else:
            self.rank[s1] = s2
            self.number[s2] += self.number[s1]


n, K, L = map(int, input().split())
pq = [tuple(int(x) for x in input().split()) for _ in range(K)]
rs = [tuple(int(x) for x in input().split()) for _ in range(L)]

uk = UnionFind(n)
for p, q in pq:
    rp = uk.find(p - 1)
    rq = uk.find(q - 1)
    if rp != rq:
        uk.union(rp, rq)

ul = UnionFind(n)
for p, q in rs:
    rp = ul.find(p - 1)
    rq = ul.find(q - 1)
    if rp != rq:
        ul.union(rp, rq)

res = [tuple([uk.find(i), ul.find(i)]) for i in range(n)]

#c = Counter(res)

#print(c)
ans = ['' for _ in range(n)]
for i in range(n):
    ans[i] = str(res.count(res[i]))

print(' '.join(ans))



### FIXED CODE ###

from collections import Counter

class UnionFind:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def find_root(self, x):
        if self.p[x] != x:
            self.p[x] = self.find_root(self.p[x])

        return self.p[x]

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

    def unite(self, x, y):
        u = self.find_root(x)
        v = self.find_root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

    def get_size(self, x):
        return self.size[self.find_root(x)]


n, K, L = map(int, input().split())
pq = [tuple(int(x)-1 for x in input().split()) for _ in range(K)]
rs = [tuple(int(x)-1 for x in input().split()) for _ in range(L)]

uk = UnionFind(n)
for p, q in pq:
    uk.unite(p, q)

ul = UnionFind(n)
for p, q in rs:
    ul.unite(p, q)

res = [uk.find_root(i) * 1000000 +  ul.find_root(i) for i in range(n)]
c = Counter(res)
ans = [0] * n

for i in range(n):
    ans[i] = c[res[i]]

print(*ans, sep=' ')
### BUGGY CODE ###

import collections

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

c = collections.Counter(a)

for i in range(n):
    r = 0
    k = a[i]
    c[k] = c[k]-1
    for j in c:
        if c[j] > 1:
            r = int(r + (c[j] * (c[j] - 1) / 2))
    print(r)
    c[k] = c[k]+1

### FIXED CODE ###

import collections

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

c = collections.Counter(a)

r = 0
for j in c:
    if c[j] > 1:
        r = int(r + (c[j] * (c[j] - 1) / 2))

tmp = r 
for i in range(n):
    r = int(r - ((c[a[i]] * (c[a[i]] - 1) / 2)) + (((c[a[i]] - 1) * (c[a[i]] - 2) / 2)))
    print(r)
    r = tmp
### BUGGY CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

import numpy as np

def canReach(src, dst):
    dist = np.sum(np.abs(src-dst)[1:3])
    time = (dst[0] - src[0])
    if time - dist == 0:
        return True
    elif time - dist > 0 and (time - dist) % 2 == 0:
        return True
    return False

N = int(input())
dst = np.array([[int(x) for x in input().split(" ")] for z in range(N)])

available = True
pos = [0, 0, 0]

for n in range(N):
    if not canReach(pos, dst[n]):
        available = False
        break
    else:
        pos = dst[n]

if available:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-

import numpy as np

N = int(input())
prev_dst = [0,0,0]

for n in range(N):
    t, x, y = map(int, input().split(" "))
    a = (t - prev_dst[0]) - (np.abs(prev_dst[1]-x) + np.abs(prev_dst[2]-y))
    if a >= 0 and a % 2 == 0:
        prev_dst = [t, x, y]
    else:
        print("No")
        exit(0)

print("Yes")
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
from collections import defaultdict
n = int(input())
sys.setrecursionlimit(max(1000, n))
# 小さすぎても怒られるので
 
cs = [0] + [int(c) for c in input().split()]
ns = defaultdict(set)
for _ in range(n-1):
    a,b = [int(c) for c in input().split()]
    ns[a].add(b)
    ns[b].add(a)
 
toru = [0] * (n+1)
def dfs(ns, prev, now, toru):
    end = defaultdict(int)
    k = cs[now]
    end[k] = 1
    s = 1 # nowで終わるパスの種類
    for u in ns[now]:
        if u==prev:
            continue
        tmp_end, tmp_toru, tmp_s = dfs(ns, now, u, toru)
        # toruの更新
        for kk, vv in tmp_end.items():
            if kk not in end:
                toru[kk] += vv * s
            else:
                toru[kk] += vv * s + end[kk] * (tmp_s+1) - ((vv+1) * end[kk])
        for kk, vv in end.items():
            if kk not in tmp_end:
                toru[kk] += vv * tmp_s
        # end, sの更新
        end[k] += tmp_s
        for kk,vv in tmp_end.items():
            if k!=kk:
                end[kk] += tmp_end[kk]
        s += tmp_s
    toru[k] += 1
#     print(now, prev, end, toru, s)
    return end, toru, s
end, toru, s = dfs(ns, prev=-1, now=1, toru=toru)
 
for item in toru[1:]:
    # print(item)
    sys.stdout.write(str(item) + "\n")


### FIXED CODE ###


import sys
# 小さすぎても怒られるので
from collections import defaultdict
n = int(input())
sys.setrecursionlimit(max(1000, 2*n))

cs = [0] + [int(c) for c in input().split()]
ns = defaultdict(set)
for _ in range(n-1):
    a,b = [int(c) for c in input().split()]
    ns[a].add(b)
    ns[b].add(a)

ans = [0] * (n+1) # kを通らないパスの総数
minus = [0] * (n+1) # uの部分木のうち
minus0 = defaultdict(int)
st = {k: [] for k in range(1, n+1)}
nextu = {}
def dfs(u, prev, ans):
    global minus, st, minus0
    k = cs[u]
    st[k].append(u)
    ss = 1
    for v in ns[u]:
        if v==prev:
            continue
        nextu[u] = v
        s = dfs(v, u, ans)
        ss += s
        tmp = s - minus[v]
        ans[k] += (int(tmp * (tmp - 1) / 2) + tmp)
    st[k].pop()
    if st[k]:
        minus[nextu[st[k][-1]]] += ss
    else:
        minus0[k] += ss
#     print(ss)
    return ss

dfs(1, -1, ans)
for k in range(1, n+1):
    tmp = n - minus0[k]
    ans[k] += (int(tmp * (tmp - 1) / 2) + tmp)
    
total = int(n * (n+1) / 2)
for i in range(1, n+1):
    print(total - ans[i])
### BUGGY CODE ###


n = int(input())

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


from functools import lru_cache
import sys
if n == 2:
    print(max(a))
    sys.exit()


@lru_cache(maxsize=100000)
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def gcd_list(li):
    g = gcd(li[0], li[1])
    for i in range(2, n):
        g = gcd(g, a[i])
    return g


def gcd_list_2(li):
    g = gcd(li[0], li[1])
    if g == 1:
        return max(gcd_list(li[0] + li[2:]), gcd_list(li[1:]))
    for i in range(2, n):
        if gcd(g, a[i]) == 1:
            return gcd_list([g] + li[i + 1:])
        else:
            g = gcd(g, a[i])
    return g


def max_gcd(a):
    g = gcd_list(a)
    a = [a[i]//g for i in range(n)]

    m = 1
    for i in range(n):
        b = a[:]
        del b[i]
        gg = gcd_list(b)
        m = max(m, gg)

    print(g * m)


max_gcd(a)

### FIXED CODE ###


n = int(input())

a = list(map(int, input().split()))
a.sort(reverse=True)


from functools import lru_cache
import sys
if n == 2:
    print(max(a))
    sys.exit()


@lru_cache(maxsize=100000)
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x


def gcd_list(li):
    if len(li) == 1:
        return li[0]
    g = gcd(li[0], li[1])
    for i in range(2, len(li)):
        g = gcd(g, li[i])
    return g


def gcd_list_2(li):
    g = gcd(li[0], li[1])
    if g == 1:
        return max(gcd_list([li[0]] + li[2:]), gcd_list(li[1:]))
    for i in range(2, n):
        if gcd(g, li[i]) == 1:
            if i == n - 1:
                return gcd_list(li[:i])
            gg = gcd_list(li[i+1:])
            bb = [gcd(li[x], gg) for x in range(i+1)]
            bb.sort()
            return bb[1]
        else:
            g = gcd(g, li[i])
    return g


def max_gcd(a):
    g = gcd_list(a)
    a = [a[i]//g for i in range(n)]
    m = gcd_list_2(a)
    print(g * m)


max_gcd(a)
### BUGGY CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
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 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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

def gcd(a,b):
    """Compute the greatest common divisor of a and b"""
    while b > 0:
        a, b = b, a % b
    return a
    
def lcm(a, b):
    """Compute the lowest common multiple of a and b"""
    return int(a * b / gcd(a, b))


N, M = LI()
S = input()
T = input()
N, M = len(S), len(T)

X = lcm(len(S), len(T))
L = X
XS = ['X' for i in range(L+1)]
XT = ['X' for i in range(L+1)]
count = 0
while True:
    XS[int(count*L/N)] = S[count]
    count += 1
    if count > N-1:
        break

count = 0
while True:
    XT[int(count*L/M)] = T[count]
    count += 1
    if count > M-1:
        break

#  print(XS, XT)
for i in range(0, L+1):
    if XS[i] != 'X' and XT[i] != 'X':
        if XT[i] != XS[i]:
            print(-1)
            exit()
print(L)


### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
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 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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

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

N, M = LI()
S = input()
T = input()

#  N, M = 10**5, 10**5
#  S = 's'*N
#  T = 't'*M

X = lcm(N, M)
L = X
#  XS = ['X' for i in range(L+1)]
#  XT = ['X' for i in range(L+1)]
XS, XT = {}, {}
count = 0
LN = L/N
while True:
    XS[int(count*LN)] = S[count]
    count += 1
    if count > N-1:
        break

count = 0
LM = L/M
while True:
    XT[int(count*LM)] = T[count]
    count += 1
    if count > M-1:
        break

for key, value in XS.items():
    #  print(key, value)
    if key in XT:
        if value != XT[key]:
            print(-1)
            exit()
#  print(XS, XT)
#  for i in range(0, L+1):
#      if XS[i] != 'X' and XT[i] != 'X':
#          if XT[i] != XS[i]:
#              print(-1)
#              exit()
print(L)
### BUGGY CODE ###

n=int(input())
s=input()
ans=0
for i in range(n):
    for j in range(i+ans,n):
        if s[i:j+1] in s[j+1:]:
            ans=max(ans,j+1-i)
        if i+ans+1>=n:
            break
print(ans)



### FIXED CODE ###

n=int(input())
s=input()
ans=0
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

for i in range(n):
    l=z_algo(s[i:])
    m=len(l)
    for j in range(m):
        ans=max(ans,min(j,l[j]))
print(ans)
### BUGGY CODE ###


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

for k in range(n-1,-1,-1):
    for i in range(n-1,-1,-1):
        for j in range(n-1,-1,-1):            
            #print(k,i,j,a)
            if (i==j or k==i or k==j):
                continue
            if (a[i][k]!=-1 and a[k][j]!=-1 and a[i][j] == a[i][k]+a[k][j]):
                a[i][j] = -1
            elif (a[i][k]!=-1 and a[k][j]!=-1 and a[i][j] > a[i][k]+a[k][j]):
                print(-1)
                exit()
            
#print(a)

ans = 0
for i in range(0,n-1):
    for j in range(i,n):
        if (a[i][j]!=-1):
            ans += a[i][j]
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    a = [list(map(int, input().split())) for _ in range(n)]
    #print(a)

    for k in range(n-1,-1,-1):
        for i in range(n-1,-1,-1):
            for j in range(n-1,-1,-1):            
                #print(k,i,j,a)
                if (i==j or k==i or k==j):
                    continue
                if (a[i][k]!=-1 and a[k][j]!=-1 and a[i][j] == a[i][k]+a[k][j]):
                    a[i][j] = -1
                elif (a[i][k]!=-1 and a[k][j]!=-1 and a[i][j] > a[i][k]+a[k][j]):
                    print(-1)
                    exit()
            
    #print(a)

    ans = 0
    for i in range(0,n-1):
        for j in range(i,n):
            if (a[i][j]!=-1):
                ans += a[i][j]
    print(ans)
    
if __name__=="__main__":
    main()
### BUGGY CODE ###

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

dp = [0]*N

for i in range(N-1):
    dp[i+1] = []
    if i >= K:
        for j in range(K):
            dp[i+1].append(dp[i-j]+abs(h[i+1]-h[i-j]))
    else:
        for j in range(i+1):
            dp[i+1].append(dp[i-j]+abs(h[i+1]-h[i-j]))

    dp[i+1] = min(dp[i+1])

print(dp[-1])

### FIXED CODE ###

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

dp = [0]*N

for i in range(N-1):
    if i >= K:
        x = dp[i]+abs(h[i+1]-h[i])
        for j in range(1,K):
            x = min(x,dp[i-j]+abs(h[i+1]-h[i-j]))
            
    else:
        x = dp[i]+abs(h[i+1]-h[i])
        for j in range(1,i+1):
            x = min(x,dp[i-j]+abs(h[i+1]-h[i-j]))
    
    dp[i+1] = x            



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

dp,dp2,mod = [1]+[0]*12,[0]*13,10**9+7
for i in input():
    if i=="?":
        for k in range(10):
            for j in range(13): dp2[(j*10+k)%13]+=dp[j]
    else:
        for j in range(13): dp2[(j*10+int(i))%13]+=dp[j]
    for j in range(13): dp2[j]%=mod
    dp,dp2 = dp2,[0]*13
print(dp[5])

### FIXED CODE ###

s = input()
ans,mod = [0]*13,10**9+7
if s[0]=="?": ans = [1]*10+[0]*3
else: ans[int(s[0])] = 1
for i in s[1:]:
    dp = [0]*13
    for j in range(13): dp[j*10%13] = ans[j]%mod
    dp+=dp
    if i=="?":
        for j in range(13): ans[j] = sum(dp[j+4:j+14])
    else:
        for j in range(13): ans[j] = dp[j+13-int(i)]
print(ans[5]%mod)
### BUGGY CODE ###

from bisect import insort

X, Y, Z, K = map(int, input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
for i in range(Z-1, 0, -1) :
    C[i] -= C[i-1]

n = []
for x in range(X) :
    for y in range(Y) :
        n.append((A[x]+B[y]+C[0], 0))
n.sort()

for _ in range(K) :
    cur, z = n.pop()
    print(cur)
    if z < Z - 1 :
        z += 1
        insort(n, (cur+C[z], z))

### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

s = []
for x in range(X) :
    for y in range(Y) :
        s.append(A[x]+B[y])
s.sort(reverse=True)

t = []
for k in range(min(K, len(s))) :
    for z in range(Z) :
        t.append(s[k]+C[z])
        
t.sort(reverse=True)

print("\n".join(map(str, t[:K])))