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

import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
cd = [list(map(int, input().split())) for _ in range(K)]

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]
  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if(x == y):
      return 
    if self.root[x] > self.root[y]:
      x, y = y, x
    self.root[x] += self.root[y]
    self.root[y] = x 
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
  def Count(self, x): # xが属するグループのサイズを返す
    return -self.root[self.Find_Root(x)]
  def Members(self, x): # xが属するグループに属する要素をリストで返す
    return [i for i in range(self.n) if self.Find_Root(i)==self.Find_Root(x)]
  def Roots(self): # 全ての根の要素をリストで返す
    return [i for i, x in enumerate(self.root) if x < 0]
  def Group_Count(self): # グループの数を返す
    return len(self.Roots())

uf = UnionFind(N+1)
friends = [[0]*(N+1) for _ in range(N+1)]
blocks = [[0]*(N+1) for _ in range(N+1)]
ans = [0]*(N+1)
roots = {i:0 for i in range(1, N+1)}
ad = [0]*(N+1)

for a, b in ab:
  uf.Unite(a, b)
  friends[a][b] = 1
  friends[b][a] = 1
  ad[a] += 1
  ad[b] += 1

for i in range(1, N+1):
  roots[uf.Find_Root(i)] += 1

for c, d in cd:
  if uf.isSameGroup(c, d):
    ad[c] += 1
    ad[d] += 1

for i in range(1, N+1):
  ans[i] = roots[uf.Find_Root(i)]

for i in range(1, N+1):
  print(ans[i]-ad[i]-1, end=" ")

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]
  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if(x == y):
      return 
    if self.root[x] > self.root[y]:
      x, y = y, x
    self.root[x] += self.root[y]
    self.root[y] = x 
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
  def Count(self, x): # xが属するグループのサイズを返す
    return -self.root[self.Find_Root(x)]
  def Members(self, x): # xが属するグループに属する要素をリストで返す
    return [i for i in range(self.n) if self.Find_Root(i)==self.Find_Root(x)]
  def Roots(self): # 全ての根の要素をリストで返す
    return [i for i, x in enumerate(self.root) if x < 0]
  def Group_Count(self): # グループの数を返す
    return len(self.Roots())

uf = UnionFind(N+1)
roots = {i:0 for i in range(1, N+1)}
each_root = [0]*(N+1)
ad = [0]*(N+1)

for _ in range(M):
  a, b = map(int, input().split())
  uf.Unite(a, b)
  ad[a] += 1
  ad[b] += 1

for i in range(1, N+1):
  r = uf.Find_Root(i)
  roots[r] += 1
  each_root[i] = r

for _ in range(K):
  c, d = map(int, input().split())
  if each_root[c] == each_root[d]:
    ad[c] += 1
    ad[d] += 1

for i in range(1, N+1):
  print(roots[each_root[i]]-ad[i]-1, end=" ")
### BUGGY CODE ###

number_of_prefecture, number_of_cities = [int(x) for x in input().split(' ')]

city_list = []

import collections
city_dict = collections.defaultdict(list)

for i in range (number_of_cities):
    prefecture_id, year_of_establishment = [int(x) for x in input().split(' ')]
    index = 0
    for k in city_dict[prefecture_id]:
        if year_of_establishment > k:
            index += 1
        else:
            break
    city_dict[prefecture_id].insert(index, year_of_establishment)
    city_list.append([prefecture_id, year_of_establishment])

for j in city_list:
    prefecture = j[0]
    year = j[1]
    city_number = city_dict[prefecture].index(year) + 1
    front_string = '0'*(6 - len(str(prefecture))) + str(prefecture)
    back_string = '0'*(6 - len(str(city_number))) + str(city_number)
    print(front_string+back_string)


### FIXED CODE ###

number_of_prefecture, number_of_cities = [int(x) for x in input().split(' ')]

city_list = []

import bisect
import collections
city_dict = collections.defaultdict(list)

for i in range (number_of_cities):
    prefecture_id, year_of_establishment = [int(x) for x in input().split(' ')]
    city_dict[prefecture_id].append(year_of_establishment)
    city_list.append([prefecture_id, year_of_establishment])

for prefecture in city_dict:
    city_dict[prefecture].sort()

for j in city_list:
    prefecture = j[0]
    year = j[1]
    city_number = bisect.bisect(city_dict[prefecture],year)
    front_string = '0'*(6 - len(str(prefecture))) + str(prefecture)
    back_string = '0'*(6 - len(str(city_number))) + str(city_number)
    print(front_string+back_string)
### BUGGY CODE ###

N, K = map(int,input().split())
x = []
count = 0
while N - K >= 0:
  N = N - K
x.append(N)
while (N - K)*(-1) <= x[0 + count]:
  count = count + 1
  x.append((N - K)*(-1))
  N = N - K
print(x[0 + count])


### FIXED CODE ###

N, K = map(int,input().split())
r = N%K
a = min(r, K-r)
print(a)
### BUGGY CODE ###

N=raw_input()
LN=raw_input().split()

n = int(N)
ln = [int(i) for i in LN]

ln.sort()

def bin_search(s,e,t):
    # return minimum i between s <= i < e where ln[i] >= t
    m = (s + e)/2
    if m == s:
        return s

    if t < ln[m]:
        return bin_search(s,m,t)
    else:
        return bin_search(m,e,t)



r = 0
for i in range(n-1, -1, -1):
    a = ln[i]
    for j in range(i-1, -1, -1):
        b = ln[j]
        c = a - b
        if j > 0 and ln[j-1] > c:
            idx = bin_search(0,j,c+1)
            r += j - idx

print r

### FIXED CODE ###

import bisect

N=int(raw_input())
LN=map(int, raw_input().split())

LN.sort()

r = 0
for i in xrange(N-1, 1, -1):
    a = LN[i]
    for j in xrange(i-1, 0, -1):
        b = LN[j]
        if a > 2*b:
            break
        idx = bisect.bisect_left(LN, a-b+1)
        if idx < j:
            r += j - idx

print r
### BUGGY CODE ###

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

ans = 0
b = []
c = 0

for i in range(n-1,0,-1):
    c = c + a[i]
    b.insert(0,c)

b.insert(0,0)

for j in range(n-1):
    ans = (a[j] * b[j+1] + ans) % (10**9+7)

print(ans)


### FIXED CODE ###

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

ans = 0
b = [0] * n
c = 0

for i in range(n):
    c = c + a[i]
    b[i] = c

for j in range(n-1):
    ans = (a[j] * (b[n-1] - b[j]) + ans) % (10**9+7)

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

import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    s = input()
    t = input()

    slen = len(s)
    tlen = len(t)
    dp = [[0 for _ in range(tlen + 1)] for _ in range(slen + 1)]

    for i in range(slen):
        for j in range(tlen):
            if s[i] == t[j]:
                dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])

    ans = ''
    while slen > 0 and tlen > 0:
        if dp[slen][tlen] == dp[slen - 1][tlen]:
            slen -= 1
        elif dp[slen][tlen] == dp[slen][tlen - 1]:
            tlen -= 1
        else:
            slen -= 1
            tlen -= 1
            ans += s[slen]
    print(ans[::-1])

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    s = input()
    t = input()

    slen = len(s)
    tlen = len(t)
    dp = [[0 for _ in range(tlen + 1)] for _ in range(slen + 1)]

    for i in range(slen):
        for j in range(tlen):
            if s[i] == t[j]:
                dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])

    ans = ''
    while slen > 0 and tlen > 0:
        if dp[slen][tlen] == dp[slen - 1][tlen]:
            slen -= 1
        elif dp[slen][tlen] == dp[slen][tlen - 1]:
            tlen -= 1
        else:
            slen -= 1
            tlen -= 1
            ans += s[slen]
    print(ans[::-1])

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

h, w, m = map(int,input().split())
maze = [[0 for _ in range(w)] for _ in range(h)]
for i in range(m):
    hh, ww = map(lambda x:int(x)-1,input().split())
    maze[hh][ww] = 1

#yoko
row = [0]*h
for r in range(h):
    row[r] = sum(maze[r])
#tate
col = [0]*w
for c in range(w):
    tmp = 0
    for r in range(h):
        tmp += maze[r][c]
    col[c] = tmp

rmax = max(row)
cmax = max(col)
ans = 0
for i,r in enumerate(row):
    if r == rmax:
        for j,c in enumerate(col):
            if c == cmax:
                if maze[i][j] == 1:
                    ans = max(ans, rmax+cmax-1)
                else:
                    ans = max(ans,rmax+cmax)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

h, w, m = map(int,input().split())

row = [0]*h
col = [0]*w
enemy = []

for i in range(m):
    hh, ww = map(lambda x:int(x)-1,input().split())
    row[hh] += 1
    col[ww] += 1
    enemy.append((hh,ww))

enemy = set(enemy)
rmax = max(row)
cmax = max(col)

on_r = row.count(rmax)
on_c = col.count(cmax)

on = 0
for hh, ww in enemy:
    if row[hh] == rmax and col[ww] == cmax:
        on += 1
if on == on_r*on_c:
    print(rmax+cmax-1)
else:
    print(rmax+cmax)
### BUGGY CODE ###

N, x = map(int, input().split())
a = list(map(int, input().split()))
count = 0

for i in range(N-1):
  while a[i]+a[i+1]>x:
    if a[i]>a[i+1]:
      a[i] -= 1
      count += 1
    else:
      a[i+1] -= 1
      count += 1

print(count)


### FIXED CODE ###

N, x = map(int, input().split())
a = list(map(int, input().split()))
count = 0

for i in range(N-1):
    while a[i]+a[i+1] > x:
        if a[i]>x:
           count += a[i]-x
           a[i] = x
        else:
           count += a[i+1] - (x-a[i])
           a[i+1] = x - a[i]

print(count)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    e = [[] for _ in range(n)]
    if m > 0:
        for _ in range(m):
            l,r,d = LI()
            e[l-1].append((r-1,d))
            e[r-1].append((l-1,-d))

    b = [False] * n
    def g(i):
        b[i] = 0
        q = [i]
        qi = 0
        nq = []
        while True:
            if len(q) == qi:
                if not nq:
                    return True
                q = nq
                qi = 0
                nq = []
            j = q[qi]
            qi += 1
            c = b[j]
            for r,d in e[j]:
                if b[r] == False:
                    b[r] = c+d
                    nq.append(r)
                else:
                    if b[r] != c+d:
                        return False
        return True

    for i in range(n):
        if b[i] != False:
            continue
        if not g(i):
            return 'No'
    return 'Yes'


print(main())




### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    e = [[] for _ in range(n)]
    if m > 0:
        for _ in range(m):
            l,r,d = LI()
            e[l-1].append((r-1,d))
            e[r-1].append((l-1,-d))

    b = [None] * n

    for i in range(n):
        if not b[i] is None:
            continue
        b[i] = 0
        q = [i]
        qi = 0
        nq = []
        while True:
            if len(q) == qi:
                if not nq:
                    break
                q = nq
                qi = 0
                nq = []
            j = q[qi]
            qi += 1
            c = b[j]
            for r,d in e[j]:
                if b[r] is None:
                    b[r] = c+d
                    nq.append(r)
                else:
                    if b[r] != c+d:
                        return 'No'

    return 'Yes'


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

s=input()
n = int(input())

for _ in range(n):
    i = list(input())

    if i[0] == '1': s=s[::-1]

    else:
        if i[2] == '1':  s=i[4] + s
        else: s+=i[4]

print(s)

### FIXED CODE ###

from collections import deque
s=input()
n = int(input())

f=False
q= deque(s)

for _ in range(n):
    i = input()

    if i[0] == '1': f=False if f else True
    else:
        _,a,b =i.split()
        
        if f :
            if a == '1':q.append(b)
            else:q.appendleft(b)
        else:
            if a == '1':q.appendleft(b)
            else:q.append(b)

if f: q.reverse()

for i in q:print(i,end='')
### BUGGY CODE ###

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
dan = [0]*(n+1)
dan[0] = 1

for i in range(1,n+1):
    if i not in a:
        dan[i] += dan[i-1]
        if i >= 2:
            dan[i] += dan[i-2]

print(dan[n]%(10**9+7))

### FIXED CODE ###

n, m = map(int, input().split())
li = [True]*(n+1)

for i in range(m):
    a = int(input())
    li[a] = False

dan = [0]*(n+1)
dan[0] = 1

for j in range(1,n+1):
    if li[j]:
        dan[j] += dan[j-1]
        if j >= 2:
            dan[j] += dan[j-2]

print(dan[n]%(10**9+7))
### BUGGY CODE ###

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

cnt = 0
for i in range(n):
    dp = 0
    for j in range(i, n):
        dp += A[j]
        if dp == 0:
            cnt += 1
            
print(cnt)

### FIXED CODE ###

from collections import Counter

def comb(n, k):
    k = min(k, n - k)
    result = 1
    for i in range(n, n - k, -1):
        result *= i
    for i in range(1, k + 1):
        result //= i 
    return result

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

S = [0] * (n + 1)
for i in range(1, n + 1):
    S[i] = S[i - 1] + A[i - 1]
    
S = Counter(S)
ans = 0
for v in S.values():
    if v > 1:
        ans += comb(v, 2)
        
print(ans)
### BUGGY CODE ###

N,M = map(int, input().split())
A = [int(i) for i in input().split()]
for i in range(M):
  b,c = map(int,input().split())
  A += [c]*b
A.sort(reverse=True)
print(sum(A[:N]))

### FIXED CODE ###

import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7


def INT_(n): return int(n)-1


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


def MF(): return map(float, input().split())


def MI_(): return map(INT_, input().split())


def LI(): return list(MI())


def LI_(): return [int(x) - 1 for x in input().split()]


def LF(): return list(MF())


def LIN(n: int): return [input() for _ in range(n)]


def LLIN(n: int): return [LI() for _ in range(n)]


def LLIN_(n: int): return [LI_() for _ in range(n)]


def LLI(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def F(): return float(input())


def ST(): return input().replace('\n', '')


def main():
    N, M = MI()
    A = LI()
    minA = min(A)
    BC = LLIN(M)
    BC.sort(reverse=True, key=lambda x: x[1])
    bc = []
    cnt = 0
    for b, c in BC:
        if cnt >= N or minA >= c:
            break
        bc += [c] * b
        cnt += b

    l = A + bc
    l.sort(reverse=True)
    ans = sum(l[:N])
    print(ans)

    """
    from bisect import bisect_left
    N, M = MI()
    A = LI()
    A.sort()
    BC = LLIN(M)
    BC.sort(key=lambda x: x[1])
    now = 0  # 要検討
    ans = 0
    for b, c in BC:
        bis = bisect_left(A, c)
        print(bis, b, c)
        if bis - now < 0:
            continue
        else:
            if bis - now > b:
                ans += b*c
                now += b
            else:
                ans += (bis - now) * c
                now = bis
                print(bis, now)
        print(ans)
    # nowまでは想いのままに

    for i in range(now, N):
        ans += A[i]
    print(ans)
"""


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

n,m=map(int,input().split())
h=list(map(int,input().split()))
lis=[]

for i in range(m):
    a,b=map(int,input().split())
    ha=h[a-1]
    hb=h[b-1]
    if ha==hb:
        if a not in lis:
            lis.append(a)
        if b not in lis:
            lis.append(b)
    if ha>hb:
        if b not in lis:
            lis.append(b)
    else:
        if a not in lis:
            lis.append(a)

print(n-len(lis))


### FIXED CODE ###

n,m=map(int,input().split())
h=list(map(int,input().split()))
lis=[]

for i in range(m):
    a,b=map(int,input().split())
    ha=h[a-1]
    hb=h[b-1]
    if ha==hb:
        lis.append(a)
        lis.append(b)
    if ha>hb:
        lis.append(b)
    else:
        lis.append(a)

print(n-len(list(set(lis))))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N,W= map(int,input().split())
ans=[[0 for e in range(W+1)] for f in range(N+1)]
for i in range(N):
 w,v=map(int,input().split())
 for k in range(0,w):
  ans[i+1][k]=ans[i][k]
 for j in range(w,W+1):
  ans[i+1][j]=max(ans[i][j-w]+v,ans[i][j])
print(max(ans[N]))


### FIXED CODE ###

import sys
input = sys.stdin.readline
N,W= map(int,input().split())
ans=[[0 for e in range(W+1)] for f in range(N+1)]
for i in range(N):
 w,v=map(int,input().split())
 for k in range(0,w):
  ans[i+1][k]=ans[i][k]
 for j in range(w,W+1):
  ans[i+1][j]=max(ans[i][j-w]+v,ans[i][j])
print(max(ans[N]))
### BUGGY CODE ###

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

right_answers = list(int(input()) for _ in list(range(Q)))
indexes = [v-1 for v in right_answers]

scores = [K for _ in range(N)]

for i in indexes:
    scores[i] = scores[i]+1
    scores = [w-1 for w in scores]

for j in scores:
    if j > 0:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

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

right_answers = list(int(input()) for _ in list(range(Q)))
indexes = [v-1 for v in right_answers]

scores = [K-Q for _ in range(N)]

for i in indexes:
    scores[i] = scores[i]+1

for j in scores:
    if j > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n = int(raw_input())
ax = []
bx = []
for _ in xrange(n):
    a,b = map(int,raw_input().split())
    ax.append(a)
    bx.append(b)

ax = ax[::-1]
bx = bx[::-1]
cnt = 0
for i in xrange(n):
    if ax[i] % bx[i] !=0:
        k = bx[i] - (ax[i] % bx[i])
        cnt += k
        ax = map(lambda x:x+k,ax)
print cnt


### FIXED CODE ###

n = int(raw_input())
ax = []
bx = []
for _ in xrange(n):
    a,b = map(int,raw_input().split())
    ax.append(a)
    bx.append(b)

ax = ax[::-1]
bx = bx[::-1]
cnt = 0
for i in xrange(n):
    if (ax[i] + cnt) % bx[i] !=0:
        k = bx[i] - ((ax[i] + cnt) % bx[i])
        cnt += k

print cnt
### BUGGY CODE ###

import numpy as np
N = int(input())
L = list(map(int,input().split()))
ans = 0
for i in range(N-2):
  candidate = L[i+1:]
  candidate_array = np.array(candidate)
  ans += sum([np.count_nonzero((candidate_array[k+1:]<L[i]+l)&(candidate_array[k+1:]>abs(l-L[i]))) for k,l in enumerate(candidate)])

print(ans)
  

### FIXED CODE ###

N = int(input())
L = list(map(int,input().split()))
L.sort(reverse = True)
ans = 0

def binary(L):
  left = -1
  right = len(L)
  t = (left+right)//2
  while right-left != 1:
    if L[t] > max_len - next_len:
      left = t
    else:
      right = t
    t = (left + right) // 2
  return left + 1
  
  
for i in range(N-2):
  max_len = L[i]
  for j in range(i+1,N-1):
    next_len = L[j]
    ans += binary(L[j+1:])
print(ans)
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


import numpy as np

n,k = list(map(int, input().split()))
v0 = np.zeros((4*k, 4*k), dtype=int)
v1 = np.zeros((4*k, 4*k), dtype=int)

for i in range(n):
    x,y,c = input().split()
    x = int(x)
    y = int(y)
    x %= 2*k
    y %= 2*k
    if c=="W":
        v = v0
    else:
        v = v1
    v[x][y] += 1
    v[x][y+2*k] += 1
    v[x+2*k][y] += 1
    v[x+2*k][y+2*k] += 1
def cumsum2(v):
    # v: h*wの2次元リスト
    v = np.cumsum(v, axis=0)
    v = np.cumsum(v, axis=1)
    c = np.zeros((v.shape[0]+1, v.shape[1]+1), dtype=int)
    c[1:, 1:] = v
    return v
c0 = cumsum2(v0)
c1 = cumsum2(v1)
ans = -1
i0 = []
i1 = []
for i in range(2*k):
    for j in range(2*k):
        i0.append([[i+k,j+k], [i+k,j], [i,j+k], [i,j], [i+2*k, j+2*k], [i+2*k,j+k], [i+k, j+2*k], [i+k, j+k]])
        i1.append([[i+2*k, j+k], [i+2*k,j], [i+k,j+k], [i+k,j], [i+k, j+2*k], [i+k,j+k], [i,j+2*k], [i,j+k]])
#         val0 = c0[i+k][j+k]-c0[i+k][j]-c0[i][j+k]+c0[i][j] + c0[i+2*k][j+2*k]-c0[i+2*k][j+k]-c0[i+k][j+2*k]+c0[i+k][j+k]
#         val1 = c1[i+2*k][j+k]-c1[i+2*k][j]-c1[i+k][j+k]+c1[i+k][j] + c1[i+k][j+2*k]-c1[i+k][j+k]-c1[i][j+2*k]+c1[i][j+k]
#         ans = max(ans, val0+val1)
i0 = np.array(i0)
i1 = np.array(i1)
val = c0[i0[:,[0,3,4,7],0], i0[:,[0,3,4,7],1]].sum(axis=1) - c0[i0[:,[1,2,5,6],0], i0[:,[1,2,5,6],1]].sum(axis=1) + c1[i1[:,[0,3,4,7],0], i1[:,[0,3,4,7],1]].sum(axis=1) - c1[i1[:,[1,2,5,6],0], i1[:,[1,2,5,6],1]].sum(axis=1)
print(val.max())

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



n,k = list(map(int, input().split()))
v = [[0]*(2*k) for _ in range(2*k)]

for i in range(n):
    x,y,c = input().split()
    x = int(x)
    y = int(y)
    if c=="B":
        x += k
    x %= 2*k
    y %= 2*k
    v[x][y] += 1
#     v[x][y+2*k] += 1
#     v[x+2*k][y] += 1
#     v[x+2*k][y+2*k] += 1
def cumsum2(v):
    # v: h*wの2次元リスト
    h,w = len(v), len(v[0])
    v.insert(0, [0]*w)
    for l in v:
        l.insert(0, 0)
    for i in range(1,h+1):
        for j in range(1,w+1):
            v[i][j] = v[i-1][j] + v[i][j-1] - v[i-1][j-1] + v[i][j]
    return v
cumsum2(v)

def sub(c, i, j):
    i %= 2*k
    j %= 2*k
    l = []
    if i<=k and j<=k:
        l = [[i,i+k,j,j+k]]
    elif i>k and j<=k:
        l = [[i,2*k,j,j+k], [0,i-k,j,j+k]]
    elif i<=k and j>k:
        l = [[i,i+k,j,2*k], [i,i+k,0,j-k]]
    else:
        l = [[i,2*k,j,2*k], [0,i-k,j,2*k], [i,2*k,0,j-k], [0,i-k,0,j-k]]
    return sum((c[z][w] - c[z][y] - c[x][w] + c[x][y]) for x,z,y,w in l)
ans = -1
for i in range(2*k):
    for j in range(2*k-i):
        val0 = sub(v, i,j) + sub(v, i+k, j+k)
#         val0 = v[i+k][j+k]-v[i+k][j]-v[i][j+k]+v[i][j] + v[i+2*k][j+2*k]-v[i+2*k][j+k]-v[i+k][j+2*k]+v[i+k][j+k]
#         val1 = v[i+2*k][j+k]-v[i+2*k][j]-v[i+k][j+k]+v[i+k][j] + v[i+k][j+2*k]-v[i+k][j+k]-v[i][j+2*k]+v[i][j+k]
        ans = max(ans, val0)
print(ans)
### BUGGY CODE ###

NM = [int(i) for i in input().split()]
N, M = NM[0], NM[1]
abList = [[int(i) for i in input().split()] for _ in range(M)]

ans = 0

while(True):
    bridgeDic = {}
    for ab in abList:
        if ab != None:
            for i in range(ab[0], ab[1]):
                if i in bridgeDic:
                    bridgeDic[i] += 1
                else:
                    bridgeDic[i] = 1

    largeNum = 0
    largeKey = 0
    for i in bridgeDic:
        if bridgeDic[i] > largeNum:
            largeNum = bridgeDic[i]
            largeKey = i

    ans += 1
    M -= bridgeDic[largeKey]
    if M <= 0:
        break

    for i in range(len(abList)):
        if abList[i] != None and abList[i][0] <= largeKey < abList[i][1]:
            abList[i] = None

print(ans)

### FIXED CODE ###

NM = [int(i) for i in input().split()]
N, M = NM[0], NM[1]
abList = sorted([[int(i) for i in input().split()] for _ in range(M)], key=lambda x: x[1])
bridge = 0
ans = 0

for ab in abList:
    if not ab[0] <= bridge < ab[1]:
        bridge = ab[1] - 1
        ans += 1

print(ans)