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

class DisjointSet:
    def __init__(self, size):
        self.rank = [0 for i in range(size)]
        self.p = [0 for i in range(size)]
        for i in range(size):
            self.makeSet(i)
    
    def makeSet(self, x):
        self.p[x] = x
        self.rank[x] = 0

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

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if self.rank[x] > self.rank[y]:
            self.p[y] = x
        else:
            self.p[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
    
    def findSet(self, x):
        if x != self.p[x]:
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]
        

from collections import defaultdict, Counter
count_friend = Counter()
friends = defaultdict(set)
blocks = defaultdict(set)
N, M, K = map(int, input().split())
ds = DisjointSet(N+1)
# graph = [[] for i in range(N+1)]
for i in range(M):
    A, B = map(int, input().split())
    ds.unite(A, B)
    count_friend[A] += 1
    count_friend[B] += 1
for i in range(K):
    C, D = map(int, input().split())
    blocks[C].add(D)
    blocks[D].add(C)
c_ids = [ds.findSet(i) for i in range(N+1)]
for i in range(1, N+1):
    friends[c_ids[i]].add(i)
ans = []
for i in range(1, N+1):
    c_id = c_ids[i]
    ans += [len(friends[c_id]-blocks[i])-count_friend[i]-1]
print(' '.join(list(map(str, ans))))
# print(ds.p)

### FIXED CODE ###

class DisjointSet:
    def __init__(self, size):
        self.rank = [0 for i in range(size)]
        self.p = [0 for i in range(size)]
        for i in range(size):
            self.makeSet(i)
    
    def makeSet(self, x):
        self.p[x] = x
        self.rank[x] = 0

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

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if self.rank[x] > self.rank[y]:
            self.p[y] = x
        else:
            self.p[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
    
    def findSet(self, x):
        if x != self.p[x]:
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]
        

from collections import defaultdict, Counter
count_friend = Counter()
# friends = defaultdict(list)
friends_cluster = Counter()
# blocks = defaultdict(set)
count_block = Counter()
N, M, K = map(int, input().split())
ds = DisjointSet(N+1)
# graph = [[] for i in range(N+1)]
for i in range(M):
    A, B = map(int, input().split())
    ds.unite(A, B)
    count_friend[A] += 1
    count_friend[B] += 1
for i in range(K):
    C, D = map(int, input().split())
    if ds.same(C, D):
        count_block[C] += 1
        count_block[D] += 1
c_ids = [ds.findSet(i) for i in range(N+1)]
for i in range(1, N+1):
    friends_cluster[c_ids[i]] += 1
ans = []
for i in range(1, N+1):
    c_id = c_ids[i]
    ans += [friends_cluster[c_id]-count_block[i]-count_friend[i]-1]
print(' '.join(list(map(str, ans))))
# print(ds.p)
### BUGGY CODE ###

n = int(input())
s = ["".join(sorted(input())) for i in range(n)]
cnt = 0
for i in range(len(s)):
    for j in s[i + 1:]:
        if s[i] == j:
            cnt += 1
        else:
            continue
print(cnt)

### FIXED CODE ###

from collections import Counter

total = 0
n = int(input())
word_list = ["".join(sorted(input())) for _ in range(n)]
count_words = dict(Counter(word_list))
for item in count_words:
    ans = 0
    tmp = count_words[item] - 1
    ans = 1/2 * tmp * (tmp + 1)
    total += ans
print(int(total))
### BUGGY CODE ###

A,B,N = map(int,input().split())
max_n = -1
endpoint = min(B-1,N)
for i in range(endpoint+1) :
    n = ((A * i) // B) - A * (i // B)
    # print(i,n)
    if (max_n < n) :
        max_n = n

print(max_n)

### FIXED CODE ###

def f(x) :
    return ((A * x) // B) - A * (x // B)

A,B,N = map(int,input().split())
print(f(min(B-1,N)))
### BUGGY CODE ###

from collections import defaultdict

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

MAX_NUM = []
len_weights = 0
def dfs(nums):
    if len(nums) == len_weights:
        sum_w = 0
        value = 0
        for i in range(len_weights):
            sum_w += weights[i] * nums[i]
            value += sum(items[weights[i]][0:nums[i]])
        return value if sum_w <= W else 0
    value = 0
    i = len(nums)
    for j in range(MAX_NUM[i] + 1):
        value = max(value, dfs(nums + [j]))
    return value

items = defaultdict(list)
for i in range(N):
    w, v = map(int, input().split())
    items[w].append(v)

for v in items.values():
    v.sort(reverse=True)

weights = sorted(items.keys())
len_weights = len(weights)
for w in weights:
    MAX_NUM.append(W // w)
print(dfs([]))


### FIXED CODE ###

from collections import defaultdict

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

MAX_NUM = []
len_weights = 0
def dfs(nums):
    if len(nums) == len_weights:
        sum_w = 0
        value = 0
        for i in range(len_weights):
            sum_w += weights[i] * nums[i]
            if nums[i] >= 1:
                value += items[weights[i]][nums[i] - 1]
        return value if sum_w <= W else 0
    value = 0
    i = len(nums)
    for j in range(MAX_NUM[i] + 1):
        value = max(value, dfs(nums + [j]))
    return value

items = defaultdict(list)
for i in range(N):
    w, v = map(int, input().split())
    items[w].append(v)

for v in items.values():
    v.sort(reverse=True)
    for i in range(1, len(v)):
        v[i] = v[i - 1] + v[i]

weights = sorted(items.keys())
len_weights = len(weights)
for w in weights:
    MAX_NUM.append(min(W // w, len(items[w])))
print(dfs([]))
### BUGGY CODE ###

n = int(input())
l = list(input())
q = int(input())
for _ in range(q):
  a,b,c = input().split()
  b = int(b)-1
  if a=='1':
    l[b] = c
  else:
    s = set()
    for t in l[b:int(c)]:
      s |= {t}
    print(len(s))

### FIXED CODE ###

n=int(input())
l=list(input())
q=int(input())
bit=[[0]*(n+1) for i in range(26)]
def bit_sum(o,i):
  s=0
  while i:
    s+=bit[o][i]
    i-=i&-i
  return s
def bit_add(o,i,x):
  while i<=n:
    bit[o][i] += x
    i+=i&-i
for i in range(n):
  bit_add(ord(l[i])-97,i+1,1)
for i in range(q):
  a,b,c=input().split()
  b=int(b)-1
  if a=='1':
    bit_add(ord(l[b])-97,b+1,-1)
    l[b]=c
    bit_add(ord(c)-97,b+1,1)
  else:
    c=int(c)
    print(sum(1 for o in range(26) if bit_sum(o,c)-bit_sum(o,b)))
### BUGGY CODE ###

n = int(input())
a = map(int, input().split())
i = 1
for x in a:
  i *= x

if i > 1000000000000000000:
  i = -1
print(i)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
i = 1
if 0 in a:
  print(0)
  exit()

for x in a:
  i *= x
  if i > 10 ** 18:
    break


if i > 10 ** 18:
  i = -1
print(i)
### BUGGY CODE ###

import sys
import math
input = sys.stdin.readline
input = sys.stdin.buffer.readline

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
def RN(N): return [input().strip() for i in range(N)]

def a(A,B,x): return math.floor(A*x/B)-A*math.floor(x/B)

def main():
    A,B,N = MI()
    max = 0
    #print(a(A,B,x))
    for x in range(0, N+1):
        if max < a(A,B,x):
            max = a(A,B,x)
    
    print(max)



    


if __name__ == "__main__":
	main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
input = sys.stdin.buffer.readline

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
def RN(N): return [input().strip() for i in range(N)]

def a(A,B,x): return (A*x//B)-A*(x//B)

def main():
    A,B,N = MI()
    """
    max = 0
    m = 0
    for x in range(0, N+1):
        ai = a(A,B,x)
        if max < ai :
            max = ai
        elif ai<0 and m == 0:
            max = ai
            m +=1

        print(x,a(A,B,x))
    """
    if N >= B:
        x = (N//B)*B-1
    elif N == B:
        x = N-1
    elif N < B:
        x = N
    print(a(A,B,x))

    



    


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

A, B = map(int, input().split())
ans = 0
for i, a in enumerate(range(A, B+1)):
    if i == 0:
        ans = a
    else:
        ans = ans ^ a
print(ans)

### FIXED CODE ###

A, B = map(int, input().split())
res = B - A
res = res % 4
if A % 2 == 0:
    ans = B
    for i in range(1, res+1):
        ans = ans ^ (B - i)
    print(ans)
    exit()
else:
    ans = A
    for i in range(0, res):
        ans = ans ^ (B - i)
    print(ans)
    exit()
### BUGGY CODE ###

import bisect

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

ans = 0

d = []

for i in range(n):
	for j in range(i+1,n):
		index = bisect.bisect_left(l,l[i]+l[j])
		for k in range(i+1,index):
			if k == j:
				continue
			if l[j] < l[k] + l[i]:
				if j < k:
					if [i,j,k] not in d:
						d.append([i,j,k])
						ans += 1
				else:
					if [i,k,j] not in d:
						d.append([i,k,j])
						ans += 1

print(ans)


### FIXED CODE ###

import bisect

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

l.sort()
#print(l)
ans = 0
for i in range(n-1):
	a = l[i]
	for j in range(i+2,n):
		b = l[j]
		c = bisect.bisect_left(l,b-a+1)
		if j - c > 0:
			if i >= c:
				ans += j-i-1
			else:
				ans += j-c
		#print(i,j,c,ans)

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

H, N = map(int, input().split())
a = [None] * (N + 1)
b = [None] * (N + 1)
for i in range(1, N + 1):
    a[i], b[i] = map(int, input().split())

# dp[i][j] = 魔法iまでからダメージの総和がj以上になるように選んだ時の魔力の最小値
# dp[i][j] = min(dp[i][j - a] + b, dp[i - 1][j])

dp = [[float('inf') for _ in range(H + 1)] for _ in range(N + 1)]
for i in range(N + 1):
    dp[i][0] = 0
for i in range(1, N + 1):
    for j in range(H + 1):
        dp[i][j] = min(dp[i][max(0, j - a[i])] + b[i], dp[i - 1][j])
print(dp[N][H])


### FIXED CODE ###

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

# dp[i][j] = 魔法iまでからダメージの総和がj以上になるように選んだ時の魔力の最小値
# dp[i][j] = min(dp[i][j - a] + b, dp[i - 1][j])

dp = [[float('inf')] * (H + 1)] * (N + 1)
for i in range(N + 1):
    dp[i][0] = 0
for i in range(1, N + 1):
    a, b = map(int, input().split())
    for j in range(H + 1):
        dp[i][j] = min(dp[i][max(0, j - a)] + b, dp[i - 1][j])
print(dp[N][H])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)

def dfs(v,val):
  cnt[v]+=val
  for u in g[v]:
    if checked[u]==1:
      continue
    checked[u]=1
    dfs(u,cnt[v])

n,q=map(int,input().split())
cnt=[0]*(n+1)
g=[[] for _ in range(n+1)]
for _ in range(n-1):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
for _ in range(q):
  v,val=map(int,input().split())
  cnt[v]+=val
checked=[0]*(n+1)
checked[1]=1
dfs(1,0)
print(*cnt[1:])

### FIXED CODE ###

import collections

n,q=map(int,input().split())
cnt=[0]*(n+1)
g=[[] for _ in range(n+1)]
for _ in range(n-1):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
for _ in range(q):
  v,val=map(int,input().split())
  cnt[v]+=val
q=collections.deque()
q.append(1)
checked=[0]*(n+1)
while q:
  v=q.pop()
  checked[v]=1
  for u in g[v]:
    if checked[u]==1:
      continue
    cnt[u]+=cnt[v]
    q.append(u)
print(*cnt[1:])
### BUGGY CODE ###

import sys
INF = 10**18
sys.setrecursionlimit(10**6)
from collections import defaultdict
def li():
    return [int(x) for x in input().split()]
from collections import deque

H, W = li()
Ch, Cw = li()
Dh, Dw = li()
S = [list(input()) for x in range(H)]

v = [(1,0), (0,1), (-1,0), (0,-1)]

def bfs():
    costmap = [[-1] * W for i in range(H)]
    costmap[Ch-1][Cw-1] = 0
    que = deque([])
    que.append((Cw, Ch))

    while que:
        # print(que)
        # 左から取り出す
        x, y = que.popleft()
        # 通常移動パターン
        for i in range(len(v)):
            nx = x + v[i][0]
            ny = y + v[i][1]
            # バリデーション
            if nx <= 0 or nx > W or ny <= 0 or ny > H:
                continue
            if S[ny-1][nx-1] != '.':
                continue
            # 初探索 or コストが下がる場合
            if costmap[ny-1][nx-1] == -1 or costmap[y-1][x-1] < costmap[ny-1][nx-1]:
                # コストゼロは左から
                que.appendleft((nx, ny))
                costmap[ny-1][nx-1] = costmap[y-1][x-1]
        # 特殊移動パターン
        for i in range(x-2, x+3):
            for j in range(y-2, y+3):
                nx, ny = i, j
                # バリデーション
                if nx <= 0 or nx > W or ny <= 0 or ny > H:
                    continue
                if S[ny-1][nx-1] != '.':
                    continue
                # 初探索 or コストが下がる場合
                if costmap[ny-1][nx-1] == -1 or costmap[y-1][x-1] < costmap[ny-1][nx-1]:
                    # コスト1は右から
                    que.append((nx, ny))
                    costmap[ny-1][nx-1] = costmap[y-1][x-1] + 1
    return costmap

costmap = bfs()
# print(costmap)
print(costmap[Dh-1][Dw-1])


### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
s=[list(input()) for i in range(h)]
 
#幅優先で解く。
dx=[1,0,-1,0]
dy=[0,1,0,-1]
def bfs():
  maze=[[-1]*w for i in range(h)]
  maze[ch-1][cw-1]=0
  qu=deque([])
  qu.append((cw-1,ch-1))
  magic=0
  
  while qu:
    x,y=qu.popleft()
    for i in range(4):
      nx=dx[i]+x
      ny=dy[i]+y
      if 0<=nx<=w-1 and 0<=ny<=h-1 and s[ny][nx]=="." and (maze[ny][nx]==-1 or maze[ny][nx]>maze[y][x]):
        qu.appendleft((nx,ny))
        maze[ny][nx]=maze[y][x]
    for i in range(x-2,x+3):
      for j in range(y-2,y+3):
        nx=i
        ny=j
        if 0<=nx<=w-1 and 0<=ny<=h-1 and s[ny][nx]=="." and (maze[ny][nx]==-1 or maze[ny][nx]>maze[y][x]+1):
          qu.append((nx,ny))
          maze[ny][nx]=maze[y][x]+1
  return maze
    
maze = bfs()
print(maze[dh-1][dw-1])
### BUGGY CODE ###

s = input()
ans = 0
while True:
    a = s.count('01')
    ans += 2*a
    s = s.replace('01', '')
    
    b = s.count('10')
    ans += 2*b
    s = s.replace('10', '')

    if not a and not b:
        break
print(ans)


### FIXED CODE ###

from collections import Counter
c = Counter(input())
print(2 * min((c['0'], c['1'])))
### BUGGY CODE ###

from heapq import heappush, heappop
n, x, y = map(int, input().split())

links = [[] for i in range(n)]
for i in range(1, n):
        links[i-1].append(i)
        links[i].append(i-1)
links[x-1].append(y-1)
links[y-1].append(x-1)

ans = [0] * (n+1)
for i in range(n):
        dist = [1e5] * n
        used = [0] * n
        que = []
        heappush(que, [0, i])
        while len(que):
                dis, v = heappop(que)
                if used[v]: continue
                ans[dis] += 1
                used[v] = True
                for to in links[v]:
                        if not used[to]:
                                heappush(que, [dis+1, to])
for i in range(1, n): print(ans[i]//2)

### FIXED CODE ###

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

ans = [0] * (n+1)
for i in range(1, n+1):
        for j in range(i+1, n+1):
                ans[min(j-i, abs(i-x)+1+abs(j-y))] += 1
for i in range(1, n): print(ans[i])
### BUGGY CODE ###

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

from collections import Counter

def main():
  n = int(input())
  la = sorted(list(map(int, input().split())))
  primes = [la[0]]
  cands = la[1:]
  while len(cands) != 0:
    prime = primes[-1]
    cands = list(filter(lambda x:x%prime != 0, cands))
    if len(cands) == 0:
      break
    primes.append(cands.pop(0))
  print(len(set(primes) - set([k for k, v in Counter(la).items() if v >= 2])))

if __name__=='__main__':
  main()


### FIXED CODE ###

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

import numpy

def main():
  n = int(input())
  la = sorted(list(map(int, input().split())))
  a_max = max(la)
  dp = numpy.ones(a_max + 1)
  counts = numpy.zeros(a_max + 1)
  for a in la:
    counts[a] += 1
    if counts[a] < 2:
      dp[2*a::a] = 0
  print(len([a for a in la if dp[a]==1 and counts[a] == 1]))

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

n,m = map(int,input().split())
lis = list(map(int,input().split()))
path = [[] for i in range(n)]

for i in range(m):
    x,y = map(int,input().split())
    x -= 1;y -= 1
    path[x].append(y)
    path[y].append(x)

gone = [-1] * n
numberindex = set()
ans = 0

for i in range(n):
    if gone[i] == -1:
        now = [i]
        realnumber = [0] * n
        numberindex.add(i)
        while now:
            a = now.pop(0)
            gone[a] = 1
            numberindex.add(a)
            realnumber[lis[a]-1] = 1
            for go in path[a]:
                if gone[go] == -1:
                    now.append(go)
                    gone[go] = 1
        for num in numberindex:
            if realnumber[num] == 1:
                ans += 1
        numberindex = set()

print(ans)

### FIXED CODE ###

import numpy as np
n,m = map(int,input().split())
lis = list(map(int,input().split()))
path = [[] for i in range(n)]

for i in range(m):
    x,y = map(int,input().split())
    x -= 1;y -= 1
    path[x].append(y)
    path[y].append(x)

gone = np.array([-1] * n)
numberindex = set()
realnumber = set()
ans = 0

for i in range(n):
    if gone[i] == -1:
        now = [i]
        while now:
            a = now.pop(0)
            gone[a] = 1
            numberindex.add(a)
            realnumber.add(lis[a]-1)
            for go in path[a]:
                if gone[go] == -1:
                    now.append(go)
                    gone[go] = 1
        ans += len(realnumber & numberindex)
        realnumber,numberindex = set(),set()
print(ans)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
S = [list(input()[:-1]) for i in range(h)]

d = [[10**20]*w for i in range(h)]

dq = deque([(ch-1,cw-1,0)])
d[ch-1][cw-1] = 0
dx = [0,-1,0,1]
dy = [-1,0,1,0]

while dq:
    nx,ny,nd = dq.popleft()
    if nd < d[nx][ny]:continue
    for delta in range(4):
        tx,ty = nx+dx[delta], ny + dy[delta]
        if 0 <= tx < h and 0 <= ty < w and S[tx][ty] == "." and d[tx][ty] > d[nx][ny]:
            d[tx][ty] = d[nx][ny]
            dq.appendleft((tx,ty,d[tx][ty]))
    for deltax in range(-2,3):
        for deltay in range(-2,3):
            tx,ty = nx+deltax, ny + deltay
            if 0 <= tx < h and 0 <= ty < w and S[tx][ty] == "." and d[tx][ty] > d[nx][ny]+1:
                d[tx][ty] = d[nx][ny] + 1
                dq.appendleft((tx,ty,d[tx][ty]))

print(d[dh-1][dw-1] if d[dh-1][dw-1] != 10**20 else -1)


### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
S = [list(input()[:-1]) for i in range(h)]

d = [[10**20]*w for i in range(h)]

dq = deque([(ch-1,cw-1,0)])
d[ch-1][cw-1] = 0
dx = [0,-1,0,1]
dy = [-1,0,1,0]

while dq:
    nx,ny,nd = dq.popleft()
    if nd < d[nx][ny]:continue
    for delta in range(4):
        tx,ty = nx+dx[delta], ny + dy[delta]
        if 0 <= tx < h and 0 <= ty < w and S[tx][ty] == "." and d[tx][ty] > d[nx][ny]:
            d[tx][ty] = d[nx][ny]
            dq.appendleft((tx,ty,d[tx][ty]))
    for deltax in range(-2,3):
        for deltay in range(-2,3):
            tx,ty = nx+deltax, ny + deltay
            if 0 <= tx < h and 0 <= ty < w and S[tx][ty] == "." and d[tx][ty] > d[nx][ny]+1:
                d[tx][ty] = d[nx][ny] + 1
                dq.append((tx,ty,d[tx][ty]))

print(d[dh-1][dw-1] if d[dh-1][dw-1] != 10**20 else -1)
### BUGGY CODE ###

import numpy as np

N = int(input())
A = np.array([int(x) for x in input().split()])
end_set = set()
count = 0

for a in A:
    if not end_set:
        count += 1
    elif a == min(min(end_set), a):
        count += 1
    end_set.add(a)

print(count)


### FIXED CODE ###

N = int(input())
A = list([int(x) for x in input().split()])
count = 0

min_a = N+1

for a in A:
    if a == min(min_a, a):
        count += 1
        min_a = a

print(count)
### BUGGY CODE ###

#!/usr/bin/env python3

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

A_n = [a + b + 1 for a, b in enumerate(A)]

ret = 0
for n in range(len(A)):
    #print(A_n[:n], n + 1 - A[n])
    ret += A_n[:n].count(n + 1 - A[n])
print(ret)


### FIXED CODE ###

#!/usr/bin/env python3

import numpy as np

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

# A_n = [a + b + 1 for a, b in enumerate(A)]

# ret = 0
# for n in range(len(A)):
#     #print(A_n[:n], n + 1 - A[n])
#     ret += A_n[:n].count(n + 1 - A[n])
# print(ret)

nmax = int(2e5 + 1)
X = [0] * nmax
Y = [0] * nmax
for n, a in enumerate(A):
    x = n - a
    y = n + a
    if x >= 0 and x < nmax:
        X[x] += 1
    if y >= 0 and y < nmax:
        Y[y] += 1
ret = 0
for x, y in zip(X, Y):
    ret += x * y
print(ret)
### BUGGY CODE ###

from heapq import heapify,heappop,heappush

X,Y,Z,K=map(int,input().split())
A=sorted(map(int,input().split()),reverse=True)
B=sorted(map(int,input().split()),reverse=True)
C=sorted(map(int,input().split()),reverse=True)
que=[[-(A[0]+B[0]+C[0]),0,0,0]];heapify(que)
Count=[[[0]*(Z+1) for i in range(Y+1)] for j in range(X+1)]

for i in range(K):
    p=heappop(que)
    print(-p[0])
    if p[1]<X-1 and Count[p[1]+1][p[2]][p[3]]==0:
        heappush(que,[-sum([A[p[1]+1],B[p[2]],C[p[3]]]),p[1]+1,p[2],p[3]])
        Count[p[1]+1][p[2]][p[3]]+=1
    if p[2]<Y-1 and Count[p[1]][p[2]+1][p[3]]==0:
        heappush(que,[-sum([A[p[1]],B[p[2]+1],C[p[3]]]),p[1],p[2]+1,p[3]])
        Count[p[1]][p[2]+1][p[3]]+=1
    if p[3]<Z-1 and Count[p[1]][p[2]][p[3]+1]==0:
        heappush(que,[-sum([A[p[1]],B[p[2]],C[p[3]+1]]),p[1],p[2],p[3]+1])
        Count[p[1]][p[2]][p[3]+1]+=1

### FIXED CODE ###

from heapq import heapify,heappop,heappush

X,Y,Z,K=map(int,input().split())
A=sorted(map(int,input().split()),reverse=True)
B=sorted(map(int,input().split()),reverse=True)
C=sorted(map(int,input().split()),reverse=True)
que=[[-(A[0]+B[0]+C[0]),0,0,0]];heapify(que)
s=set()

for i in range(K):
    p=heappop(que)
    print(-p[0])
    if p[1]<X-1 and not (p[1]+1,p[2],p[3]) in s:
        heappush(que,[-sum([A[p[1]+1],B[p[2]],C[p[3]]]),p[1]+1,p[2],p[3]])
        s.add((p[1]+1,p[2],p[3]))
    if p[2]<Y-1 and not (p[1],p[2]+1,p[3]) in s:
        heappush(que,[-sum([A[p[1]],B[p[2]+1],C[p[3]]]),p[1],p[2]+1,p[3]])
        s.add((p[1],p[2]+1,p[3]))
    if p[3]<Z-1 and not (p[1],p[2],p[3]+1) in s:
        heappush(que,[-sum([A[p[1]],B[p[2]],C[p[3]+1]]),p[1],p[2],p[3]+1])
        s.add((p[1],p[2],p[3]+1))
### BUGGY CODE ###

N, M =  map(int, (input().split(' ')))
A_list = []
B_list = []
money = 0
while len(A_list) < N:
    A, B =  map(int, (input().split(' ')))
    A_list.append(A)
    B_list.append(B)

while True:
    i = A_list.index(min(A_list))
    if B_list[i] < M:
        money += A_list[i] * B_list[i]
        M -= B_list[i]
    else:
        money += A_list[i] * M
        M = 0 
    A_list[i] = 99999999999999999999999999999999999999
    if M == 0:
        print(money)
        exit()

### FIXED CODE ###

N, M =  map(int, (input().split(' ')))
A_B_list = []
money = 0
while len(A_B_list) < N:
    A, B =  map(int, (input().split(' ')))
    A_B_list.append([A, B])
A_B_list = sorted(A_B_list)
    

for A, B in A_B_list:
    if B < M:
        money += A * B
        M -= B
    else:
        money += A * M
        M = 0 
    if M == 0:
        print(money)
        exit()