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

import collections

N,M = map(int,input().split())
L = [[False for j in range(N)] for i in range(N)]

for i in range(M) :
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    L[a][b] = True

dp = [0 for i in range(N)]

for i in range(N) :
    q = collections.deque()
    q.append(i)
    dist = [0 for i in range(N)]
    while q :
        now = q.pop()
        for j in range(N) :
            if not L[now][j] :
                continue
            dist[j] = max(dist[j], dist[now]+1)
            if j < i :
                dp[i] = max(dp[i], dist[j] + dp[j])
            else :
                q.append(j)
    dp[i] = max(dp[i], max(dist))

ans = max(dp)
print(ans)

    

### FIXED CODE ###

N,M = map(int,input().split())
L = [list(map(int,input().split())) for i in range(M)]

L_minus = [[] for i in range(N)]
L_plus = [0 for i in range(N)]

dp = [0 for i in range(N)]

for i in range(M) :
    x,y = L[i]
    x -= 1
    y -= 1
    L_plus[y] += 1
    L_minus[x].append(y)

A = []

for i in range(N) :
    if L_plus[i] == 0 :
        A.append(i)

while A :
    x = A.pop()
    
    for y in L_minus[x] :
        L_plus[y] -= 1
        if L_plus[y] == 0 :
            A.append(y)
        dp[y] = max(dp[y], dp[x]+1)

ans = max(dp)

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

#!/usr/bin/env python3
s = input()
ans = [0] * len(s)
for i in range(len(s)):
    if s[i] == "R":
        L = s[i:].index("L")
        ans[L + i - L % 2] += 1
    else:
        R = s[:i + 1][::-1].index("R")
        ans[i - R + R % 2] += 1

print(*ans)


### FIXED CODE ###

#!/usr/bin/env python3
s = input()
ans = [0] * len(s)
R = 0
L = 0
for i in range(len(s)):
    if s[i] == "R":
        R += 1
    else:
        ans[i] += R // 2
        ans[i - 1] += -(-R // 2)
        R = 0
    if s[-i - 1] == "L":
        L += 1
    else:
        ans[-i - 1] += L // 2
        ans[-i] += -(-L // 2)
        L = 0

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

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

def main():
    N = int(input())
    #s = x+ y+ z
    ret =[0]*(N+1)
    for n in range(1,N+1):
        for s in range(3,int(N**0.5)+3):
            for z in range(1,s+1):
                for y in range(1,s-z+1):
                    x = s - z - y
                    if s**2==n + x*y+y*z+z*x:
                        if x>=1 and y>=1 and z>=1:
                            ret[n]+=1
    for a in ret[1:]:
        print(a)

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

def main():
    N = int(input())
    #s = x+ y+ z
    ret =[0]*(N+1)
    for x in range(1,100):
        for y in range(1,100):
            for z in range(1,100):
                n = x**2+y**2+z**2+x*y+y*z+z*x
                if n<=N:
                    ret[n] += 1
    for i in ret[1:N+1]:
        print(i)

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

def main():
    A, B, C, D = list(map(int, input().split()))
    mod = 998244353
    dp = [[0] * (D + 1) for _ in range(C + 1)]
    dp[A][B] = 1
    for b in range(B + 1, D + 1):
        dp[A][b] = dp[A][b - 1] * A
    for a in range(A + 1, C + 1):
        dp[a][B] = dp[a - 1][B] * B % mod
        for b in range(B + 1, D + 1):
            dp[a][b] = (dp[a - 1][b] * b + dp[a][b - 1] * a - dp[a - 1][b - 1] * (a - 1) * (b - 1)) % mod

    return dp[C][D]

print(main())


### FIXED CODE ###

def main():
    A, B, C, D = list(map(int, input().split()))
    mod = 998244353
    u = [0] * (D + 1)
    v = [0] * (D + 1)
    u[B] = 1
    for b in range(B + 1, D + 1):
        u[b] = u[b - 1] * A
    for a in range(A + 1, C + 1):
        v[B] = u[B] * B % mod
        for b in range(B + 1, D + 1):
            v[b] = (u[b] * b + v[b - 1] * a - u[b - 1] * (a - 1) * (b - 1)) % mod
        u, v = v, u

    return u[D]

print(main())
### BUGGY CODE ###

from collections import defaultdict
import math
N=int(input())

div_dic=defaultdict(int)
def add_fact(x):
  for i in range(1,int(x**0.5)+1):
    if x%i==0:
      div_dic[i]+=1
      if i!=x//i:
        div_dic[x//i]+=1
  return

alist=[]
int_list=[]
for _ in range(N):
  a=input()
  if "." in a:
    seisu,shosu=a.split(".")
    seisu=int(seisu)
    shosu=int(shosu.ljust(9,'0'))
    
    bunshi=10**9*seisu+shosu
    bumbo=10**9
    gcd_bb=math.gcd(bunshi,bumbo)
    bunshi//=gcd_bb
    bumbo//=gcd_bb
    
    if bumbo==1:
      int_list.append(bunshi)
      add_fact(bunshi)
    else:
      alist.append((bunshi,bumbo))
  else:
    seisu=int(a)
    int_list.append(seisu)
    add_fact(seisu)
#print(int_list,alist,div_dic)

num_int=len(int_list)
answer=num_int*(num_int-1)//2
for bunshi,bumbo in alist:
  answer+=div_dic[bumbo]

#shosudoshi
def set_fact(x):
  ret={x}
  for i in range(2,int(x**0.5)+1):
    if x%i==0:
      ret.add(i)
      ret.add(x//i)
  return ret

#print(alist)
div_dic2=defaultdict(int)
for bunshi,bumbo in alist:
  div_set=set_fact(bunshi)  
  for d in div_set:    
    answer+=div_dic2[(bumbo,d)]
    
  for d in div_set:    
    div_dic2[(d,bumbo)]+=1
#print(div_dic2)
  
print(answer)

### FIXED CODE ###

from collections import defaultdict
N=int(input())

def pow25(x):
  f2=f5=0
  while x%2==0:
    x//=2
    f2+=1
  while x%5==0:
    x//=5
    f5+=1
  return f2,f5

pow25_dic=defaultdict(int)
for _ in range(N):
  a=input()
  if "." in a:
    seisu,shosu=a.split(".")
    seisu=int(seisu)
    shosu=int(shosu.ljust(9,'0'))    
    bunshi=10**9*seisu+shosu
  else:
    bunshi=10**9*int(a)
    
  pow25_dic[pow25(bunshi)]+=1
#print(pow25_dic)

pow25_key_list=[]
for key in pow25_dic:
  pow25_key_list.append(key)
#print(pow25_key_list)

answer=0
for i in range(len(pow25_key_list)):
  f2,f5=pow25_key_list[i]
  value=pow25_dic[(f2,f5)]
  if f2>=9 and f5>=9:    
    answer+=value*(value-1)//2
    
  for j in range(i+1,len(pow25_key_list)):
    f2_2,f5_2=pow25_key_list[j]
    if f2+f2_2>=18 and f5+f5_2>=18:
      value2=pow25_dic[(f2_2,f5_2)]
      answer+=value*value2
      
print(answer)
### BUGGY CODE ###

import math
a, b, q = map(int, input().split())
s = [-float("inf")] + [int(input()) for _ in range(a)] + [float("inf")]
t = [-float("inf")] + [int(input()) for _ in range(b)] + [float("inf")]

s.sort()
t.sort()

def near(x, buildings):
    left, right = 0, len(buildings) - 1

    while right - left > 1:
        center = (left + right) // 2
        value = buildings[center]
        if x < value:
            right = center
        elif x > value:
            left = center
        else:
            return center
    return left if abs(x - buildings[left]) < abs(x - buildings[right]) else right


for _ in range(q):
    x = int(input())

    si = near(x, s)
    spos = [si, si + 1] if s[si] < x else [si, si - 1]
    ti = near(x, t)
    tpos = [ti, ti + 1] if t[ti] < x else [ti, ti - 1]

    result = float("inf")
    for sindex in spos:
        for tindex in tpos:
            v1 = abs(x - s[sindex]) + abs(s[sindex] - t[tindex])
            v2 = abs(x - t[tindex]) + abs(t[tindex] - s[sindex])
            result = min(
                float("inf") if math.isnan(v1) else v1,
                float("inf") if math.isnan(v2) else v2,
                result
            )

    print(result)


### FIXED CODE ###

import bisect
import math
a, b, q = map(int, input().split())
inf = float("inf")
s = [-inf] + [int(input()) for _ in range(a)] + [inf]
t = [-inf] + [int(input()) for _ in range(b)] + [inf]

results = ""
for _ in range(q):
    x = int(input())
    si = bisect.bisect_right(s, x)
    spos = [s[si], s[si - 1]]

    ti = bisect.bisect_right(t, x)
    tpos = [t[ti], t[ti - 1]]

    result = float("inf")
    for svalue in spos:
        for tvalue in tpos:
            if svalue == tvalue == inf or svalue == tvalue == -inf:
                continue
            result = min(
                abs(x - svalue) + abs(svalue - tvalue),
                abs(x - tvalue) + abs(tvalue - svalue),
                result
            )

    results += str(result) + "\n"
print(results)
### BUGGY CODE ###

import math
import fractions
a,b = map(int,input().split())
ans = 1
now = fractions.gcd(a,b)
for num in range(2,fractions.gcd(a,b)+1):
  if num > now:
    break
  if now % num == 0:
    ans += 1
    while now % num == 0:
      now = now//num
print(ans)

### FIXED CODE ###

import fractions
a,b = map(int,input().split())
c = fractions.gcd(a,b)

ans = [1]
while c % 2 == 0:
  ans.append(2)
  c //= 2
i = 3
while c >= i ** 2:
  if c % i == 0:
    ans.append(i)
    c //= i
  else:
    i += 2
if c != 1:
  ans.append(c)
print(len(set(ans)))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from scipy.sparse.csgraph import dijkstra

N, M = map(int, input().split())
NN = [[0] * N for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    NN[a-1][b-1] = 1
    NN[b-1][a-1] = 1

d = dijkstra(NN, directed = False, indices = 0)
    
if d[N-1] >= 3:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys

N, M = map(int, input().split())
s = []
g = []
for i in range(M):
    a, b = map(int, input().split())
    if a == 1 and b == N:
        print("POSSIBLE")
        sys.exit()
    if a == 1:
        s.append(b)
    elif b == N:
        g.append(a)

if len(set(s) & set(g)) != 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

n=int(input())
wordlist=[input() for i in range(n)]
sortlist=[]
for i in range(n):
    a=list(wordlist[i])
    a.sort()
    a="".join(a)
    sortlist.append(a)
    
def kaijyo(n):
    ans=1
    for i in range(1,n+1):
        ans*=i
    return ans

count=0
sortlist.sort()


while sortlist:
    a=sortlist.pop()
    times=sortlist.count(a)+1
    for i in range(times-1):
        sortlist.pop()
    b=1
    for i in range(2):
        b*=(times-i)
    b=int(b/2)
    count+=b
    
print(int(count) )   

### FIXED CODE ###

n=int(input())

#単語が全て入ったリストを作るO(n)
wordlist=[input() for i in range(n)]

#wordlistを一つ一つソートさせたものをsortlistとして作るO（n）
sortlist=[]
for i in range(n):
    a=list(wordlist[i])
    a.sort()
    sortlist.append(a)
    
count=0

#ソートリストをソートするO(nlogn)
sortlist.sort()

checkword=""
check=0

for i in range(n): #O(n)
    a=sortlist.pop()
    if checkword==a:
            check+=1
            count+=check
    else:
        check=0
        checkword=a
    
print(int(count) )
### BUGGY CODE ###

MOD = 10**9 + 7
r1,c1,r2,c2 = map(int,input().split())

n = 2000100
fact = [1]*(n+1)
inv = [1]*(n+1)
ifact = [1]*(n+1)
for i in range(1,n+1):
    fact[i] = fact[i-1]*i % MOD
    inv[i] = pow(i,MOD-2,MOD)
    ifact[i] = ifact[i-1]*inv[i] % MOD

def nCr(n,r):
    return fact[n] * ifact[r] * ifact[n-r] % MOD

def f(r,c):
    temp = [nCr(k,c) for k in range(c+1,r+c+2)]
    return sum(temp) % MOD
    
print((f(r2,c2) - f(r2,c1-1) - f(r1-1,c2) + f(r1-1,c1-1)) % MOD)


### FIXED CODE ###

MOD = 10**9 + 7
r1,c1,r2,c2 = map(int,input().split())

n = 2000100
fact = [1]*(n+1)
inv = [1]*(n+1)
ifact = [1]*(n+1)
for i in range(1,n+1):
    fact[i] = fact[i-1]*i % MOD
    inv[i] = pow(i,MOD-2,MOD)
    ifact[i] = ifact[i-1]*inv[i] % MOD

def nCr(n,r):
    return fact[n] * ifact[r] * ifact[n-r] % MOD

def f(r,c):
    return nCr(r+c+2,c+1)-1
    
print((f(r2,c2) - f(r2,c1-1) - f(r1-1,c2) + f(r1-1,c1-1)) % MOD)
### BUGGY CODE ###

import sys
n = int(input())
s = list(input())
a_li = []
b_li = []
c_li = []
for i,ss in enumerate(s):
    if ss == 'R':
        a_li.append(i+1)
    elif ss == 'G':
        b_li.append(i+1)
    else:
        c_li.append(i+1)
if len(a_li) == 0 or len(b_li)== 0 or len(c_li) == 0:
    print(0)
    sys.exit()
#all_count = 0
""" for a in a_li:
    for b in b_li:
        tmp = len(c_li)
        if (2*b - a)  in c_li:
            #lili.append(2*b - a)
            tmp -= 1
        if (2*a - b)  in c_li:
            #lili.append(2*a - b)
            tmp -= 1
        if (a + b)% 2 == 0 and (a + b)//2   in c_li:
            #lili.append((a + b)//2)
            tmp -= 1
        #tmp -= len(set(lili))
        all_count += tmp
print(all_count) """

#print(a_li,b_li,c_li)
all_count = 0
for i in range(1,n-1):
    for j in range(i+1,n):
        for k in range(j+1,n+1):
            if j-i == k-j:
                continue
            else:
                if i in a_li and j in b_li and k in c_li:
                    all_count += 1
                if i in a_li and j in c_li and k in b_li:
                    all_count += 1
                if i in b_li and j in a_li and k in c_li:
                    all_count += 1
                if i in b_li and j in c_li and k in a_li:
                    all_count += 1
                if i in c_li and j in a_li and k in b_li:
                    all_count += 1
                if i in c_li and j in b_li and k in a_li:
                    all_count += 1
print(all_count)

### FIXED CODE ###

n = int(input())
s = list(input())
a_li = []
b_li = []
c_li = []
for i,ss in enumerate(s):
    if ss == 'R':
        a_li.append(i+1)
    elif ss == 'G':
        b_li.append(i+1)
    else:
        c_li.append(i+1)
count = 0
for i in range(1,n+1):
    for d in range(1,n):
        if i + 2*d > n:
            break
        if s[i-1] != s[i+d-1] and s[i+d-1] != s[i+2*d-1] and s[i-1] != s[i+2*d-1]:
            count += 1
#print(len(a_li),len(b_li),len(c_li),count)
#print(count)
print(len(a_li)*len(b_li)*len(c_li)-count)
### BUGGY CODE ###

N = int(input())
S = input()
result = 3*10**5
for i in range(0, N):
    count = 0
    for index, s in enumerate(S):
        if index == i:
            continue
        if index < i and s == "W":
            count += 1
        if index > i and s == "E":
            count += 1

    if result > count:
        result = count
print(result)

### FIXED CODE ###

N = int(input())
S = input()
ws = [0]*N
w_c = 0
for i in range(0, N):
    if S[i] == "W":
        w_c += 1
    ws[i] += w_c
es = [0]*N
e_c = 0
for i in reversed(range(0, N)):
    if S[i] == "E":
        e_c += 1
    es[i] += e_c
res = 3*10**5
for i in range(0, N):
    if i - 1 == 0:
        if es[0] < res:
            res = es[1]
        continue
    if i + 1 == N:
        if ws[i] < res:
            res = ws[i-1]
        continue
    t = ws[i-1] + es[i+1]
    if t < res:
        res = t
print(res)
### BUGGY CODE ###

from bisect import bisect
N,M = map(int, input().split())
a = list(map(int, input().split()))
for _ in range(M):
    a.sort()
    b,c = map(int, input().split())
    idx = bisect(a, c)
    if idx == 0:
        continue
    a[:min(idx, b)] = [c]*min(idx,b)

print(sum(a))


### FIXED CODE ###

from bisect import bisect
from collections import deque

N,M = map(int, input().split())
a = list(map(int, input().split()))
bc = []
for _ in range(M):
    b,c = map(int, input().split())
    bc.append((c,b))

bc.sort(key=lambda x:x[0], reverse=True)
bc = deque(bc)
a.sort()
ans = 0
for ai in a:
    if bc==deque([]):
        ans += ai
        continue
    c,b = bc[0]
    if ai<c:
        ans += c
        if b-1==0:
            bc.popleft()
            continue
        bc[0] = (c,b-1)
    else:
        ans += ai
# print(bc)
print(ans)
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
  A.append(input())

max_itr = [i for i, v in enumerate(A) if v == max(A)]
max_number = max(A)
for i in range(N):
  if i not in max_itr:
    print(max_number)
  else:
    print(sorted(A)[-2])

### FIXED CODE ###

import numpy as np
N = int(input())
A = []
for i in range(N):
  A.append(int(input()))

npA = np.array(A)
max_number = max(A)
max_itr = np.where(npA == npA.max())
if len(max_itr[0]) == 1:
  for i in range(N):
    if i != max_itr[0][0]:
      print(max_number)
    else:
      print(sorted(A)[-2])
else:
  for i in range(N):
    print(max_number)
### BUGGY CODE ###

N = int(input())
*p,= map(float,input().split())
dp = [[0]*(N+1) for _ in range(N+1)]
dp[0][0] = 1

for i in range(N):
	dp[i+1][0] = dp[i][0]*(1-p[i])
	
for i in range(N):
	for h in range(N):
		dp[i+1][h+1] = dp[i][h+1]*(1-p[i]) + dp[i][h]*p[i]

print(sum(dp[-1][N//2+1:]))

### FIXED CODE ###

N = int(input())
*p,= map(float,input().split())
dp = [[0]*(N+1) for _ in range(N+1)]
dp[0][0] = 1

for i in range(N):
	dp[i+1][0] = dp[i][0]*(1-p[i])
	
for i in range(N):
	for h in range(N):
		dp[i+1][h+1] = dp[i][h+1]*(1-p[i]) + dp[i][h]*p[i]

print(sum(dp[-1][N//2+1:]))
### BUGGY CODE ###

N,X=map(int,input().split())
x=list(map(lambda x: abs(int(x)-X), input().split()))

for i in range(min(x),0,-1):
  flag = 0
  for j in x:
    if j%i != 0:
      flag = 1
      break
  if flag == 0:
    print(i)
    break

### FIXED CODE ###

import fractions
N,X=map(int,input().split())
x=list(map(lambda x: abs(int(x)-X), input().split()))
x_min=min(x)
g_min=x_min
for i in x:
  g=fractions.gcd(g_min,i)
  if g < g_min:
    g_min = g
print(g_min)
### BUGGY CODE ###

n=int(input())
a=list(map(int, input().split()))
is_yes = True
for i, a_i in enumerate(a):
  for j, a_j in enumerate(a[i+1:]):
    if a_i == a_j:
      is_yes = False
      break
if is_yes:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

n=int(input())
a=list(map(int, input().split()))
is_yes = True
a_m = {}
for a_i in a:
  if a_i in a_m:
    is_yes = False
    break
  a_m[a_i]=True
if is_yes:
  print("YES")
else:
  print("NO")
### BUGGY CODE ###

#coding:utf-8
n,m = list(map(int,input().split()))
def divisor(n,m):
    num = m//n
    arr = []
    for i in range(1,num+1):
        if m % i == 0:
            arr.append(i)
    return arr
print (max(divisor(n,m)))


### FIXED CODE ###

#coding:utf-8
import numpy as np
def divisor(n,m):
    arr = []
    for i in range(1,(int(np.sqrt(m))+1)):
        if m % i == 0:
            if i <= m/n:
                arr.append(i)
            if m/i <= m/n:
                arr.append(int(m/i))
    return arr



n,m = list(map(int,input().split()))
print (max(divisor(n,m)))
### BUGGY CODE ###

N = int(input())
p = list(map(float, input().split()))

dp = [[0 for i in range(N+1)] for j in range(N+1)]
dp[0][0] = 1

for i in range(1,N+1):
  for j in range(N+1):
    if j == 0:
      dp[j][i] = (1-p[i-1])*dp[j][i-1]
    else:
      dp[j][i] = (1-p[i-1])*dp[j][i-1] + p[i-1]*dp[j-1][i-1]

sum_ = 0
for i in range(N//2+1, N+1):
  sum_ += dp[i][-1]

print(sum_)

### FIXED CODE ###

N = int(input())
p = list(map(float, input().split()))

dp = [[0 for i in range(N+1)] for j in range(N+1)]
dp[0][0] = 1

for i in range(1,N+1):
  for j in range(i+1):
    if j == 0:
      dp[j][i] = (1-p[i-1])*dp[j][i-1]
    else:
      dp[j][i] = (1-p[i-1])*dp[j][i-1] + p[i-1]*dp[j-1][i-1]

sum_ = 0
for i in range(N//2+1, N+1):
  sum_ += dp[i][-1]

print(sum_)
### BUGGY CODE ###

import sys
from fractions import gcd

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

K = int(read())
ans = 0

for a in range(K):
    for b in range(K):
        for c in range(K):
            ans += gcd(a+1,gcd(b+1,c+1))

print(ans)

### FIXED CODE ###

import sys
from fractions import gcd

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

K = int(read())
ans = 0

gcd_list = [[0]*210 for i in range(210)]
num_ct = [0]*210

for a in range(K):
    for b in range(K):
        tmp = gcd(a+1,b+1)
        gcd_list[a+1][b+1] = tmp
        num_ct[tmp] += 1

for c in range(K):
    for tmp in range(K):
        ans += gcd_list[c+1][tmp+1] * num_ct[tmp+1]

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

#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,k = inm()
dt = []
for i in range(n):
    t,d = inm()
    dt.append((d,t))
dt.sort(reverse=True)
a = dt[:k] # oisisa max, ignore variety

vals = [z[0] for z in a]
dsum = sum(vals)
typs = set([z[1] for z in a])
ntyp = len(typs)
mx = dsum+ntyp**2 # satisfy for a

b = dt[k:]
h = {}
for d,t in b:
    if t in typs:
        continue
    elif t not in h:
        h[t] = d
    else:
        h[t] = max(h[t],d)
c = [h[t] for t in h]
c.sort(reverse=True)
# for types not in a, max oisisa

h = {}
for d,t in a:
    if t not in h:
        h[t] = d
    else:
        h[t] = max(h[t],d)
for t in h:
    vals.remove(h[t])
vals.sort()
# oisisa list for second or below for each type

for i in range(min(len(vals),len(c))):
    dsum += c[i]-vals[i]
    ntyp += 1
    mx = max(mx,dsum+ntyp**2)
print(mx)


### FIXED CODE ###

#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,k = inm()
dt = []
for i in range(n):
    t,d = inm()
    dt.append((d,t))
dt.sort(reverse=True)
a = dt[:k] # oisisa max, ignore variety

vals = [z[0] for z in a]
dsum = sum(vals)
typs = set([z[1] for z in a])
ntyp = len(typs)
mx = dsum+ntyp**2 # satisfy for a

b = dt[k:]
h = {}
for d,t in b:
    if t in typs:
        continue
    elif t not in h:
        h[t] = d
    else:
        h[t] = max(h[t],d)
c = [h[t] for t in h]
c.sort(reverse=True)
# for types not in a, max oisisa

h = {}
for d,t in a:
    if t not in h:
        h[t] = d
    else:
        h[t] = max(h[t],d)
vals = []
for d,t in a:
    if t in h and d==h[t]:
        del h[t]
    else:
        vals.append(d)
vals.sort()
# oisisa list for second or below for each type

for i in range(min(len(vals),len(c))):
    dsum += c[i]-vals[i]
    ntyp += 1
    mx = max(mx,dsum+ntyp**2)
print(mx)
### BUGGY CODE ###

S = input()
A = []
B = [0]*2019
B[0]+=1

for i in range(len(S)):
    A.append(int(S[-i-1:])%2019)
    B[int(S[-i-1:])%2019]+=1

ans=0

for j in range(len(B)):
    ans+=(B[j]-1)*B[j]/2

print(int(ans))

### FIXED CODE ###

from collections import defaultdict

S = input()
B = defaultdict(int)
B[0]=1
ans=0
prev=0

for i in range(len(S)):
    m=(prev+int(S[-i-1])*pow(10,i,2019))%2019
    ans+=B[m]
    B[m]+=1
    prev=m

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

import fractions
def main():
  _=int(input())
  a=list(map(int,input().split()))
  a1=a[0]
  fgc=fractions.gcd
  for i in a:
    a1=(i*a1)//fgc(i,a1)
  x=[a1//i for i in a]
  print(sum(x)%(10**9+7))
  
if __name__ == '__main__':
    main()

### FIXED CODE ###

import fractions
from functools import reduce
def main():
  _=input()
  a=tuple(map(int,input().split()))
  fgcd=fractions.gcd
  def lcm_base(x, y):
    return (x * y) // fgcd(x, y)
  def lcm(numbers):
    return reduce(lcm_base, numbers, 1)
  q=lcm(a)
  x=[q//i for i in a]
  print(sum(x)%(10**9+7))
  
if __name__ == '__main__':
    main()
### BUGGY CODE ###


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

ans = set(range(1,n+1))

for i in range(m):
    l,r = map(int,input().split())
    x = set(range(l,r+1))
    ans = ans & x
    
print(len(ans))
    

### FIXED CODE ###


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

ans,ansf = 1,n

for i in range(m):
    l,r = map(int,input().split())
    ans = max(ans,l)
    ansf = min(ansf,r)
    
if ansf - ans <0:
    print(0)
else:
    print(ansf-ans+1)
### BUGGY CODE ###

N,M = map(int,input().split())
H = [int(i) for i in input().split()]
AB = [list(map(int,input().split())) for _ in range(M)]
list_N = list(range(1,N+1))
for j in range(M):
    if H[AB[j][0]-1]<H[AB[j][1]-1]:
        if AB[j][0] in list_N:
            list_N.remove(AB[j][0])
    elif H[AB[j][0]-1]>H[AB[j][1]-1]:
        if AB[j][1] in list_N:
            list_N.remove(AB[j][1])
    else:
        if AB[j][0] in list_N:
            list_N.remove(AB[j][0])
        if AB[j][1] in list_N:
            list_N.remove(AB[j][1])
print(len(list_N))

### FIXED CODE ###

def set1():
    N,M = [int(i) for i in input().split()]
    H = [int(i) for i in input().split()]
    set_N = set([i for i in range(1, N+1)])
    for i in range(M):
        A,B = [int(i) for i in input().split()]
        if H[A-1] < H[B-1]:
            if A in set_N:
                set_N.remove(A)
        elif H[B-1] < H[A-1]:
            if B in set_N:
                set_N.remove(B)
        else:
            if A in set_N:
                set_N.remove(A)
            if B in set_N:
                set_N.remove(B)
    print(len(set_N))

if __name__ == "__main__":
    set1()