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

n,w = map(int,input().split())
weight = [0 for i in range(n)]
value = [0 for i in range(n)]
for i in range(n):
    weight[i],value[i] = map(int,input().split())
    

#dp[i][j]: i番目の品物までの中から選び、重さがj以下になる時の、価値の総和の最大値
dp = [[0 for i in range(w+1)] for j in range(n+1)]
dp[1][weight[0]] = value[0]

for i in range(1,n):
    for j in range(w+1):
        if j - weight[i] >= 0:
            dp[i+1][j] = max(dp[i][j-weight[i]]+value[i],dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]
            
print(dp[n][w])

### FIXED CODE ###

n,w = map(int,input().split())
weight = [0 for i in range(n)]
value = [0 for i in range(n)]
for i in range(n):
    weight[i],value[i] = map(int,input().split())
    

#dp[i][j]: i番目の品物までの中から選び、重さがj以下になる時の、価値の総和の最大値
dp = [[None for i in range(w+1)] for j in range(n+1)]
dp[1][weight[0]] = value[0]

for i in range(1,n):
    for j in range(w+1):
        if j - weight[i] >= 0:
            if dp[i][j-weight[i]] != None and dp[i][j] != None:
                dp[i+1][j] = max(dp[i][j-weight[i]]+value[i],dp[i][j])
            elif dp[i][j-weight[i]] == None and dp[i][j] != None:
                dp[i+1][j] = dp[i][j]
            elif dp[i][j-weight[i]] != None and dp[i][j] == None:
                dp[i+1][j] = dp[i][j-weight[i]]+value[i]
            else:
                dp[i+1][weight[i]] = value[i]
        else:
            dp[i+1][j] = dp[i][j]
            
print(max(i for i in dp[n] if i is not None))
### BUGGY CODE ###

k,s=map(int,input().split())
count=0
for i in range(k+1):
  for j in range(k+1):
    for l in range(k+1):
      if i+j+l==s:
        count+=1
print(count)

### FIXED CODE ###

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

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

from fractions import gcd
from functools import reduce
gs = [reduce(gcd, A[300*i:300*(i+1)]) for i in range((N-1)//300 + 1)]

answer = 0

for i in range(N):
  k = i%300
  i = (i//300)
  
  g = reduce(gcd, A[i*300:k] + A[k+1:(i+1)*300] + gs[0:i] + gs[i+1:])

  answer = max(answer, g)

print(answer)

### FIXED CODE ###

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

L = len(A)
from functools import reduce
from fractions import gcd

def lcm(a,b):
  return (a*b)//gcd(a,b)

g = reduce(gcd, A)
l = reduce(lcm, A)

def _gcd(a,b):
  if a is None and b is None:
    return None
  if a is None:
    return b
  if b is None:
    return a
  else:
    return gcd(a,b)

class SegTree():
  import math
  def __init__(self, func, A, identity=1):
    self._func = func
    self._N = 1
    while self._N < len(A):
      self._N *= 2
       # 長さ 7 なら N=3 (2^3=8)
    self._identity = identity # maxなら-1e9, sumなら0, productなら1

    self._tree = [self._identity] * (2*self._N -1) 
    self._tree[self._N-1:self._N-1+ len(A)] = A #最下段に元の配列を
    for i in range(self._N-2, -1, -1):
      self._update_single_node(i)
    ########
    # N=3: #
    # 0000 #
    # 1122 #
    # 3456 #
    ########
    self._node_range = [(i-self._N+1,i-self._N+2) for i in range(2*self._N-1)] #right_exclusive
    for i in range(self._N-2, -1, -1):
      self._node_range[i] = (self._node_range[2*i+1][0], self._node_range[2*i+2][1])

  def _update_single_node(self,i):
    self._tree[i] = self._func(self._tree[2*i+1], self._tree[2*i+2])

  def point_update(self,i,x):
    # A[i] = x (addではないので注意)
    j = self._N-1+i
    self._tree[j] = x
    while j>0:
      j = (j-1)//2
      self._update_single_node(j)

  def range_query(self, l, r, on=0):
    # reduce(func, A[l:r])
    # onはノード[on]上と重なる部分の，ということ
    onl, onr = self._node_range[on]
    
    # ノード[on]上はすべて覆う
    if l<=onl and onr<=r:
      return self._tree[on]
    
    # 重なりなし
    elif onr<=l or r<=onl:
      return self._identity
    
    else:
      return self._func(self.range_query(l, r, on=2*on+1),
                        self.range_query(l, r, on=2*on+2))

st = SegTree(_gcd, A, identity=None)

answer = 0
for i in range(len(A)):
  st.point_update(i, A[i-1])
  answer = max(answer, st._tree[0])
  st.point_update(i, A[i])

print(answer)
### BUGGY CODE ###



N = int(input())
S = input()
S = S[::-1]

cnt = S.count('B')*S.count('G')*S.count('R')

for i in range(N-2):
    for j in range(i,N-1):
        k = 2*j-i
        if k>j and k<=N-1:
            if S[i]!=S[j] and S[i]!=S[k] and S[j]!=S[k] :
                cnt -= 1


print(cnt)

### FIXED CODE ###



N = int(input())
S = input()
S = S[::-1]

cnt = S.count('B')*S.count('G')*S.count('R')

for i in range(N-2):
    for j in range(i,N-1):
        k = 2*j-i
        if  k<=N-1:
            if S[i]!=S[j] and S[i]!=S[k] and S[j]!=S[k] :
                cnt -= 1


print(cnt)
### BUGGY CODE ###

N,K=list(map(int,input().split()))
P=list(map(int,input().split()))
ans=0
flag=0
for i in range(len(P)-K+1):
  ans=max(ans,sum(P[i:i+K]))
print((ans+K)*0.5)

### FIXED CODE ###

N,K=list(map(int,input().split()))
P=list(map(int,input().split()))
ans=[0]
ans[0]=sum(P[0:K])
for i in range(K,len(P)):
  ans.append(ans[-1]-P[i-K]+P[i])
print((max(ans)+K)*0.5)
### BUGGY CODE ###

# Author: cr4zjh0bp
# Created: Sun Mar 29 05:26:08 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

n = ni()
s = ns()

def ok(p):
    k = 0
    for i in range(n):
        if s[i] == p[k]:
            k += 1
        if k == 3:
            return True
    return False

ans = 0
for i in range(1000):
    p = "{:0>3}".format(i)
    if ok(p):
        ans += 1

print(ans)

### FIXED CODE ###

# Author: cr4zjh0bp
# Created: Sun Mar 29 05:26:08 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

n = ni()
s = ns()

def ok(p):
    k = 0
    for i in range(n):
        if s[i] == p[k]:
            k += 1
        if k == 3:
            return True
    return False

ans = 0
for i in range(1000):
    p = "{:0>3}".format(i)
    if ok(p):
        ans += 1

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

import sys
sys.setrecursionlimit(1000000)

n, q = map(int, input().split())
v = [set() for _ in range(n)]
c = [0]*(n)

for _ in range(n-1):
  a, b = map(int, input().split())
  v[a-1].add(b-1)
  v[b-1].add(a-1)

for _ in range(q):
  p, x = map(int, input().split())
  c[p-1] += x

def addcount(p, prev, prec):
  c[p] += prec
  for i in v[p]:
    if i == prev:
      continue
    addcount(i, p, c[p])
  return None

addcount(0, 0, 0)
  
print(*c)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

def input():
  return sys.stdin.readline()[:-1]

n, q = map(int, input().split())
v = [[] for _ in range(n+1)]
c = [0]*(n+1)

for _ in range(n-1):
  a, b = map(int, input().split())
  v[a].append(b)
  v[b].append(a)

for _ in range(q):
  p, x = map(int, input().split())
  c[p] += x

def addcount(p, prev):
  for i in v[p]:
    if i != prev:
      c[i] += c[p]
      addcount(i, p)
  return None
addcount(1, 0)
  
print(*c[1:])
### BUGGY CODE ###

N = int(input())
s_n = [sorted(list(input())) for i in range(N)]

ans = 0
for i in range(N - 1):
  for j in range(i + 1, N):
    if s_n[i] == s_n[j]:
      ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
d = {}
ans = 0

for i in range(n):
    s = ''.join(sorted(input()))
    if s not in d:
        d[s] = 1
    else:
        d[s] += 1
#print(d)
for k, v in d.items():
  ans += v * (v - 1) / 2

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

N, M = map(int,input().split())


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

set_ans = set(range(int(LR[0][0]),int(LR[0][1]+1)))
for m in range(1,M):
  set_ans = set_ans & set(range(int(LR[m][0]),int(LR[m][1])+1))
  if len(set_ans) == 0:
    break
print(len(set_ans))

### FIXED CODE ###

N, M = map(int,input().split())


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


    

L = [x[0] for x in LR]
R = [x[1] for x in LR]


if  min(R) - max(L)>=0:
  print(min(R)-max(L)+1)
else:
  print(0)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
from itertools import permutations,  combinations, accumulate
from functools import *
from collections import deque, defaultdict, Counter
from heapq import heapify, heappop, heappush, heappushpop

INF = float('inf')
NIL = - 1

""" Input
S = input().rstrip()

N, A, B = map(int, input().split())
A = list(map(int, input().split()))
A = np.array(input().split(), dtype=np.float64)
D = [int(input()) for _ in range(N)]
AB = [[int(x) for x in input().split()] for _ in range(N)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]
"""
N = int(input())
A = [int(input()) for _ in range(N)]

for i in range(N):
    tmp = A[i]
    A[i] = NIL
    print(max(A))
    A[i] = tmp




# def main():

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


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
from itertools import permutations,  combinations, accumulate
from functools import *
from collections import deque, defaultdict, Counter
from heapq import heapify, heappop, heappush, heappushpop

INF = float('inf')
NIL = - 1


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

max_a = max(A)
max_idx = [i for i, x in enumerate(A) if x == max_a]

if len(max_idx) > 1:
    for i in range(N):
        print(max_a)
    exit()
else:
    for i in max_idx:
        A[i] = NIL
    second_max = max(A)

    for i in range(N):
        if i in max_idx:
            print(second_max)
        else:
            print(max_a)
### BUGGY CODE ###

N = int(input())
A = list(sorted(map(int, input().split())))

flags = [True] * N

count = 0
for i in range(N):
    if flags[i]:
        for j in range(i+1, N):
            if A[j] % A[i] == 0:
                flags[j] = False
            if A[j] == A[i]:
                flags[i] = False
        if flags[i]:
            count += 1
print(count)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Amax = max(A)

counts = [0 for i in range(Amax+1)]

for a in A:
    counts[a] += 1

count = 0
for i in range(1, Amax+1):
    if counts[i] == 1:
        count += 1
    if counts[i]:
        for j in range(i*2, Amax+1, i):
            counts[j] = 0
print(count)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 0
for i in range(N) : 
    B = list(map(lambda x: A[i] % x , A))
    if B.count(0) == 1 :
        ans += 1

print(ans)


### FIXED CODE ###

N = int(input())
l = [0]*(10**6+1)
for a in map(int,input().split()) :
    l[a] += 1
ans = 0

for i in range(1, 10**6 + 1) :
    if l[i] == 1 :
        ans += 1
    if l[i] > 0 :
        for j in range(i , 10**6 + 1, i) :
            l[j] = 0

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

N, X, M = map(int,input().split())
A = [X]
Lstart = 0
for i in range(N):
    An = A[-1]**2 % M
    if An in A:
        Lstart = A.index(An)
        break
    else:
        A.append(An)
LenBefL = Lstart
LenLoop = len(A) - Lstart
if LenLoop > 0:
    ans = sum(A[:Lstart])+sum(A[Lstart:])*((N-LenBefL)//LenLoop) + sum(A[Lstart:Lstart + (N-LenBefL)%LenLoop])
else:
    ans = sum(A)
print(ans)

### FIXED CODE ###

N, X, M = map(int,input().split())
A = [X]
As = set(A)
Lstart = 0
for i in range(N):
    An = A[-1]**2 % M
    if An in As:
        Lstart = A.index(An)
        break
    else:
        A.append(An)
        As.add(An)
LenBefL = Lstart
LenLoop = len(A) - Lstart
if LenLoop > 0:
    ans = sum(A[:Lstart])+sum(A[Lstart:])*((N-LenBefL)//LenLoop) + sum(A[Lstart:Lstart + (N-LenBefL)%LenLoop])
else:
    ans = sum(A)
print(ans)
### BUGGY CODE ###

N, Y = list(map(int, input().split()))
Y //= 1000
for x in range(0, Y+1):
    for y in range(0, Y//5+1):
        z = N-x-y
        if (9*x + 4*y) == Y-N and z >= 0:
            print(x, y, N-x-y)
            exit()
print(-1, -1, -1)


### FIXED CODE ###

N, Y = list(map(int, input().split()))
Y //= 1000
for x in range(0, Y//10+1):
    for y in range(0, (Y-10*x)//5+1):
        z = N-x-y
        if (9*x + 4*y) == Y-N and z >= 0:
            print(x, y, N-x-y)
            exit()
print(-1, -1, -1)
### BUGGY CODE ###

n = list(x for x in range(1, int(input()) + 1))
p = [max(n)]
p.extend(n)

m = []
ans = 0

for i in range(len(n)):
  m.append(p[i] % (i+1))

for i in range(len(n)):
  ans += m[i]

print(ans)

### FIXED CODE ###

n = int(input())
print(n*(n-1)//2)
### BUGGY CODE ###

N, M = [int(i) for i in input().split()]
Groups = [[i] for i in range(N)]
dsts = [-1 for i in range(N)]
ABs = [[int(i)-1 for i in input().split()] for i in range(M)]
for A, B in ABs:
    dst = min(A, B)
    src = max(A, B)
    # print('A', A, B, dst, src)
    while(dsts[dst] != -1):
        dst = dsts[dst]
    while(dsts[src] != -1):
        src = dsts[src]
    if dst == src:
        continue
    dsts[src] = dst
    Groups[dst].extend(Groups[src])
    Groups[src] = []
    # print(Groups)
    # print(dsts)
ans = 0
for group in Groups:
    ans = max(ans, len(group))
print(ans)


### FIXED CODE ###

N, M = [int(i) for i in input().split()]
Groups = [1 for i in range(N)]
dsts = [-1 for i in range(N)]
ABs = [[int(i)-1 for i in input().split()] for i in range(M)]
for A, B in ABs:
    dst = min(A, B)
    src = max(A, B)
    # print('A', A, B, dst, src)
    while(dsts[dst] != -1):
        dst = dsts[dst]
    while(dsts[src] != -1):
        src = dsts[src]
    if dst != min(A, B):
        omdst = min(A, B)
        while(dsts[omdst] != dst):
            n_omdst = dsts[omdst]
            dsts[omdst] = dst
            omdst = n_omdst
    if src != max(A, B):
        omsrc = max(A, B)
        while(dsts[omsrc] != src):
            n_omsrc = dsts[omsrc]
            dsts[omsrc] = src
            omsrc = n_omsrc

    if dst == src:
        continue
    dst2 = min(dst, src)
    src2 = max(dst, src)
    dsts[src2] = dst2
    Groups[dst2] += Groups[src2]
    Groups[src2] = 0
    # print(Groups)
    # print(dsts)
print(max(Groups))
### BUGGY CODE ###


# input
A, B = map(int, input().split())

snack = max([A, B])
while snack % A != 0 or snack % B != 0:
    snack += 1

print(snack)

### FIXED CODE ###

def gcd(m, n):
    x = max(m, n)
    y = min(m, n)
    if x % y == 0:
        return y
    else:
        while x % y != 0:
            z = x % y
            x = y
            y = z
        return z


def lcm(m, n):
    return (m * n) // gcd(m, n)


# input
A, B = map(int, input().split())

# lcm
snack = lcm(A, B) 

print(snack)
### BUGGY CODE ###

N = int(input())
S = input()

def search(n):
    if n == 0:
        return False
    for i in range(N-n):
        if S[i:i+n] in S[:i] + "|" + S[i+n:]:
            return True
    return False

l = 1
r = N//2+1

while l<r:
    mid = (l+r)//2
    if search(mid):
        l = mid+1
    else:
        r = mid

print(l-1)


### FIXED CODE ###

N = int(input())
S = input()

maxL = 0

for i in range(1, N-1):
    cnt = 0
    left = 0
    for j in range(0, N-i):
        if S[j]==S[j+i]:
            cnt+=1
            if maxL < cnt:
                maxL = cnt
            if cnt == i:
                break
        else:
            cnt = 0
            left = j + 1

print(maxL)
### BUGGY CODE ###

import math
A,B,N = map(int,input().split())
res = 0
ans = 0
for i in range(1,N+1):
    res_bar = math.floor((A*i)/B)-A*math.floor(i/B)
    if res_bar >= res:
        res = res_bar
        ans = i
    else:
        break
print(res)


### FIXED CODE ###

import math
 
a, b, n = map(int, input().split())
ans = 0
tmp = 0
 
if n > b - 1:
    n = b-1
 
ans = math.floor(a*n/b) - a*math.floor(n/b)
 
print(ans)
### BUGGY CODE ###

x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=[]
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
for i in range(min(x,k)):
  for j in range(min(y,k)):
    for l in range(min(z,k)):
      if i*j*l>k:
        break
      else:
        ans.append(a[i]+b[j]+c[l])
ans.sort(reverse=True)
for i in range(k):
  print(ans[i])


### FIXED CODE ###

x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=[]
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
for i in range(min(x,k)):
  for j in range(min(y,k)):
    if i*j>k:
      break
    for l in range(min(z,k)):
      if i*j*l>k:
        break
      else:
        ans.append(a[i]+b[j]+c[l])
ans.sort(reverse=True)
for i in range(k):
  print(ans[i])
### BUGGY CODE ###

import math
from functools import reduce

K = int(input())

res = 0

def gcd(*numbers):
    return reduce(math.gcd, numbers)

for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            res += gcd(a,b,c)

print(res)

### FIXED CODE ###

import math
from collections import defaultdict

d = defaultdict(lambda : defaultdict(int))

K = int(input())

res = 0

for a in range(1, K+1):
    for b in range(1, K+1):
        d[a][b] = math.gcd(a,b)

for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            res += d[d[a][b]][c]

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

from collections import defaultdict
def main():
    def f(n):
        if n == 0:
            return 0
        if d[n] != 0:
            return d[n]
        d[n] = f(n % sum(list(map(int, bin(n)[2:])))) + 1
    def rev(i):
        if X[i] == '0':
            print(d[b % (c + 1)] + 1 if (b := (m + (1 << (n - i - 1)))) != 0 else 0)
        else:
            print(d[b % (c - 1)] + 1 if (b := (m - (1 << (n - i - 1)))) != 0 else 0)

    n = int(input())
    X = list(input())
    d = defaultdict(int)
    d[0] = 0
    for i in range(1, n):
        f(i)
    c = sum(list(map(int, X)))
    m = int(''.join(X), 2)
    for i in range(n):
        rev(i)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    def f(n):
        if n == 0: return 0
        return f(n % bin(n).count('1')) + 1
    n = int(input())
    X = list(input())
    c = sum(list(map(int, X)))
    m = int(''.join(X), 2)
    mp, mm = m % (c + 1), m % (c - 1) if c - 1 != 0 else 0
    jp, jm = 1, 1
    ans = [0] * n
    for i in range(n - 1, -1, -1):
        if X[i] == '0':
            mod = c + 1
            ans[i] = f((mp + jp) % mod) + 1
        else:
            ans[i] = f((mm - jm + mod) % mod) + 1 if (mod := c - 1) != 0 else 0
        jp, jm = (jp << 1) % (c + 1), (jm << 1) % (c - 1) if c - 1 != 0 else 0
    [print(a) for a in ans]
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from heapq import heappush, heappop
import itertools
sx,sy,gx,gy=map(int,input().split())
n=int(input())
g = [[] for i in range(n+2)]
data=[(sx+sy*1j,0)]
for i in range(n):
    a,b,c=map(int,input().split())
    data.append((a+b*1j,c))
data.append((gx+gy*1j,0))

for i,j in itertools.product(range(n+2), range(n+2)):
    if i>=j:
        continue
    tmp=abs(data[i][0]-data[j][0])-data[i][1]-data[j][1]
    g[i].append((tmp,j))
    g[j].append((tmp,i))

dist=[2828427127 for i in range(n+2)]
dist[0]=0
que=[]
heappush(que,(0,0))
while que:
    c,v=heappop(que)
    if dist[v]<c:
        continue
    for x in g[v]:
        tmp=x[0]+c if not x[0]<0 else c
        if tmp<dist[x[1]]:
            dist[x[1]]=tmp
            heappush(que,(tmp,x[1]))
print(dist[n+1])


### FIXED CODE ###

from heapq import heappush, heappop
sx,sy,gx,gy=map(int,input().split())
n=int(input())
g = [[] for i in range(n+2)]
data=[(sx+sy*1j,0)]
for i in range(n):
    a,b,c=map(int,input().split())
    data.append((a+b*1j,c))
data.append((gx+gy*1j,0))

for i in range(n+2):
    for j in range(i+1,n+2):
        tmp=abs(data[i][0]-data[j][0])-data[i][1]-data[j][1]
        g[i].append((tmp,j))
        g[j].append((tmp,i))

dist=[2828427127 for i in range(n+2)]
visited=[False for i in range(n+2)]
dist[0]=0
que=[]
heappush(que,(0,0))

while que:
    c,v=heappop(que)
    if visited[v]:
        continue
    visited[v]=True
    for x in g[v]:
        if visited[x[1]]:
            continue
        tmp=x[0]+c if not x[0]<0 else c
        if tmp<dist[x[1]]:
            dist[x[1]]=tmp
            heappush(que,(tmp,x[1]))
print(dist[n+1])
### BUGGY CODE ###

import math
N, K = map(int, input().split())

As = sorted(list(map(int, input().split())))
Bs = sorted(list(map(int, input().split())))[::-1]
Cs = [a*b for a, b in zip(As, Bs)]
BCs = list(zip(Bs, Cs))

def func(target):
    r = 0
    for b, c in BCs:
        r += math.ceil(max(0, c - target) / b)
    return int(r <= K)

def bsearch():
    min_i, max_i = 0, max(Cs)+1
    target = 0
    # func(index) <= target < func(index+1) となるindexを返す
    index = (max_i + min_i)//2
    while True:
        if func(index) <= target:
            if target < func(index+1):
                return index + 1
            index, min_i = (index+1 + max_i)//2, index+1
            continue
        index, max_i = (index-1 + min_i)//2, index-1

if __name__ == '__main__':
    print(bsearch())


### FIXED CODE ###

import math
N, K = map(int, input().split())
As = sorted(list(map(int, input().split())))
Bs = sorted(list(map(int, input().split())))[::-1]
Cs = [a*b for a, b in zip(As, Bs)]
BCs = list(zip(Bs, Cs))

def func(target):
    r = 0
    for b, c in BCs:
        r += math.ceil(max(0, c - target) / b)
    return r <= K

if __name__ == '__main__':
    min_i, max_i, index = 0, max(Cs)+1, 1
    while True:
        if func(index):
            index, max_i = (index-1 + min_i)//2, index-1
        else:
            index, min_i = (index+1 + max_i)//2, index+1
        if min_i > max_i:
            print(min_i)
            break
### BUGGY CODE ###

N,M = list(map(int, input().split()))

lst1 = [int(input()) for i in range(M)]

from functools import lru_cache
@lru_cache(maxsize=1000000007)
def fib(n):
  a, b = 1, 2
  for i in range(1,n+1):  
    if (i == 1):
      if (i in lst1):
        a, b = 0, 1
      yield a
    else:
      if (i in lst1):
        a, b = 0, a
      else:
        a, b = b, b+a
      yield a

lst2 = [i for i in fib(N)]
print(lst2[-1] % 1000000007)

### FIXED CODE ###

n,m=map(int,input().split())
D=[1] * (n + 1)
for _ in range(m):
    D[int(input())] = 0
for i in range(n+1):
    if i > 1:
        D[i] = (D[i-1] + D[i-2]) % 1000000007 * D[i]
print(D[i])
### BUGGY CODE ###

N=int(input())
S=str(input())
result = float('inf')
for i in range(N):
  S_1=S[:i]
  S_2=S[i+1:]
  result = min(result,S_1.count('W')+S_2.count('E'))
print(result)

### FIXED CODE ###

N=int(input())
S=str(input())

E=[0]*N
W=[0]*N
c=0
for i in range(N):
  W[i] =c
  if S[i]=='W':
    c +=1
c=0
for j in range(N):
  E[-1-j]=c
  if S[-1-j]=='E':
    c +=1
E=[E[0]]+E+[0]
W=[0]+W+[W[-1]]
answer=float('inf')
for i in range(N+2):
  answer=min(answer,E[i]+W[i])
print(answer)
### BUGGY CODE ###

N, Q = map(int, raw_input().split())
string = raw_input()
a = []
for i,j in enumerate(range(Q)):
    temp = map(int, raw_input().split())
    if i == 0:
        result = str(string[temp[0]-1:temp[1]].count('AC'))
    else:
        result += '\n' + str(string[temp[0]-1:temp[1]].count('AC'))
print(result)

### FIXED CODE ###

N, Q = map(int, raw_input().split())
string = raw_input()
cnt = [0]
for i in range(N):
#    print(i)
#    print(string[i-2:i])
#    if i == 0:
#        cnt.append(0)
#        continue
    if string[i-1:i+1] == 'AC':
        cnt.append(cnt[i]+1)
        continue
    cnt.append(cnt[i])

for j in range(Q):
    #print(j)
    pare = map(int, raw_input().split())
    print(cnt[pare[1]] - cnt[pare[0]])