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

'''
expv[i][j][k] = 1 +
                expv[i-1][j][k] * (i / N) +
                expv[i+1][j-1][k] * (j / N) +
                expv[i][j+1][k-1] * (k / N) + 
                expv[i][j][k] * ((N - i - j - k) / N)

nonlp = 1 - (N-i-j-k) / N 
expv[i][j][k] =  (1 + ~~) / nonlp

'''

N = int(input())

sushi_count = {1:0, 2:0, 3:0}
for a in map(int, input().split()):
    sushi_count[a] += 1

expv = [[[-1] * (sushi_count[3]+1) for i in range(N-sushi_count[1]+1)] for i in range(N+1)]

expv[0][0][0] = 0.0

def get_expv(i, j, k):
    result = 0.0
    if expv[i][j][k] != -1:
        return expv[i][j][k]
    nonlp = 1.0 - (N-i-j-k) / N
    result += 1
    if i != 0:
        result += get_expv(i-1, j, k) * (i / N)
    if j != 0:
        result += get_expv(i+1, j-1, k) * (j / N)
    if k != 0:
        result += get_expv(i, j+1, k-1) * (k / N)
    result /= nonlp
    expv[i][j][k] = result
    return result

print(get_expv(sushi_count[1], sushi_count[2], sushi_count[3]))


### FIXED CODE ###

import numpy as np
from numba import njit


@njit('f8(i8,i8,i8,i8,f8[:,:,:])')
def get_expv(N, i, j, k, expv):
    result = 0.0
    if expv[i][j][k] != -1:
        return expv[i][j][k]
    nonlp = 1.0 - (N-i-j-k) / N
    result += 1
    if i != 0:
        result += get_expv(N, i-1, j, k, expv) * (i / N)
    if j != 0:
        result += get_expv(N, i+1, j-1, k, expv) * (j / N)
    if k != 0:
        result += get_expv(N, i, j+1, k-1, expv) * (k / N)
    result /= nonlp
    expv[i][j][k] = result
    return result

def main():
    N = int(input())

    sushi_count = {1:0, 2:0, 3:0}
    for a in map(int, input().split()):
        sushi_count[a] += 1
    sh = (N+1, N-sushi_count[1]+1, sushi_count[3]+1)
    expv = np.full(sh, -1.0)

    expv[0][0][0] = 0.0

    print(get_expv(N, sushi_count[1], sushi_count[2], sushi_count[3], expv))

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

from collections import deque
S = input()
S = [S[i] for i in range(len(S))]
S = deque(S)                         
Q = int(input())
rev = 1
for i in range(Q):
  comm = input()
  if comm == "1":
    rev *= -1
  else:
    T, F, C = comm.split()
    F = int(F) * 2 - 3
    if rev * F == 1:
      S.append(C)
    else:
      S.appendleft(C)
ans = ""
for i in range(len(S)):
  ans += S[i * rev + (rev-1) // 2]
print(ans)
      

### FIXED CODE ###

from collections import deque
S = input()
S = [S[i] for i in range(len(S))]
S = deque(S)                         
Q = int(input())
rev = 1
for i in range(Q):
  comm = input()
  if comm == "1":
    rev *= -1
  else:
    T, F, C = comm.split()
    F = int(F) * 2 - 3
    if rev * F == 1:
      S.append(C)
    else:
      S.appendleft(C)
S = list(S)
ans = ""
for i in range(len(S)):
  ans += S[i * rev + (rev-1) // 2]
print(ans)
### BUGGY CODE ###

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

minH = int(1e9)
for xyh in xyhs:
  minH = min(minH, xyh[2])

cx, cy, H = 0, 0, 0
for h in range(minH, int(1e9)+200):
  if H != 0: break
  for x in range(101):
    if H != 0: break
    for y in range(101):
      if H != 0: break
      for xyh in xyhs:
        if max(h - abs(xyh[0]-x) - abs(xyh[1]-y), 0) != xyh[2]:
          break
      else:
        cx, cy, H = x, y, h
        break

print(cx, cy, H)


### FIXED CODE ###

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

minH = 0
for xyh in xyhs:
  minH = max(minH, xyh[2])

cx, cy, H = 0, 0, 0
for h in range(minH, minH+200):
  if H != 0: break
  for x in range(101):
    if H != 0: break
    for y in range(101):
      if H != 0: break
      for xyh in xyhs:
        if max(h - abs(xyh[0]-x) - abs(xyh[1]-y), 0) != xyh[2]:
          break
      else:
        cx, cy, H = x, y, h
        break

print(cx, cy, H)
### BUGGY CODE ###

from scipy.sparse.csgraph import csgraph_from_dense, dijkstra
inf = 10 ** 10

n = int(input())
edge = [[inf] * n for i in range(n)]
for _  in range(n - 1):
    a, b, c = map(int,input().split())
    edge[a - 1][b - 1] = c

G = csgraph_from_dense(edge, null_value = inf)
q, k = map(int,input().split())
d = dijkstra(G, False, indices= k - 1)
for _ in range(q):
    x, y = map(int,input().split())
    dis = d[x - 1] + d[y - 1]
    print(int(dis))


### FIXED CODE ###

#BFS
from collections import deque
def bfs(G):
    q=deque()
    q.append((k - 1, -1, 0))

    while q:
        #qの先頭を取り出す
        V, P, C = q.popleft()
        for new, cost in G[V]:
            if new == P:continue
            temp = C + cost
            q.append((new, V, temp))
            stand[new] = temp

n = int(input())
route_list = [[] for i in range(n)]  # 辺の移動の際のコスト
for i in range(n - 1):
    s, t, d = map(int, input().split())
    route_list[s - 1].append((t - 1, d))
    route_list[t - 1].append((s - 1, d))
# print(route_list)
q, k = map(int,input().split())


stand = [0] * n
bfs(route_list)
for i in range(q):
    x, y = map(int,input().split())
    temp = stand[x - 1] + stand[y - 1]
    print(temp)
### BUGGY CODE ###

from heapq import heappush, heappop

N, D, A = map(int, input().split())

data = []
for _ in range(N):
	x, h = map(int, input().split())
	heappush(data, (x, 0, h))

total = 0
height = 0
while data:
	x, type, h = heappop(data)
	if type == 0:
		if height < h:
			count = (h - height + A - 1) // A
			total += count
			height += count * A
			heappush(data, (x + D * 2, 1, count * A))
	else:
		height -= h

print(total)


### FIXED CODE ###

N, D, A = map(int, input().split())

data = []
for _ in range(N):
	data.append(tuple(map(int, input().split())))

data.sort()

queue = []
i = 0
j = 0
total = 0
height = 0
while i < N:
	if j >= len(queue) or data[i][0] <= queue[j][0]:
		x, h = data[i]
		i += 1
		if height < h:
			count = (h - height + A - 1) // A
			total += count
			height += count * A
			queue.append((x + D * 2, count * A))
	else:
		height -= queue[j][1]
		j += 1

print(total)
### BUGGY CODE ###

from collections import Counter
from collections import defaultdict
import math
import random
import heapq as hq
from math import sqrt
import sys
from functools import reduce


def input():
    return sys.stdin.readline().strip()


def iinput():
    return int(input())


def tinput():
    return input().split()


def rinput():
    return map(int, tinput())


def rlinput():
    return list(rinput())


mod = int(1e9)+7


def factors(n):
    return set(reduce(list.__add__,
                      ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))


# ----------------------------------------------------

if __name__ == "__main__":
    n, weigh = rinput()
    w, v = [], []
    for i in range(n):
        wi, vi = rinput()
        w.append(wi)
        v.append(vi)

    mxv = sum(v)
    dp = [[float('inf') for i in range(mxv+1)]for j in range(n+1)]
    for i in range(n+1):
        dp[i][0]=0
    # print(w_v)
    for item in range(1, n+1):
        for val in range(1, mxv+1):
            if v[item-1] <= val:
                dp[item][val] = min(
                    dp[item-1][val-v[item-1]]+w[item-1], dp[item-1][val])
            else:
                dp[item][val] = dp[item-1][val]
    # print(dp)
    ans=float('inf')
    for i in range(mxv,0,-1):
        if dp[n][i]<=weigh:
            ans=i
            break
    print(ans)



### FIXED CODE ###

from collections import Counter
from collections import defaultdict
import math
import random
import heapq as hq
from math import sqrt
import sys
from functools import reduce


def input():
    return sys.stdin.readline().strip()


def iinput():
    return int(input())


def tinput():
    return input().split()


def rinput():
    return map(int, tinput())


def rlinput():
    return list(rinput())


mod = int(1e9)+7


def factors(n):
    return set(reduce(list.__add__,
                      ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))


# ----------------------------------------------------

if __name__ == "__main__":
    n, weigh = rinput()
    w, v = [], []
    for i in range(n):
        wi, vi = rinput()
        w.append(wi)
        v.append(vi)

    mxv = sum(v)
    dp = [[99999999999 for i in range(mxv+1)]for j in range(n+1)]
    for i in range(n+1):
        dp[i][0]=0
    # print(w_v)
    for item in range(1, n+1):
        for val in range(1, mxv+1):
            if v[item-1] <= val:
                dp[item][val] = min(
                    dp[item-1][val-v[item-1]]+w[item-1], dp[item-1][val])
            else:
                dp[item][val] = dp[item-1][val]
    # print(dp)
    ans=0
    for i in range(mxv+1):
        if dp[n][i]<=weigh:
            ans=i
    print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())
rev = False
ans = list(S)
for i in range(Q):
    tfc = input()
    if tfc == '1':
        rev = not rev
    else:
        t,f,c = tfc.split()
        if f == '1':
            if rev: ans = ans + [c]
            else: ans = [c] + ans
        elif f == '2':
            if rev: ans = [c] + ans
            else: ans = ans + [c]

if rev: ans.reverse()

print(''.join(ans))

### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())
rev = False
ans = deque(S)
for i in range(Q):
    tfc = input()
    if tfc == '1':
        rev = not rev
    else:
        t,f,c = tfc.split()
        if f == '1':
            if rev: ans.append(c)
            else: ans.appendleft(c)
        elif f == '2':
            if rev: ans.appendleft(c)
            else: ans.append(c)

if rev: ans.reverse()

print(''.join(ans))
### BUGGY CODE ###

import time
time.sleep(3)
print(0)

### FIXED CODE ###

X, A = [int(i) for i in input().split()]
print(0 if A > X else 10)
### BUGGY CODE ###

#coding: utf-8
A = list(map(int, input().split()))
N = A[0]
K = A[1]

n = 0
sw = 0
while True:
  if N%K == 0:
    N = 0
    break
  sw = abs(N-K)
  n += 1
  if N > sw:
    N = sw
  else:
    break
print(N)

### FIXED CODE ###

#coding: utf-8
A = list(map(int, input().split()))
N = A[0]
K = A[1]

n = 0
sw = 0
while True:
  if N%K == 0:
    N = 0
    break
  if (N/K) //1:
    C = N//K
    N = N-C*K

  sw = abs(N-K)
  n += 1
  if N > sw:
    N = sw
  else:
    break
print(N)
### BUGGY CODE ###

k,s=map(int,input().split())
br=0
k+=1
for x in range(k):
    for y in range(k):
        z=s-x-y
        if x+y+z==s and z>=0 and z<k:
            br+=1
        
print(br)

### FIXED CODE ###

k,s=map(int,input().split())
br=0
k+=1
for x in range(k):
    for y in range(k):
        z=s-x-y
        if x+y+z==s and z>=0 and z<k:
            br+=1
        
print(br)
### BUGGY CODE ###

N, A, B, C, D = [int(c) for c in input().split()]
S = input() + '##'

r2 = set()
r1 = {B-1}

for i, c in enumerate(S):
    if c=='.' and (i-2 in r1 or i-1 in r1):
        r1.add(i)

for x in range(A-1, C):
    if S[x]=='#' : r0 = set()
    else:
        r0=r1|r2
        r0.discard(x)
        if S[x-1]=='.' and (x-2 in r0 or x-3 in r0):
            r0.add(x-1)
        if S[x-2]=='.' and (x-3 in r0 or x-4 in r0):
            r0.add(x-2)
                
    r2=r1
    r1=r0

out = 'Yes' if D-1 in r0 else 'No'
print(out)


### FIXED CODE ###

N, A, B, C, D = [int(c) for c in input().split()]
S = input()

reachable = {B-1}
unreachable = set()
for i, c in enumerate(S):
    if c=='.' and (i-2 in reachable or i-1 in reachable):
        reachable.add(i)


for x in range(A, C):
    if x>=2 and S[x-1]=='#' and S[x-2]=='#':
        print('No')
        exit()

    unreachable.add(x)    
    if S[x-1]=='.' and ((x-2 in reachable and x-2 not in unreachable) or
                        (x-3 in reachable and x-3 not in unreachable) or
                        (x-1 in reachable and S[x-2]=='.' and S[x]=='.')
    ):
        unreachable.discard(x-1)
    if S[x-2]=='.' and ((x-3 in reachable and x-3 not in unreachable) or
                        (x-4 in reachable and x-4 not in unreachable)):
        unreachable.discard(x-2)
        
out = 'Yes' if D-1 in reachable and D-1 not in unreachable else 'No'
print(out)

# ##..#..
# #######
# S##.#..
# .#.##..
# #######
# .#..##.
# .#..#.#


 # #.S#.#...#.#...
 # .U.#.#...#.#...
 # ..##.#...#.#...
 # ###############
 # ...###...#.#...
 # ###############
 # ...#.##..#.#...
 # ...#.#.#.#.#...
 # ...#.#..##.#...
 # ###############
 # ...#.#...###...
 # ###############
 # ...#.#...#.##..
 # ...#.#...#.#.#.
 # ...#.#...#.#G.#
### BUGGY CODE ###

N = int(input())

for n in range(1, N+1):
    s = n//5
    cnt = 0
    flag = 0
    for x in range(1, s+1):
        for y in range(x, s+1):
            for z in range(y, s+1):
                siki = x**2 + y**2 + z**2 + x*y + y*z + z*x

                if siki == n:
                    # print('ans = ', siki)
                    if (x==y)and(y==z):
                        cnt += 1
                    elif (x!=y)and(y!=z):
                        cnt += 6
                    else:
                        cnt += 3
                # elif siki > n:
                    flag = 1
                    break
                elif siki > n:
                    break

            if flag:
                break
        if flag:
            break
    print(cnt)

### FIXED CODE ###

n=int(input())

ans=[0]*(n+1)

for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            f= x**2 + y**2 + z**2 + x*y + y*z + z*x
            if f<=n:
                ans[f]+=1

for i in range(1,n+1):
    print(ans[i])
### BUGGY CODE ###

K = int(input())
def gcd(i, j):
  if i<j:
    tmp=i
    i=j
    j=tmp
  if i%j==0:
    return j
  else:
    return gcd(j, i%j)
count = 0
for i in range(1, K+1):
  for j in range(1, K+1):
    x=gcd(i, j)
    for k in range(1, K+1):
      count += gcd(x, k)
print(count)


### FIXED CODE ###

import math
K = int(input())
count = 0
for i in range(1, K+1):
  for j in range(1, K+1):
    x=math.gcd(i, j)
    for k in range(1, K+1):
      _gcd=math.gcd(x, k)
      count += _gcd
print(count)
### BUGGY CODE ###

def resolve():
    N, M, K = map(int, input().split())
    fri = [[] for _ in range(N)]
    for i in range(M):
        a, b = map(int, input().split())
        fri[a-1].append(b-1)
        fri[b-1].append(a-1)
    blo = [[] for _ in range(N)]
    for i in range(K):
        c, d = map(int, input().split())
        blo[c-1].append(d-1)
        blo[d-1].append(c-1)

    can = [[] for _ in range(N)]
    for i in range(N):
        vis = [False for _ in range(N)]
        s = [i]
        while len(s) > 0:
            v = s.pop()
            vis[v] = True
            for j in fri[v]:
                if vis[j]:
                    continue
                s.append(j)
                if j not in fri[i] and j not in blo[i] and j not in can[i]:
                    can[i].append(j)
    ans = []
    for i in range(N):
        ans.append(len(can[i]))
    print(*ans, sep=' ')
resolve()

### FIXED CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
class UnionFind():
    def __init__(self, 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 resolve():
    N, M, K = lr()
    uf = UnionFind(N)
    fr = [0]*N
    for i in range(M):
        a, b = lr()
        uf.union(a-1, b-1)
        fr[a-1] += 1
        fr[b-1] += 1
    ans = [uf.size(x) - fr[x] - 1 for x in range(N)]
    for i in range(K):
        c, d = lr()
        if uf.same(c-1, d-1):
            ans[c-1] -= 1
            ans[d-1] -= 1
    print(*ans, sep=' ')
resolve()
### BUGGY CODE ###

# coding: utf-8

n, k = map(int, input().rstrip().split())    # 2 <= n <= 10^5, 1 <= k <= 100
h = list(map(int, input().rstrip().split()))

dp = [float('inf') for _ in range(n)]
dp[0] = 0
for i in range(1, n):
    js = max(i - k, 0)
    dp[i] = min(dp[j] + abs(h[i] - h[j]) \
        for j in range(js, i))
print(dp[i])


### FIXED CODE ###

# coding: utf-8

def f(n, k, h):
    dp = [0 for _ in range(n)]
    for i in range(1, n):
        js = max(i - k, 0)
        dp[i] = min(dp[j] + abs(h[i] - h[j]) \
            for j in range(js, i))
        # print(dp)
    return(dp[i])

n, k = map(int, input().rstrip().split())    # 2 <= n <= 10^5, 1 <= k <= 100
h = list(map(int, input().rstrip().split()))

print(f(n, k, h))
### BUGGY CODE ###

from scipy.sparse import lil_matrix
from scipy.sparse.csgraph import dijkstra
n, m = map(int, input().split())
graph = lil_matrix((n+1,n+1), dtype=int)
for i in range(m):
    u, v = map(int, input().split())
    graph[u, v] = 1
start, goal = map(int, input().split())
graph = graph * graph * graph
k = dijkstra(graph, indices=start)
if k[goal] != float('inf'):
    print(int(k[goal]))
else:
    print(-1)

### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
inf = 10**9
def bfs(start):
    dist = [inf for i in range((n+1) * 3)]
    que = deque()
    que.append(start)
    finished = set()
    dist[start] = 0
    while que:
        node = que.popleft()
        if node not in finished:
            finished.add(node)
            for i in adjacent_list[node]:
                dist[i] = min(dist[i], dist[node] + 1)
                que.append(i)
    return dist

adjacent_list = [[] for i in range((n+1)*3)]
for _ in range(m):
    u, v = map(int, input().split())
    for i in range(3):
        adjacent_list[u*3 + i].append(v*3 +((i+1)%3))
start, goal = map(int, input().split())
graph = bfs(start*3)
if graph[goal*3] != inf:
    print(int(graph[goal*3]) // 3)
else:
    print(-1)
### BUGGY CODE ###

from itertools import accumulate
import sys
input = sys.stdin.readline

n = int(input())
ans = [1]
a = list(map(int, input().split()))
for i in range(n):
    ans += list(accumulate(a[i:]))
print(ans.count(0))

### FIXED CODE ###

import sys
import itertools
from collections import Counter
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
cumsum = itertools.accumulate([0] + a)
counter = Counter(cumsum)
ans = 0

for value in counter.values():
    ans += value * (value - 1) // 2

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

k,s=map(int,input().split())
count=0
for x in range(k+1):
  for y in range(k+1):
    for z in range(k+1):
      if x+y+z==s:
        count+=1
print(count)

### FIXED CODE ###

k,s=map(int,input().split())
count=0

if k*3==s:
  print(1)
  exit()

for x in range(k+1):
  for y in range(k+1):
    z=s-x-y
    if z>=0 and z<=k:
      count+=1
print(count)
### BUGGY CODE ###

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

#dp[j][k][s] = (x0...xj からk枚選んでxiの合計をsにするような選び方の総数)
dp = [[[0]*(a*n+1) for k in range(n+1) ] for j in range(n)]


dp[0][0][0] = 1
if x[0]<= a*n:
    dp[0][1][x[0]] = 1
    
for j in range(n-1):
    for k in range(n+1):
        for s in range(a*n+1):
            if k == 0 and s == 0:
                dp[j+1][k][s] = 1
            if k>j+2:
                dp[j+1][k][s]=0
            elif s>=x[j+1] and k>= 1:
                dp[j+1][k][s]=dp[j][k][s] + dp[j][k-1][s-x[j+1]]
            else:
                dp[j+1][k][s]=dp[j][k][s]

res = 0
for i in range(1,n+1):
    res += dp[n-1][i][a*i]

print(res)

### FIXED CODE ###

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

#dp[j][k][s] = (x0...xj からk枚選んでxiの合計をsにするような選び方の総数)
dp = [[[0 for s in range(a*n+1) ] for k in range(n+1) ] for j in range(n)]

for j in range(n):
    dp[j][0][0]=1
    if x[0]<= a*n:
        dp[j][1][x[0]] = 1

for j in range(n-1):
    for k in range(n+1):
        for s in range(a*n+1):
            if k>j+2:
                dp[j+1][k][s]=0
            elif s>=x[j+1] and k>= 1:
                dp[j+1][k][s]=dp[j][k][s] + dp[j][k-1][s-x[j+1]]
            else:
                dp[j+1][k][s]=dp[j][k][s]

res = 0
for i in range(1,n+1):
    res += dp[n-1][i][a*i]

print(res)
### BUGGY CODE ###

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

ans = a[0]
for i in range(1, n):
  ans = ans * a[i]

if ans > 1000000000000000000:
  ans = -1

print(ans)

### FIXED CODE ###

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

if (0 in a):
  print(0)
else:
  ans = 1
  for num in a:
    ans *= num
    if ans > 1000000000000000000:
      print(-1)
      exit()
  print(ans)
### BUGGY CODE ###

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

def gcd(a,b):
    while b:
        a, b = b, a%b
    return a

def gcdlist(l):
    a = l[0]
    for i in range(len(l)):
        a = gcd(a,l[i])
    return a


dp = [a[0]]*(n)
dp[0] = a[1]
ldp = len(dp)
for i in range(1, n):
    a1 = a[i]
    ji = 0
    g1 = 0
    for j in range(ldp):
        if dp[j] == 1 or j == i: continue
        if j > i and ji == 0:
            if g1 == 0:
                g1 = gcd(a1, dp[j])
                ji = 1
                dp[j] = g1
                g1 = 1
            else:
                dp[j] = g1
        else:
            dp[j] = gcd(a1, dp[j])

print(max(dp))


### FIXED CODE ###


def gcd(a,b):
    while b:
        a, b = b, a%b
    return a

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

left = [0] * (n + 1)
for i in range(1, n):
    left[i] = gcd(left[i - 1], a[i - 1])

right = [0] * (n + 1)
for i in range(1, n):
    right[n - i] = gcd(right[n - i + 1], a[n - i])

ans = 0
for i in range(n):
    ans = max(ans, gcd(left[i], right[i + 1]))
print(ans)
### BUGGY CODE ###

N_ken, M_hon = map(int, input().split())
A_en = []
B_hon = []
yen = 0
hon = M_hon

for i in range(N_ken):
    a, b = map(int, input().split())
    A_en.append(a)
    B_hon.append(b)

while (hon > 0):
    index = A_en.index(min(A_en))
    tmp = min(hon, B_hon[index])
    yen += A_en[index] * tmp
    
    hon -= tmp
    A_en.remove(A_en[index])
    B_hon.remove(B_hon[index])

print(yen)

### FIXED CODE ###

N_ken, M_hon = map(int, input().split())
ab = []
yen = 0
hon = 0

for i in range(N_ken):
    tmp = list(map(int, input().split()))
    ab.append(tmp)

ab.sort()

for a, b in ab:
    tmp = min(M_hon - hon, b)
    yen += tmp * a
    hon += tmp
    
    if (hon == M_hon):
        break

print(yen)
### BUGGY CODE ###

N = int(input())
D = [int(i)-1 for i in input().split()]
M = int(input())
T = [int(i)-1 for i in input().split()]

flag = True

for t in T:
    if t in D:
        D.remove(t)
    else:
        flag = False
        break

if flag:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

from collections import Counter
N = int(input())
D = [int(i) for i in input().split()]
M = int(input())
T = [int(i) for i in input().split()]

cD = Counter(D)

for t in T:
    if cD.get(t,0) == 0:
        print('NO')
        exit()
    else:
        cD[t] -= 1

print("YES")
### BUGGY CODE ###

import sys
input = sys.stdin.readline
f = lambda : map(int,input().split())
n, q = f()
s = input()
for _ in range(q):
  l, r = f()
  ans = 0
  for i in range(l-1,r-1):
    if s[i:i+2] == 'AC':
      ans += 1
  print(ans)

### FIXED CODE ###

f = lambda : map(int,input().split())
n, q = f()
s = input()

cnt = 0
ln = [0]*n
for i in range(1,n):
  if s[i-1:i+1] == 'AC':
    cnt += 1
  ln[i] = cnt
for _ in range(q):
  l, r = f()
  print(ln[r-1]-ln[l-1])