Harryxun/stf_run huggingface dataset:
import sys
input = sys.stdin.readline

h, w = map(int, input().split())
s = []
for _ in range(h):
    s.append(input())

result = 0
#memo = {}


def terasu(x, y, d):
    #print(x, y, h, w)
    if y < 0 or x < 0 or y >= h or x >= w:
        return 0
    # if (x, y) in memo.keys():
    #    return 0
    if s[y][x] == "#":
        return 0
    #memo[(x, y)] = True
    if d == "f":
        return 1 + terasu(x + 1, y, "e") + terasu(x, y - 1, "s") + terasu(x, y+1, "n") + terasu(x-1, y, "w")
    elif d == "e":
        return 1 + terasu(x + 1, y, "e")
    elif d == "s":
        return 1 + terasu(x, y - 1, "s")
    elif d == "n":
        return 1 + terasu(x, y+1, "n")
    elif d == "w":
        return 1 + terasu(x-1, y, "w")


for y in range(h):
    for x in range(w):
        result = max(result, terasu(x, y, "f"))
print(result)

### FIXED CODE ###

#解説コードコピペです

import numpy as np
 
def solve():
    H, W = list(map(int, input().split()))
    grid = []
    for i in range(H):
        grid.append(list(input()))
    #print((np.array(grid) == ".") * 1) #行列演算 "." ならTrue そうでなければFalseの行列をつくる *1で1と0に変換
    grid = (np.array(grid) == ".") * 1  # ランプをおける:1, 障害物:0
 
    L = np.zeros((H,W), dtype=int) #0でうめつくした行列をつくる
    R = np.zeros((H,W), dtype=int)
    U = np.zeros((H,W), dtype=int)
    D = np.zeros((H,W), dtype=int)
    
    for j in range(W): #列単位で処理
        if j == 0:
            L[:, j] = grid[:, j]
        else:
            L[:, j] = (L[:, j-1] + 1) * grid[:, j] #gridでかけることで 障害物があったときにそのマスを0にする
    
    for j in range(W-1, -1, -1):
        if j == W-1:
            R[:, j] = grid[:, j]
        else:
            R[:, j] = (R[:, j+1] + 1) * grid[:, j]
 
    for i in range(H):
        if i == 0:
            U[i] = grid[i] * 1
        else:
            U[i] = (U[i-1] + 1) * grid[i]
    
    for i in range(H-1, -1, -1):
        if i == H-1:
            D[i] = grid[i]
        else:
            D[i] = (D[i+1] + 1) * grid[i]
 
    ans = np.max(L+R+U+D-3)
    print(ans)
 
 
if __name__ == "__main__": #ここはしらん
    solve()
a, b = map(int, input().split())
c　= (a * b) % 2
if c == 0:
  print('Even')
else:
  print('Odd')

### FIXED CODE ###

# -*- coding: utf-8 -*-
a, b = map(int, input().split())
c = (a * b) % 2
if c == 0:
  print("Even")
else :
  print("Odd")
n = int(input())
N = 10**9
x = [0]*(N+1)
x1= [0]*N
x2= [0]*N
for i in range(n):
    a , b = map(int, input().split())
    x[a-1]+=1
    x[b]-=1

for i in range(1,N):
    x[i]=x[i]+x[i-1]

for i in range(1,N):
    x1[i]=x1[i]+x1[i-1]

x.reverse()
for i in range(1,N):
    x2[i]=x2[i]+x2[i-1]

ans =0
if n % 2 == 1:
    for i in range(N):
        if x1[i]+x2[i]>n//2:
            ans +=1
    print(ans)
else:
    for i in range(N):
        if x1[i]+x2[i]>n//2:
            ans +=1
    print(ans*2+1)


### FIXED CODE ###

n = int(input())
al=[]
bl=[]
for i in range(n):
    a , b = map(int, input().split())
    al.append(a)
    bl.append(b)
al.sort()
bl.sort()
if n%2==1:
    mi = al[n//2]
    ma = bl[n//2]
    print(int(ma-mi)+1)
else:
    mi = (al[n//2-1]+al[n//2])/2
    ma = (bl[n//2-1]+bl[n//2])/2
    print(int((ma-mi)*2+1))
import random
n = list(x for x in range(input()))
k = int(input())
l = 0

while l <= k:
  d = random.randint(1, n)
  print(d)
  for m in range(d):
    print(random.choice(n))
  l += 1
  

### FIXED CODE ###

n, k = map(int, input().split())
a = []

for _ in range(k):
  d = int(input())
  a += [int(m) for m in input().split()]

print(n - len(set(a)))
n = int(input())
sum = 0
for i in range(n):
    x,u = input()
    if u == "JPY":
        sum += float(x)
    else:
        sum += float(x)*380000
print(sum)

### FIXED CODE ###

n = int(input())
sum = 0
for i in range(n):
    x,u = input().split()
    if u == "JPY":
        sum += float(x)
    else:
        sum += float(x)*380000
print(sum)
def main(N,Y):
    # type: (int, int) -> None
    """
    次の方程式
        x + y + z = N
        10x + 5y + z = Y
    の解を探索する．zを消去すると
        9x + 4y = Y - N
      where
        x >= 0
        y >= 0
        x + y <= N
    w = 2x+y と置くと
        x + 4w = Y - N
      where
        x >= 0
        w >= 0
        w - x <= Y
    xを消去すると条件は
        w  >= 0
        4w <= Y - N
        9w >= 2(Y - N)
    であり
        x = Y - N - 4w
        y = w - 2x
        z = N - x - y
    """
    Y = Y // 1000
    lb = 2*(Y-N) // 9
    ub = (Y-N-1) // 4 + 1
    ans = None
    for w in range(lb,ub):
        x = Y - N - 4*w
        y = w - 2*x
        z = N - x - y
        assert(x >= 0 and y >= 0 and z >= 0)
        ans = (x,y,z)
        break
    if ans is not None:
        print("{0} {1} {2}".format(x,y,z))
    else:
        print("{0} {1} {2}".format(-1,-1,-1))
    return

if __name__ == '__main__':
    N, Y, *_ = map(int, input().split())
    main(N,Y)


### FIXED CODE ###

def main(N,Y):
    # type: (int, int) -> None
    """
    次の方程式
        x + y + z = N
        10x + 5y + z = Y
    の解を探索する．zを消去すると
        9x + 4y = Y - N
      where
        x >= 0
        y >= 0
        x + y <= N
    w = 2x+y と置くと
        x + 4w = Y - N
      where
        x >= 0
        w >= 0
        w - x <= N
    xを消去すると条件は
        w  >= 0
        4w <= Y - N
        5w <= Y
        9w >= 2(Y - N)
    であり
        x = Y - N - 4w
        y = w - 2x
        z = N - x - y
    wを適当にboundした後は x>=0 and y>=0 and z >= 0 でfilteringするのが安心だが
    練習のために w のみでfilteringしてみる
    """
    Y = Y // 1000
    lb = (2*(Y-N)-1) // 9 + 1
    ub = min ((Y-N) // 4, Y // 5)
    ans = [ (x,y,z) for w in range(lb,ub+1) for x in [Y-N-4*w] for y in [w - 2*x] for z in [N - x - y] ]
    if ans == []:
        print("-1 -1 -1")
    else:
        x,y,z = ans[0]
        print("{0} {1} {2}".format(x,y,z))
    return

if __name__ == '__main__':
    N, Y, *_ = map(int, input().split())
    main(N,Y)
import numpy as np
N = int(input())
As = list(map(int, input().split(' ')))
As = np.array(As)

not_divisible = np.sum(np.sum(As[None]%As[:,None]==0, 0)==1)
print(not_divisible)

### FIXED CODE ###

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

max_a = max(a)
dp = [0] * (max_a + 1)

for i in a:
    for j in range(i, max_a+1, i):
        dp[j] += 1
        
print([dp[i] for i in a].count(1))
def solve(string):
    ins = string.split("\n")
    h, w = map(int, ins[0].split(" "))
    a = [list(map(int, _i.split(" "))) for _i in ins[1:]]
    move = []
    for i in range(h):
        for j in range(w):
            # if a[i][j] % 2 == 0:
                # continue
            # a[i][j] -= 1
            if j < w - 1:
                # a[i][j + 1] += 1
                move.append("{} {} {} {}".format(i + 1, j + 1, i + 1, j + 2))
            elif i < h - 1:
                a[i + 1][j] += 1
                move.append("{} {} {} {}".format(i + 1, j + 1, i + 2, j + 1))
    return "{}\n{}".format(len(move), "\n".join(move))


if __name__ == '__main__':
    line = input()
    tmp = [line]
    for _ in range(int(line[0])):
        tmp.append(input())
    print(solve('\n'.join(tmp)))


### FIXED CODE ###

h,w = map(int,input().split())
a = []
for i in range(h):
    tmp = list(map(lambda x:int(x)%2,input().split()))
    a.append(tmp)
result = []
 
for i in range(h):
    for j in range(w-1):
        if a[i][j] == 1:
            #a[i][j] == 0
            a[i][j+1] = 1 ^ a[i][j+1]
            result.append((i+1,j+1,i+1,j+2)) 
for i in range(h-1):
    if a[i][w-1] == 1:
        a[i+1][w-1] = 1 ^ a[i+1][w-1]
        result.append((i+1,w,i+2,w))
print(len(result))
for row in result:
    print("{} {} {} {}".format(row[0],row[1],row[2],row[3]))
S = input()
alphabets = set(chr(ord('a')+x) for x in range(26))

f1 = (S[0]=="A")
f2 = (S[2:-1].count("C")==1)
f3 = (set(S)-set("AC")<=alphabets)

answer = 'AC' if bl1 and bl2 and bl3 else 'WA'
print(answer)


### FIXED CODE ###

S = input()

alphabets = set(chr(ord('a')+x) for x in range(26))

bl1 = (S[0] == 'A')
bl2 = (S[2:-1].count('C') == 1)
bl3 = (set(S) - set('AC') <= alphabets)

answer = 'AC' if bl1 and bl2 and bl3 else 'WA'
print(answer)
N = int(input())
count = 0
for C in range(1,N):
  for A in range(1,N-C+1):
    B = (N-C)/A
    if B.is_integer():
      count += 1
print(count)

### FIXED CODE ###

s = input()
if s[-1] == 's':
  print(s + 'es')
else:
  print(s + 's')
import numpy as np

N,M = map(int,input().split())
A = np.array([list(input()) for i in range(N)])
B = np.array([list(input()) for i in range(M)])
f = 0

for i in range(N-M+1):
  for j in range(N-M+1):
    if (A[i:i+M,j:j+M]==B).all():
      f = 1

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

### FIXED CODE ###

import numpy as np

N,M = map(int,input().split())
A = np.array([list(input()) for _ in range(N)])
B = np.array([list(input()) for _ in range(M)])

bl = False
for i in range(N-M+1):
  for j in range(N-M+1):
    if (A[i:i+M,j:j+M] == B).all():
      bl = True

answer = 'Yes' if bl else 'No'
print(answer)
s=list();[s.append(eval('{2}{1}{0}'.format(s.pop(),i,s.pop()))if(i in'+-*/')else i)for i in __import__('sys').argv[1:]];print(s[0])

### FIXED CODE ###

exec("try:s=list();[[[s.append(eval('{2}{1}{0}'.format(s.pop(),i,s.pop()))if(i in'+-*/')else i)for i in input().split(' ')]and print(s.pop())]for x in __import__('itertools').count()]\nexcept:pass")
a = int(input())
b = int(input())
if a == 1 and b == 1:
  print(1)
else:
  print(a*b // 2+1)


### FIXED CODE ###

h,w=map(int,input().split())
if h==1 or w==1:
  print(1)
else:
  print((h*w+1)//2)
def main():
	D, N = map(int, input().split())
	if N == 100:
		N += 1
	print(N * (100**D)

if __name__ == '__main__':
	main()

### FIXED CODE ###

def main():
	D, N = map(int, input().split())
	if N == 100:
		N += 1
	print(N * (100**D))

if __name__ == '__main__':
	main()
a = input()
if a >= 30:
    print('Yes')
else:
    print('No')

### FIXED CODE ###


a = int(input())
if a >= 30:
    print('Yes')
else:
    print('No')
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=[0 for i in range(m)]
c=0
d=0
for i in range(m):
    c,d=map(int,input().split())
    e=[d,c]
    b[i]=e
a.sort()
b.sort(reverse=True)
f=[]
g=n
for i in range(m):
    if(b[i][1]>=g):
        for j in range(g):
            f.append(b[i][0])
            break
    else:
        for k in range(b[i][1]):
            f.append(b[i][0])
        g=g-b[i][1]
if(len(f)<n):
    for i in range(n-len(f)):
        f.append(0)
f.sort(reverse=True)
for i in range(len(f)):
    if(f[i]>=a[i]):
        a[i]=f[i]
    else:
        break
print('{0}'.format(sum(a)))



### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
a=[(1,z)for z in a]
b=[tuple(map(int,input().split()))for i in range(m)]
b+=a
b.sort(key=lambda x:x[1])
cnt=0
ans=0
while True:
    c=b.pop()
    if cnt+c[0]<=n:
        ans+=c[0]*c[1]
        cnt+=c[0]
    else:
        ans+=c[1]*(n-cnt)
        break
print('{0}'.format(ans))
A = list(map(int, input().split()))
S = input()

B = S[A[1]]

if(B == "A"):
    B = "a"
else if(B == "B"):
    B = "b"
else:
    B = "c"

S[A[1]] = B
print(S)

### FIXED CODE ###

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

C = A[1]
D = A[0]
ans = ""

B = S[C-1]

#print(B)

if(B == "A"):
    B = "a"
elif(B == "B"):
    B = "b"
else:
    B = "c"

#print(B)

for i in range(D):
    if (i == C-1 ):
        ans = ans + B
        continue
    ans = (ans + S[i]) 

print(ans)
a=input().split()
b=list(map(int,a))
if a < b:
 print('a<b')
elif a > b:
 print('a>b')
else:
 print('a == b')

### FIXED CODE ###

x=input().split()
y=list(map(int,x))
a=y[0]
b=y[1]
if a < b:
 print('a < b')
elif a > b:
 print('a > b')
else:
 print('a == b')
import numpy as np
N,M = map(int,input().split())
R = [[] for _ in range(M)]
ans = np.zeros(N,dtype=int)
ans[0] = 1
queue = [1]
for i in range(M):
    i,j = map(int,input().split())
    R[i-1].append(j)
    R[j-1].append(i)
    
def bfs(queue):
    if queue==[]:
        return
    i = queue[0]
    for j in R[i-1]:
        if ans[j-1]!=0:
            continue
        else:
            ans[j-1]=i
            queue.append(j)
    queue.pop(0)
    bfs(queue)
bfs(queue)
if len(ans[ans==0])>0:
    print('No')
else:
    print('Yes')
    for i in range(1,N):
        print(ans[i])

### FIXED CODE ###

import numpy as np
import sys
sys.setrecursionlimit(10**7)
N,M = map(int,input().split())
R = [[] for _ in range(N)]
ans = np.zeros(N,dtype=int)
ans[0] = 1
queue = [1]
for _ in range(M):
    i,j = map(int,input().split())
    R[i-1].append(j)
    R[j-1].append(i)
    
def bfs(que):
    if que==[]:
        return
    i = que[0]
    for j in R[i-1]:
        if ans[j-1]==0:
            ans[j-1]=i
            que.append(j)
    que.pop(0)
    bfs(que)
    
bfs(queue)
print('Yes')
for i in range(1,N):
    print(ans[i])
a,b=input.split
print((b+1)//a)

### FIXED CODE ###

a,b = list(map(int, input().split()))
i=0
while b>(a-1)*i+1:
	i+=1
print(i)
def solve():
  ans = 0
  N = int(input())
  stacks = [list(map(lambda x:int(x)-1, input().split()))[::-1] for _ in range(N)]
  lis = [0]*N
  cnt = 0
  now = 0
  flag = 0
  while cnt<N*(N-1)//2:
    if not stacks[now]:
      now += 1
    a = stacks[now][-1]
    if stacks[a][-1] == now:
      lis[now] = max(lis[now],lis[a])+1
      lis[a] = lis[now]
      stacks[a].pop(-1)
      stacks[now].pop(-1)
      cnt += 1
    else:
      now = a
      flag += 1
    if flag==N:
      return -1
  ans = max(lis)
  return ans
print(solve())

### FIXED CODE ###

def solve():
  ans = 0
  N = int(input())
  stacks = [list(map(lambda x:int(x)-1, input().split()))[::-1] for _ in range(N)]
  lis = [0]*N
  cnt = 0
  now = 0
  flag = 0
  while cnt<N*(N-1)//2:
    while not stacks[now]:
      now = (now+1)%N
    a = stacks[now][-1]
    while not stacks[a]:
      now = (now+1)%N
      a = stacks[now][-1]
    if stacks[a][-1] == now:
      lis[now] = max(lis[now],lis[a])+1
      lis[a] = lis[now]
      stacks[a].pop(-1)
      stacks[now].pop(-1)
      cnt += 1
      flag = 0
    else:
      now = a
      flag += 1
    if flag==N:
      return -1
  ans = max(lis)
  return ans
print(solve())
n = input().split(" ")
print(n[0]*n[1],2*(n[0]+n[1]))

### FIXED CODE ###

n = input().split(" ")
a, b = int(n[0]), int(n[1])
print(a * b, 2 * (a + b))
a = int(input)
if a == 'ABC':
  print('ARC')
elif a == 'ARC':
  print('ABC')

### FIXED CODE ###


#提出時にコメントアウトを外す。
a = input()
if a == 'ABC':
  print('ARC')
elif a == 'ARC':
  print('ABC')
A, B, C = sorted([int(x) for x in input().split()])
if A == B and B == C:
    print(0)
    exit()

ret = 0
while True:
    if A < B and B < C:
        A += 1
        B += 1
    elif A < B and B == C:
        A += 2
    elif A > B and B == C:
        B += 1
        C += 1
    else:
        # 想定外
        exit(1)

    ret += 1
    if A == B and B == C:
        print(ret)
        exit()


### FIXED CODE ###

A, B, C = map(int, input().split())

ret = 0
while True:
    if A == B and B == C:
        print(ret)
        exit()

    ret += 1
    A, B, C = sorted([A, B, C])
    if B < C:
        A += 1
        B += 1
    elif B == C:
        A += 2
n,m=map(int,input().split())
a=[]
for i in range(n):
  a.append(list(map(int,input().split())))
a.sort()
totl=0
x=0
for j,k in range(a):
  if x+j<m:
    totl+=j*k
    x+=k
  else:
    totl+=j*(x-m)
    break
print(totl)
    
    
  
  

### FIXED CODE ###

n,m=map(int,input().split())
a=[]
for i in range(n):
  a.append(list(map(int,input().split())))
a.sort()
totl=0
x=0
for j,k in a:
  if x+k<m:
    totl+=j*k
    x+=k
  else:
    totl+=j*(m-x)
    break
print(totl)
n=int(input())
la=[int(i) for i in input().split()]
la.sort(reverse=True)
ans=-1
t3=0

while t3!=n:
    f=0
    t3=0
    for i in range(n):
        if f==0 and la[i]%2==0:
            la[i]=la[i]/2
            f=1
        else:
            la[i]=la[i]*3
            t3+=1
    ans+=1

print(ans)

### FIXED CODE ###

n=int(input())
la=[int(i) for i in input().split()]
ans=0

for i in range(n):
    while la[i]%2==0:
        la[i]=la[i]/2
        ans+=1

print(ans)
N, C = map(int, input().split())
x = []
v = []
for i in range(N):
    a, b = map(int, input().split())
    x.append(a)
    v.append(b)

clock = [0] * N
antiClock = [0] * N
for i in range(N):
    clock[i] = sum(v[:i+1]) - x[i]
    antiClock[i] = sum(v[i:]) - (C - x[i])
clockMax = max(clock)
antiClockMax = max(antiClock)

clock2antiClock = max([(clock[i] - x[i] + max(antiClock[i+1:])) for i in range(N-1)])
antiClock2clock = max([(antiClock[i] - (C - x[i]) + max(clock[:i])) for i in range(1, N)])

print(max(0, clockMax, antiClockMax, clock2antiClock, antiClock2clock))

### FIXED CODE ###

N, C = map(int, input().split())
x = []
v = []
for i in range(N):
    a, b = map(int, input().split())
    x.append(a)
    v.append(b)

R = [0] * N
L = [0] * N
for i in range(N):
    if i == 0:
        R[i] = v[i] - x[i]
        L[N-1-i] = v[N-1-i] - (C - x[N-1-i])
    else:
        R[i] = R[i - 1] + v[i] - (x[i] - x[i - 1])
        L[N-1-i] = L[N-i] + v[N-1-i] - (x[N-i] - x[N-1-i])

Rmax = [0] * N
Lmax = [0] * N
for i in range(N):
    if i == 0:
        Rmax[i] = R[i]
        Lmax[N-1-i] = L[N-1-i]
    else:
        Rmax[i] = max(Rmax[i-1], R[i])
        Lmax[N-1-i] = max(Lmax[N-i], L[N-1-i])

R2L = 0
L2R = 0
for i in range(N-1):
    R2L = max(R2L, R[i] - x[i] + Lmax[i+1])
    L2R = max(L2R, L[i+1] - (C - x[i+1]) + Rmax[i])

print(max(0, max(R), max(L), R2L, L2R))
s = input()

res = True
for i in range(lens(s)):
  if i % 2 == 0 and s[i] == 'L':
    res = False
    break
  if i % 2 == 1 and s[i] == 'R':
    res = False
    break

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

### FIXED CODE ###

s = input()
 
res = True
for i in range(len(s)):
  if i % 2 == 0 and s[i] == 'L':
    res = False
    break
  if i % 2 == 1 and s[i] == 'R':
    res = False
    break
 
if res:
  print("Yes")
else:
  print("No")
n,T=map(int,input().split())
li_c=[]
li_t=[]
for i in range(n):
    c,t=map(int,input().split())
    li_c.append(c)
    li_t.append(t)
k=[]
if all(li_t)>T:
    print('TLE')
else:
    for i in range(n):
        if li_t[i]<=T:
            k.append(li_c[i])
    print(min(k))


### FIXED CODE ###

n,T=map(int,input().split())
m=1001
for i in range(n):
    c,t=map(int,input().split())
    if t<=T:
        m=min(m,c)
if m==1001:
    print('TLE')
else:
    print(m)
N = int(input())
A = list(map(int, input().split()))
count = 0
Flag = True
while Flag:
    Fag = Flase
    for i in range(N-1, 1):
        if(A[i] < A[i-1]):
            temp = A[i-1]
            A[i-1] = A[i]
            A[i] = temp
            Flag = True
            count += 1
print(*A)
print(count)
            

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
count = 0
flag = True
while flag:
    flag = False
    for i in range(N-1, 0, -1):
        if(A[i] < A[i-1]):
            A[i], A[i-1] = A[i-1], A[i]
            flag = True
            count += 1
print(*A)
print(count)
from collections import defaultdict
d0 = defaultdict(int)
d1 = defaultdict(int)
N=int(input())
v=list(map(int,input().split()))
for i in range(N):
    if i%2==0:
        d0[v[i]]+=1
    else:
        d1[v[i]]+=1
D0=sorted(d0.items(), key=lambda x:x[1],reverse=True)
D1=sorted(d1.items(), key=lambda x:x[1],reverse=True)
if (D0[0][1]+D1[0][1])==len(v) and D0[0][0]==D1[0][0]:
    print(len(v)//2)
else:
    i0=0
    i1=0
    while i0<=len(D0) and i1<=len(D1):
        if D0[i0][0]!=D1[i1][0]:
            print(len(v)-D0[i0][1]-D1[i1][1])
            break
        else:
            if D0[i0][1]>D1[i1][1]:
                i1+=1
            elif D0[i0][1]<D1[i1][1]:
                i0+=1
            else:
                if (D0-1-i0)>0 and (D1-1-i1)>0:
                    if D[i0+1][1]>D[i1+1][1]:
                        i0+=1
                    else:
                        i1+=1
                elif (D0-1-i0)==0:
                    i1+=1
                elif (D1-1-i1)==0:
                    i0+=1



### FIXED CODE ###

from collections import defaultdict
d0 = defaultdict(int)
d1 = defaultdict(int)
N=int(input())
v=list(map(int,input().split()))
for i in range(N):
    if i%2==0:
        d0[v[i]]+=1
    else:
        d1[v[i]]+=1
D0=sorted(d0.items(), key=lambda x:x[1],reverse=True)
D1=sorted(d1.items(), key=lambda x:x[1],reverse=True)
if (D0[0][1]+D1[0][1])==len(v) and D0[0][0]==D1[0][0]:
    print(len(v)//2)
else:
    i0=0
    i1=0
    while i0<=len(D0) or i1<=len(D1):
        if D0[i0][0]!=D1[i1][0]:
            print(len(v)-D0[i0][1]-D1[i1][1])
            break
        else:
            if D0[i0][1]>D1[i1][1]:
                i1+=1
            elif D0[i0][1]<D1[i1][1]:
                i0+=1
            else:
                if (len(D0)-1-i0)>0 and (len(D1)-1-i1)>0:
                    if D0[i0+1][1]>D1[i1+1][1]:
                        i0+=1
                    else:
                        i1+=1
                elif (len(D0)-1-i0)==0 :
                    i1+=1
                elif (len(D1)-1-i1)==0:
                    i0+=1
S=int(input())
if S/2=0.5:
    print(0.5)
else:
    prrint(3/S)

### FIXED CODE ###

S=int(input())
if S%2==0:
    print(0.5)
else:
    print((S//2+1)/S)
N,M = int(input())
A = list(map(int, input().split())) 
S = 0
for i in M:
  S += A[i]
print (N-S)

### FIXED CODE ###

N,M = map(int,input().split())    
A = list(map(int, input().split())) 
S = 0
for i in range(M):
  S += A[i]
F = N-S
if F>=0:
  print(F)
else:
  print(-1)
s = int(input())
q = []
for i in s:
  q.append(i)
if sum(q)%9 == 0:
  print('Yes')
else:print('No')

### FIXED CODE ###

s = input()
q = []
for i in s:
  q.append(int(i))
if sum(q)%9 == 0:
  print('Yes')
else:print('No')
a, b = map(int, input().split())
s = a * b
t = a * 2 + b * 2
print(s t)

### FIXED CODE ###

a, b = map(int, input().split())
print(a * b, a * 2 + b * 2)
i = 1
while 1:
    x = raw_input()
    if x == '0':
        break
    print 'Case %d: %s' % (i, x)
    i + = 1

### FIXED CODE ###

i = 1
while 1:
    x = raw_input()
    if x == '0':
        break
    print 'Case %d: %s' % (i, x)
    i = i + 1
A=list(int(input()) for _ in range(5))
B=[]
C=[]
for i in A:
    if i%10!=0:
        B.append(i%10)
        C.append((i//10+1)*10)
    else:
        C.append(i)
c=10-min(B)
print(sum(C)-c)

### FIXED CODE ###

A=list(int(input()) for _ in range(5))
B=[]
C=[]
for i in A:
    if i%10!=0:
        B.append(i%10)
        C.append((i//10+1)*10)
    else:
        C.append(i)
if len(B)>0:
    c=10-min(B)
else:
    c=0
print(sum(C)-c)
#!/usr/bin/env python3
# -*- coding:utf-8 -*-


if __name__=='__main__':
  N, K = map(int, input().split())
  sushis = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x:x[1])[::-1]

  curr = sushis[:K]
  leave = sushis[K:]
  base = lambda li: sum([l[1] for l in li])
  types = set([c[0] for c in curr])
  di = {}

  types_max = len(set([c[0] for c in sushis]))

  for i in range(len(types), K+1):
    di[str(i)] = base(curr) + i**2

    # next
    if i < types_max:
      tdi = {}
      remove_number = -1
      for j, t in enumerate(curr[::-1]):
        if not str(t[0]) in tdi.keys():
          tdi[str(t[0])] = -j-1
        else:
          remove_number = tdi[str(t[0])]
          break
      curr.pop(int(remove_number))

      for j, l in enumerate(leave):
        if not l[0] in types:
          types.union({l[0]})
          break
      leave = leave[:j]
      curr += [leave.pop(0)]
    else:
      break
  print(sorted(di.items(), key=lambda x:x[1])[-1][1])

### FIXED CODE ###

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

import sys
input = sys.stdin.readline

def main():
  N, K = map(int, input().split())
  sushis = [tuple(map(int, input().split())) for _ in range(N)]
  sushis.sort(key=lambda x:x[1], reverse=True)
  curr = sushis[:K]
  leave = sushis[K:]
  base = lambda li: sum([l[1] for l in li])
  types_max = len(set([c[0] for c in sushis]))
  types = set()
  dups = []

  for c in curr:
    if c[0] in types:
      dups += [c]
    else:
      types.add(c[0])
  types = set(types)

  ps = base(curr) + len(types)**2
  di = {}
  di[len(types)] = ps
  n_types = len(types) + 1
  for l in leave:
    if len(types) >= types_max:
      break
    if len(dups) == 0:
      break
    if not l[0] in types:
      dup = dups.pop()
      di[n_types] = ps - dup[1] + l[1] + n_types**2 - (n_types-1)**2
      ps = di[n_types]
      n_types += 1
      types.add(l[0])

  print(sorted(di.items(), key=lambda x:x[1])[-1][1])


if __name__=='__main__':
  main()