Harryxun/stf_run huggingface dataset:
from pprint import pprint
def main():
    fp=open("result.txt","w")
    n = int(input())
    for i in range(n):
        a = input()
        b = input()
        na=len(a)
        nb=len(b)
        array = [[0]*nb for i in range(na)]
        #array = [[0 for i in range(nb)] for j in range(na)]
        for i in range(na):
            for j in range(nb):
                c = 0
                if i==0:
                    if a[i]==b[j]:
                        array[i][j]=1
                elif j==0:
                    if a[i]==b[j]:
                        array[i][j]=1
                else:
                    if a[i] == b[j]:
                        c = 1
                        array[i][j] = max(
                            array[i-1][j],
                            array[i][j-1],
                            array[i-1][j-1]+c)
        print(array[na-1][nb-1])
    fp.close()
if __name__ == "__main__":
    main()



### FIXED CODE ###

#dj 16D8101012J ito jun
import sys
def search(a,b):
    na=len(a)
    nb=len(b)
    array = [[0]*(nb+1) for _ in range(na+1)]
    for i,x in enumerate(a,1):
        prerow=array[i-1]
        row=array[i]
        for j,y in enumerate(b,1):
            if x == y:
                row[j]=prerow[j-1]+1
            elif prerow[j] < row[j-1]:
                row[j] = row[j-1]
            else:
                row[j] = prerow[j]
    return array[-1][-1]

n = int(input())
strs = [list(i) for i in sys.stdin.read().splitlines()]
result = [search(strs[i*2], strs[i*2+1]) for i in range(n)]
print(*result, sep="\n")
words = ("dream", "erase", "eraser", "dreamer")

s = input()

while len(s) > 0:
    match = False
    for w in words:
        if s.endwith(w):
            s = s[:-len(w)]
            match = True
            break
    if match is False:
        print("NO")
        exit()
print("YES")


### FIXED CODE ###

words = ("dream", "erase", "eraser", "dreamer")

s = input()

while len(s) > 0:
    match = False
    for w in words:
        if s.endswith(w):
            s = s[:-len(w)]
            match = True
            break
    if match is False:
        print("NO")
        exit()
print("YES")
#!/usr/bin/python
# -*- coding: utf-8 -*-

# def
def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(map(int,input().split())))
    return np.array(x)

def str_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(input()))
    return np.array(x)

def int_map():
    return map(int,input().split())

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

def print_space(l):
    return print(" ".join([str(x) for x in l]))

# import
import collections as col

import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix


# main code
N,M = int_map()
AB = int_mtx(M)

l = np.zeros((N,N))
for i in range(0,M):
    l[AB[i][0]-1,AB[i][1]-1] = 1

n, labels = connected_components(l)

ll = list(labels)
aa = col.Counter(ll)
print(aa.most_common()[0][1])

### FIXED CODE ###


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

# def
def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(map(int,input().split())))
    return np.array(x)

def str_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(input()))
    return np.array(x)

def int_map():
    return map(int,input().split())

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

def print_space(l):
    return print(" ".join([str(x) for x in l]))

# import
import collections as col

import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix


# main code
N,M = int_map()

i = []
j = []

for z in range(0,M):
    a,b = int_map()
    i.append(a-1)
    j.append(b-1)
    
d = [1]*M

csr = csr_matrix((d,(i,j)),(N,N))


n, labels = connected_components(csr)

ll = list(labels)
aa = col.Counter(ll)
print(aa.most_common()[0][1])
import math

N,K =list(map(int,input().split(" ")))
As= list(map(int,input().split(" ")))
g = As[0]
ma = -1
for a in As:
    g = math.gcd(g,a)
    ma = max(ma,a)
    if K == a:
        print("POSSIBLE")
        exit()
if K % g == 0 and ma >= K:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

import fractions

N,K =list(map(int,input().split(" ")))
As= list(map(int,input().split(" ")))
g = As[0]
ma = -1
for a in As:
    g = fractions.gcd(g,a)
    ma = max(ma,a)
    if K == a:
        print("POSSIBLE")
        exit()
if K % g == 0 and ma >= K:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
n,m = map(int,input().split())
a = list(map(int,input().split()))
bc = list(list(map(int,input().split())) for i in range(m))

a.sort()
bc.sort(reverse=True,key=lambda x:x[1])
t = 0
for i in range(m):
    for j in range(bc[i][0]):
        if a[t] < bc[i][1]:
            a[t] = bc[i][1]
            t+=1
        else:
            break

print(sum(a))


### FIXED CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
bc = list(list(map(int,input().split())) for i in range(m))

a.sort()
bc.sort(reverse=True,key=lambda x:x[1])
t = 0
for i in range(m):
    for j in range(bc[i][0]):
        if t != n:
            if a[t] < bc[i][1]:
                a[t] = bc[i][1]
                t+=1
            else:
                break
        else:
            break
    else:
        continue
    break

print(sum(a))
A,B=[int(x) for x in stdin.readline().rstrip().split()]
S=(stdin.readline().rstrip())
flag=True
if S[:A].isdecimal() != True:
    flag = False
elif S[A:A+1] != "-":
    flag = False
elif S[A+1:].isdecimal() != True:
    flag = False

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

### FIXED CODE ###

from sys import stdin
A,B=[int(x) for x in stdin.readline().rstrip().split()]
S=(stdin.readline().rstrip())
flag=True
if S[:A].isdecimal() != True:
    flag = False
elif S[A:A+1] != "-":
    flag = False
elif S[A+1:].isdecimal() != True:
    flag = False

if flag:
    print("Yes")
else:
    print("No")
t=list(map(int,input().split()))
a=list(map(int,input().split()))
b=list(map(int,input().split()))
p,q=[0],[0]
x,y=[(a[0]-b[0])*t[0],(a[1]-b[1])*t[1]]
#print(x,y,abs(x)<abs(y))
#exit()
if x+y==0:
    print("infinity")
elif (x<0 and y<0) or (x>0 and y>0):
    print(0)
elif (x<0 and x+(x+y)>0) or (x>0 and x+(x+y)<0):
    print(1)
elif x<0 and x+y>0:
    print((abs(x)//(x+y))*2+[0,1][abs(x)%(x+y)>1])
elif x>0 and x+y<0:
    print((abs(y)//(x+y))*2+[0,1][abs(y)%(x+y)>1])
else:
    print(hhh)

### FIXED CODE ###

T1, T2 = map(int, input().split())
A1, A2 = map(int, input().split())
B1, B2 = map(int, input().split())
 
P = (A1 - B1) * T1
Q = (A2 - B2) * T2
if P > 0:
	P *= -1
	Q *= -1
 
if P + Q < 0:
	print(0)
elif P + Q == 0:
	print("infinity")
else:
	S = (-P) // (P + Q)
	T = (-P) % (P + Q)
	if T != 0:
		print(S * 2 + 1)
	else:
		print(S * 2)
ip1 = input().split()
N = int(ip1[0])
L = int(ip1[1])
strings = []
for i in range(N):
    strings.append(input())
strings.sort()
ans = ""
for i in range(len(strings)):
    ans += string[i]

print(ans)


### FIXED CODE ###

ip1 = input().split()
N = int(ip1[0])
L = int(ip1[1])
strings = []
for i in range(N):
    strings.append(input())
strings.sort()
ans = ""
for i in range(len(strings)):
    ans += strings[i]

print(ans)
N, Y = map(int, input().split())
# i: man, j: gosen, k: sen
output_flag=0
for i in range(0, N+1):
    if output_flag==0:
        for j in range(0, N+1-i):
            k = N-i-j
            if 10000*i+5000*j+1000*k==Y:
                print(i, j, k)
                not_output_flag=1
                break
    else:
        break
if not_output_flag==0:
    print(-1, -1, -1)

### FIXED CODE ###

N, Y = map(int, input().split())
man = -1
gosen = -1
sen = -1
for i in range(0, N+1):
    for j in range(0, N+1-i):
        k = N-i-j
        total = 10000*i+5000*j+1000*k
        if total==Y:
            man = i
            gosen = j
            sen = k
print(man, gosen, sen)
import math
N,M = map(int,input().split())
count = 0
if N*2>M:
    count = math.floor(M/2)
else:
    temp=M-2*N
    ans = N+math.floor(temp/4)

print(ans)
    


### FIXED CODE ###

import math
N,M = map(int,input().split())
count = 0
if N*2>M:
    count = math.floor(M/2)
else:
    temp=M-2*N
    count = N+math.floor(temp/4)

print(count)
# 無限回試行できる時、Kの最小値を最大化する問題
s = input()
now = s[0]
cnt = 1
use = []
for i in range(1,len(s)):
    if now == s[i]:
        cnt += 1
    else:
        use.append(cnt)
        cnt = 1
        now = s[i]
use.append(cnt)

min_prob = len(s)
def ketsugou(l):
    global min_prob
    #一番小さいやつをくっつけていく
    m = l.index(min(l))
    if m == 0 or m == len(l) - 1:
        s1 = l[m]
        s2 = sum(l) - l[m]
        min_prob = min(min_prob, max(s1, s2))
        if m == 0:
            l.pop(0)
            l[0] += s1
        else:
            l.pop()
            l[-1] += s1
    else:
        s1 = l[:m + 1]
        s2 = l[:m]
        s3 = l[m:]
        s4 = l[m+1:]
        min_prob = min(min_prob, max(s1, s2,s3,s4))
        if l[m - 1] < l[m + 1]:
            l[m - 1] += l[m]
        else:
            l[m + 1] += l[m]
        l.pop(m)
while(len(use) > 1):
    ketsugou(use)
print(min_prob)


### FIXED CODE ###

# 無限回試行できる時、Kの最小値を最大化する問題
s = input()
now = s[0]
cnt = 1
use = []
for i in range(1,len(s)):
    if now == s[i]:
        cnt += 1
    else:
        use.append(cnt)
        cnt = 1
        now = s[i]
use.append(cnt)

min_prob = len(s)
sum_s = sum(use)
def ketsugou(l):
    global min_prob
    global sum_s
    #一番小さいやつをくっつけていく
    m = l.index(min(l))
    if m == 0 or m == len(l) - 1:
        s1 = l[m]
        s2 = sum_s - l[m]
        min_prob = min(min_prob, max(s1, s2))
        if m == 0:
            l = l[1:]
            l[0] += s1
        else:
            l.pop()
            l[-1] += s1
    else:
        s1 = sum(l[:m])
        s2 = s1 + l[m]
        s3 = sum_s - s1
        s4 = sum_s - s2
        min_prob = min(min_prob, max(s1, s2,s3,s4))
        if l[m - 1] < l[m + 1]:
            l[m - 1] += l[m]
        else:
            l[m + 1] += l[m]
        l.pop(m)
#while(len(use) > 1):
#    ketsugou(use)
sum_ss = 0
for i in range(len(use)):
    sum_ss += use[i]
    min_prob = min(min_prob, max(sum_s - sum_ss, sum_ss))

print(min_prob)
n = int(input())
s = list(input())
k = int(input())
d = s[k - 1]
for i in range(n):
    if s[i] != d:
        s[i] = '*'
print(''.join(s))


### FIXED CODE ###

a, b, c = map(int, input().split())
if a < c < b or b < c < a:
    print('Yes')
else:
    print('No')
cases = 1
while num = raw_input ( ) != 0 :
    print "Case " , cases , ": " , num

### FIXED CODE ###

cases = 1
while True :
    num = raw_input ( )
    if int ( num ) == 0 :
        break
    print "Case %d: %d" % ( int ( cases ) , int ( num ) )
    cases += 1
import math

def solution(n, a):
    gcd_left = [0]
    gcd_right = [0]
    for i in range(n):
        gcd_left.append(math.gcd(gcd_left[i], a[i]))
        # 順に(0とa[-1]), (a[-1]とa[-2]),...の比較
        # 要は右端から順にgcdを求めている
        gcd_right.append(math.gcd(gcd_right[i], a[-(i + 1)]))

    gcd_right = gcd_right[::-1]  # gcd_right[i]がi番目以降のgcdとなるように反転

    ans = []
    for i in range(n):
        ans.append(math.gcd(gcd_left[i], gcd_right[i + 1]))
        
    return max(ans)

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    print(solution(n, a))

### FIXED CODE ###

import unittest
import fractions


def solution(n, a):
    gcd_left = [0]
    gcd_right = [0]
    for i in range(n):
        gcd_left.append(fractions.gcd(gcd_left[i], a[i]))
        # 順に(0とa[-1]), (a[-1]とa[-2]),...の比較
        # 要は右端から順にgcdを求めている
        gcd_right.append(fractions.gcd(gcd_right[i], a[-(i + 1)]))

    gcd_right = gcd_right[::-1]  # gcd_right[i]がi番目以降のgcdとなるように反転

    ans = []
    for i in range(n):
        ans.append(fractions.gcd(gcd_left[i], gcd_right[i + 1]))


    return max(ans)


class MyTestCase(unittest.TestCase):
    def test1(self):
        self.assertEqual(solution(3, [7, 6, 8]), 2)

    def test2(self):
        self.assertEqual(solution(3, [12, 15, 18]), 6)

    def test3(self):
        self.assertEqual(solution(2, [1000000000, 1000000000]), 1000000000)




if __name__ == '__main__':

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

    unittest.main()
def main():
    n, *a = map(int, open(0).read().split())
    m = [0] * (n + 1)
    res = []
    for i in range(n, 0, -1):
        x = a[i - 1] % 2
        y = m[i] % 2
        if x != y:
            res.append(i)
            c = i // 2
            j = 1
            while j < c:
                if i % j == 0:
                    res[j] += 1
                j += 1

    m = len(res)
    print(m)
    if m == 1:
        print(res[0])
    elif m > 1:
        l = ' '.join(map(str, res))
        print(l[::-1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def solve():
    N, *a_l = map(int, open(0).read().split())
    a_l = [0] + a_l

    for i in range(N//2, 0, -1):
        a_l[i] = sum(a_l[i::i]) % 2

    b_l = [i for i, x in enumerate(a_l) if x]

    print(len(b_l))
    if len(b_l) != 0:
        print(' '.join(map(str, b_l)))


if __name__ == '__main__':
    solve()
#coding:utf-8
import math

r=int(input())
print("%.6f"%(2*math.pi*r)+" %.6f"%(math.pi*r**2))

### FIXED CODE ###

#coding:utf-8
import math

r=float(input())
print("%.6f"%(math.pi*r**2)+" %.6f"%(2*math.pi*r))
import sys
n=int(input())
a=list(map(int,input().split()))
if n==1:
  print(Yes)
  sys.exit()
for i in range(1,n-1):
  if a[i+1] >= a[i] and a[i] >=a [i-1]:
    continue
  if a[i+1]>=a[i]-1 and a[i]-1>=a[i-1]:
    a[i]=a[i]-1
    continue
  elif i==1 and a[0]-1==a[1]:
    a[0]-=1
    continue
  else:
    print("No")
    sys.exit()
print("Yes")

### FIXED CODE ###

import sys
n=int(input())
a=list(map(int,input().split()))
if len(a)==1:
  print("Yes")
  sys.exit()
if len(a)==2 and a[0]<=a[1]:
  print("Yes")
  sys.exit()
elif len(a)==2:
  print("No")
  sys.exit()
  
for i in range(1,n-1):
  if a[i+1]>=a[i]-1 and a[i]-1>=a[i-1]:
    a[i]=a[i]-1
    continue

  if a[i+1] >= a[i] and a[i] >=a [i-1]:
    continue
  else:
    print("No")
    sys.exit()
print("Yes")
cards = []
for suit in ('S','H','C','D'):
    for num in range(1,14):
        cards.append(suit+' '+str(num))

N = raw_input()

for n in xrange(N):
    suit, number = raw_input().split()
    cards.remove(suit+' '+y)


for card in cards:
    print card

### FIXED CODE ###

cards = []
for suit in ('S','H','C','D'):
    for num in range(1,14):
        cards.append(suit+' '+str(num))

N = int(raw_input())

for n in xrange(N):
    suit, number = raw_input().split()
    cards.remove(suit+' '+number)


for card in cards:
    print card
def waru(a,b):
  if a%b==0:
    return a//b
  else:
    return (a//b)+1
N,K=map(int,input().split())
A=list(map(int,input().split()))
ue=sum(A)
sita=0
for i in range(40):
  n=(ue+sita)//2
  L=[waru(i,n)-1 for i in A]
  if sum(L)>K:
    sita=n
  else:
    ue=n
  if ue==sita:
    print(ue)
    exit()
  elif ue-sita==1:
    n=sita
    L=[waru(i,n)-1 for i in A]
    if sum(L)>K:
      print(n+1)
      exit()
    else:
      print(n)
      exit()

### FIXED CODE ###

def waru(a,b):
  if a%b==0:
    return a//b
  else:
    return (a//b)+1
N,K=map(int,input().split())
A=list(map(int,input().split()))
ue=sum(A)
sita=1
for i in range(50):
  n=(ue+sita)//2
  L=[waru(i,n)-1 for i in A]
  if sum(L)>K:
    sita=n
  else:
    ue=n
  if ue==sita:
    print(ue)
    exit()
  elif ue-sita==1:
    n=sita
    L=[waru(i,n)-1 for i in A]
    if sum(L)>K:
      print(n+1)
      exit()
    else:
      print(n)
      exit()
N,M=map(int,input().split())
slist=[]
for i in range(M):
    slist.append(list(map(int,input().split())))

ans=["0"]*N

for i in range(N):
    if ans[slist[i][0]-1]=="0":
        ans[slist[i][0]-1]=slist[i][1]
    elif ans[slist[i][0]-1]!=slist[i][1]:
        ans=["-1"]
        break



if N>1:
    if ans[0]=="0":
        ans[0]=1
    elif ans[0]==0:
        ans=["-1"]
        

for i in range(len(ans)):
    if ans[i]=="0":
        ans[i]=0

print(*ans,sep=(""))

### FIXED CODE ###


N,M=map(int,input().split())
slist=[]
for i in range(M):
    slist.append(list(map(int,input().split())))
ans=["0"]*N


for i in range(len(slist)):
    #print("i",i)
    if ans[slist[i][0]-1] == "0":
        ans[slist[i][0]-1] = slist[i][1]
    elif ans[slist[i][0]-1] == slist[i][1]:
        continue
    else:
        ans=["-1"]
        break

#print(ans)

if N>=2:
    if ans[0]=="0":
        ans[0]=1
    elif ans[0]==0:
        ans=["-1"]


    
for i in range(len(ans)):
    if ans[i]=="0":
        ans[i]=0

print(*ans,sep=(""))
s = input()
print(s[0]+str(len(s)-2)+s[len(s)])

### FIXED CODE ###

s = input()
print(s[0]+str(len(s)-2)+s[-1])
def main(){
 

    n = input()
    for i in n-1:
        R[i] = input()
 
    max = R[1] - R[0]
    min = R[0]
 
    for i+1 in n-1:
        if R[i]-min>max:
            max = R[i] - min
        if R[i]<min:
            min = R[i]
 
    print max

}
 

### FIXED CODE ###

n = input()

R = [input() for i in range(n)]
  
max = R[1] - R[0]
min = R[0]
  
for i in range(1,n):
    if R[i] - min > max:
        max = R[i] - min
    if R[i] < min:
        min = R[i]
  
print max
import collections
import math

n = int(input())
sl = collections.Counter([str(sorted(input())) for _ in range(n)])

ret = 0
for _, v in sl.most_common():
    if 2 <= v:
        ret += int(math.factorial(v) / math.factorial(2) / math.factorial(v - 2))

print(ret)


### FIXED CODE ###

import collections

n = int(input())
sl = collections.Counter([str(sorted(input())) for _ in range(n)])

ret = 0
for _, v in sl.most_common():
    if 2 <= v:
        ret += v * (v - 1) // 2

print(ret)
num_town, num_move = map(int, input().split())
teleports = list(map(lambda x: int(x) - 1, input().split()))

current = 0
memo = {}
for i in range(num_move):
    if memo.get(current) == 2:
        break
    if not memo.get(current):
        memo[current] = 1
    else:
        memo[current] += 1
    destination = teleports[current]
    current = destination

loop = {k:v for k,v in memo.items() if v==2}
minus = {k:v for k,v in memo.items() if v==1}

new_move_count = (num_move - len(minus)) % len(loop)

if num_move < new_move_count:
    new_move_count = num_move
    current = 0

for i in range(new_move_count):
    destination = teleports[current]
    current = destination

print(current + 1)


### FIXED CODE ###

num_town, num_move = map(int, input().split())
teleports = list(map(lambda x: int(x) - 1, input().split()))

current = 0
memo = {}
for i in range(num_move):
    if memo.get(current) == 2:
        break
    if not memo.get(current):
        memo[current] = 1
    else:
        memo[current] += 1
    destination = teleports[current]
    current = destination

loop = {k:v for k,v in memo.items() if v==2}
minus = {k:v for k,v in memo.items() if v==1}

new_move_count = 0
if len(loop) == 0:
    current = 0
    new_move_count = num_move
else:
    new_move_count = (num_move - len(minus)) % len(loop)

for i in range(new_move_count):
    destination = teleports[current]
    current = destination

print(current + 1)
def divde(argv):

    dlist=[]
    i = 1
    for i in range (1,int(argv)+1):
        if(int(argv)%i==0):
            dlist.append(i)
    return dlist

def compare(A,B):
    D =[]
    for i in range (len(A)):
        for j in range(len(B)):
            if A[i]==B[j]:
                D.append(B[j])
    return D

if __name__ == "__main__":
    string = input()
    a, b, c = string.split()

    A = []
    A = divde(a)
    B = []
    B = divde(int(b))
    D = []
    D = compare(A,B)

    D.reverse()

    q = D.index(int(c))
    print(q+1)

### FIXED CODE ###

def divde(argv):

    dlist=[]
    i = 1
    for i in range (1,int(argv)+1):
        if(int(argv)%i==0):
            dlist.append(i)
    return dlist

def compare(A,B):
    D =[]
    for i in range (len(A)):
        for j in range(len(B)):
            if A[i]==B[j]:
                D.append(B[j])
    return D

if __name__ == "__main__":
    string = input()
    a, b, c = string.split()

    A = []
    A = divde(a)
    B = []
    B = divde(int(b))
    D = []
    D = compare(A,B)

    D.reverse()

    q = int(c)-1
    print(D[q])
#残り1種類のグループとそうでないグループに分けておく，残り1種類になったら移動
#判定のため，各tごとにdのリスト（ソート済み）と，dのリストを参照する番号を持っておく

import heapq

N,K=map(int,input().split())
dt=[[0,0] for _ in range(N)]
gr=[[] for _ in range(N)]#tの種類ごとにまとめる
x=0#種類数
ans=0#先に全部食べたことにして，いらないものを除く

for i in range(N):
    dt[i][1],dt[i][0]=map(int,input().split())
    ans+=dt[i][0]
    if gr[dt[i][1]-1]==[]:
        x+=1
    gr[dt[i][1]-1].append(dt[i])
ans+=x*x

single=[]
multi=[]
heapq.heapify(single)
heapq.heapify(multi)

num_i=[0]*N#各tに対してどこを見るか

for i in range(N):
    gr[i].sort()
    if gr[i]!=[]:
        if len(gr[i])==1:
            heapq.heappush(single,gr[i][0])
        else:
            heapq.heappush(multi,gr[i][0])
    

for i in range(N-K):
    a=heapq.heappop(single)
    b=heapq.heappop(multi)
    if a[0]+(2*x-1)<=b[0]:
        ans-=a[0]+(2*x-1)
        x-=1
        heapq.heappush(multi,b)
    else:
        ans-=b[0]
        heapq.heappush(single,a)
        num_i[b[1]-1]+=1
        if num_i[b[1]-1]==len(gr[b[1]-1])-1:
            heapq.heappush(single,gr[b[1]-1][-1])
        else:
            heapq.heappush(multi,gr[b[1]-1][num_i[b[1]-1]])
                                       
print(ans)

### FIXED CODE ###

#残り1種類のグループとそうでないグループに分けておく，残り1種類になったら移動
#判定のため，各tごとにdのリスト（ソート済み）と，dのリストを参照する番号を持っておく

import heapq

N,K=map(int,input().split())
dt=[[0,0] for _ in range(N)]
gr=[[] for _ in range(N+1)]#tの種類ごとにまとめる
x=0#種類数
ans=0#先に全部食べたことにして，いらないものを除く

for i in range(N):
    dt[i][1],dt[i][0]=map(int,input().split())
    dt[i][1]-=1
    ans+=dt[i][0]
    if gr[dt[i][1]]==[]:
        x+=1
    gr[dt[i][1]].append(dt[i])
ans+=x*x

single=[]
multi=[]
heapq.heapify(single)
heapq.heapify(multi)

num_i=[0]*N#各tに対してどこを見るか

for i in range(N):
    gr[i].sort()
    if gr[i]!=[]:
        if len(gr[i])==1:
            heapq.heappush(single,gr[i][0])
        else:
            heapq.heappush(multi,gr[i][0])
    
inf=10**19
heapq.heappush(single,[inf,N])#絶対に選ばないものを入れておく
heapq.heappush(multi,[inf,N])
    
    
    
for i in range(N-K):
    a=heapq.heappop(single)
    b=heapq.heappop(multi)
    if a[0]+(2*x-1)<=b[0]:#種類ボーナスも含めて小さい方を取り除く
        ans-=a[0]+(2*x-1)
        x-=1
        heapq.heappush(multi,b)
    else:
        ans-=b[0]
        heapq.heappush(single,a)
        tt=b[1]
        num_i[tt]+=1
        if num_i[tt]==len(gr[tt])-1:
            heapq.heappush(single,gr[tt][-1])
        else:
            heapq.heappush(multi,gr[tt][num_i[tt]])
                                       
print(ans)
n=int(input());a=list(map(int,input().split()));c,ans=1,0
for i in range(n-1)
  if a[i]==a[i+1]:c+=1
  else:
    if c>=2:ans+=c//2
    c=1
print(ans)

### FIXED CODE ###

n=int(input());a=list(map(int,input().split()));c,ans=1,0
for i in range(n-1):
  if a[i]==a[i+1]:c+=1
  else:
    if c>=2:ans+=c//2
    c=1
if c>=2:ans+=c//2
print(ans)
H,N = map(int, input().split())
lists = list(map(int, input().split())
lists.sort()
if N>=2 and lists[N-1]+lists[N-2]>=H:
  print('Yes')
If N==1 and lists[0]>=H:
  print('Yes')
if N==1 and lists[0]<H:
  print('No')
else:
  print('No')

### FIXED CODE ###

H, A = map(int,input().split())
a = int(H/A)
b = H/A
if a==b:
  print(a)
else:
  c = a+1
  print(c)
s=input()
print(s[:2]+"8"+s[4:]

### FIXED CODE ###

s=input()
print(s[:3]+"8"+s[4:])