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

X=raw_input()
while 1:
    if 'SSSSSSSSSSSSSSSTTTTTTTTTTTTTTT' in X:
       X=X.replace('SSSSSSSSSSSSSSSTTTTTTTTTTTTTTT','')
    elif 'SSSSSSSSSSTTTTTTTTTT' in X:
       X=X.replace('SSSSSSSSSSTTTTTTTTTT','')
    elif 'SSSSSSSTTTTTTT' in X:
       X=X.replace('SSSSSSSTTTTTTT','')
    elif 'SSSSSTTTTT' in X:
       X=X.replace('SSSSSTTTTT','')
    elif 'SSSTTT' in X:
       X=X.replace('SSSTTT','')
    elif 'ST' in X:
       X=X.replace('ST','')
    else:
        break
print len(X)

### FIXED CODE ###

X=raw_input()
l=[0,0]
for i in X:
    if i=='S':
        l[0]+=1
    elif i=='T' and l[0]>0:
        l[0]-=1
    else:
        l[1]+=1
print sum(l)
### BUGGY CODE ###

from itertools import permutations

d, g = map(int, input().split())
g = g // 100
p = []
c = []

for _ in range(d):
	pp, cc = map(int, input().split())
	p.append(pp)
	c.append(cc // 100)

ans = float("inf")
for array in permutations(range(d)):
	gap = g
	num = 0
	for a in array:
		if p[a] * (a + 1) >= gap:
			num += (gap - 1) // (a + 1) + 1
			break
		elif p[a] * (a + 1) + c[a] >= gap:
			num += p[a]
			break
		else:
			num += p[a]
			gap -= p[a] * (a + 1) + c[a]

	if num < ans:
		ans = num

print(ans)

### FIXED CODE ###

from itertools import permutations

d, g = map(int, input().split())
g = g // 100
p = []
c = []

for _ in range(d):
	pp, cc = map(int, input().split())
	p.append(pp)
	c.append(cc // 100)

ans = float("inf")
for array in permutations(range(d)):
	gap = g
	num = 0
	for a in array:
		if p[a] * (a + 1) >= gap:
			num += (gap - 1) // (a + 1) + 1
			break
		elif p[a] * (a + 1) + c[a] >= gap:
			num += p[a]
			break
		else:
			num += p[a]
			gap -= p[a] * (a + 1) + c[a]

	if num < ans:
		ans = num

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

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

from operator import mul
from functools import reduce
def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

ab=cmb(n,a)+cmb(n,b)

cnt=0
nCr=1
for r in range(n):
    nCr_1 = nCr * (n - r) // (r + 1)
    nCr = nCr_1
    cnt+=nCr_1
print(cnt-ab)

### FIXED CODE ###

n, a, b = map(int, input().split())
mod = 10**9 + 7
 
 
def nCr(n, r, mod):
    r = min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n+1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod
 
 
print((pow(2, n, mod)-1-nCr(n, a, mod)-nCr(n, b, mod)) % mod)
### BUGGY CODE ###

import math

n, q = map(int, input().split(" "))
s = input()

lrL = [list(map(int, input().split(" "))) for _ in range(q)]

idx = []
for i in range(n - 1):
    if s[i] == "A" and s[i + 1] == "C":
        idx.append(i)

for l, r in lrL:
    print(len(list(filter(lambda x: l - 1 <= x <= r - 2, idx))))


### FIXED CODE ###

import math

n, q = map(int, input().split(" "))
s = input()

lrL = [list(map(int, input().split(" "))) for _ in range(q)]

li = [0] * n
mx = 0
for i in range(n - 1):
    if s[i] == "A" and s[i + 1] == "C":
        mx += 1
    li[i + 1] = mx

for l, r in lrL:
    print(li[r - 1] - li[l - 1])
### BUGGY CODE ###

import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
e = dd(list)

for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

def clean():
  global res
  for i in range(1, N + 1):
    a = sorted(res[i], reverse = True)
    d = -1
    for j in range(len(a)):
      x = a[j]
      if qd[x] <= d: res[i].discard(x)
      d = max(d, qd[x])

res = [set() for _ in range(N + 1)]
Q = int(input())
qd = [0] * Q
qc = [0] * Q
for i in range(Q):
  v, d, c = map(int, input().split())
  qd[i] = d
  qc[i] = c
  res[v].add(i)
  clean()
#print(qc)

for t in range(10):
  tres = [set() | s for s in res]
  for x in range(1, N + 1):
    for y in e[x]:
      for z in res[x]:
        if qd[z] > t: tres[y].add(z)
  res = tres
  clean()
#print(res)

for r in res[1: ]:
  if len(r): print(qc[max(r)])
  else: print(0)

### FIXED CODE ###

import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
e = dd(list)

for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
mxd = 0
res = [[-1] * 11 for _ in range(N + 1)]
Q = int(input())
qd = [0] * Q
qc = [0] * Q
for i in range(Q):
  v, d, c = map(int, input().split())
  qd[i] = d
  qc[i] = c
  res[v][d] = i
  mxd = max(mxd, d)
#print(qc)

#print(mxd)
for t in range(mxd):
  tres = [x[: ] for x in res]
  for x in range(1, N + 1):
    for y in e[x]:
      for i in range(t + 1, 11):
        res[y][i] = max(res[y][i], tres[x][i])

#print(res)
for r in res[1: ]:
  x = -1
  for i in range(11):
    if r[i] != -1: x = max(x, r[i])
  if x == -1: print(0)
  else: print(qc[x])
### BUGGY CODE ###

import itertools
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    h_list = list(map(int, input().split()))
    c_list = list(itertools.combinations(range(N),2))
    ans = 0

    for c in c_list:
            if abs(c[0] - c[1]) == h_list[c[0]] + h_list[c[1]]:
                ans += 1

    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

input()
A = [int(h) for h in input().split()]
iph_dic = {}
pair_of_spies = 0

for i, h in enumerate(A):
    if i - h in iph_dic:
        pair_of_spies += iph_dic[i - h]
    if i + h in iph_dic:
        iph_dic[i + h] += 1
    else:
        iph_dic[i + h] = 1

print(pair_of_spies)
### BUGGY CODE ###

import queue

nv, ne = map(int, input().split(' '))
in_degrees = [[] for _ in range(nv)]
q = queue.Queue()
o = []

for _ in range(ne):
    s, t = map(int, input().split(' '))
    in_degrees[t].append(s)

for i in range(nv):
    if len(in_degrees[i]) == 0: q.put(i)

while not q.empty():
    v = q.get()
    o.append(v)

    for i in range(nv):
        if v in in_degrees[i]:
            in_degrees[i].remove(v)
            if len(in_degrees[i]) == 0: q.put(i)

[print(v) for v in o]

### FIXED CODE ###

nv, ne = map(int, input().split(' '))
in_degs = [0] * nv
q = []
outs = {}
o = []

for _ in range(ne):
    s, t = map(int, input().split(' '))

    if s in outs: outs[s].append(t)
    else: outs[s] = [t]

    in_degs[t] += 1

for i in range(nv):
    if in_degs[i] == 0: q.append(i)

while q:
    v = q.pop(0)
    o.append(v)

    if v in outs:
        for out in outs[v]:
            in_degs[out] -= 1
            if in_degs[out] == 0: q.append(out)

[print(v) for v in o]
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
count=0
for i in range(N):
    p=A[i]
    if p==0:
        count+=1
    for j in range(i+1,N):
        p+=A[j]
        if p==0:
            count+=1
print(count)

### FIXED CODE ###

n = int(input())
*A, = map(int, input().split())
S = [0]
for i in range(n):
    S.append(S[-1] + A[i])
C = {}
for s in S:
    try:
        C[s] += 1
    except BaseException:
        C[s] = 1
print(sum([v * (v - 1) // 2 for v in C.values()]))
### BUGGY CODE ###

N = int(input())
A = {}
for i in range(N):
    A[i] = list(map(lambda x: int(x)-1, input().split()))

days = 0
games_amount = 0
for i in range(N*(N-1)//2):
    games = 0
    played = set()
    for j in range(N):
        if len(A[j]) == 0 or j in played or A[j][0] in played:
            continue
        if A[A[j][0]][0] == j:
            t1 = A[j].pop(0)
            played.add(t1)
            played.add(A[t1].pop(0))
            games += 1
            games_amount += 1
    if games == 0:
        print(-1)
        exit(0)
    else:
        days += 1
    if games_amount == N*(N-1)//2:
        break
print(days)


### FIXED CODE ###

import time

start = time.time()

N = int(input())
A = [list(map(lambda x: int(x)-1, input().split())) for i in range(N)]
B = [0]*N
days = 0
games_amount = 0

for i in range(N*(N-1)//2):
    games = 0
    played = set()
    for j in range(N):
        if len(A[j]) == 0 or j in played or A[j][0] in played:
            continue
        if A[A[j][0]][0] == j:
            t1 = A[j].pop(0)
            played.add(t1)
            played.add(A[t1].pop(0))
            games += 1
            games_amount += 1
    if games == 0:
        print(-1)
        exit(0)
    else:
        days += 1
    if games_amount == N*(N-1)//2:
        break
    if time.time() - start > 1.9:
        print(N*(N-1)//2)
        exit(0)
print(days)
### BUGGY CODE ###

n = int(input())
a = []
b = []
for i in range(n):
    c,d = map(int,input().split())
    a.append(c)
    b.append(d)

#下限
all_time = 0
f = n

while(True):
    #上限
    up = min(b)
#    print("up:"+str(up))
    s_time = 0
#    print(b)
    for i in range(n):
#        print(i)
        if b[i] == up:
            s_time += a[i]
            del b[i]
            del a[i]
#            print(b)
            f -= 1
        if i >= f-1:
            break
            # if i != n-1:
            #     i -= 1
    
    all_time += s_time
    if all_time > up:
        print("No")
#        print(all_time)
        break

#    print("length:"+str(len(b)))
    if len(b) == 0:
        print("Yes")
        break


### FIXED CODE ###

n = int(input())
l = []
for i in range(n):
    c,d = map(int,input().split())
    l.append([c,d])

l.sort(key = lambda x:x[1])

time = 0
ans = "Yes"
for i in range(n):
    limit = l[i][1]
    time += l[i][0]
    if time > limit:
        ans = "No"
        break

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

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

s.append(9)
ran = []
a = 0
i = 1
#ランレングス圧縮
while i < len(s):
    if s[a] == s[i]:
        i +=1
    else:
        ran.append(i-a)
        a = i
        i += 1
ran.append(0)
ran.append(0)
ran.append(0)
b = s[0]
result = []
i = 0
counter = 0
if len(ran)-3 <= k*2:
    print(n)
else:
    while i+2*k <= len(ran)-3:
        if s[counter] == 1:
            result.append(sum(ran[i:2*k+i+1]))
        else:
            result.append(sum(ran[i:2*k+i]))
        counter += ran[i]
        i += 1
    print(max(result))

### FIXED CODE ###

n, k = map(int, input().split())
s = list(map(int, list(str(input()))))
c = 0
ran = [0,0]
for i in range(n):
    if s[c] == s[i]:
        ran[-1] += 1
    else:
        ran.append(i+1)
        c = i
result = []
for i in range(1, len(ran)):
    if s[ran[i-1]] == 1:
        result.append(ran[min(i+2*k,len(ran)-1)]-ran[i-1])
    else:
        result.append(ran[min(i+2*k-1, len(ran)-1)]-ran[i-1])
print(max(result))
### BUGGY CODE ###

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x == y:
      return
    if self.parents[x] > self.parents[y]:
      x, y = y, x
    self.parents[x] += self.parents[y]
    self.parents[y] = x

  def size(self, x):
    return -self.parents[self.find(x)]

  def same(self, x, y):
    return self.find(x) == self.find(y)

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

  def group_count(self):
    return len(self.roots())

  def all_group_members(self):
    return {r: self.members(r) for r in self.roots()}

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M = map(int, input().split())
AB = []
for _ in range(M):
  A, B = map(int, input().split())
  AB.append((A-1, B-1))

uf = UnionFind(N)
unhappy = [N*(N-1)//2]

for A, B in reversed(AB):
  uf.union(A, B)
  happy = 0
  for i in uf.roots():
    temp = uf.size(i)
    happy += temp*(temp-1)//2
  unhappy.append(N*(N-1)//2 - happy)

print(*reversed(unhappy[:-1]), sep="\n")

### FIXED CODE ###

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x == y:
      return
    if self.parents[x] > self.parents[y]:
      x, y = y, x
    self.parents[x] += self.parents[y]
    self.parents[y] = x

  def size(self, x):
    return -self.parents[self.find(x)]

  def same(self, x, y):
    return self.find(x) == self.find(y)

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

  def group_count(self):
    return len(self.roots())

  def all_group_members(self):
    return {r: self.members(r) for r in self.roots()}

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M = map(int, input().split())
AB = []
for _ in range(M):
  A, B = map(int, input().split())
  AB.append((A-1, B-1))

uf = UnionFind(N)
unhappy = [N*(N-1)//2]

def conb(x):
  return x*(x-1)//2

for A, B in reversed(AB):
  old_ap, old_bp = uf.find(A), uf.find(B)
  if old_ap == old_bp:
    uf.union(A, B)
    unhappy.append(unhappy[-1])
  else:
    old_happy = conb(uf.size(old_ap)) + conb(uf.size(old_bp))
    uf.union(A, B)
    new_happy = conb(uf.size(A))
    happy = new_happy - old_happy
    unhappy.append(unhappy[-1] - happy)

print(*reversed(unhappy[:-1]), sep="\n")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N, K = MI()
    s = set()
    mod = 998244353
    for i in range(K):
        l, r = MI()
        for j in range(l, r+1):
            s.add(j)
    dp = [0] * (N+1)
    dp[1] = 1
    for i in range(1, N):
        for ss in s:
            idx = i + ss
            if idx < N+1:
                dp[i+ss] += dp[i] % mod
        # print(dp)
    # for ss in s:
    #     for i in range(ss, N, ss):
    #         dp[i] += 1
    # print(dp)
    print(dp[N] % mod)
            
if __name__ == '__main__':
    solve()



### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N, K = MI()
    S = []
    mod = 998244353
    for i in range(K):
        l, r = MI()
        S.append((l, r))
    dp = [0] * (N+1)
    dp[1] = 1
    C = [0] * (N+1)
    C[1] = 1
    for i in range(2, N+1):
        for s in S:
            l = max(1, i - s[1])
            r = i - s[0]
            if r < 1:
                continue
            dp[i] += (C[r] - C[l-1]) % mod
        C[i] += (dp[i] + C[i-1]) % mod
    print(dp[N] % mod)
            
if __name__ == '__main__':
    solve()
### BUGGY CODE ###

N = int(input())
A=[]
B=[]
for i in range(N):
    a,b = map(int,input().split())
    c = 0
    for j in range(i):
        if B[j] > b:
            c = j
            break
        c = i
    A.insert(c,a)
    B.insert(c,b)
found = True
SUM = 0
for i in range(N):
    SUM = SUM + A[i]
    if B[i] < SUM:
        found = False
if found:
    print("Yes")
else:
    print("No")
    



### FIXED CODE ###

N = int(input())
A=[]
B=[]
for i in range(N):
    a,b = map(int,input().split())
    c = 0
    A.append(a)
    B.append(b)
def merge_sort(arr,b):
    if len(arr) <= 1:
        return (arr,b)

    mid = len(arr) // 2
    # ここで分割を行う
    left = arr[:mid]
    right = arr[mid:]
    leftt =b[:mid]
    rightt = b[mid:]

    # 再帰的に分割を行う
    left,leftt = merge_sort(left,leftt)
    right,rightt = merge_sort(right,rightt)

    # returnが返ってきたら、結合を行い、結合したものを次に渡す
    return merge(left, right,leftt,rightt)


def merge(left, right,leftt,rightt):
    merged = []
    mergedd = []
    l_i, r_i = 0, 0

    # ソート済み配列をマージするため、それぞれ左から見ていくだけで良い
    while l_i < len(left) and r_i < len(right):
        # ここで=をつけることで安定性を保っている
        if left[l_i] <= right[r_i]:
            merged.append(left[l_i])
            mergedd.append(leftt[l_i])
            l_i += 1
        else:
            merged.append(right[r_i])
            mergedd.append(rightt[r_i])
            r_i += 1

    # 上のwhile文のどちらかがFalseになった場合終了するため、あまりをextendする
    if l_i < len(left):
        merged.extend(left[l_i:])
        mergedd.extend(leftt[l_i:])
    if r_i < len(right):
        merged.extend(right[r_i:])
        mergedd.extend(rightt[r_i:])
    return (merged,mergedd)
B,A = merge_sort(B,A)
found = True
SUM = 0
for i in range(N):
    SUM = SUM + A[i]
    if B[i] < SUM:
        found = False
if found:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

import bisect
import sys
input = sys.stdin.readline
from collections import deque
def solve():
  
  n,m = (int(i) for i in input().split())
  a = list(int(i) for i in input().split())
  a.sort()
  tmp = deque([])
  for i in range(m):
    l,r = (int(i) for i in input().split())
    tmp.append((l,r))
  tmp= sorted(tmp,key=lambda tmp: tmp[1],reverse =True)
  ans = 0
  while tmp:
    if len(a) == 0:
      break
    b,c = tmp.pop(0)
    place = bisect.bisect_left(a,c)-1
    if place == -1:
      break
    else:
        a = a[min(1+place,b)::]
        ans += c*(min(1+place,b))
    #print(a)
  if a:
   ans += sum(a)
  print (ans)
solve()

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline
from collections import deque
def solve():
  
  n,m = (int(i) for i in input().split())
  a = list(int(i) for i in input().split())
  a = deque(sorted(a))
  tmp = deque([])
  for i in range(m):
    r,l = (int(i) for i in input().split())
    tmp.append((l,r))
  tmp= deque(sorted(tmp,reverse =True))
  ans = 0
  while tmp:
    c,b = tmp.popleft()
    place = bisect.bisect_left(a,c)-1
    if place == -1:
      break
    else:
        if len(a) == 0:
           break
        for i in range(min(1+place,b)):
           a.popleft()
        ans += c*(min(1+place,b))
    #print(a)
  if a:
   ans += sum(a)
  print (ans)
solve()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
xs = []
ys = []
for i in range(n):
    x,y = map(int, input().split())
    xs.append([x,i])
    ys.append([y,i])

xs.sort()
ys.sort()

edges = []
for tmp in [xs,ys]:
    for i in range(n-1):
        tmp_0 = tmp[i]
        tmp_1 = tmp[i+1]
        edges.append([ tmp_1[0] - tmp_0[0], tmp_1[1], tmp_0[1] ])

edges.sort()

ans = 0
uf = list(range(n))
remains = set(range(1,n))

def get_root(a):
    tmp = uf[a]
    if(a == tmp):
        return a
    uf[a] = get_root(tmp)
    if((uf[a] == 0)& (a in remains) ):
        remains.remove(a)
    return uf[a]

def update(a, next):
    if(a != uf[a]):
        update(uf[a], next)
    uf[a] = next

# print(edges)

for edge in edges:
    cost, a, b = edge
    root_a = get_root(a)
    root_b = get_root(b)
    min_ = min(root_a, root_b)
    if( root_a != root_b):
        update(a, min_)
        update(b, min_)
        ans += cost
        # print(uf)
        # print(ans)
    if(min_ == 0):
        rem_temp = remains.copy()
        for remain in rem_temp:
            get_root(remain)

        if(len(remains) == 0):
            print(ans)
            exit()

### FIXED CODE ###

import sys
input = sys.stdin.readline

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self,x):
        if(self.parents[x] < 0):
            return x
        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def size(self, x):
        return self.parents[ self.find(x) ] * -1

    def same(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        return (x_root == y_root)

    def union(self,x,y):
        x_root = self.find(x)
        y_root = self.find(y)
        if(x == y):
            return

        if( self.parents[x_root] <= self.parents[y_root] ):
            self.parents[x_root] += self.parents[y_root]
            self.parents[y_root] = x_root
        else:
            self.parents[y_root] += self.parents[x_root]
            self.parents[x_root] = y_root

    def members(self,x):
        root = self.find(x)
        ret = [ i for i in range(self.n) if self.find(i) == root ]
        return ret

    def roots(self):
        ret = [ i for i in range(self.n) if self.parents[i] < 0]
        return ret

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

n = int(input())
xs = []
ys = []
for i in range(n):
    x,y = map(int, input().split())
    xs.append([x,i])
    ys.append([y,i])

xs.sort()
ys.sort()

edges = []
for tmp in [xs,ys]:
    for i in range(n-1):
        tmp_0 = tmp[i]
        tmp_1 = tmp[i+1]
        edges.append([ tmp_1[0] - tmp_0[0], tmp_1[1], tmp_0[1] ])

edges.sort()

ans = 0
uf = UnionFind(n)

for edge in edges:
    cost, a, b = edge
    if uf.same(a,b) == False:
        uf.union(a,b)
        ans += cost

    if( uf.size(a) == n):
        print(ans)
        exit()