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

import sys
input = sys.stdin.readline

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))


def main():
    N, M =two_int()

    key_list=[]
    treasures=[]

    for i in range(M):
        mon,_ =two_int()
        key_list.append(mon)
        temp = map(lambda x: 1<<(x-1), many_int())
        sums = sum(temp)
        treasures.append(sums)

    max_index=2**N
    INF=10**15

    dp=[INF for i in range(max_index)]
    sets=set([j for j in range(M)])
    dp_i=[set([]) for i in range(max_index)]
    dp[0]=0

    for i in range(max_index-1):
        
        lists = list( sets - set(dp_i[i]))
        min_key=0
        for j in lists:
            new_i = int(bin(treasures[j] | i),2)
            cost = dp[i] + key_list[j]
            dp[new_i] = min(dp[new_i], cost) 
            min_key = j
        dp_i[i] = dp_i[i] | set([min_key])
        
    goal_index=max_index-1
    if dp[goal_index]!=INF:
        print(dp[goal_index])
    else:
        print(-1)

main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))


def main():
    N, M =two_int()

    key_list=[]
    treasures=[]
    check={}

    for i in range(M):
        mon,_ =two_int()
        temp = map(lambda x: 1<<(x-1), many_int())
        sums = sum(temp)
        
        if sums in check:
            if check[sums] > mon:
                check[sums]=mon
        else:
            check[sums]=mon
            
    for k,v in check.items():
        key_list.append(v)
        treasures.append(k)

    max_index=2**N
    INF=10**15

    dp=[INF for i in range(max_index)]
    dp[0]=0
    M=len(key_list)

    for i in range(max_index-1):
        for j in range(M):
            new_i = int(bin(treasures[j] | i),2)
            cost = dp[i] + key_list[j]
            dp[new_i] = min(dp[new_i], cost) 
        
    goal_index=max_index-1
    if dp[goal_index]!=INF:
        print(dp[goal_index])
    else:
        print(-1)

main()
### BUGGY CODE ###

from collections import defaultdict
import heapq
n,m,s,t=list(map(int, input().strip().split()))
links_y=defaultdict(list)
links_s=defaultdict(list)
for i in range(m):
    u,v,a,b=list(map(int, input().strip().split()))
    links_y[u-1].append((v-1,a))
    links_y[v-1].append((u-1,a))
    links_s[u-1].append((v-1,b))
    links_s[v-1].append((u-1,b))

def dijkstra(frm, links):
    dist=[float('inf')]*n
    dist[frm]=0
    Q=[(0,frm)]
    heapq.heapify(Q)
    while Q:
        d,u = heapq.heappop(Q)
        for v,dd in links[u]:
            if dist[v]> d+dd:
                dist[v]=dd+d
                heapq.heappush(Q,(dist[v],v))
    return dist
yen_cost=dijkstra(s-1,links_y)
snk_cost=dijkstra(t-1,links_s)
sumyensnk=[i+j for i,j in zip(yen_cost,snk_cost)]
min_snk=[float('inf')]*n
tmp=float('inf')
for i in range(n)[::-1]:
    min_snk[i] = min(sumyensnk[i],tmp)
    tmp = min_snk[i]
money=10**15
for sumsnk in min_snk:
    print(money-sumsnk)

### FIXED CODE ###

import heapq
n,m,s,t=list(map(int, input().strip().split()))
links_y=[[]for i in range(n) ]
links_s=[[]for i in range(n) ]
INF=float('inf')
for i in range(m):
    u,v,a,b=list(map(int, input().strip().split()))
    links_y[u-1].append((v-1,a))
    links_y[v-1].append((u-1,a))
    links_s[u-1].append((v-1,b))
    links_s[v-1].append((u-1,b))

def dijkstra(frm, links):
    dist=[INF]*n
    dist[frm]=0
    Q=[(0,frm)]
    heapq.heapify(Q)
    while Q:
        d,u = heapq.heappop(Q)
        for v,dd in links[u]:
            if dist[v]> d+dd:
                dist[v]=dd+d
                heapq.heappush(Q,(dist[v],v))
    return dist
yen_cost=dijkstra(s-1,links_y)
snk_cost=dijkstra(t-1,links_s)
sumyensnk=[i+j for i,j in zip(yen_cost,snk_cost)]
min_snk=[INF]*n
tmp=INF
for i in range(n)[::-1]:
    min_snk[i] = min(sumyensnk[i],tmp)
    tmp = min_snk[i]
money=10**15
for sumsnk in min_snk:
    print(money-sumsnk)
### BUGGY CODE ###

N,M,V = list(map(int,input().split()))
A=list(map(int,input().split()))
B=list(map(int,input().split()))
S=list(map(int,A+B))
ans=0
time=0
if sum(S)<=V:
  print(N+M)
  exit()
K=sorted(S)
for i in range(N+M):
  if K[0]+time>V:
    print(ans)
    exit()
  else:
    time+=K[0]
    K.pop(0)
    ans+=1

### FIXED CODE ###

a,b,money=list(map(int,input().split()))
A=[0]+list(map(int,input().split()))
B=[0]+list(map(int,input().split()))
for i in range(1,a+1):
  A[i]+=A[i-1]
for j in range(1,b+1):
  B[j]+=B[j-1]
ans=0
b_cnt=b
for a_cnt in range(a+1):
  if A[a_cnt]>money:
    continue
  while A[a_cnt]+B[b_cnt]>money:
    b_cnt-=1
  ans=max(ans,a_cnt+b_cnt)
print(ans)
### BUGGY CODE ###

from copy import deepcopy

N, M, L = map(int, input().split())
inf = 10**9 + 1
dist = [[inf] * N for i in range(N)]
for i in range(M):
    A, B, C = map(int, input().split())
    dist[A-1][B-1] = dist[B-1][A-1] = C

# Floyd-Warshall algorithm
for k in range(N):
    for i in range(N):
        for j in range(i+1, N):
            min_dist = min(dist[i][j], dist[i][k] + dist[k][j])
            dist[i][j] = dist[j][i] = min_dist

refill = [list(map(lambda x: 1 if x <= L else inf, d)) for d in dist]
for k in range(N):
    for i in range(N):
        for j in range(i+1, N):
            min_refill = min(refill[i][j], refill[i][k] + refill[k][j])
            refill[i][j] = refill[j][i] = min_refill

Q = int(input())
for i in range(Q):
    s, t = map(int, input().split())
    print(refill[s-1][t-1] - 1 if refill[s-1][t-1] < inf else -1)


### FIXED CODE ###

from scipy.sparse.csgraph import floyd_warshall
import numpy as np

N, M, L = map(int, input().split())
inf = 10**9 + 1
dist = [[inf] * N for i in range(N)]
for i in range(M):
    A, B, C = map(int, input().split())
    dist[A-1][B-1] = dist[B-1][A-1] = C

dist = floyd_warshall(dist, directed=False)
dist = np.where(dist <= L, 1, inf)
dist = floyd_warshall(dist, directed=False)
dist = np.where(dist < inf, dist-1, -1)

Q = int(input())
for i in range(Q):
    s, t = map(int, input().split())
    print(int(dist[s-1, t-1]))
### BUGGY CODE ###

from functools import reduce
from operator import mul

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

j = 1000000000000000000

ans = 1

ans = reduce(mul, An)


if ans <= j :
    print(ans)
    
else :
    print('-1')



### FIXED CODE ###


n = int(input())
An = [int(x) for x in input().split()]
An.sort(reverse=True)

if 0 in An:
    print(0)
    exit()

j = 10 ** 18
ans = 1
for i in range(n):
    if ans > j:
        print(-1)
        quit()
    ans *= An[i]

if ans > j :
    print(-1)
    
else :
    print(ans)
### BUGGY CODE ###

import bisect as bi
N=int(input())
L=list(map(int,input().split()))

count=0
l=sorted(L)
#print(l)
for i in range(N-2):
    for j in range(i+1,N-1):
        index=bi.bisect_right(l[j+1:],l[i]+l[j]-1)
        count+=index
        
print(count)

### FIXED CODE ###

import bisect as bi
N=int(input())
L=list(map(int,input().split()))

count=0
l=sorted(L)
#print(l)
for i in range(N-2):
    for j in range(i+1,N-1):
        count+=bi.bisect_left(l,l[i]+l[j],j+1)-j-1
         
print(count)
### BUGGY CODE ###

def main():
    from fractions import gcd
    n, m = map(int, input().split())
    ans = 1
    l = int(m / n)
    for i in range(2, l + 1):
        p, q = divmod(m, i)
        if q != 0 or p < n:
            continue

        ans = max(ans, i)

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n, m = map(int, input().split())
    for i in range(int(m / n), 0, -1):
        if m % i == 0:
            print(i)
            break


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

n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
ldp=[[0]*k for _ in xrange(n)]
rdp=[[0]*k for _ in xrange(n)]
for i in xrange(n):
    ldp[i][0]=True
    rdp[i][0]=True
    if a[i]<k:
        ldp[i][a[i]]=True
    if a[n-i-1]<k:
        rdp[i][a[n-1-i]]=True
for i in xrange(1,n):
    for j in xrange(k):
        if j-a[i]>=0:
            ldp[i][j]|=ldp[i-1][j-a[i]]|ldp[i-1][j]
        else:
            ldp[i][j]|=ldp[i-1][j]
        if j-a[n-1-i]>=0:
            rdp[i][j]|=rdp[i-1][j-a[n-1-i]]|rdp[i-1][j]
        else:
            rdp[i][j]|=rdp[i-1][j]
rsum=[[0]*k for _ in xrange(n)]
for i in xrange(n):
    for j in xrange(k):
        if j==0:
            rsum[i][j]=rdp[i][j]
        else:
            rsum[i][j]=rsum[i][j-1]+rdp[i][j]
cnt=0
for i in xrange(n):
    if k-a[i]<=0:
        cnt+=1
        continue
    for j in xrange(k):
        if i==0:
            left=0
        elif i==n-1:
            if ldp[i-1][j] and a[i]+j>=k:
                cnt+=1
                break
            continue
        else:
            if ldp[i-1][j]:
                left=j
            else:
                continue
        if k-a[i]-left<=0:
            cnt+=1
            break
        if rsum[n-2-i][k-1-left]-rsum[n-2-i][k-a[i]-left-1]:
            cnt+=1
            break
print n-cnt

### FIXED CODE ###

n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
a.sort()
used=[False]*n
idx=n-1
cnt=0
while True:
    if idx-cnt<0:
        break
    tmp=sum(a[idx-cnt:idx+1])
    if tmp<k:
        cnt+=1
        continue
    for i in xrange(idx-cnt,idx+1):
        used[i]=True
    tmp-=a[idx-cnt]
    for i in xrange(idx-cnt-1,-1,-1):
        if tmp+a[i]>=k:
            used[i]=True
        else:
            break
    idx-=1
    cnt=0
ans=0
for i in xrange(n):
    if not used[i]:
        ans+=1
print ans
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline

def main():
    h, w = map(int, input().split())
    board = [list(input().strip()) for i in range(h)]

    white = [[False] * w for i in range(h)]

    q = deque()
    for y in range(h):
        for x in range(w):
            if board[y][x] == ".":
                white[y][x] = True
            else:
                q.append((x, y, 0))

    step = 0
    len_ = len(q)
    while len_ > 0:
        x, y, step = q.popleft()
        len_ -= 1
        for n_x, n_y in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:
            if 0 <= n_x and n_x < w and 0 <= n_y and n_y < h:
                if white[n_y][n_x]:
                    q.append((n_x, n_y, step+1))
                    len_ += 1
                    white[n_y][n_x] = False

    print(step)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.readline

def main():
    H, W = map(int, input().split())

    INF = int(1e7)
    a = np.array([list(map(lambda x: 0 if x=="#" else INF, list(input().strip()))) for i in range(H)])

    for i in range(H-1):
        a[i+1] = np.minimum(a[i] + 1, a[i+1])
    for i in range(H-1, 0, -1):
        a[i-1] = np.minimum(a[i] + 1, a[i-1])
    
    for i in range(W-1):
        a[:, i+1] = np.minimum(a[:, i] + 1, a[:, i+1])
    for i in range(W-1, 0, -1):
        a[:, i-1] = np.minimum(a[:, i] + 1, a[:, i-1])

    print(np.max(a))

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

R,C,K = map(int,input().split())
dp = [[[0 for l in range(4)] for _ in range(C+1)] for f in range(R+1)]
vl = [[0 for _ in range(C+1)] for f in range(R+1)]

for i in range(K):
	r,c,v = map(int,input().split())
	vl[r][c] = v

for i in range(1, R+1):
	for j in range(1, C+1):
		dp[i][j][0] = max(dp[i][j][0], dp[i-1][j][0], dp[i-1][j][1], dp[i-1][j][2], dp[i-1][j][3])
		dp[i][j][3] = max(dp[i][j-1][3], dp[i][j][2]+vl[i][j], dp[i][j-1][2]+vl[i][j])
		dp[i][j][2] = max(dp[i][j-1][2], dp[i][j][1]+vl[i][j], dp[i][j-1][1]+vl[i][j])
		dp[i][j][1] = max(dp[i][j-1][1], dp[i][j][0]+vl[i][j], dp[i][j-1][0]+vl[i][j])

print(max(dp[R][C][0], dp[R][C][1], dp[R][C][2], dp[R][C][3]))

### FIXED CODE ###

R,C,K = map(int,input().split())
dp0 = [[0 for _ in range(C+1)] for f in range(R+1)]
dp1 = [[0 for _ in range(C+1)] for f in range(R+1)]
dp2 = [[0 for _ in range(C+1)] for f in range(R+1)]
dp3 = [[0 for _ in range(C+1)] for f in range(R+1)]
vl = [[0 for _ in range(C+1)] for f in range(R+1)]

for i in range(K):
	r,c,v = map(int,input().split())
	vl[r][c] = v

for i in range(1, R+1):
	for j in range(1, C+1):
		dp0[i][j] = max(dp0[i][j], dp0[i-1][j], dp1[i-1][j], dp2[i-1][j], dp3[i-1][j])
		dp3[i][j] = max(dp3[i][j], dp3[i][j-1], dp2[i][j-1]+vl[i][j], dp2[i][j]+vl[i][j])
		dp2[i][j] = max(dp2[i][j], dp2[i][j-1], dp1[i][j-1]+vl[i][j], dp1[i][j]+vl[i][j])
		dp1[i][j] = max(dp1[i][j], dp1[i][j-1], dp0[i][j-1]+vl[i][j], dp0[i][j]+vl[i][j])

print(max(dp0[R][C], dp1[R][C], dp2[R][C], dp3[R][C]))
### BUGGY CODE ###

n, m = map(int, input().split())
a = []
for i in range(m):
    l, r = map(int, input().split())
    if i == 0: a = set([int(i) for i in range(l, r+1)])
    else:
        a &= set([int(i) for i in range(l, r+1)])
print(len(a))

### FIXED CODE ###

n, m = map(int, input().split())
a = []
flag = True
for i in range(m):
    l, r = map(int, input().split())
    if i == 0: 
        l1 = l
        r1 = r
    else:
        if r < l1 or r1 < l:
            flag = False
        elif l1 < l:
            l1 = l
        elif r1 > r:
            r1 = r
if flag: print(r1-l1+1)
else: print(0)
### BUGGY CODE ###

import sys
import math
from copy import deepcopy
from collections import deque, defaultdict
from operator import mul
from functools import reduce
sys.setrecursionlimit(20000000)

# input = sys.stdin.readline


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

    for i in range(M):
        stuff[stuff.index(max(stuff))] = math.floor(stuff[stuff.index(max(stuff))] / 2)

    print(sum(stuff))


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import math
from copy import deepcopy
from collections import deque, defaultdict
from heapq import heappush, heappop
from operator import mul
from functools import reduce
sys.setrecursionlimit(20000000)

input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    stuff = []
    for x in input().split():
        heappush(stuff, -int(x))

    for i in range(M):
        heappush(stuff, -math.floor(-heappop(stuff) / 2))

    print(-sum(stuff))


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

def mp(a,n,mod):
    if n==1:
        return a%mod
    aq=(mp(a,n//2,mod))**2
    ar=a**(n%2)
    return (((aq)%mod)*ar)%mod


def s_comb(n,k):
    s=1
    r=min(k,n-k)
    p=10**9+7
    for c in range(r):
        s=(s*(n-c)*mp(c+1,p-2,p))%p
    return s

x,y=map(int,input().split())
if (x+y)%3!=0 or 2*y<x or 2*x<y:
    print(0)
else:
    r=int(min(2*y-x,2*x-y)/3)
    print(s_comb(int((x+y)/3),r))


### FIXED CODE ###



def s_comb(n,k):
    s=1
    r=min(k,n-k)
    p=10**9+7
    for c in range(r):
        s=(s*(n-c)*pow(c+1,p-2,p))%p
    return s

x,y=map(int,input().split())
if (x+y)%3!=0 or 2*y<x or 2*x<y:
    print(0)
else:
    r=int(min(2*y-x,2*x-y)/3)
    print(s_comb(int((x+y)/3),r))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def solve():
    INF = float('inf')

    def WarshallFloyd(adjList, INF):
        numV = len(adjList)
        D = [[INF]*numV for _ in range(numV)]
        for u, adj in enumerate(adjList):
            for v, wt in adj:
                D[u][v] = wt
            D[u][u] = 0

        for k in range(numV):
            Dk = D[k]
            for i in range(numV):
                Di = D[i]
                Dik = Di[k]
                for j in range(numV):
                    D2 = Dik + Dk[j]
                    if D2 < Di[j]:
                        D[i][j] = D2

        return D

    N, M, L = map(int, input().split())
    adjL = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        a, b = a-1, b-1
        adjL[a].append((b, c))
        adjL[b].append((a, c))
    Q = int(input())
    querys = [tuple(map(int, input().split())) for _ in range(Q)]

    cost1ss = WarshallFloyd(adjL, INF)

    adjL2 = [[] for _ in range(N)]
    for a in range(N):
        for b in range(a+1, N):
            if cost1ss[a][b] <= L:
                adjL2[a].append((b, 1))
                adjL2[b].append((a, 1))

    cost2ss = WarshallFloyd(adjL2, INF)

    anss = []
    for s, t in querys:
        s, t = s-1, t-1
        cost = cost2ss[s][t]
        if cost == INF:
            anss.append(-1)
        else:
            anss.append(cost-1)

    print('\n'.join(map(str, anss)))


solve()


### FIXED CODE ###

def solve():
    INF = float('inf')

    def WarshallFloyd(adjList):
        numV = len(adjList)
        D = [[INF]*numV for _ in range(numV)]
        for u, adj in enumerate(adjList):
            for v, wt in adj:
                D[u][v] = wt
            D[u][u] = 0
        for k in range(numV):
            Dk = D[k]
            for i in range(numV):
                Di = D[i]
                Dik = Di[k]
                for j in range(numV):
                    D2 = Dik + Dk[j]
                    if D2 < Di[j]:
                        D[i][j] = D2
        return D

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

    D = WarshallFloyd(adjL)

    adjL2 = [[] for _ in range(N)]
    for i in range(N):
        for j in range(i+1, N):
            if D[i][j] <= L:
                adjL2[i].append((j, 1))
                adjL2[j].append((i, 1))

    D = WarshallFloyd(adjL2)

    Q = int(input())
    anss = []
    for _ in range(Q):
        s, t = map(int, input().split())
        s, t = s-1, t-1
        if D[s][t] == INF:
            anss.append(-1)
        else:
            anss.append(D[s][t]-1)

    print('\n'.join(map(str, anss)))


solve()
### BUGGY CODE ###

N = int(input()) 
A = []

for j in range(N):
    A += [input()]

for i in range(N):
    S = A.copy()
    del S[i]
    print(max(S))
    

### FIXED CODE ###

N = int(input()) 
A = []
 
for j in range(N):
    A += [int(input())]

maxnumber = max(A)
secondmax = sorted(A)[-2]

for i in range(N):
    if(maxnumber != A[i]):
       print(maxnumber)
    else:
       print(secondmax)
### BUGGY CODE ###

import itertools
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
DP = [[1000000 for i in range(N)] for j in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    DP[a - 1][b - 1] = c
    DP[b - 1][a - 1] = c

for i in range(N):
    for j in range(N):
        for k in range(N):
            DP[i][j] = min([DP[i][j], DP[i][k] + DP[k][j]])
ans = 0
for i in range(1, R):
    ans += DP[r[i - 1] - 1][r[i] - 1]


root = list(itertools.permutations(r))
finalans = 100000000
for i in root:
    ans = 0
    for j in range(1, R):
        ans += DP[i[j - 1] - 1][i[j] - 1]
    if ans < finalans:
        finalans = ans
        
print(finalans)

### FIXED CODE ###

def ABC073D():
    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    ABC = [list(map(int, input().split())) for i in range(M)]
    root = [[1000000000 for i in range(N)] for j in range(N)]
    for i, j, k in ABC:
        root[i - 1][j - 1] = k
        root[j - 1][i - 1] = k

    import itertools
    def kumiawase(list_name):  # list_name(リスト)のすべての並び替え
        return itertools.permutations(list_name)


    from scipy.sparse import csgraph
    root = csgraph.floyd_warshall(root)

    a = kumiawase(r)
    ans = float("inf")
    for i in a:
        key = 0
        for j in range(len(i) - 1):
            key += root[i[j] - 1][i[j + 1] - 1]
        if ans > key:
            ans = int(key)
    #print(root)
    print(ans)
ABC073D()
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
b = []
for i in range(n):
    b.append(a[i])
    b.reverse()
print(*b)

### FIXED CODE ###

from collections import deque
n = int(input())
a = [int(i) for i in input().split()]
b = deque()
for i, x in enumerate(a):
    if i%2 == n%2:
        b.append(x)
    else:
        b.appendleft(x)
print(*b)
### BUGGY CODE ###

N, C = map(int, input().split())
program = []
program_list = [False for _ in range((((10 ** 5) * 2) + 10))]
for _ in range(C + 1):
    program.append(program_list.copy())

for _ in range(N):
    s, t, c = map(int, input().split())
    s -= 0.5
    s *= 2
    s = int(s)
    t *= 2
    for i in range(s, t):
        program[c][i] = True

max_c = 0
for i in range(len(program_list)):
    c = 0
    for j in range(1, C + 1):
        if program[j][i]:
            c += 1
    if c > max_c:
        max_c = c
print(max_c)


### FIXED CODE ###

N, C = map(int, input().split())
program = []
program_list = [False for _ in range((((10 ** 5) * 2) + 10))]
for _ in range(C + 1):
    program.append(program_list.copy())

for _ in range(N):
    s, t, c = map(int, input().split())
    s2 = (t * 2) - ((s * 2) - 1)
    program[c][(s * 2) - 1:t * 2] = [True] * s2

max_c = 0
for i in range(len(program_list)):
    c = 0
    for j in range(1, C + 1):
        if program[j][i]:
            c += 1
        if c > max_c:
            max_c = c
print(max_c)
### BUGGY CODE ###

s=input()
cnt=0
le=len(s)
for i in range(1,le-3):
    for j in range(i+3,le+1):
        number=s[i-1:j]
        if int(number)%2019==0:
            cnt+=1
print(cnt)

### FIXED CODE ###

s=input()[::-1]
mod=[0]*2019
mod[0]=1
x=1
num=0
ans=0

for t in s:
    num += int(t) * x
    num %= 2019
    x *= 10
    x %= 2019
    mod[num] +=1

for u in mod:
    ans += u*(u-1)//2

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

s = input()
k = 0
while True:
  if "10" in s:
    i = s.index("10")
    s = list(s)
    s.pop(i)
    s.pop(i)
    s = "".join(s)
    k += 2
  elif "01" in s:
    i = s.index("01")
    s = list(s)
    s.pop(i)
    s.pop(i)
    s = "".join(s)
    k += 2
  else:
    print(k)
    break

### FIXED CODE ###

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

n,q = [int(i) for i in input().split()]
s = input()
ac_loc = []
flag = False
for i in range(n-1):
  if flag:
    flag = False
    continue
  if s[i:i+2] == 'AC':
    ac_loc.append(i)
    flag = True

l = []
r = []
for i in range(q):
  l_tmp, r_tmp = [int(j) for j in input().split()]
  l.append(l_tmp-1)
  r.append(r_tmp-1)
  
for i in range(q):
  ans = sum((l[i]<=j and j+1<=r[i]) for j in ac_loc)
  print(ans)

### FIXED CODE ###

n,q = [int(i) for i in input().split()]
s = input()
l = []
r = []
for i in range(q):
  l_tmp, r_tmp = [int(j) for j in input().split()]
  l.append(l_tmp-1)
  r.append(r_tmp-1)
  
ac_cnt = s.count('AC')
r_cnt = [ac_cnt]
l_cnt = [0]
for i in range(1,n):
  if s[i-1:i+1] == 'AC':
    r_cnt.append(r_cnt[i-1]-1)
    l_cnt.append(l_cnt[i-1]+1)
  else:
    r_cnt.append(r_cnt[i-1])
    l_cnt.append(l_cnt[i-1])
    
for i in range(q):
  ans = r_cnt[l[i]] + l_cnt[r[i]] - ac_cnt
  print(ans)