CodeEff/ECCO huggingface dataset:
# Original solution
from sys import stdin


def main():
    lines = stdin.readlines()
    S = lines[1]
    lr = [[int(j) - 1 for j in i.split()] for i in lines[2:]]
    AC = [0]
    pre = 0
    for c1, c2 in zip(S[:], S[1:]):
        if c1 == "A" and c2 == "C":
            pre += 1
        AC.append(pre)
    for l, r in lr:
        print((AC[r] - AC[l]))
    return


main()


# Optimized solution
from sys import stdin


def main():
    lines = stdin.readlines()
    S = lines[1]
    lr = [[int(j) - 1 for j in i.split()] for i in lines[2:]]
    AC = []
    pre = None
    cnt = 0
    for c in S:
        if c == "A":
            pre = "A"
        elif pre == "A" and c == "C":
            cnt += 1
            pre = None
        elif pre == "A":
            pre = None
        AC.append(cnt)
    for l, r in lr:
        print((AC[r] - AC[l]))
    return


main()
# Original solution
from sys import stdin


def main():
    readline = stdin.readline
    read = stdin.read
    N, Q = list(map(int, readline().split()))
    S = readline().strip()
    * LR, = [int(x) - 1 for x in read().split()]
    AC = []
    pre = None
    cnt = 0
    for c in S:
        if c == "A":
            pre = "A"
        elif pre == "A" and c == "C":
            cnt += 1
            pre = None
        elif pre == "A":
            pre = None
        AC.append(cnt)
    for l, r in zip(*[iter(LR)] * 2):
        print((AC[r] - AC[l]))
    return


main()


# Optimized solution
from sys import stdin


def main():
    readline = stdin.readline
    read = stdin.read
    N, Q = list(map(int, readline().split()))
    S = readline().strip()
    LR = [int(x) - 1 for x in  read().split()]
    AC = []
    pre = None
    cnt = 0
    for c in S:
        if c == "A":
            pre = "A"
        elif pre == "A" and c == "C":
            cnt += 1
            pre = None
        elif pre == "A":
            pre = None
        AC.append(cnt)
    for l, r in zip(*[iter(LR)] * 2):
        print((AC[r] - AC[l]))
    return


main()
# Original solution
from sys import stdin


def main():
    read = stdin.read
    N, Q = list(map(int, input().split()))
    S = input().strip()
    LR = [int(x) - 1 for x in  read().split()]
    AC = []
    pre = None
    cnt = 0
    for c in S:
        if c == "A":
            pre = "A"
        elif pre == "A" and c == "C":
            cnt += 1
            pre = None
        elif pre == "A":
            pre = None
        AC.append(cnt)
    for l, r in zip(*[iter(LR)] * 2):
        print((AC[r] - AC[l]))
    return


main()


# Optimized solution
from sys import stdin


def main():
    N, Q = list(map(int, input().split()))
    S = input().strip()
    LR = [int(x) - 1 for x in  stdin.read().split()]
    AC = []
    pre = None
    cnt = 0
    for c in S:
        if c == "A":
            pre = "A"
        elif pre == "A" and c == "C":
            cnt += 1
            pre = None
        elif pre == "A":
            pre = None
        AC.append(cnt)
    for l, r in zip(*[iter(LR)] * 2):
        print((AC[r] - AC[l]))
    return


main()
# Original solution
import sys

l = input().split()
N = int(l[0])
Q = int(l[1])
l = input().split()
S = l[0]

L = [0]*Q
R = [0]*Q

ac = 'AC'

for i in range(Q):
    l = input().split()
    L[i] = int(l[0])
    R[i] = int(l[1])

#print(N,Q,S,L,R)

def count(S):
    length = len(S)
    c = 0
    for i in range(length - 1):
        # print(S[i:i+2])
        if ac == S[i:i+2]:
            c += 1
    return c

table = [0]*len(S)

for i in range(len(S)):
    table[i] = count(S[i:])

for i in range(Q):
    print((table[L[i]-1] - table[R[i]-1]))


# Optimized solution
import sys

l = input().split()
N = int(l[0])
Q = int(l[1])
l = input().split()
S = l[0]

L = [0]*Q
R = [0]*Q

ac = 'AC'

for i in range(Q):
    l = input().split()
    L[i] = int(l[0])
    R[i] = int(l[1])

#print(N,Q,S,L,R)

def count(S, table):
    length = len(S)
    c = 0
    for i in range(length - 1):
        # print(S[i:i+2])
        if ac == S[length - i - 2:length - i]:
            c += 1
        table[i+1] = c

length_S = len(S)
table = [0]*length_S

count(S, table)
# print(table)

for i in range(Q):
    print((table[length_S - L[i]] - table[length_S - R[i]]))
# Original solution
import sys
import time
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(eval(input()))
def MAP(): return [int(s) for s in input().split()]

N, Q = MAP()
S = input().rstrip()
LR = [MAP() for _ in range(Q)]

loc = [0]*N
#start = time.time()
for i in range(N-1):
	if S[i]+S[i+1] == 'AC': loc[i] += 1
#print(loc)
#elapsed_time = time.time() - start
#print("elapsed_time:{0}".format(elapsed_time) + "[sec]")

#start = time.time()
for l, r in LR:
	print((sum(loc[l-1:r-1])))
	#tmp = (loc[r-1]-loc[l-1])
#elapsed_time = time.time() - start
#print("elapsed_time:{0}".format(elapsed_time) + "[sec]")

# Optimized solution
import sys
import time
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(eval(input()))
def MAP(): return [int(s) for s in input().split()]

N, Q = MAP()
S = input().rstrip()
LR = [MAP() for _ in range(Q)]

loc = [0]*N
for i in range(N-1):
	if S[i]+S[i+1] == 'AC':
		loc[i+1] += loc[i]+1
	else:
		loc[i+1] = loc[i]
#print(loc)

for l, r in LR:
	print((loc[r-1]-loc[l-1]))
# Original solution
# coding: utf-8
import sys
import itertools


def sr():
    return sys.stdin.readline().rstrip()


def ir():
    return int(sr())


def lr():
    return list(map(int, sr().split()))


N, Q = lr()
S = sr()

ac = [0] * (N - 1)
for i, x in enumerate(zip(S[:], S[1:])):
    if x[0] == 'A' and x[1] == 'C':
        ac[i] = 1

for _ in range(Q):
    l, r = lr()
    print((sum(ac[l - 1: r - 1])))


# Optimized solution
# coding: utf-8
import sys
import itertools


def sr():
    return sys.stdin.readline().rstrip()


def ir():
    return int(sr())


def lr():
    return list(map(int, sr().split()))


N, Q = lr()
S = sr()

ac = [0] * (N - 1)
for i, x in enumerate(zip(S[:], S[1:])):
    if x[0] == 'A' and x[1] == 'C':
        ac[i] = 1

cum = list(itertools.accumulate(ac))
ans_list = []
for _ in range(Q):
    l, r = lr()
    if (l - 2 < 0):
        result = cum[r - 2]
    else:
        result = cum[r - 2] - cum[l - 2]
    ans_list.append(result)
[print(ans) for ans in ans_list]
# Original solution
import bisect

n, q = list(map(int, input().split()))
s = input().strip()
lrs = [list(map(int, input().split())) for _ in range(q)]

indices = []
for i, (c0, c1) in enumerate(zip(s, s[1:])):
    if c0 == 'A' and c1 == 'C':
        indices.append(i)

indices_c = [i + 1 for i in indices]
for (l, r) in lrs:
    li = bisect.bisect_left(indices, l - 1)
    ri = bisect.bisect_left(indices_c, r)
    print((ri - li))

# Optimized solution
import sys

input = sys.stdin.readline

ri = lambda: int(eval(input()))
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

n, q = ril()
s = rs()
acc = [0] * n
for i in range(1, n):
    if s[i - 1:i + 1] == 'AC':
        acc[i] = acc[i - 1] + 1
    else:
        acc[i] = acc[i - 1]
for _ in range(q):
    l, r = ril()
    print((acc[r - 1] - acc[l - 1]))
# Original solution
import sys

input = sys.stdin.readline

ri = lambda: int(eval(input()))
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

n, q = ril()
s = rs()
acc = [0] * n
for i in range(1, n):
    if s[i - 1:i + 1] == 'AC':
        acc[i] = acc[i - 1] + 1
    else:
        acc[i] = acc[i - 1]
for _ in range(q):
    l, r = ril()
    print((acc[r - 1] - acc[l - 1]))

# Optimized solution
import sys

input = sys.stdin.readline

ri = lambda: int(eval(input()))
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

n, q = ril()
s = rs()
ls = rils(q)
acc = [0] * n
for i in range(1, n):
    if s[i - 1:i + 1] == 'AC':
        acc[i] = acc[i - 1] + 1
    else:
        acc[i] = acc[i - 1]
for l, r in ls:
    print((acc[r - 1] - acc[l - 1]))
# Original solution
n,q=[int(i) for i in input().split()]
s=input().replace("AC","10")
f=[1 if s[i]=="1" else 0 for i in range(n)]
for i in range(q):
  l,r=[int(i)-1 for i in input().split()]
  print((sum(f[l:r])))


# Optimized solution
n,q=list(map(int,input().split()))
l=[0 for i in range(n)]
for i,v in enumerate(list(input().replace("AC","X!"))):
    l[i]=l[i-1]+(v=="!")
for c in range(q):
    h,m=list(map(int,input().split()))
    print((l[m-1]-l[h-1]))
# Original solution
#!/usr/bin/env python3
import sys


def solve(N: int, Q: int, S: str, l: "List[int]", r: "List[int]"):
    for (li, ri) in zip(l, r):
        print((S[li - 1 : ri].count("AC")))


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    l = [int()] * (Q)  # type: "List[int]"
    r = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        l[i] = int(next(tokens))
        r[i] = int(next(tokens))
    solve(N, Q, S, l, r)

if __name__ == '__main__':
    main()


# Optimized solution
#!/usr/bin/env python3
import sys


def solve(N: int, Q: int, S: str, l: "List[int]", r: "List[int]"):
    table = [0] * (N + 1)

    for i in range(N):
        table[i + 1] = table[i] + (1 if S[i : i + 2] == "AC" else 0)

    for i in range(Q):
        print((table[r[i] - 1] - table[l[i] - 1]))

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    l = [int()] * (Q)  # type: "List[int]"
    r = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        l[i] = int(next(tokens))
        r[i] = int(next(tokens))
    solve(N, Q, S, l, r)

if __name__ == '__main__':
    main()
# Original solution
import sys
readline = sys.stdin.readline

N, Q = list(map(int, readline().split()))
S = list(readline())
lr = []
for i in range(Q):
    l, r = list(map(int, readline().split()))
    lr.append([l-1, r])

ac = 0
acs = [0 for i in range(N)]
for i in range(N):
    if S[i] == 'A' and ac == 0:
        ac += 1
    elif S[i] == 'C' and ac == 1:
        acs[i - 1] = 1
        ac = 0
    else:
        ac = 0

for i in range(Q):
    l, r = lr[i]
    print((acs[l:r-1].count(1)))

# Optimized solution
import sys
readline = sys.stdin.readline

N, Q = list(map(int, readline().split()))
S = readline()
t = [0] * (N + 1)
for i in range(N):
    t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
    l, r = list(map(int, readline().split()))
    print((t[r-1] - t[l-1]))
# Original solution
import re

N, Q = list(map(int, input().split()))
S = input().rstrip()

for i in range(Q):
    l, r = list(map(int, input().split()))
    s = S[l-1:r]
    print((len(re.findall('AC', s))))



# Optimized solution
N, Q = list(map(int, input().split()))
S = input().rstrip()

cs = [0]
cnt = 0

for i in range(N-1):
    if S[i:i+2] == 'AC':
        cnt += 1
    cs.append(cnt)

for i in range(Q):
    l, r = list(map(int, input().split()))
    print((cs[r-1]-cs[l-1]))
# Original solution
# AOJ 1030 Cubes Without Holes
# Python3 2018.7.6 bal4u

import sys
from sys import stdin
input = stdin.readline

while True:
	n, h = list(map(int, input().split()))
	if n == 0: break
	f = [[[0 for k in range(3)] for c in range(500)] for r in range(500)]
	ans = n**3
	for i in range(h):
		c, a, b = input().split()
		a, b = int(a)-1, int(b)-1
		ans -= n
		if c == "xy":
			f[a][b][0] = 1
			ans += sum([(f[a][j][1] | f[a][j][2]) for j in range(n)])
		elif c == "xz":
			f[a][b][1] = 1
			ans += sum([(f[a][j][0] | f[i][b][2]) for j in range(n)])
		else:
			f[a][b][2] = 1
			ans += sum([(f[j][a][0] | f[j][b][1]) for j in range(n)])
	print(ans)


# Optimized solution
# AOJ 1030 Cubes Without Holes
# Python3 2018.7.6 bal4u

import sys
from sys import stdin
input = stdin.readline

while True:
	n, h = list(map(int, input().split()))
	if n == 0: break
	ans = []
	for i in range(h):
		c, a, b = input().split()
		a, b = int(a)-1, int(b)-1
		if c == "xy":
			ans += [a+b*n+z*n**2 for z in range(n)]
		elif c == "xz":
			ans += [a+y*n+b*n**2 for y in range(n)]
		else:
			ans += [x+a*n+b*n**2 for x in range(n)]
	print((n**3-len(set(ans))))
# Original solution
# AOJ 1030 Cubes Without Holes
# Python3 2018.7.6 bal4u

import sys
from sys import stdin
input = stdin.readline

while True:
	n, h = list(map(int, input().split()))
	if n == 0: break
	ans = []
	for i in range(h):
		c, a, b = input().split()
		a, b = int(a)-1, int(b)-1
		if c == "xy":
			ans += [a+b*n+z*n**2 for z in range(n)]
		elif c == "xz":
			ans += [a+y*n+b*n**2 for y in range(n)]
		else:
			ans += [x+a*n+b*n**2 for x in range(n)]
	print((n**3-len(set(ans))))


# Optimized solution
# AOJ 1030 Cubes Without Holes
# Python3 2018.7.6 bal4u

import sys
from sys import stdin
input = stdin.readline

# n <= 500,  2^9 = 512
while True:
	n, h = list(map(int, input().split()))
	if n == 0: break
	ans = []
	for i in range(h):
		c, a, b = input().split()
		a, b = int(a)-1, int(b)-1
		if c == "xy":
			ans += [a+(b<<9)+(z<<18) for z in range(n)]
		elif c == "xz":
			ans += [a+(y<<9)+(b<<18) for y in range(n)]
		else:
			ans += [x+(a<<9)+(b<<18) for x in range(n)]
	print((n**3-len(set(ans))))
# Original solution
N = int(eval(input()))
dp = [[0] * 3 for i in range(100)]

MOD = int(1e9+7)
maxBit = 70
while not (N >> maxBit):
    maxBit -= 1

dp[maxBit][0] = 1
dp[maxBit][1] = 1
for i in range(maxBit-1, -1, -1):
    for j in range(3):
        bit = (N >> i) & 1
        for k in range(3):
            nj = 2 * j + bit - k
            if nj < 0:
                continue
            nj = min((nj, 2))
            dp[i][nj] += dp[i+1][j]
            dp[i][nj] %= MOD

print((sum(dp[0]) % MOD))


# Optimized solution
N = int(eval(input()))
s = bin(N)[2:]
n = len(s)
dp = [[0] * 4 for i in range(len(s)+1)]
dp[0][0] = 1
MOD = int(1e9) + 7
for i in range(n):
    b = 1 if s[i] == '1' else 0
    for j in range(4):
        for k in range(3):
            nj = min(((j << 1) + b - k, 3))
            if 0 <= nj:
                dp[i+1][nj] += dp[i][j]
                dp[i+1][nj] %= MOD
print((sum(dp[n]) % MOD))
# Original solution
N = int(eval(input()))

d = {0: 1, 1: 2}

def f(n):
  if n in d:
    return d[n]
  d[n] = (f(n // 2) + f((n - 1) // 2) + f((n - 2) // 2)) % (10**9 + 7)
  return d[n]

print((f(N)))

# Optimized solution
def f(n):
 if n in d:return d[n]
 d[n]=f(n//2)+f((n-1)//2)+f((n-2)//2);return d[n]
d={0:1,1:2};print((f(int(eval(input())))%(10**9+7)))
# Original solution
MOD = 10**9 + 7
n = int(eval(input()))
ans = set()

def dfs(a:int, b:int, digit:int, memo:set):
    u = a^b
    v = a+b
    
    if u > n or v > n:
        return 0
    
    else:        
        if digit == 0:
            memo.add((u,v))
            return 0
            
        else:
            dfs(a+pow(2,digit-1), b+pow(2,digit-1), digit-1, memo)
            dfs(a+pow(2,digit-1), b, digit-1, memo)
            dfs(a, b, digit-1, memo)
            
dfs(0,0,60,ans)

print((len(ans) % MOD))


# Optimized solution
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())


MOD = 10**9+7

n = ni()
n_bit = len(bin(n)[2:])

dp = [[0]*4 for _ in range(n_bit+1)]
dp[0][0] = 1

for bit in range(n_bit):
    digit = int(bin(n)[2+bit:2+bit+1])
    
    if digit:
        dp[bit+1][0] = (dp[bit][0]) % MOD
        dp[bit+1][1] = (dp[bit][0] + dp[bit][1]) % MOD
        dp[bit+1][2] = (dp[bit][1]) % MOD
        dp[bit+1][3] = (dp[bit][1] + 3*dp[bit][2] + 3*dp[bit][3]) % MOD
        
    else:
        dp[bit+1][0] = (dp[bit][0] + dp[bit][1]) % MOD
        dp[bit+1][1] = (dp[bit][1]) % MOD
        dp[bit+1][2] = (dp[bit][1] + dp[bit][2]) % MOD
        dp[bit+1][3] = (2*dp[bit][2] + 3*dp[bit][3]) % MOD
        
print((sum(dp[n_bit]) % MOD))
# Original solution
N=int(eval(input()))
mod=10**9+7

ANSLIST=[1]
for i in range(61):
    ANSLIST.append((ANSLIST[-1]*3-1)%mod)

ANS=[1, 2, 4, 5]
ANSDICT=dict()
def ans(k):
    if 0<=k<=3:
        return ANS[k]
    if ANSDICT.get(k)!=None:
        return ANSDICT[k]
    for i in range(61):
        if k==2**i-2:
            return ANSLIST[i]-1
        if k==2**i-1:
            return ANSLIST[i]
        if 2**i-1>k:
            break
    x=k-(2**(i-1)-1)

    ANSDICT[k]=(ans(x-1)+ANSLIST[i-1]*2-ans(2**(i-1)-x-2)-1)%mod
    return ANSDICT[k]

print((ans(N)))

# Optimized solution
import sys
sys.setrecursionlimit(10**9)

N=int(eval(input()))
mod=10**9+7
DP=dict()
DP[(0,0)]=1#a+b,a^b
DP[(1,0)]=1
DP[(1,1)]=2

def ans(S,X):
    #print(S,X)
    if DP.get((S,X))!=None:
        return DP[(S,X)]
    if S==0:
        return 1
    #if X>S:
    #    return ans(S,S)
    

    DP[(S,X)]=(ans(S//2,X//2)+ans((S-1)//2,(X-1)//2)+ans((S-2)//2,(X-2)//2))%mod
    #一番下の桁をみて、bitが0,0の場合,1,0の場合,1,1の場合.
    #三つ目の場合は本来ans((S-2)//2,X//2)だが,今回扱うのはS=Xのときで,X>Sのときは0になるので,ans((S-2)//2,(X-2)//2)で良いはず.
    return DP[(S,X)]

print((ans(N,N)))
# Original solution
N = int(eval(input()))
d = []
for i in range(N):
    h, p = list(map(int, input().split()))
    d.append((h, p))

d = sorted(d, key=lambda x: x[0] + x[1])
INF = float('inf')
dp = [[INF] * (N + 1) for i in range(N + 1)]
dp[0][0] = 0
for i in range(1, N + 1):
    for j in range(N + 1):
        dp[i][j] = dp[i - 1][j]
        if j == 0:
            continue
        if dp[i - 1][j - 1] > d[i - 1][0]:
            continue
        dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + d[i - 1][1])

for i in range(N, -1, -1):
    if dp[N][i] < INF:
        print(i)
        exit()


# Optimized solution
N = int(eval(input()))
d = []
for i in range(N):
    h, p = list(map(int, input().split()))
    d.append((h, p))

d = sorted(d, key=lambda x: x[0] + x[1])
INF = float('inf')
dp1 = [INF] * (N + 1)
dp2 = [INF] * (N + 1)
dp1[0] = 0
for i in range(1, N + 1):
    for j in range(N + 1):
        dp2[j] = dp1[j]
        if j == 0:
            continue
        if dp1[j - 1] > d[i - 1][0]:
            continue
        dp2[j] = min(dp2[j], dp1[j - 1] + d[i - 1][1])
    dp1, dp2 = dp2, dp1

for i in range(N, -1, -1):
    if dp1[i] < INF:
        print(i)
        exit()
# Original solution
N = int(eval(input()))
HPs = [tuple(map(int, input().split())) for i in range(N)]

HPs.sort(key=lambda x: x[0] + x[1])

INF = float('inf')
dp = [0]
for H, P in HPs:
    if dp[-1] != INF:
        dp += [INF]
    dp = list(map(min, list(zip([0] + [hgt + P if hgt <= H else INF for hgt in dp], dp))))

dp += [INF]
print((dp.index(INF) - 1))


# Optimized solution
N = int(eval(input()))
HPs = [tuple(map(int, input().split())) for i in range(N)]

HPs.sort(key=lambda x: x[0] + x[1])

dp = {0: 0}
for H, P in HPs:
    for num, minH in list(dp.items()):
        if H >= minH:
            if num + 1 in dp:
                dp[num + 1] = min(dp[num + 1], minH + P)
            else:
                dp[num + 1] = minH + P

print((max(dp.keys())))
# Original solution
N = int(eval(input()))
HP = sorted([list(map(int,input().split())) for i in range(N)],key = lambda x: x[0]+x[1])
dp = [[float('inf') for i in range(N+1)] for j in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    for j in range(N+1):
        if dp[i-1][j-1] <= HP[i-1][0]:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+HP[i-1][1])
        else:
            dp[i][j] = dp[i-1][j]
for i in range(N,-1,-1):
    if dp[-1][i] != float('inf'):
        print(i)
        break

# Optimized solution
N = int(eval(input()))
HP = sorted([list(map(int,input().split())) for i in range(N)],key = lambda x: x[0]+x[1])
dp1 = [float('inf') for i in range(N+1)]
dp2 = [float('inf') for i in range(N+1)]
dp1[0] = 0
dp2[0] = 0
for i in range(1,N+1):
    for j in range(N+1):
        if dp1[j-1] <= HP[i-1][0]:
            dp2[j] = min(dp1[j],dp1[j-1]+HP[i-1][1])
        else:
            dp2[j] = dp1[j]
    dp1,dp2 =dp2,dp1
for i in range(N,-1,-1):
    if dp1[i] != float('inf'):
        print(i)
        break
# Original solution
import sys
n, m = list(map(int,input().split()))

if n >= m:
  print((0))
  sys.exit()
  
x = list(map(int,input().split()))
x.sort()
between = [x[i+1]-x[i] for i in range(len(x)-1)]
between.sort(reverse = True)
print((sum(between[n-1:])))

# Optimized solution
import sys
n, m = list(map(int,input().split()))

if n >= m:
  print((0))
  sys.exit()
  
x = sorted(list(map(int,input().split())))
print((sum(sorted([x[i+1]-x[i] for i in range(m-1)],reverse = True)[n-1:])))
# Original solution
import sys
import heapq
inf = 10**6
n, m = list(map(int, input().split()))

if n >= m:
  print((0))
  sys.exit()

a = [int(x) for x in input().split()]
a.sort()

count = []
heapq.heapify(count)
for i in range(m-1):
  heapq.heappush(count, -a[i+1]+a[i])

ans = 0
for j in range(n-1):
  ans -= heapq.heappop(count)
ans = max(a)-min(a)-ans
print(ans)

# Optimized solution
m, n = list(map(int, input().split()))
a = [int(x) for x in input().split()]
a.sort()
b = [a[i+1]-a[i] for i in range(n-1)]
b.sort(reverse=True)

print((a[-1]-a[0]-sum(b[:min([m-1, n-1])])))
# Original solution
N,M=[int(x) for x in input().split()]

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

X.sort();

dif = [X[i+1]-X[i] for i in range(M-1)]
if M==1:
    dif = [0]
ans = sum(dif)
for i in range(N-1):
    ans -= max(dif)
    dif[dif.index(max(dif))] = 0

print(ans)


# Optimized solution
import sys

N,M=[int(x) for x in input().split()]
X = [int(x) for x in input().split()]

if N>=M:
    print((0))
    sys.exit()

X.sort();

dif = [X[i+1]-X[i] for i in range(M-1)]
dif.sort()
dif.reverse()
if M==1:
    dif = [0]

ans = sum(dif)
for i in range(N-1):
    ans -= dif[i]

print(ans)
# Original solution
n,m=list(map(int,input().split()))
x=input().split()
for i in range(m):
    a=int(x[i])
    x[i]=a
if n==1:
    print((max(x)-min(x)))
elif m==1 or n>=m:
    print((0))
else:
    goukei=0
    l=[0]
    i=0
    x.sort()
    a=0
    b=0
    if m>1:
        while i<m-1:
            a=x[i]
            b=x[i+1]
            goukei+=b-a
            l.append(b-a)
            i+=1
    i=0
    l.sort()
    while i<n-1:
        a=max(l)
        goukei-=a
        l.remove(a)
        i+=1
        if l==[]:
            break
    print(goukei)

# Optimized solution
n,m=list(map(int,input().split()))
x=list(map(int,input().split()))
x.sort()
if n==1:
    print((max(x)-min(x)))
elif m==1 or n>=m:
    print((0))
else:
    x.sort()
    goukei=0
    l=[0]
    for i in range(m-1):
        goukei+=x[i+1]-x[i]
        l.append(x[i+1]-x[i])
    i=0
    l.sort()
    for i in range(n-1):
        goukei-=l[-1-i]
    print(goukei)
# Original solution
import sys
n,m = list(map(int,input().split()))
x = list(map(int,input().split()))
x.sort()
if n>=m:
    print((0))
    sys.exit()
dis = [x[i+1]-x[i] for i in range(m-1)]
dis.sort()
print((sum(dis[:m-n])))

# Optimized solution
n,m = list(map(int,input().split()))
x = list(map(int,input().split()))
x.sort()
if n>=m:
    print((0))
    exit()
dis = [x[i+1]-x[i] for i in range(m-1)]
dis.sort()
if n>1:
    del dis[-(n-1):]
print((sum(dis)))