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

# -*- coding: utf-8 -*-
"""
Created on Sun Apr  7 00:03:49 2019

@author: Yamazaki Kenichi
"""
import heapq

X,Y,Z,K = map(int,input().split())
A = list(map(int,input().split())) + [-10**9]
B = list(map(int,input().split())) + [-10**9]
C = list(map(int,input().split())) + [-10**9]
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
Q = []
T = [[[-1 for i in range(Z+1)] for i in range(Y+1)] for i in range(X+1)]
T[0][0][0] = 1
heapq.heappush(Q,[-(A[0]+B[0]+C[0]),0,0,0])
for i in range(K-1):
    k = heapq.heappop(Q)
    s1,s2,s3 = k[1],k[2],k[3]
    if T[s1+1][s2][s3] == -1:
        heapq.heappush(Q,[-(A[s1+1]+B[s2]+C[s3]),s1+1,s2,s3])
        T[s1+1][s2][s3] = 1
    if T[s1][s2+1][s3] == -1:
        heapq.heappush(Q,[-(A[s1]+B[s2+1]+C[s3]),s1,s2+1,s3])
        T[s1][s2+1][s3] = 1
    if T[s1][s2][s3+1] == -1:
        heapq.heappush(Q,[-(A[s1]+B[s2]+C[s3+1]),s1,s2,s3+1])
        T[s1][s2][s3+1] = 1
    print(-k[0])
k = heapq.heappop(Q)
print(-k[0])


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Wed Apr 10 22:30:07 2019

@author: Yamazaki Kenichi
"""
import heapq
#import random
#X,Y,Z,K = 1000,1000,1000,3000
#A = random.sample(range(10**9),1000)
#B = random.sample(range(10**9),1000)
#C = random.sample(range(10**9),1000)

X,Y,Z,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
Q = []
T = [[-1 for i in range(X)] for i in range(Y)]
T[0][0] = 0
heapq.heappush(Q,[-(A[0]+B[0]+C[0]),0,0,0])
for i in range(K-1):
    k = heapq.heappop(Q)
    s1,s2,s3 = k[1],k[2],k[3]
    if s1 + 1 != X and T[s1+1][s2] < s3:
        heapq.heappush(Q,[-(A[s1+1]+B[s2]+C[s3]),s1+1,s2,s3])
        T[s1+1][s2] += 1
    if s2 + 1 != Y and T[s1][s2+1] < s3:
        heapq.heappush(Q,[-(A[s1]+B[s2+1]+C[s3]),s1,s2+1,s3])
        T[s1][s2+1] += 1
    if s3 + 1 != Z and T[s1][s2] < s3 + 1:
        heapq.heappush(Q,[-(A[s1]+B[s2]+C[s3+1]),s1,s2,s3+1])
        T[s1][s2] += 1
    print(-k[0])
k = heapq.heappop(Q)
print(-k[0])
### BUGGY CODE ###


N = int(input())

dep = []

for i in range(N):

    dep.append([0] * N)


lis = []

for i in range(N):

    l1 = []

    for j in range(N):

        l1.append([])

    lis.append(l1)

A = []

for i in range(N):

    a = list(map(int,input().split()))
    A.append(a)

    for j in range(len(a)-1):

        lmi = min(i,a[j]-1)
        lma = max(i,a[j]-1)
        rmi = min(i,a[j+1]-1)
        rma = max(i,a[j+1]-1)

        lis[lmi][lma].append([rmi,rma])

Q = []

 
for i in range(N):

    if i + 1 == A[A[i][0]-1][0] and i + 1 < A[i][0]:
        Q.append([i,A[i][0]-1])
        dep[i][A[i][0]-1] = 1

#print (Q)
#print (lis)
flag = True
if len(Q) == 0:
    flag = False


ans = 1

while len(Q) > 0 and ans < N * (N-1) // 2 + 5:

    q = Q.pop(0)

    for nex in lis[q[0]][q[1]]:

        l = nex[0]
        r = nex[1]

        if dep[l][r] < dep[q[0]][q[1]] + 1:
            dep[l][r] = dep[q[0]][q[1]] + 1
            Q.append([l,r])

            ans = max(ans,dep[l][r])

if ans <= N * (N-1) // 2 and flag:
    print (ans)
else:
    print (-1)
        


### FIXED CODE ###


N = int(input())

A = []

for i in range(N):

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

    A.append(a)

Q = []
for i in range(N):

    if A[ A[i][0]-1 ][0] == i + 1 and A[i][0]-1 > i:
        Q.append([min(A[i][0]-1,i),max(A[i][0]-1,i),1])

day = 0

while len(Q) > 0:

    q = Q.pop(0)

    del A[q[0]][0]
    del A[q[1]][0]




    if len(A[q[0]]) > 0 and A[ A[q[0]][0] - 1 ][0] == q[0] + 1:
        Q.append([min(A[q[0]][0] - 1,q[0]),max(A[q[0]][0] - 1,q[0]),q[2]+1])

    if len(A[q[1]]) > 0 and A[ A[q[1]][0] - 1 ][0] == q[1] + 1:
        Q.append([min(A[q[1]][0] - 1,q[1]),max(A[q[1]][0] - 1,q[1]),q[2]+1])

    day = max(day,q[2])

flag = True

for a in A:
    if len(a) > 0:
        flag = False
        
if flag:
    print (day)
else:
    print (-1)
### BUGGY CODE ###

from operator import itemgetter
import sys

# スペース区切りの整数入力
n,d,a = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
e = []
for i in range(n):
    e.append([int(x) for x in input().split()])
e.sort(key=itemgetter(0))

atk_times_sum = 0

while len(e) > 0:
    atk_l = e[0][0]
    atk_u = e[0][0] + d*2
    if e[0][1] % a == 0:
        atk_times = int(e[0][1] / a)
    else:
        atk_times = int(e[0][1] / a) + 1
    atk_times_sum += atk_times
    for i in range(len(e)-1,-1,-1):
        if atk_l <= e[i][0] and e[i][0] <= atk_u:
            e[i][1] -=  a * atk_times
            if e[i][1] <=  0:
                del(e[i])

print(atk_times_sum)

### FIXED CODE ###

from operator import itemgetter
from collections import deque
import sys

# スペース区切りの整数入力
n,d,a = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
e = []
for i in range(n):
    e.append([int(x) for x in input().split()])
e.sort(key=itemgetter(0))

atk_times_sum = 0
atk_que = deque()
atk_acm_p = 0

for i in range(n):
    while len(atk_que) > 0:
        if atk_que[0][0] < e[i][0]:
            atk_u,atk_p = atk_que.popleft()
            atk_acm_p -= atk_p
        else:
            break
    e[i][1] -= atk_acm_p
    if e[i][1] <= 0:
        continue
    atk_u = e[i][0] + d*2
    if e[i][1] % a == 0:
        atk_times = e[i][1] // a
    else:
        atk_times = e[i][1] // a + 1
    e[i][1] = 0 
    atk_times_sum += atk_times
    atk_p = a * atk_times
    atk_acm_p += atk_p
    atk_que.append([atk_u,atk_p])

print(atk_times_sum)
### BUGGY CODE ###

N = int(input())
for ai in range(1,3500):
    for bi in range(1,3500):
        try:
            ci = N*ai*bi/(4*ai*bi-N*ai-N*bi)
        except:
            continue
        if ci == int(ci) and ci > 0:
            print(ai,bi,int(ci))
            exit()


### FIXED CODE ###

N = int(input())
for ai in range(1,3500):
    for bi in range(1,3500):
        try:
            ci = N*ai*bi/(4*ai*bi-N*ai-N*bi)
        except:
            continue
        if ci == int(ci) and ci > 0:
            print(ai,bi,int(ci))
            exit()
### BUGGY CODE ###

N = int(input())
#S = [input() for i in range(N)]
S=[]
ans_list = []
temp_ans = 0
ans = 0

for i in range(N):
    S.append(''.join(sorted(list(input()))))

string_set = set(S)

for s in string_set:
    for i in S:
        if s==i:
            temp_ans += 1
    ans_list.append(temp_ans)
    temp_ans = 0

for a in ans_list:
    ans += a*(a-1)/2

print(round(ans))

### FIXED CODE ###

N = int(input())
#S = [input() for i in range(N)]
S=[]
ans_dic={}
temp_ans = 1
ans = 0

for i in range(N):
    temp = sorted(list(input()))
    temp = ''.join(temp)
    #S.append(''.join(temp))
    #alpha_dic[temp[0]].append(i) 
    if temp in ans_dic:
        ans_dic[temp] += 1
    else:
        ans_dic[temp] = 1
    
for key,value in ans_dic.items():
    ans += value*(value-1)/2

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

N=int(input())

res=1
for i in range(1,N+1):
  res=res*i

print(res%(10**9+7))

### FIXED CODE ###

N=int(input())

res=1
for i in range(1,N+1):
  res=res*i
  res=res%(10**9+7)

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

def main():
    N=int(input())
    P=[int(_) for _ in input().split()]
    ans = 0
    for i in range(N):
        if P[i] == min(P[:i+1]):
            ans += 1
    print(ans)
main()


### FIXED CODE ###

INF=float('inf')

def main():
    N=int(input())
    P=[int(_) for _ in input().split()]
    tmp=INF
    ans = 0

    for i in range(N):
        if tmp > P[i]:
            ans += 1
        tmp = min(tmp, P[i])
    print(ans)

main()
### BUGGY CODE ###

class UnionFind:

    # n要素で初期化
    def __init__(self,n):
        self.par = list(range(n))
        self.rank = [0]*n

    # 木の根を求める
    def find(self,x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    # xとyの属する集合を併合
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return None
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # xとyが同じ集合に属するか否か
    def same(self,x,y):
        return self.find(x) == self.find(y)

if __name__ == '__main__':
    n,k,l = map(int,input().split())
    UF_k = UnionFind(n)
    UF_l = UnionFind(n)
    for i in range(k):
        p,q = map(int,input().split())
        UF_k.unite(p-1,q-1)
    for i in range(l):
        r,s = map(int,input().split())
        UF_l.unite(r-1,s-1)

    for i in range(n):
        res = 0
        for j in range(n):
            if UF_k.same(i,j) and UF_l.same(i,j):
                res += 1
        print(res,end=' ')
    



### FIXED CODE ###

import bisect
class UnionFind:

    # n要素で初期化
    def __init__(self,n):
        self.par = list(range(n))
        self.rank = [0]*n
        self.memo = {}

    # 木の根を求める
    def find(self,x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    # xとyの属する集合を併合
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return None
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # xとyが同じ集合に属するか否か
    def same(self,x,y):
        return self.find(x) == self.find(y)

if __name__ == '__main__':
    n,k,l = map(int,input().split())
    UF_k = UnionFind(n)
    UF_l = UnionFind(n)
    for i in range(k):
        p,q = map(int,input().split())
        UF_k.unite(p-1,q-1)
    for i in range(l):
        r,s = map(int,input().split())
        UF_l.unite(r-1,s-1)
    l = []
    dic = {}
    for i in range(n):
        tmp = (UF_k.find(i),UF_l.find(i))
        l.append(tmp)
        if tmp in dic:
            dic[tmp] += 1
        else:
            dic[tmp] = 1
    
    for fac in l:
        print(dic[fac],end=' ')
### BUGGY CODE ###

N, W = [int(i) for i in input().split()]
w, v = [0]*N, [0]*N
 
for i in range(N):
  w[i], v[i] = [int(_) for _ in input().split()]
  
dp = [[0] * (W+1) for _ in range(N+1)]
# dp[i][j] i番目までの荷物で重さがjを超えないように選んだときの価値の最大値
for i in range(N):
  for j in range(W+1):
    if j < w[i]:# i番目の荷物の重さw[i]がjを超えているので，入れる可能性がない
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])# 入れ場合と入れない場合を比較
      
print(dp[N][W])

### FIXED CODE ###

N, W = [int(i) for i in input().split()]
w, v = [0]*N, [0]*N
 
for i in range(N):
  w[i], v[i] = [int(_) for _ in input().split()]
  
dp = [[0] * (W+1) for _ in range(N+1)]
# dp[i][j] i番目までの荷物で重さがjを超えないように選んだときの価値の最大値
for i in range(N):
  for j in range(W+1):
    dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    if j + w[i] <= W:
      dp[i+1][j+w[i]] = max(dp[i+1][j+w[i]], dp[i][j] + v[i])
      
print(dp[N][W])
### BUGGY CODE ###

N=int(input())

a=list(map(int,input().split()))
A=[]
B=[]
for x in range(len(a)):
    A.append(a[x])
    B.append(a[x])
    
start_is_plus=0
if A[0]<=0:
    start_is_plus+=(1-A[0])
    A[0]=1

for i in range(1,len(A)):
    if i%2==1:
        if sum(A[:i+1])>=0:
            start_is_plus+=(sum(A[:i+1])+1)
            A[i]-=(sum(A[:i+1])+1)
    else:
        if sum(A[:i+1])<=0:
            start_is_plus+=(1-sum(A[:i+1]))
            A[i]+=(1-sum(A[:i+1]))
#print(A)  
start_is_minus=0
if B[0]>=0:
    start_is_minus+=(B[0]+1)
    B[0]=(-1)
    
for j in range(1,len(B)):
    if j%2==1:
       if sum(B[:j+1])<=0:
            start_is_minus+=(1-sum(B[:j+1]))
            B[j]+=(1-sum(B[:j+1]))
    else:
        if sum(B[:j+1])>=0:
            start_is_minus+=(sum(B[:j+1])+1)
            B[j]-=(sum(B[:j+1])+1) 
#print(B)
print(min(start_is_minus,start_is_plus))

### FIXED CODE ###

N=int(input())

L=list(map(int,input().split()))

Pnum=0
Psum=0
if L[0]>=1:
    Pnum=L[0]
else:
    Psum=1-L[0]
    Pnum=1
for i in range(1,N):
    if i%2==1:
        if Pnum+L[i]<=-1:
            Pnum=Pnum+L[i]
        else:
            Psum+=(Pnum+L[i]+1)
            Pnum=-1
    else:
        if Pnum+L[i]>=1:
            Pnum=Pnum+L[i]
        else:
            Psum+=(1-Pnum-L[i])
            Pnum=1
            
Mnum=0
Msum=0
if L[0]<=-1:
    Mnum=L[0]
else:
    Msum=L[0]+1
    Mnum=-1
for i in range(1,N):
    if i%2==0:
        if Mnum+L[i]<=-1:
            Mnum=Mnum+L[i]
        else:
            Msum+=(Mnum+L[i]+1)
            Mnum=-1
    else:
        if Mnum+L[i]>=1:
            Mnum=Mnum+L[i]
        else:
            Msum+=(1-Mnum-L[i])
            Mnum=1

print(min(Psum,Msum))
### BUGGY CODE ###

class DLL:
    class Node:
        def __init__(self, x, y, z):
            self.v = x
            self.prv = y
            self.nxt = z

    def __init__(self):
        init = DLL.Node(None, None, None)
        init.prv = init
        init.nxt = init
        self.size = 0
        self.init = init

    def insert(self, x):
        i = self.init
        j = i.nxt
        k = DLL.Node(x, i, j)
        i.nxt = k
        j.prv = k
        self.size += 1

    def deleteFirst(self):
        #if self.size != 0:
        i = self.init
        k = i.nxt
        j = k.nxt
        i.nxt = j
        j.prv = i
        self.size -= 1

    def deleteLast(self):
        #if self.size != 0:
        i = self.init
        k = i.prv
        j = k.prv
        i.prv = j
        j.nxt = i
        self.size -= 1

    def delete(self, x):
        #if self.size != 0:
        i = self.init
        k = i.nxt
        while 1:
            if k.v == x:
                """
                i = k.prv
                j = k.nxt
                i.nxt = j
                j.prv = i
                """
                k.prv.nxt = k.nxt
                k.nxt.prv = k.prv
                self.size -= 1
                break
            else:
                if k.nxt == i:
                    break
                else:
                    k = k.nxt

    def prt(self):
        f = self.init
        s = f.nxt
        l = f.prv
        while 1:
            if s != l:
                print(s.v, end=' ')
                s = s.nxt
            else:
                print(l.v)
                break

n = int(input())
L = DLL()

for i in range(n):
    com = input()
    if com == "deleteFirst":
        L.deleteFirst()
    elif com == "deleteLast":
        L.deleteLast()
    else:
        C = com.split()
        if C[0] == "insert":
            L.insert(int(C[1]))
        elif C[0] == "delete":
            L.delete(int(C[1]))
    #L.prt()
    
L.prt()



### FIXED CODE ###

from collections import deque

n = int(input())
L = deque()

for i in range(n):
    com = input()
    if com[0] == 'i':
        C = com.split()
        L.appendleft(int(C[1]))
    else:
        if com[6] == 'F':
            L.popleft()
        elif com[6] == 'L':
            L.pop()
        else:
            C = com.split()
            x = int(C[1])
            try:
                L.remove(x)
            except:
                pass

print(*L)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    #%% import
    from itertools import product
    from collections import deque

    #%% input
    n=int(input())
    V=[(i,j) for i,j in product(range(n),range(n)) if i<j]
    N=len(V) # N=n*(n-1)//2

    #%% adjacency list
    outs={v:[] for v in V}
    indeg={v:0 for v in V}
    for i in range(n):
        edge=list(map(lambda x:int(x)-1,input().split()))
        for j in range(len(edge)-1): # 各iにつきn-1個の辺が与えられる
            v0 = (min(i,edge[j]),max(i,edge[j]))
            v1 = (min(i,edge[j+1]),max(i,edge[j+1]))
            outs[v0].append(v1)
            indeg[v1]+=1

    #%% topological sort
    Q=deque(v for v in V if indeg[v]==0)
    res=[]
    while(Q):
        v0=Q.popleft()
        res.append(v0)
        for v1 in outs[v0]:
            indeg[v1]-=1
            if indeg[v1]==0: Q.append(v1)

    #%% judge whether G is DAG
    if len(res)<N:
        print("-1")
        return

    #%% Longest Path Problem
    LP={v:1 for v in V}
    for v0 in res:
        for v1 in outs[v0]:
            LP[v1]=max(LP[v1],LP[v0]+1)
    print(max(LP.values()))

resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from itertools import product
    n=int(input())
    match=[[0]*n for _ in range(n)]
    V=0 # V=n(n-1)/2
    for i,j in product(range(n),repeat=2):
        if(i>=j): continue
        match[i][j]=V
        V+=1

    def toID(i,j):
        if(i>j): i,j=j,i
        return match[i][j]

    E=[[] for _ in range(V)]
    for i in range(n):
        A=list(map(lambda x:int(x)-1,input().split()))
        for j in range(1,n-1):
            E[toID(i,A[j-1])].append(toID(i,A[j]))
    # あとは頂点VのグラフをdfsしてLongest pathの長さを求める
    # -1: unchecked, -2: checked and uncalculated
    dp=[-1]*V
    flag=True
    def dfs(v):
        global flag
        dp[v]=-2
        length=0
        for nv in E[v]:
            if(dp[nv]==-2):
                print(-1)
                exit()
            if(dp[nv]==-1):
                dfs(nv)
            length=max(length,dp[nv]+1)
        dp[v]=length
    # calculate
    for i in range(V): dfs(i)
    print(max(dp)+1 if(flag) else -1)
resolve()
### BUGGY CODE ###

import sys
input=sys.stdin.readline
N=int(input())
A=list(map(int,input().split()))
for x in range(N):
    y=x+1
    
    print(A.count(y))
    



### FIXED CODE ###

import sys
input=sys.stdin.readline
import collections

N=int(input())
A=list(map(int,input().split()))
c=collections.Counter(A)
for x in range(N):
    y=x+1
    
    print(c[y])
### BUGGY CODE ###

import numpy as np
N = int(input())
base = np.zeros((1,3))
for _ in range(N):
  base = np.vstack([base, np.array(list(map(int, input().split()))).reshape(1,-1) ])

base = base[1:]

DP_list = [0 for _ in range(N)]
pre_check = -1

for i in range(0,N):
  for j in [0,1,2]:
    if j != pre_check:
      PRE = DP_list[i-1] if i>0 else 0
      if PRE + base[i, j] > DP_list[i]:
        DP_list[i] = PRE + base[i, j]
        pre_check_cnt = j
  pre_check = pre_check_cnt

print(int(DP_list[-1]))

### FIXED CODE ###

N = int(input())
a, b, c = [0] * N, [0] * N, [0] * N
for i in range(N):
	a[i], b[i], c[i] = map(int, input().split())
dp = [[0] * 3 for _ in range(N)]
#print(dp)
dp[0] = [a[0], b[0], c[0]]
for i in range(N - 1):
	dp[i + 1][0] = max(dp[i + 1][0], dp[i][1] + a[i + 1], dp[i][2] + a[i + 1])
	dp[i + 1][1] = max(dp[i + 1][1], dp[i][0] + b[i + 1], dp[i][2] + b[i + 1])
	dp[i + 1][2] = max(dp[i + 1][2], dp[i][0] + c[i + 1], dp[i][1] + c[i + 1])
print(max(dp[N - 1]))
### BUGGY CODE ###

n = int(input())
list_A = input().split()
q = int(input())
SUM = sum(map(int, list_A))
for i in range(q):
  b, c = input().split()
  dif = 0
  if b in list_A:
    num = list_A.count(b)
    list_A = [c if x == b else x for x in list_A]
    dif = num*(int(c) - int(b))
  else:
    pass
  SUM += dif
  print(SUM)

### FIXED CODE ###

import sys
from collections import Counter
n = int(sys.stdin.readline().rstrip())
A = list(map(int, sys.stdin.readline().rstrip().split()))
q = int(sys.stdin.readline().rstrip())
count_dic = Counter(A)
SUM = sum(A)
for i in range(q):
  b, c = map(int, input().split())
  SUM += count_dic[b]*(c - b)
  count_dic[c] += count_dic[b]
  count_dic[b] = 0
  print(SUM)
### BUGGY CODE ###

# import sys
# input = sys.stdin.readline
# import re
# import itertools
import collections

def main():
    n = int(input())
    s = input_list()
    sc = collections.Counter(s)
    q = int(input())
    ans = []
    for i in range(q):
        b, c = input_list()
        sc[c] += sc[b]
        if b in sc:
            sc.pop(b)
        a = 0
        for k, v in sc.items():
            a += k*v
        ans.append(a)
    for a in ans:
        print(a)


def count_tento(l, cur):
    count = 0
    for v in l:
        if v > cur:
            count += 1
    return count

def input_list():
    return list(map(int, input().split()))

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

if __name__ == '__main__':
    main()


### FIXED CODE ###

# import sys
# input = sys.stdin.readline
# import re
# import itertools
import collections

def main():
    n = int(input())
    s = input_list()
    sc = collections.Counter(s)
    q = int(input())
    data = []
    for i in range(q):
        b, c = input_list()
        sc[c] += sc[b]
        if i > 0:
            data.append(c*sc[b] - b * sc[b])
        if b in sc:
            sc.pop(b)
    ans = 0
    for k, v in sc.items():
        ans += k*v
    aa = [ans]
    for i, v in enumerate(data[::-1]):
        aa.append(aa[i] - v)
    for a in aa[::-1]:
        print(a)


def count_tento(l, cur):
    count = 0
    for v in l:
        if v > cur:
            count += 1
    return count

def input_list():
    return list(map(int, input().split()))

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

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


#MAX_N = 25; # nの最大値

#入力
n, W = map(int, input().split())
s = []
for i in range(n):#h:高さ
    s.append([int(m) for m in input().split()])
w = []
v = []
for i in range(n):
    w.append(s[i][0])
    v.append(s[i][1])

# メモ化テーブル。
# dp[i][j]はi番目以降の品物から重さの和がj以下なるように選んだときの価値の和の最大値を表す。
# -1なら値が未決定であることを表す
dp = []
for i in range(n + 1):
    dp.append([])
for p in range(n + 1):
    for q in range(W + 1):
        dp[p].append(-1)

# i番目以降の品物から重さの和がj以下なるように選んだときの、
# 取りうる価値の総和の最大値を返す関数
def rec(i, j):
    if dp[i][j] != -1:
    # すでに調べたことがあるならその結果を再利用
        return dp[i][j]

    #res = 0
    if i == n:
    # 品物がもう残っていないときは、価値の和の最大値は0で確定
        res = 0
        dp[i][j] = res
    elif j < w[i]:
    # 残りの容量が足りず品物iを入れられないので、入れないパターンだけ処理
    # i+1 以降の品物のみを使ったときの最大値をそのままこの場合の最大値にする
        res = rec(i + 1, j)
        dp[i][j] = res
    else:
    # 品物iを入れるか入れないか選べるので、両方試して価値の和が大きい方を選ぶ
        res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i])#深さ優先探索
        dp[i][j] = res
    return dp[i][j]


print(rec(0, W))

### FIXED CODE ###

#入力
n, W = map(int, input().split())
s = []
for i in range(n):#h:高さ
    s.append([int(m) for m in input().split()])
s.sort(key=lambda x:(x[0], x[1]))
s0 = []
s1 = []
s2 = []
s3 = []
for i in range(n):
    if i == 0:
        w0 = s[i][0]
        s0.append(s[i])
    elif s[i][0] == w0:
        s0.append(s[i])
    elif s[i][0] == w0 + 1:
        s1.append(s[i])
    elif s[i][0] == w0 + 2:
        s2.append(s[i])
    elif s[i][0] == w0 + 3:
        s3.append(s[i])
s0.sort(key=lambda x: x[1], reverse=True)
s1.sort(key=lambda x: x[1], reverse=True)
s2.sort(key=lambda x: x[1], reverse=True)
s3.sort(key=lambda x: x[1], reverse=True)
w = []
v = []
t0 = 0
t1 = 0
t2 = 0
t3 = 0
u0 = 0
u1 = 0
u2 = 0
u3 = 0
u = []
for h in range(-1, len(s0)):
    if h == -1:
        t0 = 0
        u0 = 0
    else:
        t0 += s0[h][0]
        u0 += s0[h][1]
    for i in range(-1, len(s1)):
        if i == -1:
            t1 = 0
            u1 = 0
        else:
            t1 += s1[i][0]
            u1 += s1[i][1]
        for j in range(-1, len(s2)):
            if j == -1:
                t2 = 0
                u2 = 0
            else:
                t2 += s2[j][0]
                u2 += s2[j][1]
            for k in range(-1, len(s3)):
                if k == -1:
                    t3 = 0
                    u3 = 0
                else:
                    t3 += s3[k][0]
                    u3 += s3[k][1]
                if t0 + t1 + t2 + t3 <= W:
                    u.append(u0 + u1 + u2 + u3)
print(max(u))