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

import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
import math
import fractions
from heapq import heappush, heappop


#read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

MOD = 10**9+7


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


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


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

lm = 1
s = 0

for i in range(N):
    lm = lcm(A[i], lm)
    #s += lm // MOD
    #lm %= MOD

#lm %= MOD
# print(lm)
ans = 0
for i in range(N):
    m = modinv(A[i], MOD)
    ans += lm * m
    ans %= MOD

print(ans)


### FIXED CODE ###

import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
import math
import fractions
from heapq import heappush, heappop


#read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

MOD = 10**9+7


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


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


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

lm = 1
s = 0

for i in range(N):
    lm = lcm(A[i], lm)
    #s += lm // MOD
    #lm %= MOD

lm %= MOD
# print(lm)
ans = 0
for i in range(N):
    m = modinv(A[i], MOD)
    ans += lm * m
    ans %= MOD

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

import sys
sys.setrecursionlimit(10**7)
num_ver, times_plus = map(int,input().split())
graph_ls = [[] for _ in range(num_ver)]
for i in range(num_ver-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    graph_ls[a].append(b)
    graph_ls[b].append(a)

point_ls = [0] * num_ver
for i in range(times_plus):
    ver, point = map(int,input().split())
    ver -= 1
    point_ls[ver] += point

ans_ls = [0] * num_ver
visited_ls = [0] * num_ver

def dfs(ver,point_before):
    visited_ls[ver] = 1
    point_after = point_before + point_ls[ver]
    ans_ls[ver] = point_after
    for nex in graph_ls[ver]:
        if not visited_ls[nex]:
            dfs(nex, point_after)

dfs(0,0)
for ans in ans_ls:
    print(ans)

### FIXED CODE ###

from collections import deque
n,q = map(int,input().split())
ad_ls = [[] for _ in range(n+1)]
count_ls = [0] * (n+1)
done_ls = [0] * (n+1)
for i in range(n-1):
    a,b = map(int,input().split())
    ad_ls[a].append(b)
    ad_ls[b].append(a)
for i in range(q):
    p,x = map(int,input().split())
    count_ls[p] += x
def turn(ver):
    if ad_ls[ver]:
        for ad in  ad_ls[ver]:
            if not done_ls[ad]:
                count_ls[ad] += count_ls[ver]
                q.append(ad)
    done_ls[ver] = 1
q = deque()
q.append(1)
while len(q) > 0:
    target = q.popleft()
    turn(target)
count_ls = list(map(str, count_ls))
print(' '.join(count_ls[1:]))
### BUGGY CODE ###

import collections


def p_c():
    n = int(input())
    s = [input() for _ in range(n)]

    s_d = [collections.Counter(i) for i in s]
    ans = 0

    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            if s_d[i] == s_d[j]:
                ans += 1

    print(ans//2)


if __name__ == '__main__':
    p_c()

### FIXED CODE ###

from collections import Counter

def p_c():
    n = int(input())
    ans = 0

    l = ["".join(sorted(input())) for _ in range(n)]

    a = Counter(l).values()

    for i in a:
        ans += sum(range(i))

    print(ans)
    
    
if __name__ == '__main__':
    p_c()
### BUGGY CODE ###

import sys

tree={}
VALUE = 0
LEFT = 1
RIGHT = 2
np = -1

home=0
tree[home]=[None, None, None]

def search(p, x):
    while p != None:
        tmp = tree[p][VALUE]
        if tmp == x: return True
        if x < tmp:
            p = tree[p][LEFT]
        else:
            p = tree[p][RIGHT]
    return False

def insert(p, x):
    global np
    if p == None or np == -1:
        np += 1
        tree[np] = [x, None, None]
        return np
    tmp = tree[p][VALUE]
    if x== tmp: return p
    elif x<tmp:
        tree[p][LEFT]=insert(tree[p][LEFT],x)
    else:
        tree[p][RIGHT]=insert(tree[p][RIGHT],x)
    return p

def preorder(p):
    if p == None: return []
    p1, p2 = tree[p][1:3]
    return [tree[p][VALUE]] + preorder(p1) + preorder(p2)

def inorder(p):
    if p == None: return []
    p1, p2 = tree[p][1:3]
    return inorder(p1) + [tree[p][VALUE]] +inorder(p2)

n = int(input())
i = 0
while i<n:
    s = raw_input()
    if s[0]=='i':
        insert(home,int(s[7:]))
    elif s[0]=='p':
        print ' ' + ' '.join(map(str, inorder(home)))
        print ' ' + ' '.join(map(str, preorder(home)))
    i += 1

### FIXED CODE ###

import sys

tree={}
np = -1

home=0
tree[home]=[None, None, None]

def search(p, x):
    while p != None:
        tmp = tree[p]
        if tmp[0] == x: return True
        if x < tmp[0]:
            p = tmp[1]
        else:
            p = tmp[2]
    return False

def node(x):
    global np
    np += 1
    tree[np] = [x, None, None]
    return np

def insert(p, x):
    if p == None or np == -1: return node(x)
    tmp = tree[p]
    if x== tmp[0]: return p
    elif x<tmp[0]:
        tree[p][1]=insert(tmp[1],x)
    else:
        tree[p][2]=insert(tmp[2],x)
    return p

def preorder(p):
    if p == None: return []
    p1, p2 = tree[p][1:3]
    return [tree[p][0]] + preorder(p1) + preorder(p2)

def inorder(p):
    if p == None: return []
    p1, p2 = tree[p][1:3]
    return inorder(p1) + [tree[p][0]] +inorder(p2)

n = int(input())
i = 0
while i<n:
    s = raw_input()
    if s[0]=='i':
        insert(0,int(s[7:]))
    elif s[0]=='p':
        print ' ' + ' '.join(map(str, inorder(home)))
        print ' ' + ' '.join(map(str, preorder(home)))
    i += 1
### BUGGY CODE ###

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

LR = []
for _ in range(M):
    l, r = map(int, input().split())
    LR.append((l, r))
    
cards = LR[:]
master_ids = set(range(cards[0][0], cards[0][1]+1))
for l, r in cards:
    ids = set(range(l, r+1))
    master_ids = master_ids & ids
    if not master_ids:
        break
    
ans = len(master_ids)
print(ans)


### FIXED CODE ###

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

LR = []
for _ in range(M):
    l, r = map(int, input().split())
    LR.append((l, r))
    
cards = LR[:]

import sys
INT_MAX = sys.maxsize

left_id = 0
right_id = INT_MAX
for l, r in cards:
    left_id = max(left_id, l)
    right_id = min(right_id, r)
    
if left_id <= right_id:
    ans = right_id + 1 - left_id
else:
    ans = 0
print(ans)
### BUGGY CODE ###

def main():
    N, M = (int(i) for i in input().split())
    from math import gcd

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

    def prime_factorize(n):
        res = {2: 0}
        for i in range(2, n+1):
            if i*i > n:
                break
            if n % i != 0:
                continue
            ex = 0
            while n % i == 0:
                ex += 1
                n //= i
            res[i] = ex
        if n != 1:
            res[n] = 1
        return res

    B = [int(i)//2 for i in input().split()]
    c = set()
    L = 1
    for b in B:
        L = lcm(L, b)
        c.add(prime_factorize(b)[2])

    if len(c) != 1:
        print(0)
    else:
        ans = 0
        i = 1
        while L*i <= M:
            ans += 1
            i += 2
        print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline

    def gcd(x, y):
        if y == 0:
            return x
        while y != 0:
            x, y = y, x % y
        return x

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

    N, M = (int(i) for i in input().split())
    A = [int(i)//2 for i in input().split()]
    cnt = [0]*(N)
    for i, a in enumerate(A):
        while a % 2 == 0:
            cnt[i] += 1
            a //= 2
    if any(cnt[0] != c for c in cnt):
        return print(0)
    L = 1
    for a in A:
        L = lcm(L, a)

    ans = 0
    mul = 1
    while L*mul <= M:
        ans += 1
        mul += 2
    print(ans)


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

from math import gcd

K=int(input())
sum=0

for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      tmp= gcd(i,j)
      sum += gcd(tmp,k)
      
print(sum)


### FIXED CODE ###

from math import gcd

K=int(input())
sum=0

for i in range(1,K+1):
  for j in range(1,K+1):
    tmp= gcd(i,j)
    for k in range(1,K+1):      
      sum += gcd(tmp,k)
      
print(sum)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**6)
N,Q=map(int, sys.stdin.readline().split())

al=[ [] for _ in range(N+1) ]	#隣接リスト
for _ in range(N-1):
	u,v=map(int, sys.stdin.readline().split())
	al[u].append(v)
	al[v].append(u)

increment=[ 0 for _ in range(N+1) ]
for _ in range(Q):
    p,x=map(int, sys.stdin.readline().split())
    increment[p]+=x

socre=[ 0 for _ in range(N+1) ] #各頂点のカウンターの値を記録
visit=[ 0 for _ in range(N+1) ] #0なら未訪問、1なら訪問済み
point=0
def dfs(par,cur):
    visit[cur]=1
    global point
    point+=increment[cur]
    socre[cur]+=point       #各頂点のカウンターの値を記録
    old=point   #拡張点が子孫に遷移する前のカウンターの値を記録
    for to in al[cur]:
        if visit[to]==0:
            dfs(cur,to)
            point=old   #子孫に遷移し、増えたカウンターの値を自分の時の点数に戻す
dfs(-1,1)

for i in range(1,N+1):
    print socre[i],

### FIXED CODE ###

import sys
from collections import deque

N,Q=map(int, sys.stdin.readline().split())

 
al=[ [] for i in range(N+1) ]
 
for _ in range(N-1):
	a,b=map(int, sys.stdin.readline().split())
	al[a].append(b)
	al[b].append(a)

Visit=[ None for i in range(N+1) ] 
score=[ 0 for i in range(N+1) ] 

for _ in range(Q):
	p,x=map(int, sys.stdin.readline().split())
	score[p]+=x


q=deque()
q.append(1)

while q:
	fro=q.popleft()
	Visit[fro]=1
	for to in al[fro]:
		if Visit[to] is None:
			score[to]+=score[fro]
			q.append(to)


for i,ans in enumerate(score):
	if i==0:	continue
	print ans,
### BUGGY CODE ###

def check(sum, i, j, size):
    s = sum[i][j] - sum[i - size][j] - sum[i][j - size] + sum[i - size][j - size]
    return s == 0

def mm(sum, n, size):
    for i in range(size, n + 1):
            for j in range(size, n + 1):
                if check(sum, i, j, size):
                    return True
    return False

def m(sum, n):
    r = 0
    left, mid, right = 0, 0, n
    while left <= right:
        mid = (left + right) / 2
        if mm(sum, n, mid):
            r = max(r, mid)
            left = mid + 1
        else:
            if left == right:
                break
            right = mid
    return r

while True:
    n = int(raw_input())
    if n == 0:
        break
    s = [map(int, raw_input().replace('.','0').replace('*','1')) for i in range(n)]
    sum = [[0] * (n + 1) for i in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            sum[i][j] += s[i - 1][j - 1]
            sum[i][j] += (sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1])
    print m(sum, n)

### FIXED CODE ###

while True:
    n = int(raw_input())
    if n == 0:
        break
    s = [raw_input() for i in range(n)]
    dp = [[0] * (n + 1) for i in range(n + 1)]
    for i in range(n):
        for j in range(n):
            if s[i][j] == '.':
                dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1
    print max(map(max, dp))
### BUGGY CODE ###

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

mod = 10 **9 +7
kinds = 0

def mod_factorial(n, m):
    r = 1
    for i in range(1, n+1):
        r *= i
        r %= m
    return r

def mod_inv_factorial(n, m):
    invs = [0] * (n + 1)
    invs[1] = 1
    for i in range(2, n + 1):
        invs[i] = m - invs[m % i] * (m//i) % m

    R = [1] * (n+1)

    for i in range(1, n+1):
        if i > 1:
            R[i] = R[i-1]*invs[i]
            R[i] %= m
        else:
            R[i] = invs[i]
    return R


fact_n = mod_factorial(n, mod)
Rs = mod_inv_factorial(n, mod)


for i in range(1, n+1):
    if i != a and i != b:
        kinds += fact_n * Rs[i] * Rs[n-i]
        kinds %= mod

print(kinds % mod)

### FIXED CODE ###

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

mod = 10 **9 +7
kinds = 0

def mod_factorial(nr, nl, m):
    r = 1
    for i in range(nl+1, nr+1):
        r *= i
        r %= m
    return r

def mod_inv_factorial(n1, n2, m):
    n = max(n1, n2)
    invs = [0] * (n + 1)
    invs[1] = 1
    for i in range(2, n + 1):
        invs[i] = m - invs[m % i] * (m//i) % m
        
    r1 = 1
    r2 = 1
    for i in range(1, n1+1):
        r1 *= invs[i]
        r1 %= m
    for i in range(1, n2+1):
        r2 *= invs[i]
        r2 %= m
    return r1, r2
        
        



kinds = 2 ** n -1

la = max(a, n-a)
sa = min(a, n-a)
lb = max(b, n-b)
sb = min(b, n-b)

upper1 = mod_factorial(n, la, mod)
upper2 = mod_factorial(n, lb, mod)

r1, r2 = mod_inv_factorial(sa, sb, mod)

print((kinds - upper1 * r1 - upper2 * r2)% mod)
t = 0
### BUGGY CODE ###

from math import gcd
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))

pc = True
gg = A[0]
so = set()

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            while temp%i==0:
                temp //= i
            arr.append(i)
    if temp!=1:
        arr.append(temp)
    if arr==[]:
        arr.append(n)
    return arr

for a in factorization(A[0]):
    if a > 1:
        so.add(a)

for i in range(1, N):
    for a in factorization(A[i]):
        if a in so:
            pc = False
            break
        if a > 1:
            so.add(a)
    gg = gcd(A[i], gg)

if pc:
    print("pairwise coprime")
elif gg == 1:
    print("setwise coprime")
else:
    print("not coprime")

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))

x = max(A)
hurui = [x]*(x+1)
for i in range(2, x+1):
    for j in range(i, x+1, i):
        hurui[j] = min(i, hurui[j])

cnt = Counter([1])
for i in range(N):
    num = A[i]
    while num > 1:
        x = hurui[num]
        while num%x == 0:
            num //= x
        cnt[x] += 1

a = cnt.most_common(1)[0][1]
if a == 1:
    print("pairwise coprime")
elif a < N:
    print("setwise coprime")
else:
    print("not coprime")
### BUGGY CODE ###

import sys

n = int(input())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))
day = 0
match = [0 for i in range(n)]
while match != [n - 1 for i in range(n)]:
    flag = False
    add = [False for i in range(n)]
    for i in range(n):
        if match[i] <= n - 2:
            j = a[i][match[i]] - 1
            if a[j][match[j]] - 1 == i:
                add[i] = True
                add[j] = True
                flag = True
    if flag == True:
        match = [match[i] + int(add[i]) for i in range(n)]
        day += 1
    else:
        break
else:
    print(day)
    sys.exit()
print(-1)

### FIXED CODE ###

import sys, collections
input = sys.stdin.readline

n = int(input())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))
nums = [0 for i in range(n)]
day = 0
match = 0
flag = True
queue = collections.deque([])
temp = set()
for i in range(1, n + 1):
    i2 = a[i - 1][0]
    if a[i2 - 1][0] == i:
        if i not in temp:
            queue.append([i, i2])
            temp.add(i)
            temp.add(i2)
if not queue:
    flag = False
while queue:
    temp = []
    while queue:
        test = queue.popleft()
        match += 1
        num1, num2 = test[0], test[1]
        nums[num1 - 1] += 1
        nums[num2 - 1] += 1
        temp.append(num1)
        temp.append(num2)
    flag2 = False
    temp2 = set()
    for i in temp:
        if nums[i - 1] <= n - 2:
            new_num = a[i - 1][nums[i - 1]]
            if nums[new_num - 1] <= n - 2 and a[new_num - 1][nums[new_num - 1]] == i:
                if i not in temp2:
                    queue.append([i, new_num])
                    flag2 = True
                    temp2.add(i)
                    temp2.add(new_num)
    if flag2 == False and match < n * (n - 1) // 2:
        flag = False
        break
    day += 1

if flag == True:
    print(day)
else:
    print(-1)
### BUGGY CODE ###

import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
#sys.setrecursionlimit(10 ** 9)
import math
import heapq

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

areas = []
for i in range(M):
	a, b = list(map(int, input().split()))
	bisect.insort(areas, [b - 1, a])

num = 0
loc = 0
for i in range(M):
	if loc < areas[i][1]:
		num += 1
		loc = areas[i][0]

print(num)

### FIXED CODE ###


import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
#sys.setrecursionlimit(10 ** 9)
import math
import heapq

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

areas = []
for i in range(M):
	a, b = list(map(int, input().split()))
	areas.append([b - 1, a])
areas.sort()

num = 0
loc = 0
for i in range(M):
	if loc < areas[i][1]:
		num += 1
		loc = areas[i][0]

print(num)
### BUGGY CODE ###

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

for i in range(N):
    print(A.count(i+1))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = [0 for i in range(N)]

for i in A:
    ans[i-1]+=1

for i in ans:
    print(i)
### BUGGY CODE ###

import bisect
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())))
for i in reversed(range(M)):
    bisect.insort(A, A.pop(-1)//2)
print(sum(A))

### FIXED CODE ###

import heapq
N, M = map(int, input().split())
heap = [-i for i in list(map(int, input().split()))]
heapq.heapify(heap)
for i in range(M):
    heapq.heappush(heap, -(-heapq.heappop(heap)//2))
print(-sum(heap))
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
c=0
pos=0
temp=[]
flag=1
if l.count(1)==0:
    print(-1)
else:
        
    for i in range(1,max(l)+1):
        if i==1:
            
            x=l.index(i)
            temp.append(x)
        else:
            try:
                x=l[temp[-1]::].index(i)+temp[-1]
                temp.append(x)
            except:
    
                break
    
    print(n-len(temp))
            

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
ans=[[]for i in range(n+1)]
for i in range(n):
    ans[l[i]].append(i+1)

    
c=1
tem=[]
ch=0
while 1:
    if c>n:
        break
    else:
        
        if len(ans[c])==0:
            break
        else:
            flag=0
            for i in ans[c]:
                if i>ch:
                    tem.append(i)
                    ch=i
                    flag=1
                    break
            if not flag:
                break
            else:
                c+=1
                    
                
if len(tem)==0:
    print(-1)
else:
    print(n-len(tem))
### BUGGY CODE ###

N,M=map(int,input().split())
cards=[1]*N

for i in range(M):
    l,r=map(int,input().split())
    if l!=1:
        cards[:l-1]=[0]*(l-1)
    if r!=N:
        cards[r:]=[0]*(N-r)
    
print(sum(cards))

### FIXED CODE ###

N,M=map(int,input().split())
cards_l=1
cards_r=N


for i in range(M):
    l,r=map(int,input().split())
    cards_l=max(cards_l,l)
    cards_r=min(cards_r,r)
    #print(r,cards_r)
print(max(0,cards_r-cards_l+1))
### BUGGY CODE ###

# https://atcoder.jp/contests/abc072/tasks/arc082_a
# C - Together

n = int(input().split()[0])
a_list = list(map(int, input().split()))

a_op_list = [(a-1, a, a+1)for a in a_list]
max_count = 0

for a in set(a_list):
    count = len([x for x in a_list if x in [a+1, a, a-1]])
    max_count = count if count > max_count else max_count

print(max_count)


### FIXED CODE ###

# https://atcoder.jp/contests/abc072/tasks/arc082_a
# C - Together
import itertools
import collections

n = int(input().split()[0])
a_list = list(map(int, input().split()))

a_op_list = [[a-1, a, a+1] for a in a_list]
a_op_list = itertools.chain.from_iterable(a_op_list)
c = collections.Counter(a_op_list)
max_count = max(c.values())

print(max_count)
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

X, Y, Z, K = MAP()
A = LIST()
B = LIST()
C = LIST()

A=sorted(A)[::-1]
B=sorted(B)[::-1]
C=sorted(C)[::-1]

D = []
#解法1
for i in range(len(A)):
	for j in range(len(B)):
		D.append(A[i]+B[j])
D.sort(reverse=True)
ans = []
for i in range(len(C)):
	for j in range(len(D[0:K])):
		ans.append(C[i]+D[j])
ans.sort(reverse=True)
for i in ans[0:K]:
	print(i)


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

X, Y, Z, K = MAP()
A = LIST()
B = LIST()
C = LIST()

A=sorted(A)[::-1]
B=sorted(B)[::-1]
C=sorted(C)[::-1]
ans = []
for i in range(len(A)):
	for j in range(len(B)):
		for k in range(len(C)):
			if (i+1)*(j+1)*(k+1) <= K:
				ans.append(A[i]+B[j]+C[k])
			else:
				break
for i in sorted(ans)[::-1][0:K]:
	print(i)
### BUGGY CODE ###

import heapq

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

for _ in range(m):
    b, c = map(int, input().split())
    for __ in range(b):
        mn = heapq.heappop(a)
        if mn < c:
            heapq.heappush(a, c)
        else:
            heapq.heappush(a, mn)
            break

print(sum(a))

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
heapq.heapify(a)
bc = sorted(
    [list(map(int, input().split())) for _ in range(m)],
    reverse=True,
    key=lambda x: x[1],
)

for i in bc:
    b, c = i
    for _ in range(b):
        mn = heapq.heappop(a)
        if mn < c:
            heapq.heappush(a, c)
        else:
            heapq.heappush(a, mn)
            break

print(sum(a))