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

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

for i in reversed(range(1, m//n + 1)):
    if m % i == 0:
        print(i)
        break


### FIXED CODE ###

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

for i in reversed(range(1, m//n + 1)):
    if m % i == 0:
        print(i)
        break
### BUGGY CODE ###

import sys
input=sys.stdin.readline
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#N = int(input())
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = list(map(int,input().split()))
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
from collections import defaultdict
d = defaultdict(int)
N,M = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A)
for i in range(M):
    b,c = map(int,input().split())
    d[c] += b
d = dict(d)
d = sorted(d.items(),key = lambda x:x[0],reverse = True)
n = len(d)
index = 0
for i in range(n):
    d[i] = list(d[i])
D = [0] * N
index = 0
for k in range(N):
    if d[index][1] != 0:
        d[index][1] -= 1
        D[k] = d[index][0]
    else:
        index += 1
        if index  == n:
            break
        else:
            d[index][1] -= 1
            D[k] = d[index][0]  
Max = 0
for X in range(N+1):
    s = 0
    for v in range(N):
        if v < X:
            s += D[v]
        else:
            s += A[v]
    Max = max(s,Max)
print(Max)


### FIXED CODE ###

import sys
input=sys.stdin.readline
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#N = int(input())
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = list(map(int,input().split()))
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
from collections import defaultdict
d = defaultdict(int)
N,M = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A)
for i in range(M):
    b,c = map(int,input().split())
    d[c] += b
d = dict(d)
d = sorted(d.items(),key = lambda x:x[0],reverse = True)
n = len(d)
index = 0
for i in range(n):
    d[i] = list(d[i])
D = [0] * N
index = 0
for k in range(N):
    if d[index][1] != 0:
        d[index][1] -= 1
        D[k] = d[index][0]
    else:
        index += 1
        if index  == n:
            break
        else:
            d[index][1] -= 1
            D[k] = d[index][0]  
Max = 0

for p in A:
    Max += p
for X in range(N):
    if A[X] < D[X]:
        Max += D[X] - A[X]
    else:
        break
print(Max)
### BUGGY CODE ###

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

c = [[0 for i in range(a[0]+1)] for j in range(a[0]+1)]

for i in range(a[1]):
    n,m = map(int,input().split())
    c[n][m] += 1

d = [[0 for i in range(a[0]+4)] for j in range(a[0]+4)]

for i in range(a[0]+1):
    for j in range(a[0]+1):
        d[i][j+1] = d[i][j] + c[i][j]

for i in range(a[2]):
    n,m = map(int,input().split())
    s = 0
    for j in range(n,m+1):
        s += d[j][m+1] - d[j][j]
    print(s)

### FIXED CODE ###

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

c = [[0 for i in range(a[0]+1)] for j in range(a[0]+1)]

for i in range(a[1]):
    n,m = map(int,input().split())
    c[n][m] += 1

d = [[0 for i in range(a[0]+4)] for j in range(a[0]+4)]

for i in range(a[0]+1):
    for j in range(a[0]+1):
        d[i][j+1] = d[i][j] + c[i][j]

for i in range(a[2]):
    n,m = map(int,input().split())
    s = 0
    for j in range(n,m+1):
        s += d[j][m+1] - d[j][j]
    print(s)
### BUGGY CODE ###

N = int(input())
life = list(map(int, input().split()))
while len(life) >1:
    life.sort()
    life_array = [life[0]] + [i%life[0] for i in life if i%life[0] !=0]
    life = []
    for i in life_array:
        if i not in life:
            life.append(i)

print(life[0])

### FIXED CODE ###

N = int(input())
life = list(map(int, input().split()))
while len(life) >1:
    life.sort()
    life_array = [life[0]] + [i%life[0] for i in life if i%life[0] !=0]
    life = life_array
    #for i in life_array:
        #if i not in life:
            #life.append(i)
 
print(life[0])
### BUGGY CODE ###

N,K = map(int,input().split())
S = input()
tmp = 1
tbl = []
cont = 0
for s in S:
    if int(s) == tmp:
        cont += 1
    else:
        tbl.append(cont)
        cont = 1
        tmp = abs(tmp-1)
tbl.append(cont)
if len(tbl) % 2 == 0:
    tbl.append(0)
max = 0
for i in range(0,len(tbl),2):
    if sum(tbl[i:i+K*2+1]) > max:
        max = sum(tbl[i:i+K*2+1])
print(max)

### FIXED CODE ###

N,K = map(int,input().split())
S = list(map(int,input()))
tmp = 1
nums = []
cont = 0
for s in S:
    if int(s) == tmp:
        cont += 1
    else:
        nums.append(cont)
        cont = 1
        tmp = 1 - tmp
if cont != 0:
    nums.append(cont)
if len(nums) % 2 == 0:
    nums.append(0)
cml = [0]
for n in nums:
    cml.append(cml[-1]+n)
ans = []
for i in range(0,len(cml),2):
    ans.append(cml[min(len(cml)-1,i+K*2+1)]-cml[i])
print(max(ans))
### BUGGY CODE ###

import bisect


def main():
    N = int(input())
    P = list(map(int, input().split()))

    ans = 0
    i = N
    m = 1
    if P[0] == 1:
        print(1)
        return 0

    for j in range(N):
        if len(P) == 1:
            ans+=1
            break

        try:
            i = P.index(m)
            ans += 1
        except ValueError:
            pass
        m += 1
        P = P[0:i]


    print(ans)

    return 0


if __name__ == '__main__':
    main()

### FIXED CODE ###

import bisect
import numpy as np

def main():
    N = int(input())
    P = list(map(int, input().split()))


    ans = 1
    f = P[0]

    for i in range(1, N):
        f_o = P[i]
        if f >= f_o:
            ans+=1
            f = f_o
    print(ans)
    return 0


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

n = int(input())
A = [list(map(int,input().split())) for _ in range(n)]
count=0
match=0
flag=True
while(match!=n*(n-1)//2):
    s=set()
    for i in range(1,n+1):
        if (i not in s) and A[i-1] and (A[i-1][0] not in s):
            j = A[i-1][0]
            if i==A[j-1][0]:
                match+=1
                s|={i,j}
                A[i-1].pop(0)
                A[j-1].pop(0)
    if not s:
        flag = False
        break
    count+=1
print(count if flag else -1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from itertools import product
    n=int(input())
    match=[[0]*n for _ in range(n)]
    V=0 # V=n(n-1)/2
    for i,j in product(range(n),repeat=2):
        if(i>=j): continue
        match[i][j]=V
        V+=1

    def toID(i,j):
        if(i>j): i,j=j,i
        return match[i][j]

    E=[[] for _ in range(V)]
    for i in range(n):
        A=list(map(lambda x:int(x)-1,input().split()))
        for j in range(1,n-1):
            E[toID(i,A[j-1])].append(toID(i,A[j]))
    # あとは頂点VのグラフをdfsしてLongest pathの長さを求める
    # -1: unchecked, -2: checked and uncalculated
    dp=[-1]*V
    flag=True
    def dfs(v):
        global flag
        dp[v]=-2
        length=0
        for nv in E[v]:
            if(dp[nv]==-2):
                print(-1)
                exit()
            if(dp[nv]==-1):
                dfs(nv)
            length=max(length,dp[nv]+1)
        dp[v]=length
    # calculate
    for i in range(V): dfs(i)
    print(max(dp)+1 if(flag) else -1)
resolve()
### BUGGY CODE ###

import numpy as np
N = int(input())
L = np.array(input().split(),dtype = int)

m = min(N,max(L))

r = np.array(np.linspace(1,m,m),int)


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

for i in range(m):
    for j in range(N):
        dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])
        if r[i] == L[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j]+1)

ans = np.max(dp,axis=1)

c = np.array(np.linspace(0,m,m+1))
#print(c)
#print(ans)
d = np.where(ans==c,ans,0)
#print(d)
e = max(d)
if e == 0:
    print(-1)
else:
    print(N-e)

### FIXED CODE ###

import numpy as np
N = int(input())
L = np.array(input().split(),dtype = int)

m = min(N,max(L))

r = np.array(np.linspace(1,m,m),int)


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

for i in range(0,N):
    if dp[i]+1 ==L[i]:
        dp[i+1] = dp[i]+1
    else:
        dp[i+1] = dp[i]

a = max(dp)
if a == 0:
    print(-1)
else:
    print(N-a)
### BUGGY CODE ###

#A1 ~ Aiまでの和 O(logN)
def BIT_query(BIT,idx):
    res_sum = 0
    if idx == 0:
        return 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(BIT,idx,x,n):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return

def main():
    N, Q = map( int, input().split())
    C = list( map( int, input().split()))
    LRI = []
    for i in range(Q):
        l, r = map( int, input().split())
        LRI.append((r,l, i))
    LRI.sort(key=lambda x:x[0])
    lastAppend = [-1]*(N+1)
    BIT = [0]*(N+1)
    ANS = [0]*Q
    now = 1
    for r, l, i in LRI:
        while now <= r:
            c = C[now-1]
            if lastAppend[c] == -1:
                BIT_update(BIT, now, 1,N)
            else:
                BIT_update(BIT, now, 1,N)
                BIT_update(BIT, lastAppend[c],-1,N)
            lastAppend[c] = now                
            now += 1
        ANS[i] = BIT_query(BIT,r) - BIT_query(BIT,l-1)
    print( "\n".join( map( str, ANS)))
    
if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, Q = map( int, input().split())
    C = list( map( int, input().split()))
    LRI = []
    for i in range(Q):
        l, r = map( int, input().split())
        LRI.append((r,l,i))
    LRI.sort(key=lambda x:x[0])
    lastAppend = [-1]*(N+1)
    BIT = [0]*(N+1)
    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        if idx == 0:
            return 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= N:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    ANS = [0]*Q
    now = 1
    for r, l, i in LRI:
        while now <= r:
            c = C[now-1]
            if lastAppend[c] == -1:
                BIT_update(now, 1)
            else:
                BIT_update( now, 1)
                BIT_update(lastAppend[c],-1)
            lastAppend[c] = now                
            now += 1
        ANS[i] = BIT_query(r) - BIT_query(l-1)
    print( "\n".join( map( str, ANS)))
    
    

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

import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def combinations_count(n, r):
    if n == 1:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))



def main():
    S = SI()
    
    ls = []
    for s in range(len(S)):
        ls.append(int(S[s:])%2019)

    import collections

    ls_c = collections.Counter(ls)
    ls_cv = list(ls_c.values())

    ans = 0

    for p in ls_cv:
        ans += combinations_count(p,2)
    ans += ls_c[0]
    print(ans)



if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def combinations_count(n, r):
    if n == 1:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def main():
    S = SI()
    
    ls = []
    len_S = len(S)
    rem = 0

    for s in range(len_S-1,-1,-1):
        rem = (rem+int(S[s])* pow(10, len_S-s-1, 2019))%2019
        ls.append(rem)
    
    import collections

    cls = collections.Counter(ls)
    clsv= list(cls.values())

    ans = 0

    for p in clsv:
        ans += combinations_count(p,2)
    ans += cls[0]
    print(ans)



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

S=input()
N=int(len(S))
for _ in range(N):
    A=S
    S=S.replace("10","")
    S=S.replace("01","")
    if A==S:
        break
print(N-int(len(S)))

### FIXED CODE ###

S=input()
print(min(S.count("0"),S.count("1"))*2)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)

def f(x):
    memo = {}
    if x == 0:
        return True
    elif x < 0:
        return False
    elif x in memo.keys():
        return f(memo[x])
    for i in range(6):
        if f(x-100-i):
            memo[x] = True
            return True
    return False

def main():
    X = int(input())
    print(int(f(X)))

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3

def solve(x):
    if x >= 2000:
        return True
    memo = [True] + [False]*x

    def dp(k):
        if k == 0:
            return True
        for i in range(100,106):
            if k-i >= 0 and memo[k-i]:
                return True
        
        return False
    
    for i in range(x):
        memo[i+1] = dp(i+1)
    return memo[x]



def main():
    X = int(input())
    print(int(solve(X)))
    return

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

K=int(input())
Q=[9,8,7,6,5,4,3,2,1]


for i in range(1,K+1):
    deq=Q.pop()
    mod=deq%10
    if mod!=0:
        Q.insert(0,10*deq+mod-1)
    Q.insert(0,10*deq+mod)
    if mod!=9:
        Q.insert(0,10*deq+mod+1)
print(deq)

### FIXED CODE ###

import queue

K=int(input())
Q=queue.Queue()
for i in range(1,10):
    Q.put(i)

for i in range(1,K+1):
    deq=Q.get()
    mod=deq%10
    if mod!=0:
        Q.put(10*deq+mod-1)
    Q.put(10*deq+mod)
    if mod!=9:
        Q.put(10*deq+mod+1)
print(deq)
### BUGGY CODE ###

from collections import deque

def main():
    N, M = map(int, input().split(' '))
    edge = [[] for i in range(N+1)] #各node(index)から繋がるnode(value)
    for _ in range(M):
        a, b = map(int, input().split(' '))
        edge[a].append(b)
        edge[b].append(a)
    signpost = [0 for i in range(N+1)]
    q = deque([1])
    visited = []
    while q:
        node = q.popleft()
        visited.append(node)
        for e in edge[node]:
            if e in visited:
                continue
            if signpost[e] == 0:
                signpost[e] = node
                q.append(e)
    if 0 in signpost[2:]:
        print('No')
    else:
        print('Yes')
        for i in signpost[2:]:
            print('{:.1g}'.format(i))        

if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque

def main():
    N, M = map(int, input().split(' '))
    edge = [[] for i in range(N+1)]
    for _ in range(M):
        a, b = map(int, input().split(' '))
        edge[a].append(b)
        edge[b].append(a)
    signpost = [None] * (N+1)
    signpost[0] = signpost[1] = 0
    q = deque([1])
    dist = [0 for i in range(N+1)]
    while q:
        node = q.popleft()
        for e in edge[node]:
            if signpost[e] is None:
                dist[e] = dist[node] + 1
                signpost[e] = node
                q.append(e)
    if 0 in signpost[2:]:
        print('No')
    else:
        print('Yes')
        for i in signpost[2:]:
            print(i)        

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

n = int(input())
s = []
for i in range(n):
    s.append(input())

tmp = s[:]
tmp = list(set(tmp))
cnt = []
for i in tmp:
    cnt.append([i, s.count(i)])

ans = []
m = 0
for i in cnt:
    if m == i[1]:
        ans.append(i[0])
    elif m < i[1]:
        ans.clear()
        ans.append(i[0])
        m = i[1]

ans.sort()
for i in ans:
    print(i)

### FIXED CODE ###

from collections import Counter
n = int(input())
s = [input() for _ in range(n)]
c = Counter(s)
m = 0
for v in c.values():
	m = max(m, v)
ans = []
for k, v in c.items():
	if v == m:
		ans.append(k)
ans.sort()
print(*ans, sep="\n")
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]

for i in range(n):
  b = a.copy()
  del b[i]
  print(max(b))

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]

# ほとんどは全体のmax?
m1 = max(a)

# max値が多い場合用に2nd max
m2 = sorted(a)[n-2]

for i in range(n):
  if a[i] == m1:
    print(m2)
  else:
    print(m1)
### BUGGY CODE ###

K,S=map(int,input().split())
cnt=0
for i in range(K+1):
    for t in range(i,K+1):
        for s in range(t,K+1):
            if i+t+s==S:
                if i==t==s:
                    cnt+=1
                elif i==t or i==s or t==s:
                    cnt+=3
                else:
                    cnt+=6
            else:
                continue
print(cnt)

### FIXED CODE ###

K,S=map(int,input().split())
cnt=0
for i in range(K+1):
    for t in range(K+1):
        s=S-i-t
        if 0<=s<=K:
            cnt+=1
        else:
            continue
print(cnt)
### BUGGY CODE ###

N, Q = map(int,input().split())
S = list(input())
TD = [input().split() for _ in range(Q)]

res = [1]*N
for t, d in TD:
  for i in range(N):
    if res[i] == 0 or t not in S:
      continue
    if t == S[i]:
      if d == "L":
        if i == 0:
          res[i] = 0
          break
        res[i-1] += res[i]
        res[i] = 0
      else:
        if i == N-1:
          res[i] = 0
          break
        res[i+1] += res[i]
        res[i] = 0
print(sum(res))

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, Q = map(int,input().split())
S = "0"+input()+"0"
TD = [input().rstrip().split() for _ in range(Q)]
l, r = 0, N+1
for t, d in TD[::-1]:
  if t == S[l] and d == "R":
    l -= 1
  elif t == S[l+1] and d == "L":
    l += 1
  if t == S[r] and d == "L":
    r += 1
  elif t == S[r-1] and d == "R":
    r -= 1
print(max(0, r-l-1))
### BUGGY CODE ###

import itertools
total = int(input())
lis1 = []
for x in range(total):
  lis1.append(input())
lis2 = []
for name in lis1:
  if "M" == name[0] or "A" == name[0] or "R" == name[0] or "C" == name[0] or "H" == name[0]:
    lis2.append(name)
count = 0
for a in itertools.combinations(lis2,3):
  if a[0][0] != a[1][0] and a[1][0] != a[2][0] and a[0][0] != a[2][0]:
    count += 1
print(count)


### FIXED CODE ###

from collections import deque,Counter
from itertools import permutations,combinations,combinations_with_replacement

N = int(input())
rows = [input()[0] for _ in range(N)]

cnt = Counter(rows)

ans = 0
for k in combinations(["M","A","R","C","H"],3):
    ans += cnt[k[0]]*cnt[k[1]]*cnt[k[2]]

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

import numpy as np
N, X, Y = map(int,input().split())
X = X-1
Y = Y-1
NN = np.array([np.zeros(N,dtype='int')]*N)
NN2 = np.array([np.zeros(N,dtype='int')]*N)

  
for i in range(N):
  for j in range(i,N):
    NN[i][j] = j-i
for i in range(N):
  for j in range(i+1,N):
    NN2[i][j] = abs(i-X)+abs(j-Y)+1
#print(NN)
#print(NN2)
NN_max = np.minimum(NN, NN2)
#print(NN_max)
for i in range(1,N):
  print(len(np.where(NN_max==i)[0]))

### FIXED CODE ###

N, X, Y = map(int,input().split())
X = X-1
Y = Y-1
CNT = [0]*(N)
for i in range(N):
  for j in range(i+1,N):
    nn1 = j-i
    nn2 = abs(i-X)+abs(j-Y)+1
    if nn1>nn2:
      CNT[nn2] += 1
    else:
      CNT[nn1] += 1
for i in range(1,N):
  print(CNT[i])
### BUGGY CODE ###

a, b = map(int, input().split())
ans = 1
for i in range(a, b+1):
  ans *= i
if ans < 0:
  print("Negative")
elif ans > 0:
  print("Positive")
else:
  print("Zero")

### FIXED CODE ###

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

if a<=0 and 0<=b:
  print("Zero")  
elif a < 0 and min(b-a,-a)%2 == 0:
  print("Negative")
else:
  print("Positive")
### BUGGY CODE ###

import math
m,n=map(int,input().split())
f=abs(m-n)
if f == 0:
  ans=2*math.factorial(m)*math.factorial(n)
  print(ans)
  exit()
elif f == 1:
  ans=math.factorial(m)*math.factorial(n)
  print(ans)
  exit()
else:
  print(0)
  exit()

### FIXED CODE ###

import math
MOD = 1000000007
m,n=map(int,input().split())
f=abs(m-n)
if f == 0:
  ans=2*math.factorial(m)*math.factorial(n)%MOD
  print(ans)
  exit()
elif f == 1:
  ans=math.factorial(m)*math.factorial(n)%MOD
  print(ans)
  exit()
else:
  print(0)
  exit()
### BUGGY CODE ###

# D Knapsack 1
import sys

sys.setrecursionlimit(10**8)

n, w = map(int,input().split())
wv_list = [[int(x) for x in input().split()] for y in range(n)]

dp = [[float("-Inf")] * (w+1) for _ in range(n+1)]
dp[0] = [0]*(w+1)
memo = [[False] * (w+1) for _ in range(n+1)]
memo[0] = [True] * (w+1)

def dp_solve(i, j):
    if memo[i][j]:
        return dp[i][j]
    _w,_v = wv_list[i-1]
    _ret = 0
    if j-_w < 0:
        _ret = dp_solve(i-1, j)
    else:
        _ret = max(dp_solve(i-1, j), dp_solve(i-1, j-_w) + _v)
    dp[i][j] = _ret
    memo[i][j] = True
    return _ret

print(dp_solve(n, w))

### FIXED CODE ###

# D Knapsack 1

from collections import deque

n, w = map(int,input().split())
wv_list = deque([[int(x) for x in input().split()] for y in range(n)])

dp = [[float("-Inf")] * (w+1) for _ in range(n+1)]
dp[0] = [0]*(w+1)

for i in range(n):
    _w,_v = wv_list.popleft()
    for j in range(w+1):
        if j-_w < 0:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j-_w]+_v)

print(dp[n][w])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
inf = 10**9
H, N = map(int, input().split())
AB = []
for n in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))
AB.sort(reverse=True, key=lambda x: x[0])
dp = [inf] * (H + 10 ** 4)
dp[0] = 0
for a, b in AB:
    for h in range(H):
        if dp[h] != inf:
            tmp = dp[h] + b
            if tmp < dp[h + a]:
                dp[h + a] = tmp
print(min(dp[H:]))


### FIXED CODE ###

inf = 10 ** 9


def main():
    H, N = map(int, input().split())
    AB = []
    for n in range(N):
        a, b = map(int, input().split())
        AB.append((a, b))
    AB.sort(reverse=True, key=lambda x: x[0])
    dp = [inf] * (H + 10 ** 4)
    dp[0] = 0
    for a, b in AB:
        for h in range(H):
            # if dp[h] == inf:
            #     continue
            # else:
            #     dp[h+a] = min(dp[h]+b, dp[h+a])
            if dp[h] != inf:
                tmp = dp[h] + b
                if tmp < dp[h + a]:
                    dp[h + a] = tmp
    print(min(dp[H:]))


main()
### BUGGY CODE ###

N, Q = map(int, input().split(" "))
S = input()
for i in range(Q):
    l, r = map(int, input().split(" "))
    ans = 0
    #x = []
    for j in range(l-1, r-1):
        #jにl-1からr-2までを代入する
        #x.append(S[j])
        if S[j]=="A":
            if S[j+1]=="C":
                ans += 1
            #else:
                #ans += 0
        #else:
            #ans += 0
    print(ans)
    #print(x)


### FIXED CODE ###

N, Q = map(int, input().split(" "))
S = input()
t = [0]*(N+1)
#N+1個の0を持つリスト
for i in range(N):
    if S[i:i+2] == "AC":
        #S[x, y]は文字列Sのx番目からy-1番目までの文字列
        t[i + 1] = t[i] + 1
    else:
        t[i + 1] = t[i]
#S=0123...
#T=0123...

for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1]-t[l-1])
#l, r = 123...
#r番目までのときのACの数はt[r-1]