Harryxun/stf_run huggingface dataset:
H,W=map(int,input().split())
red=[]
blue=[]
for i in range(H):
  A=list(map(int,input().split()))
  red.append(A)
for i in range(H):
  B=list(map(int,input().split()))
  blue.append(B)
list=[[[0 for i in range(80*(j+k+1))] for j in range(W)] for k in range(H)]
list[0][0][abs(red[0][0]-blue[0][0])]=1
for i in range(H):
  for j in range(W):
    for k in range(len(list[i][j])):
      if list[i][j][k]==1:
        if i+1<H:
          if abs(k-abs(red[i+1][j]-blue[i+1][j]))<12801: 
            list[i+1][j][abs(k-abs(red[i+1][j]-blue[i+1][j]))]=1
          if abs(k+abs(red[i+1][j]-blue[i+1][j]))<12801: 
            list[i+1][j][abs(k+abs(red[i+1][j]-blue[i+1][j]))]=1
        if j+1<W:
          if abs(k-abs(red[i][j+1]-blue[i][j+1]))<12801: 
            list[i][j+1][abs(k-abs(red[i][j+1]-blue[i][j+1]))]=1
          if abs(k+abs(red[i][j+1]-blue[i][j+1]))<12801: 
            list[i][j+1][abs(k+abs(red[i][j+1]-blue[i][j+1]))]=1           
for i in range(12801):
  if list[H-1][W-1][i]==1:
    print(i)
    break

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
for i in range(1,N):
  A[i]+=A[i-1]
A=[(A[i]-i-1)%K for i in range(N)]
A=[0]+A
from collections import Counter
if K>N:
  a=Counter(A)
  ans=0
  for v in a.values():
    ans+=v*(v-1)/2
  print(int(ans))
else:
  ans=0
  d={}
  for i in range(K):
    if A[i] in d:
      ans+=d[A[i]]
      d[A[i]]+=1
    else:
      d[A[i]]=1
  for i in range(K,N+1):
    d[A[i-K]]-=1
    if A[i] in d:
      ans+=d[A[i]]
      d[A[i]]+=1
    if A[i] not in d or d[A[i]]==0:
      d[A[i]]=1
  print(ans)
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]))
n, x = map(int, input().split())
a = list(map(int, input().split()))
if n == 1:
    print(abs(x-a[0]))
    exit()
a.sort()
else:
    box = [a[i+1]-a[i] for i in range(n-1)]
    b = min(box)
    for i in range(1,b+1):
        for j in range(n-1):
            if box[j]%i:
                break
            if j == n-2:
                ans = i
    d = abs(x-a[0])
    if ans <= d:
        for i in range(1,ans+1):
            if d%i:
                continue
            else:
                temp = i
        print(temp)
    else:
        for i in range(1,d+1):
            if ans%i:
                continue
            else:
                temp = i
        print(temp)



### FIXED CODE ###

a,b = map(int, input().split())
if a*b % 2:
    print('Yes')
else:
    print('No')
def main():
	# k = int(input())
	# s = str(input())
	n,m = map(int,input().split())
	#1行R列
	h = list(map(int,input().split()))
	#R行1列
	# l = [int(input()) for i in range(n)]
	#R行C列
	l = [list(map(int, input().split())) for i in range(m)]

	ans = int(n)
	del_list = set()
	for i in range(m):
		if l[i][0] != l[i][1] and h[min(l[i][0]-1,l[i][1]-1)] not in del_list:
			ans -= 1
			del_list.add(min(h[l[i][0]-1],h[l[i][1]-1]))
			# print("i del {}".format(min(h[l[i][0]-1],h[l[i][1]-1])))
		else:
			if h[l[i][0]-1] in del_list and h[l[i][1]-1] in del_list:
				ans += 0
			elif h[l[i][0]-1] in del_list:
				ans -= 1
				del_list.add(min(h[l[i][0]-1]))
			else:
				ans -= 1
				del_list.add(min(h[l[i][1]-1]))
	print(ans)





if __name__ == '__main__':
	main()

### FIXED CODE ###

def main():
	n,m = map(int,input().split())
	h = list(map(int,input().split()))
	l = [list(map(int, input().split())) for i in range(m)]

	ans = int(n)
	del_list = set()
	for i in range(m):
		if h[l[i][0]-1] > h[l[i][1]-1] and l[i][1] not in del_list:
			ans -= 1
			del_list.add(l[i][1])
		elif h[l[i][0]-1] < h[l[i][1]-1] and l[i][0] not in del_list:
			ans -= 1
			del_list.add(l[i][0])
		elif h[l[i][0]-1] == h[l[i][1]-1]:
			if l[i][0] not in del_list and l[i][1] not in del_list:
				ans -= 2
				del_list.add(l[i][0])
				del_list.add(l[i][1])
			elif l[i][0] not in del_list:
				ans -= 1
				del_list.add(l[i][0])
			elif l[i][1] not in del_list:
				ans -= 1
				del_list.add(l[i][1])
			else:
				ans += 0
		else:
			ans += 0

	print(ans)





if __name__ == '__main__':
	main()
class edge():
    def __init__(self,_to,_cost):
        self.to = _to;
        self.cost = _cost;

N = int(input())
tree = [[] for i in range(N+1)]

for i in range(N-1):
    a,b,c = list(map(int,input().split()))
    a = a - 1
    b = b - 1
    tree[a].append(edge(b,c))
    tree[b].append(edge(a,c))
Q,K = list(map(int,input().split()))
K = K - 1
dmax = 10**14 + 1
depth = [dmax for _ in range(N)]

def DFS(v,p,d):
    depth[v] = d
    for e in tree[v]:
        if e.to == p:
            continue
        DFS(e.to, v, d + e.cost)
DFS(K,-1,0)

for _ in range(Q):
    x,y = list(map(int, input().split()))
    x = x - 1
    y = y - 1
    print(depth[x] + depth[y])


### FIXED CODE ###

import sys;sys.setrecursionlimit(int(1e7))

class edge():
    def __init__(self,_to,_cost):
        self.to = _to;
        self.cost = _cost;

N = int(input())
tree = [[] for i in range(N+1)]

for i in range(N-1):
    a,b,c = map(int,input().split())
    a = a - 1
    b = b - 1
    tree[a].append(edge(b,c))
    tree[b].append(edge(a,c))
Q,K = map(int,input().split())
K = K - 1
depth = [None]*N

def DFS(v,p,d):
    depth[v] = d
    for e in tree[v]:
        if e.to == p:
            continue
        DFS(e.to, v, d + e.cost)
DFS(K,-1,0)

for _ in range(Q):
    x,y = map(int, input().split())
    x = x - 1
    y = y - 1
    print(depth[x] + depth[y])
def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    
    L = [0 for i in range(n1+1)]
    R = [0 for i in range(n2+1)]

    for i in range(n1):
        L[i] = A[left + i]
        
    for i in range(n2):
        R[i] = A[mid + i]
    
    L[n1]=100000000
    R[n2]=100000000

    cnt1 = 0
    cnt2 = 0
    
    for k in range(left, right):
        if L[cnt1] <= R[cnt2]:
            A[k] = L[cnt1]
            cnt1 += 1
        else:
            A[k] = R[cnt2]
            cnt2 +=  1
    
    global cnt
    cnt += cnt1 + cnt2
    
    
def mergeSort(A, left, right):
    if left+1 < right:
        mid = (left + right)//2
        
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)
        

n = int(input().rstrip())
A = list(map(int,input().split(" ")))
cnt = 0
mergeSort(A, 0 , len(A))
print(" ".join(list(map(str,A))))
print(str(cnt))

### FIXED CODE ###

def merge(A, left, mid, right):
#    n1 = mid - left
#    n2 = right - mid
    
#    L = [0 for i in range(n1+1)]
#    R = [0 for i in range(n2+1)]

#    for i in range(n1):
#        L[i] = A[left + i]
#        
#    for i in range(n2):
#        R[i] = A[mid + i]
    
#    L[n1]=1000000001
#    R[n2]=1000000001

    L = A[left:mid] + [1000000001]
    R = A[mid:right] + [1000000001]

    cnt1 = 0
    cnt2 = 0
    
    for k in range(left, right):
        if L[cnt1] <= R[cnt2]:
            A[k] = L[cnt1]
            cnt1 += 1
        else:
            A[k] = R[cnt2]
            cnt2 +=  1
    
    global cnt
    cnt += cnt1 + cnt2
    
    
def mergeSort(A, left, right):
    if left+1 < right:
        mid = (left + right)//2
        
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)
        

n = int(input().rstrip())
A = list(map(int,input().split(" ")))
cnt = 0
mergeSort(A, 0 , len(A))
print(" ".join(list(map(str,A))))
print(str(cnt))
import sys
 
def input():
    return sys.stdin.readline().strip()
 
n = int(input())
A = list(map(int, input().split()))
sum = 1
for i in range(n):
    sum *= A[i]
if(sum > 10**18):
    sum = -1
print(sum)


### FIXED CODE ###

import sys

def input():
    return sys.stdin.readline().strip()

a, b = map(int, input().split())
print(a*b)
N=int(input())
S=list(input())
check=[]
for i in range(N-1):
  if S[i]==S[i+1]:
    check.append(i)
for i in check:
  S.pop(i)


### FIXED CODE ###

N=int(input())
S=list(input())
check=[]
for i in range(N-1):
  if S[i]==S[i+1]:
    check.append(i)
check=reversed(check)
for i in check:
  S.pop(i)
print(len(S))
import bisect
import sys
sys.setrecursionlimit(10**6)


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

edges = [[] for _ in range(n)]
for _ in range(n-1):
    from_, to = map(int, input().split())
    edges[from_-1].append(to-1)
    edges[to-1].append(from_-1)


DP = [10**6] * n
DP[0] = 0
ans = [0] * n


def dfs(node):
    node = node
    num = A[node]
    lis = bisect.bisect_left(DP, num)

    prev = DP[lis]
    update = lis
    ans[node] = update
    DP[lis] = num
    for to in edges[node]:
        if not ans[to]:
            dfs(to)

    DP[lis] = prev


dfs(0)
for res in ans:
    print(res)


### FIXED CODE ###

import bisect
import sys
sys.setrecursionlimit(10**8)


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

edges = [[] for _ in range(n)]
for _ in range(n-1):
    from_, to = map(int, input().split())
    edges[from_-1].append(to-1)
    edges[to-1].append(from_-1)


DP = [10**9+7] * (n+1)
DP[0] = 0
ans = [0] * n


def dfs(node):
    node = node
    num = A[node]
    update_idx = bisect.bisect_left(DP, num)
    prev = DP[update_idx]
    DP[update_idx] = num
    lis = bisect.bisect_left(DP, 10**9+1) - 1
    ans[node] = lis
    for nex in edges[node]:
        if not ans[nex]:
            dfs(nex)

    DP[update_idx] = prev


dfs(0)
for res in ans:
    print(res)
#C
W, H, x, y = map(int, input().split())
S = W*H/2
ans = '0'
if W/2 == x and H/2 == y:
    ans = '1'

print(f"{S} {ans}")

### FIXED CODE ###

#C
W, H, x, y = map(int, input().split())
S = W*H/2
ans = '0'
if W/2 == x and H/2 == y:
    ans = '1'

print("{} {}".format(S, ans))
import numpy as np

NM=np.array(input().split(" "),dtype=np.int32)

result={}
pre_idx=""
tmp=[]
for i in range(NM[1]):
    s=input().split(" ")
    idx=s[0]
    if(pre_idx!=idx):
        result[idx]=[]
        result[idx].append(s[1])
    else:
        result[idx].append(s[1])
    pre_idx=idx

corrects=0
penalty=0
keys=result.keys()

for k in keys:
    L=result[k]
    idx=L.index('AC')
    if(idx==-1):
        continue
    else:
        penalty+=idx
        corrects+=1

print("{} {}".format(corrects,penalty))

### FIXED CODE ###

import numpy as np

NM=np.array(input().split(" "),dtype=np.int32)

result={}
tmp=[]

for i in range(NM[1]):
    s=input().split(" ")
    result.setdefault(s[0],[]).append(s[1])

corrects=0
penalty=0
keys=result.keys()

for k in keys:
    L=result[k]
    if('AC' in L):
        idx=L.index('AC')
    else:
        idx=-1
    if(idx==-1):
        continue
    else:
        penalty+=idx
        corrects+=1

print("{} {}".format(corrects,penalty))
N= int(input())
s = []

for _ in range(N):
    s.append(input())

for i in range(N):
    s[i] = tuple(sorted(s[i]))

import collections
c = collections.Counter(s)
d = [i for i in c.values()]

counter = 0
from math import factorial
for i in d:
    if i > 1:
        counter += i(i-1)/2

print(int(counter)) 

### FIXED CODE ###

N= int(input())
s = []

for _ in range(N):
    s.append(input())

for i in range(N):
    s[i] = tuple(sorted(s[i]))

import collections
c = collections.Counter(s)
d = [i for i in c.values()]

counter = 0
from math import factorial
for i in d:
    if i > 1:
        counter += i*(i-1)/2

print(int(counter))
n = int(input())
list_n = []
for i in range(n):
    list_n.append(int(input()))

if len(list_n) == len(set(list_n)):
    print("YES")
else:
    print("NO")

### FIXED CODE ###

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

if len(list_n) == len(set(list_n)):
    print("YES")
else:
    print("NO")
d = [input() for i in range(5)]
p = [int(list(i)[-1]) for i in d]
if p.count(0) == 0:
  n = p.index(min(p))
else:
  q = sorted(p)
  while q.count(0) != 0:
    q.remove(0)
  m = q[0]
  n = p.index(m)
  
x = int(d[n])
del d[n]

for i in range(len(d)):
  if list(d[i])[-1] == "0":
    continue
  else:
    d[i] = int(d[i])
    d[i] = (int(d[i]/10)+1)*10
    
d = [int(num) for num in d]

print(sum(d)+x)

### FIXED CODE ###

lst = [input() for i in range(5)]
d = [int(num) for num in lst]
lst_one = [int(list(i)[-1]) for i in lst]
if lst_one.count(0) == len(lst_one):
  print(sum(d))
else:
  if lst_one.count(0) == 0:
    idx = lst_one.index(min(lst_one))
  else:
    no_zero = [i for i in lst_one if i != 0]
    m = min(no_zero)
    idx = lst_one.index(m)

  x = d[idx]
  del d[idx]

  for i in range(len(d)):
    if d[i] % 10 != 0:
      d[i] = 10*(int((d[i]/10))+1)
    else:
      continue
  print(sum(d) + x)
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

x = [0] * M
y = [0] * M
c = [0] * M

min = 99999999

for i in range(M):
    x[i], y[i], c[i] = map(int, input().split())
    cost = a[x[i] - 1] + b[y[i] - 1] - c[i]
    if cost < min:
        min = cost

for i in range(A):
    if a[i] > cost:
        continue
    for j in range(B):
        if b[j] > cost:
            break
        cost = a[i] + b[j]
        if cost < min:
            min = cost

print(min)

### FIXED CODE ###

input = input()

if len(input) % 2:
    print("No")
    exit(0)

result = "Yes"
isHi = False
for i in range(len(input)-1):
    if isHi:
        isHi = False
        continue;

    str = input[i] + input[i+1]
    if str != "hi":
        result = "No"
        break

    isHi = True

print(result)
n = int(input())
lis=[]
for i in range(n):
    lis.append(int(input()))

lis.sort()

count=0
while len(lis)>0:
    if lis[0]==lis[1]:
        del lis[:2]
    else:
        del lis[0]
        count+=1
print(count)

### FIXED CODE ###

n = int(input())
lis=[]
for i in range(n):
    lis.append(int(input()))

lis.sort()

count=0
while len(lis)>1:
    if lis[0]==lis[1]:
        del lis[:2]
    else:
        del lis[0]
        count+=1
print(count+len(lis))
sa = list(reversed(input()))
sb = list(reversed(input()))
sc = list(reversed(input()))

turn = sa.pop()

while True:
    if (turn == "a" and not sa) or (turn == "b" and not sb) or (turn == "c" and not sc):
        break
    elif turn == "a":
        turn = sa.pop()
    elif turn == "b":
        turn = sb.pop()
    else turn == "c":
        turn = sc.pop()

print(turn.upper())


### FIXED CODE ###

sa = list(reversed(input()))
sb = list(reversed(input()))
sc = list(reversed(input()))

turn = sa.pop()

while True:
    if (turn == "a" and not sa) or (turn == "b" and not sb) or (turn == "c" and not sc):
        break
    elif turn == "a":
        turn = sa.pop()
    elif turn == "b":
        turn = sb.pop()
    else:
        turn = sc.pop()

print(turn.upper())
if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
  
if len(set(A)) == len(N):
    print('Yes')
else:
    print('No')

### FIXED CODE ###

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
if len(A) == len(set(A)):
    print('YES')
else:
    print('NO')
import math
n , k = map(int, input().split())

mod = 10 ** 9 + 7
red_count = n - k 
for i in range(1, k+1):
    if red_count + 1 - i < 0:
        print(0)
        continue
    b_dif = math.factorial(k-1) / (math.factorial(i-1) * math.factorial(k-i))
    
    r_dif = math.factorial(red_count + 1)  /  (math.factorial(i) * math.factorial(red_count + 1 - i))

    
    print(int(r_dif * b_dif % mod))

### FIXED CODE ###


from scipy.misc import comb
n , k = map(int, input().split())

mod = 10 ** 9 + 7
red_count = n - k 
for i in range(1, k+1) :
    if red_count + 1 - i < 0 :
        print(0)
        
    else:

        print(comb(red_count+1, i , exact = True)*comb(k-1, i-1, exact=True) % mod)
a,b=map(int,input().split())
print(a*b+" "+(a+b)*2)

### FIXED CODE ###

a,b=map(int,input().split())
print(a*b,(a+b)*2)
from collections import deque
S=input()
q=int(input())
que=deque(S)
rev=False
for i in range(q):
      s=input()
      if s=='1':
            rev=not rev
      else:
            t,f,c=s.split()
            if (f=='1' and rev==False) or (f=='2' and rev==True):
                  que.appendleft(c)
            else:
                  que.append(c)
if rev:
      que=que[::-1]
print(''.join(que))
            

### FIXED CODE ###

S=input()
q=int(input())
RV=0
A="A"
for i in range(q):
    IN=input()
    if IN=="1":
        RV+=1
    else:
        t,f,c=IN.split()
        if RV%2==0:
            if f=="1":
                A=c+A               
            else:
                A=A+c
        else:
            if f=="1":
                A=A+c
            else:
                A=c+A
if RV%2==0:
    for i in range(len(A)):
        if A[i]=="A":
            print(A[:i]+S+A[i+1:])
else:
    A=A[::-1]
    for i in range(len(A)):
        if A[i]=="A":
            print(A[:i]+S[::-1]+A[i+1:])
a = list(map(int,input().split()))
if (a * b) % 2 == 0:
  print("Even")
else:
  print("Odd")

### FIXED CODE ###

a = list(map(int,input().split()))
if (a[0] * a[1]) % 2 == 0:
  print("Even")
else:
  print("Odd")
#!usr/bin/env python3

import sys


def string_to_list_spliter():
    sys.stdin.readline()
    lst = [int(i) for i in sys.stdin.readline().split()]
    return lst


def main():
    lst = string_to_list_spliter()
    print(min(lst), max(lst), sum())


if __name__ == '__main__':
    main()

### FIXED CODE ###

#!usr/bin/env python3

import sys


def string_to_list_spliter():
    lst = [int(i) for i in sys.stdin.readline().split()]
    return lst


def main():
    # XXX: N????????´??°??????????????????????????????AOJ?????£???????????????
    n = sys.stdin.readline()
    lst = string_to_list_spliter()
    print(min(lst), max(lst), sum(lst))


if __name__ == '__main__':
    main()
N = int(input())
a = []
for i in range(N):
    a.append(int(input())
max_profit = a[1] - a[0]
for i in range(2,N):
	if a[i] - a[i-1] > max_profit:
		max_profit = a[i] - a[i-1]
print(str(max_profit))

### FIXED CODE ###

N = int(input())
a = []
for i in range(N):
    a.append(int(input()))
max_profit = a[1] - a[0]
min_val = min(a[1],a[0])
for i in range(2,N):
	if a[i] < min_val:
		min_val = a[i]
	elif a[i] - min_val > max_profit:
		max_profit = a[i] - min_val
print(str(max_profit))
n = int(input())
 i = 0

 l = list(map(int, input().split()))
 Max = l[0]
 Min = l[0]
 for i in range(0,n):
 	
 	if l[i] > Max: l[i],Max = Max,l[i]
 	if l[i] < Min: l[i],Min = Min,l[i]
 	
 	sum = 0
 	sum += l[i]  
 	
 	print(f"{Min} {Max} {sum}")



### FIXED CODE ###

n = int(input())
i = 0

l = list(map(int, input().split()))
Max = l[0]
Min = l[0]
sum = 0
for i in range(0,n):
	sum += l[i]
	a = l[i]#変数の値が下の行の処理で変わってしまうのでaとかにしておく
	if a > Max:
		a,Max = Max,a
	if  a < Min:
		a,Min = Min,a
	
	
print(f"{Min} {Max} {sum}")
n,k=map(int(input()).split())
A=list(map(int,input().split()))


if k>=n:
  print(abs(A[k-1]-A[0]))
else:
  dp=list(range(n))
  for i in range(k):
    dp[i]=abs(A[i]-A[0])
  for i in range(n-k):
    temp=list(range(k))
    for j in range(k):
      temp[j-1]=dp[i]+abs(A[i+k]-A[i])
      dp[i+k]=min(temp1,temp2)
  print(dp[n-1])

### FIXED CODE ###

n,k=map(int,input().split())
A=list(map(int,input().split()))

if k>=n:
  print(abs(A[n-1]-A[0]))
else:
  dp=list(range(n))
  for i in range(k):
    dp[i]=abs(A[i]-A[0])
  for i in range(n-k):
    temp=list(range(k))
    for j in range(k):
      temp[j]=dp[i+j]+abs(A[i+k]-A[i+j])
    dp[i+k]=min(temp)
  print(dp[n-1])
k=input()  
odd=1
even=0
for i in range(2,k+1) 
     if i%2==0:
        even+=1
     else:
           odd+=1
print(odd*even)

### FIXED CODE ###

k = int(input())
x = [i for i in range(1, k+1) if i & 1 == 0]
y = [i for i in range(1, k+1) if i & 1 == 1]
print(len(x)*len(y))
import sys
sys.setrecursionlimit(100000000)

def main():
    N,K = map(int,input().split())
    sushi = [tuple(map(int,input().split())) for _ in range(N)]

    sushi.sort(key = lambda x:x[1],reverse = True)
    ans = 0
    dic = {}
    change = []
    for a,b in sushi[:K]:
        if a in dic:
            dic[a].append(b)
            change.append((a,b))
        else:
            dic[a] = [b]
        ans += b

    various = len(dic)
    ans += various ** 2
    ret = ans
    used_type = {a for a in dic.keys()}
    suggestion = [p for p in sushi[K:] if p[0] not in used_type]
    for a,b in suggestion:
        if a in used_type:
            continue
        dic[change[-1][0]].pop()
        ret -= change[-1][1]
        ret += b + 2*various + 1
        dic[a] = b
        change.pop()
        various += 1
        used_type.add(a)
        ans = max(ans,ret)
    print(ans)
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)

def main():
    N,K = map(int,input().split())
    sushi = [tuple(map(int,input().split())) for _ in range(N)]

    sushi.sort(key = lambda x:x[1],reverse = True)
    ans = 0
    dic = {}
    change = []
    for a,b in sushi[:K]:
        if a in dic:
            dic[a].append(b)
            change.append((a,b))
        else:
            dic[a] = [b]
        ans += b

    various = len(dic)
    ans += various ** 2
    ret = ans
    used_type = set(dic.keys())
    suggestion = [p for p in sushi[K:] if p[0] not in used_type]
    for a,b in suggestion:
        if len(change) == 0:
            break
        if a in used_type:
            continue
        dic[change[-1][0]].pop()
        ret -= change[-1][1]
        ret += b + 2*various + 1
        dic[a] = b
        change.pop()
        various += 1
        used_type.add(a)
        ans = max(ans,ret)
    print(ans)
if __name__ == '__main__':
    main()
n, q = map(int, input().split())
tree = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

xs = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    xs[p-1] += x

ans = [0] * n

def dfs(u, parent=None):
    ans[u] = ans[parent] + xs[u]
    for v in tree[u]:
        if not v == parent:
            dfs(v, u)

dfs(0, 0)
print(' '.join([str(i) for i in ans]))


### FIXED CODE ###

n=int(input())
vs=list(map(int,input().split()))
while not len(vs)==1:
    vs.sort()
    a=vs.pop(0)
    b=vs.pop(0)
    t=(a+b)/2
    vs.append(t)
print(vs[0])
N,K=map(int,input().split())
A=list(map(int,input().split()))
done=[0 for _ in range(N)]
done[0]=1
W=[0]
loop=0
city=0

for i in range(N):
    if done[A[i]-1]==2:
        init=W.index(A[i]-1)
        loop=i-init
        break
    elif city==A[city]-1:
        init=i
        loop=1
        break
    city=A[city]-1
    W.append(city)
    done[city]+=1

if min(done)>0:
    init=0
    loop=N

print(W[(K-init)%loop+init]+1)

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
done=[-1 for _ in range(N)]
done[0]=0
n=0
now=0
init=0
loop=N
log=[0]

while n<N:
    log.append(A[log[-1]]-1)
    n+=1
    if done[log[-1]]>-1:
        init=done[log[-1]]
        loop=n-done[log[-1]]
        break
    done[log[-1]]=n

if K<init:
    print(log[K]+1)
else:
    num=init+(K-init)%loop
    print(log[num]+1)
line = input()
count  = 0

for i in range(3):
  if line[i] == '1':
    count += 1

return count

### FIXED CODE ###

line = input()
count  = 0

for i in range(3):
  if line[i] == '1':
    count += 1

print(count)