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

def main():
  import sys
  input = sys.stdin.readline
  h, w = map(int, input().split())
  A = []
  B = []
  for i in range(h):
    row = list(map(int, input().split()))
    A.append(row)
  for i in range(h):
    row = list(map(int, input().split()))
    B.append(row)
 
  dp = [[{} for j in range(w+1)] for i in range(h+1)]
  dp[0][0][abs(A[0][0] - B[0][0])] = 1
  for i in range(h):
    for j in range(w):
      for item in dp[i][j]:
        if j < w - 1:
          dif = abs(A[i][j+1] - B[i][j+1])
          dp[i][j+1][item+dif] = 1
          dp[i][j+1][abs(item-dif)] = 1
        if i < h - 1:
          dif = abs(A[i+1][j] - B[i+1][j])
          dp[i+1][j][item+dif] = 1
          dp[i+1][j][abs(item-dif)] = 1
  print(min(dp[h-1][w-1].keys()))
if __name__ == '__main__':
  main()


### FIXED CODE ###

import sys
def main():
  input = sys.stdin.readline
  h, w = map(int, input().split())
  A = []
  AB = []
  A_append = A.append
  AB_append = AB.append
  for i in range(h):
    row = list(map(int, input().split()))
    A_append(row)
  for i in range(h):
    row = [abs(A[i][j] - int(b)) for j, b in enumerate(input().split())]
    AB_append(row)
 
  dp_cur = [set([]) for _ in range(w)]
  dp_cur[0].add(AB[0][0])
  for i in range(h):
    dp_next = [set([]) for _ in range(w)]
    for j in range(w):
      if j < w - 1:
        add1 = dp_cur[j+1].add
        dif1 = AB[i][j+1]
      if i < h - 1:
        add2 = dp_next[j].add
        dif2 = AB[i+1][j]
      for item in dp_cur[j]:
        if j < w - 1:
          add1(item+dif1)
          add1(abs(item-dif1))
        if i < h - 1:
          add2(item+dif2)
          add2(abs(item-dif2))
    if i == h - 1:
      break
    dp_cur = dp_next
  print(min(dp_cur[w-1]))
if __name__ == '__main__':
  main()
### BUGGY CODE ###

from sys import stdin

num = int(input())

list2 = ["END"]
cur = list2.index("END")

for i in range(num):
	cmd = stdin.readline().strip().split()

	if cmd[0] == "0":
		#直前にxを挿入する.その要素を指す
#		if cur == 0:
#			list2.insert(0,cmd[1])
#			cur = 0
#		else:
		list2.insert(cur,cmd[1])
#		print("cur="+str(cur))

	elif cmd[0] == "1":
		#正の場合カーソルを＋移動、負の場合－移動
		cur += int(cmd[1])
#		print("cur="+str(cur))
	else:
		#該当の要素を削除。curは後ろを指す(curは移動しない！).無ければENDを指す
		tmp = cur
		list2.pop(cur)
		cur1 = list2.index("END")
		if tmp == cur1 - 1:
			cur = list2.index("END")
#		print("cur="+str(cur))
#	print(list2)

#print("----")
list2.remove("END")
print(*list2,sep='\n')



### FIXED CODE ###

from sys import stdin

class QueueNode(object):
	def __init__(self,data,next=None,prev=None):
		self.data = data
		self.next = next
		self.prev = prev

class LinkList(object):
	def __init__(self,head=None):
		self.head = head
		self.tail = head
		self.cur  = head

	def insert_q(self,data):
		node = QueueNode(data)

		if self.cur is None:
			self.head = node
			self.tail = node
			self.cur  = node
			return

		currentNode = self.cur
		preNode = currentNode.prev

		if currentNode.prev is None:
			currentNode.prev = node
			node.next = currentNode
			self.head = self.cur = node
		else:
			if self.tail is not None:
				currentNode.prev = node
				node.prev = preNode
				node.next = currentNode
				preNode.next = node
				self.cur = node
			else:
				currentNode.next = node
				node.prev = currentNode
				node.next = None
				self.cur = node
				self.tail = node


	def move_q(self,mv):
		currentNode = self.cur
		cnt = mv
		while cnt != 0:
			if mv < 0:#prev
				if currentNode.prev is None:
					self.head = self.cur = currentNode
					break
				else:
					currentNode = currentNode.prev
					self.cur = currentNode
					cnt += 1
			else:#next
				if currentNode.next is None:
					self.cur = currentNode
					break
				else:
					currentNode = currentNode.next
					self.cur = currentNode
					cnt -= 1


	#カレントを削除する
	def delete_q(self):
		currentNode = self.cur
		nexNode = currentNode.next
		preNode = currentNode.prev

		#自身の前がいない（=先頭）
		if preNode is None:
			nexNode.prev = None
			self.head = nexNode
			self.cur = nexNode
		#自身の後ろがいない（=末尾）
		elif nexNode is None:
			preNode.next = None
			self.tail = None
		else:
			preNode.next = currentNode.next
			nexNode.prev = currentNode.prev
			self.cur = currentNode.next

	#先頭を表示する
	def print_q(self):
		if self.head is not None:
			print(self.head.data)

	#全体表示（先頭から）
	def print_all(self):
		if self.head is not None:
			currentNode = self.head
			while currentNode.next is not None:
				print(currentNode.data)
				currentNode = currentNode.next

if __name__ == '__main__':

	loopnum = int(input())

	ll = LinkList()
	ll.insert_q("E")
	for i in range(loopnum):
		cmd = stdin.readline().strip().split()
		if cmd[0] == "0":
			t = int(cmd[1])
			ll.insert_q(t)
		elif cmd[0] == "1":
			t = int(cmd[1])
			ll.move_q(t)
		else:
			ll.delete_q()
	ll.print_all()
### BUGGY CODE ###

from collections import Counter
s=input()
n=len(s)
M=[0]*(n+1)
mod=2019
for i in range(n):
	M[n-1-i]=int(s[n-1-i:])%mod
MC=Counter(M)
r=0
for v in MC.values():
	r+=v*(v-1)//2
print(r)

### FIXED CODE ###

from collections import Counter
s=input()
n=len(s)
M=[0]
mod=2019
for i in range(n):
	m=(M[-1]+int(s[n-1-i])%mod*pow(10,i,mod))%mod
	M.append(m)
MC=Counter(M)
r=0
for v in MC.values():
	if v>1:
		r+=v*(v-1)//2
print(r)
### BUGGY CODE ###


import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)
# ----------

INF = float("inf")
MOD = 10 ** 9 + 7
# ----------

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

bits = [0] * 40

for i in range(N):
    for j in range(40):
        if A[i] >> j & 1:
            bits[j] += 1

pow2 = defaultdict(int)
for i in range(50):
    pow2[i] = pow(2, i)


ans = 0
for i in range(K+1):
    tmp = 0
    for j in range(40):
        bit_count = bits[j]
        if i >> j & 1:
            bit_count = N - bit_count
        tmp += pow2[j] * bit_count
    ans = max(ans, tmp)

print(ans)


### FIXED CODE ###

MAX_DIGIT = 50
SMALL = 1
EQUAL = 0

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

dp = [[-1 for _ in range(2)] for _ in range(100)]
dp[0][0] = 0

for d in range(MAX_DIGIT):
    mask = 1 << (MAX_DIGIT - d - 1)
    # A で元々 d 桁目にビットが立っているものの個数
    num = 0
    for i in range(N):
        if A[i] & mask:
            num += 1

    # X の d 桁目を 0, 1 にしたときのコスト
    cost0 = mask * num  # 元々の 1 の個数
    cost1 = mask * (N - num)  # 元々の 0 の個数(反転するから)

    # "K 未満 -> K 未満" の遷移
    if dp[d][SMALL] != -1:
        # 0 でも 1 でも自在に大きい方
        dp[d+1][SMALL] = max(dp[d+1][SMALL], dp[d][SMALL] + max(cost0, cost1))

    # "K ぴったり -> K 未満" の遷移
    if dp[d][0] != -1:
        if K & mask:
            # K の d 桁目が 1 だったら、X の d 桁目は 0 にする
            dp[d+1][SMALL] = max(dp[d+1][SMALL], dp[d][EQUAL] + cost0)

    # "K ぴったり -> K ぴったり" の遷移
    if dp[d][EQUAL] != -1:
        if K & mask:
            dp[d+1][EQUAL] = max(dp[d+1][EQUAL], dp[d][EQUAL] + cost1)
        else:
            dp[d+1][EQUAL] = max(dp[d+1][EQUAL], dp[d][EQUAL] + cost0)


ans = max(dp[MAX_DIGIT][EQUAL], dp[MAX_DIGIT][SMALL])
print(ans)
### BUGGY CODE ###

import heapq

n, m, s, t = map(int, input().split())

root1 = {}
root2 = {}
   
for i in range(m):
    u, v, a, b = map(int, input().split())
    root1[(u, v)] = a
    root2[(u, v)] = b

def edge(G, x):
    return([(b, G[(a, b)]) for (a, b) in G if a == x] + [(a, G[(a, b)]) for (a, b) in G if b == x])

def min_cost(G, start, end):
    S = [[0, start]]
    heapq.heapify(S)
    D = [float("inf")] * n
    D[start - 1] = 0
    while len(S) > 0:
        cost, site = heapq.heappop(S)
        if D[site - 1] > cost:
            D[site - 1] = cost
        for (site2, cost2) in edge(G, site):
            if D[site2 - 1] > cost + cost2:
                heapq.heappush(S, [cost + cost2, site2])
    return D[end - 1]

cost = []
for i in range(n):
    cost.append(min_cost(root1, s, i + 1) + min_cost(root2, i + 1, t))

for i in range(n):
    print(10 ** 15 - min(cost[i:]))

### FIXED CODE ###

import heapq

n, m, s, t = map(int, input().split())

root1 = []
for i in range(n):
    root1.append({})
root2 = []
for i in range(n):
    root2.append({})
   
for i in range(m):
    u, v, a, b = map(int, input().split())
    root1[u - 1][v] = a
    root1[v - 1][u] = a
    root2[u - 1][v] = b
    root2[v - 1][u] = b

def min_cost(root, start): # 経路の端点を１つ指定して任意の点への最小コストを計算
    S = [[0, start]]
    heapq.heapify(S)
    D = [float("inf")] * n
    D[start - 1] = 0
    while len(S) > 0:
        cost, site = heapq.heappop(S)
        if D[site - 1] < cost:
            continue
        for site2, cost2 in root[site - 1].items():
            if D[site2 - 1] > cost + cost2:
                D[site2 - 1] = cost + cost2
                heapq.heappush(S, [cost + cost2, site2])
    return D

jpy = min_cost(root1, s) # 円で両替地点まで移動する最小コスト
snuke = min_cost(root2, t) # 両替地点からスヌークで移動する最小コスト
cost = [jpy[i] + snuke[i] for i in range(n)] # 両替地点についてループ

minimum_cost = []
temp_min = cost[n - 1]
for i in reversed(range(n)):
    temp_min = min(temp_min, cost[i])
    minimum_cost.append(temp_min)

for i in reversed(range(n)):
    print(10 ** 15 - minimum_cost[i])
### BUGGY CODE ###

s=str(input())
se=[s]
n=len(s)
num=0
total=n*(n-1)//2 +1
for i in range(n):
  for j in range(i+1,n):
    if s[i]==s[j]:
      num+=1
print(total-num)

### FIXED CODE ###

s=str(input())
L=[0]*26
n=len(s)
for i in range(n):
  L[ord(s[i])-97]+=1
num=0
total=n*(n-1)//2 +1
for i in range(26):
  if L[i]>1:
    num+=L[i]*(L[i]-1)//2
print(total-num)
### BUGGY CODE ###

def insertion_sort(array):
    n = array[0]
    for i in range(1, len(array)):
        tmp = array[i]
        if array[i] <= n :
            break
        else:
            array[i-1] = tmp
            array[i] = n
            
    return array

n,m = (int(i) for i in input().split()) 
a = [int(i) for i in input().split()]
a.sort(reverse=True)
for i in range(m):
    down = a[0]
    a.remove(down)
    a.insert(0,down//2)
    a = insertion_sort(a)
    
print(sum(a))






### FIXED CODE ###

n,m = (int(i) for i in input().split()) 
a = [int(i) for i in input().split()]
b = []

a.sort(reverse=True)

for i in range(m):
    if i == 0:
        down = a[0]
        a.remove(down)
        b.append(down//2)
    else:
        if a != [] and a[0] >= b[0]:
            down = a[0]
            a.remove(down)
        else:
            down = b[0]
            b.remove(down)
        b.append(down//2)
    
print(sum(a)+sum(b))
### BUGGY CODE ###

n, m = (int(i) for i in input().split())  
a = [[int(i) for i in input().split()] for i in range(n)] 
lis = []

for x in a:
  lis += [x[0]] * x[1]

lis.sort()
print(sum(lis[:m]))

### FIXED CODE ###

n, m = (int(i) for i in input().split())  
a = [[int(i) for i in input().split()] for i in range(n)] 
dic = {}
lis = []

a.sort()
ans = 0
for x in a:
  if x[1] >= m:
    ans += x[0] * m
    break
  else:
    ans += x[0] * x[1]
    m -= x[1]

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

S = list(input())
N = len(S)
Aidxs = []
i = 0
while i < N:
  if S[i] == "A":
    Aidxs.append(i)
  i += 1
ans = 0
L = len(Aidxs)
i = 0
while i < L:
  idx = Aidxs[i]
  if "".join(S[idx:idx+3]) == "ABC":
    ans += 1
    S[idx] = "B"
    S[idx+1] = "C"
    S[idx+2] = "A"
    Aidxs[i] += 2
    i = max(0, i-2)
  else:
    i += 1
print(ans)

### FIXED CODE ###

S = input()
N = len(S)
ans = 0
cnt = 0
i = 0
while i < N:
  if S[i] == "A":
    cnt += 1
    i += 1
  elif "".join(S[i:i+2]) == "BC":
    ans += cnt
    i += 2
  else:
    cnt = 0
    i += 1
print(ans)
### BUGGY CODE ###

import sys

nCr_memo = {}

def solve(n, k):
    for i in range(k):
        i += 1
        ans = nCr(n - k + 1, i) * nCr(k - 1, i - 1)
        print  ans % (10**9 + 7)


def nCr(n, r):
    key = str(n) + '_' + str(r)
    if key in nCr_memo:
        return nCr_memo[key]

    a = 1
    b = 1
    for i in range(r):
        a *= (n - i)
        b *= (i + 1)

    nCr_memo[key] = a / b
    return nCr_memo[key]


if __name__ == '__main__':

    n, k = map(int, sys.stdin.readline().strip().split(" "))
    solve(n, k)

### FIXED CODE ###

import sys
 
nCr_memo = {}
 
def solve(n, k):
    for i in range(k):
        i += 1
        ans = nCr(n - k + 1, i) * nCr(k - 1, i - 1)
        print  ans % (10**9 + 7)
 
 
def nCr(n, r):
    key = str(n) + '_' + str(r)
    if key in nCr_memo:
        return nCr_memo[key]
 
    a = 1
    b = 1
    for i in range(r):
        a *= (n - i)
        b *= (i + 1)
 
    nCr_memo[key] = a / b
    return nCr_memo[key]
 
 
if __name__ == '__main__':
 
    n, k = map(int, sys.stdin.readline().strip().split(" "))
    solve(n, k)
### BUGGY CODE ###

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    ruiseki = [a[0]]
    for i in range(n-1):
        ruiseki.append(ruiseki[i]+a[i+1])
    ans = 0
    for i in range(n-1):
        if ruiseki[i] == 0:
            ans += 1
        for j in range(i+1, n):
            if ruiseki[j]-ruiseki[i] == 0:
                ans += 1
    if ruiseki[-1] == 0:
        ans += 1
    print(ans)
    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import numpy as np
import math
import collections
import fractions
import itertools

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    ruiseki = [0]
    ans = 0
    for i in range(n):
        ruiseki.append(ruiseki[i]+a[i])
    c = collections.Counter(ruiseki).values()
    for i in c:
        ans += i*(i-1)//2
    print(ans)
    return 0

if __name__ == "__main__":
    solve()
### BUGGY CODE ###

import itertools
N = int(input())
S = list(map(int, input()))
dic = dict()
ans = 0

for i in range(N - 2):
	for j in range(i + 1, N - 1):
		for k in range(j + 1, N):
			a = (S[i], S[j], S[k])
			if not a in dic:
				dic[a] = 1
				ans += 1
print(ans)

### FIXED CODE ###

import collections
N = int(input())
S = list(map(int, input()))
ans = 0
first = [0 for _ in range(10)]
lst = [[0 for _ in range(10)] for _ in range(10)]

for i in range(N):
	ima = 100
	if first[S[i]] == 0:
		first[S[i]] = 1
		ima = S[i]
	for j in range(10):
		if ima != j and first[j] == 1 and lst[j][S[i]] == 0:
			lst[j][S[i]] = 1
			ans += len(collections.Counter(S[i + 1:]))
				
				
print(ans)
### BUGGY CODE ###

k=int(input())
ans=0
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

def gcdlist(l):
    a = l[0]
    for i in range(len(l)):
        a = gcd(a,l[i])
    return a
sumlis={}
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            lis=sorted([a,b,c])
            if a==b==c:
                ans+=a
            elif a==1 or b==1 or c==1:
                ans+=1
            elif lis in sumlis.values(): 
                ans+=sumlis[lis]
            else:
                x=gcdlist(lis)
                sumlis[x]=sumlis
                ans+=x
                
print(ans)

### FIXED CODE ###

k=int(input())
ans=0
import math
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

def gcdlist(l):
    a = l[0]
    for i in range(len(l)):
        a = gcd(a,l[i])
    return a

sumlis={}
for a in range(1,k+1):
    for b in range(1,k+1):
        t=math.gcd(a,b)
        for c in range(1,k+1):
            ans+=math.gcd(t,c)
                
print(ans)
### BUGGY CODE ###

import sys
import os
import itertools

n = int(input())

def is_prime(n):
    for p in range(2, n):
        if n % p == 0:
            return 0
    return 1

a = is_prime(n)
if a == 1:
    print(n-1)
    sys.exit()

l = []
for i in range(2, n):
    for j in range(2, n):
        if i*j == n:
            l.append((i-1)+(j-1))
        else:
            continue

print(min(l))

### FIXED CODE ###

import sys
import os
import itertools

n = int(input())

def make_divisors(n):
    divisors = {}
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors[i] = n//i
            if i != n // i:
                divisors[i] = n//i

    return divisors

ans = make_divisors(n)
m = max(ans)
print( (m-1) + ans[m]-1)
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split()]

like = []
cnt = 0
for i in range(N):
    s = set([A[i], i+1])
    if s in like:
        cnt+=1
    else:
        like.append(s)
print(cnt)


### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]

like = []
cnt = 0
for i in range(N):
    if A[A[i]-1] == i+1:
        cnt+=1
print(cnt//2)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

# D - Triangles
def binary_search(i, j):
	global N

	left = j
	right = N
	
	while right - left > 1:
		mid = (left + right) // 2
		
		if is_match(mid, i, j):
			left = mid
		else:
			right = mid
	
	return left
		

def is_match(mid, i, j):
	global L
	
	a = L[i]
	b = L[j]
	c = L[mid]
	
	if b < c + a and c < a + b:
		return True
	else:
		return False


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

ans = 0

for i in range(N - 2):
	for j in range(i + 1, N - 1):
		k = binary_search(i, j)
		
		if k > j and k < N:
			ans += k - j
			
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

# D - Triangles
def binary_search(i, j):
	global N

	left = j
	right = N
	
	while right - left > 1:
		mid = (left + right) // 2
		
		if is_match(mid, i, j):
			left = mid
		else:
			right = mid
	
	return left
		

def is_match(mid, i, j):
	global L
	
	a = L[i]
	b = L[j]
	c = L[mid]
	
	if b < c + a and c < a + b:
		return True
	else:
		return False


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

ans = 0

for i in range(N - 2):
	for j in range(i + 1, N - 1):
		k = binary_search(i, j)
		
		if k > j and k < N:
			ans += k - j
			
print(ans)
### BUGGY CODE ###

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

cnt = [float('inf')]*n
cnt[0], cnt[1] = 0, abs(h[0]-h[1])
for i in range(2, n):
    l = [abs(h[m]-h[i])+cnt[m] for m in range(max(0,i-k),i)]
    cnt[i] = min(l)
print(cnt[n-1])


### FIXED CODE ###

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

cnt = [0]*n
for i in range(1, n):
    j = max(0,i-k)
    cnt[i] = min(abs(h[m]-h[i])+cnt[m] for m in range(j,i))
print(cnt[n-1])
### BUGGY CODE ###

N,M=map(int, input().split())
l = [0] * M
r = [0] * M
for i in range(M):
  l[i], r[i] = map(int, input().split())
a=0
for i in range(1,N+1):
  flag=0
  for j in range(M):
    if i<l[j] or i>r[j]:
      flag=1
  if flag==0:
    a+=1
print(a)   

### FIXED CODE ###

n,m=map(int,input().split())
x=1;y=n
for _ in range(m):
  l,r=map(int,input().split())
  if x<l:
    x=l
  if y>r:
    y=r
print(max(y-x+1,0))
### BUGGY CODE ###

#xorの性質
#AxorA=0、交換法則、結合法則が成立、bitごとに独立して考える！
n=int(input())
a=list(map(int,input().split()))
res=0
for j in range(60):
  s=0 #1の数
  for i in a:
    if (i>>j & 0b1)==0b1:
      s+=1
  r=2**j*(n-s)*s
  res=(res+r)%(10**9+7)
print(res)

### FIXED CODE ###

#xorの性質
#AxorA=0、交換法則、結合法則が成立、bitごとに独立して考える！

import numpy as np

n=int(input())
a=np.array(list(map(int,input().split())))
res=0
for j in range(60):
  s=0 #1の数
  """
  for i in a:
    if (i>>j & 0b1)==0b1:
      s+=1
  """
  s=np.count_nonzero(a>>j&1)
  r=2**j*(n-s)*s
  res=(res+r)%(10**9+7)
print(res)
### BUGGY CODE ###

mod = 998244353
def comb(n, r):
    if n < r:return 0
    if n < 0 or r < 0:return 0
    return fa[n] * fi[r] % mod * fi[n - r] % mod
n, k = map(int, input().split())
fa = [1] * (k + 1)
fi = [1] * (k + 1)
for i in range(1, k + 1):
    fa[i] = fa[i - 1] * i % mod
    fi[i] = pow(fa[i], mod - 2, mod)
ans = 0
for i in range(k - n + 1):
    ans += comb(k - 1, n + i - 1)
    ans %= mod
print(ans)

### FIXED CODE ###

mod = 998244353
def comb(n, r):
    if n < r:return 0
    if n < 0 or r < 0:return 0
    return fa[n] * fi[r] % mod * fi[n - r] % mod
n, k = map(int, input().split())
fa = [1] * (k + 1)
fi = [1] * (k + 1)
for i in range(1, k + 1):
    fa[i] = fa[i - 1] * i % mod
    fi[i] = pow(fa[i], mod - 2, mod)
ans = 0
for i in range(k - n + 1):
    ans += comb(k - 1, n + i - 1)
    ans %= mod
print(ans)
### BUGGY CODE ###

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

cnt = {}

for a in A:
    if a not in cnt:
        cnt[a] = 0
    cnt[a] += 1

cnt = sorted(cnt.items(), key=lambda x: x[1])
ans = 0

while len(cnt) > K:
    ans += cnt[0][1]
    cnt = cnt[1:]

print(ans)


### FIXED CODE ###

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

cnt = {}

for a in A:
    if a not in cnt:
        cnt[a] = 0
    cnt[a] += 1

cnt = sorted(cnt.items(), key=lambda x: x[1])
ans = 0

for i in range(len(cnt)):
    if len(cnt) - i <= K:
        break
    ans += cnt[i][1]

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

import statistics
import copy

n = int(input())
a = list(map(int, input().split()))
ao = copy.copy(a)
for i in range(n):
    a.pop(i)
    print(statistics.median(a))
    a = copy.copy(ao)


### FIXED CODE ###

import statistics

n = int(input())
x = list(map(int, input().split()))
xmd = statistics.median(x)
xs = sorted(x)
for i in x:
    if i < xmd:
        print(xs[n // 2])
    else:
        print(xs[n // 2 - 1])
### BUGGY CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,Q = inpl()

lines = defaultdict(set)
for _ in range(N-1):
    a,b = inpl()
    a,b = a-1,b-1
    lines[a].add(b)

adds = [0]*N
for _ in range(Q):
    p,x = inpl()
    adds[p-1] += x

ans = [0]*N

q = queue.LifoQueue()
q.put([0,0])

while not q.empty():
    x,cnt = q.get()
    cnt += adds[x]
    ans[x] += cnt
    for t in lines[x]:
        q.put([t,cnt])

print(' '.join(map(str,ans)))


### FIXED CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,Q = inpl()

lines = defaultdict(set)
for _ in range(N-1):
    a,b = inpl()
    a,b = a-1,b-1
    lines[a].add(b)
    lines[b].add(a)

adds = [0]*N
for _ in range(Q):
    p,x = inpl()
    adds[p-1] += x

visited = [False]*N
ans = [0]*N

q = queue.LifoQueue()
q.put([0,0])

while not q.empty():
    x,cnt = q.get()
    visited[x] = True
    cnt += adds[x]
    ans[x] += cnt
    for t in lines[x]:
        if not visited[t]:
            q.put([t,cnt])

print(' '.join(map(str,ans)))
### BUGGY CODE ###

n,m = map(int,input().split())
A = [int(i) for i in input().split()]

A.sort(reverse=True)

def bisect(A,x):
  lo = -1
  hi = len(A)
  while lo+1 < hi:
    idx = (lo+hi)//2
    if A[idx] > x:
      lo = idx
    else:
      hi = idx
  return lo

for i in range(m):
  v = A.pop(0)//2
  idx = bisect(A,v)+1
  A = A[:idx] + [v] + A[idx:]

print(sum(A))

### FIXED CODE ###

from heapq import heappop, heappush, heapify
n, m = map(int, input().split())
a = [-int(i) for i in input().split()]

heapify(a)
for _ in range(m):
  l = heappop(a)
  heappush(a, -((-l)//2))

print(-sum(a))
### BUGGY CODE ###

K = int(input())
if K % 2 == 0 :
    print('-1')
elif K % 5 == 0 :
    print('-1')
else:
    n = 0
    for i in range(1000000):
        n = n * 10 + 7
        if n % K == 0:
            print(i+1)
            break
    else:
        print('-1')


### FIXED CODE ###

K = int(input())
if K % 2 == 0:
    print(-1)
elif K % 5 == 0:
    print(-1)
else:
    S = 7
    for i in range(K+1):
        if S % K == 0:
            print(i+1)
            break
        else:
            S = S % K
            S = S * 10 + 7
    else:
        print(-1)
### BUGGY CODE ###

N, M = map(int, input().split())
AB = list(list(map(int, input().split())) for _ in range(M))

AB_sorted = sorted(AB, key=lambda x : x[1])

removed_bridge = []
for ab in AB_sorted:
    for bridge in removed_bridge:
        if ab[0] < bridge < ab[1]:
            break
    else:
        removed_bridge.append(ab[1] - 0.5)

print(len(removed_bridge))

### FIXED CODE ###

N, M = map(int, input().split())
AB = list(list(map(int, input().split())) for _ in range(M))

AB_sorted = sorted(AB, key=lambda x : x[1])

removed_bridge = []
for ab in AB_sorted:
    if removed_bridge:
        if ab[0] < removed_bridge[-1] < ab[1]:
            continue
    removed_bridge.append(ab[1] - 0.5)

print(len(removed_bridge))