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

import sys
from queue import Queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000000)

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

A = [-1]*M
B = [-1]*M
C = [-1]*M
nodes_edges = [[] for _ in range(N)]
rev_nodes_edges = [[] for _ in range(N)]
coin = [-float('inf')]*N
coin[0] = 0
availables = set()

for edge in range(M):
    a, b, c = map(int, input().split())
    A[edge] = a-1
    B[edge] = b-1
    C[edge] = c-P
    nodes_edges[a-1].append(edge)
    rev_nodes_edges[b-1].append(edge)

def cut_graph(node):
    edges = rev_nodes_edges[node]
    availables.add(node)
    for edge in edges:
        prev = A[edge]
        if prev in availables:
            continue
        cut_graph(prev)

cut_graph(N-1)
q = Queue()
q.put(0)
count = 0
limit = M*(1+len(availables))
while not q.empty():
    if count == limit:
        print(-1)
        break
    node = q.get()
    edges = nodes_edges[node]
    for edge in edges:
        nxt = B[edge]
        if nxt not in availables:
            continue
        new_coin = C[edge]+coin[node]
        if new_coin > coin[nxt]:
            coin[nxt] = new_coin
            q.put(nxt)
    count += 1
else:
    ans = coin[N-1]
    ans = 0 if ans < 0 else ans
    print(ans)


### FIXED CODE ###

import sys
import time
from queue import Queue
limit_time = time.time() + 1.70
input = sys.stdin.readline
sys.setrecursionlimit(1000000000)

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

A = [-1]*M
B = [-1]*M
C = [-1]*M
nodes_edges = [[] for _ in range(N)]
rev_nodes_edges = [[] for _ in range(N)]
coin = [-float('inf')]*N
coin[0] = 0
availables = set()

for edge in range(M):
    a, b, c = map(int, input().split())
    A[edge] = a-1
    B[edge] = b-1
    C[edge] = c-P
    nodes_edges[a-1].append(edge)
    rev_nodes_edges[b-1].append(edge)

def cut_graph(node):
    edges = rev_nodes_edges[node]
    availables.add(node)
    for edge in edges:
        prev = A[edge]
        if prev in availables:
            continue
        cut_graph(prev)

cut_graph(N-1)
q = Queue()
q.put(0)
count = 0
limit = M*(1+len(availables))
while not q.empty():
    if time.time() >= limit_time:
        print(-1)
        break
    node = q.get()
    edges = nodes_edges[node]
    for edge in edges:
        nxt = B[edge]
        if nxt not in availables:
            continue
        new_coin = C[edge]+coin[node]
        if new_coin > coin[nxt]:
            coin[nxt] = new_coin
            q.put(nxt)
    count += 1
else:
    ans = coin[N-1]
    ans = 0 if ans < 0 else ans
    print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
a = [int(i) for i in input().split()]
for i in range(m):
    b,c = map(int,input().split())
    a.extend([c]*b)
a.sort()
print(sum(a[len(a)-n:]))

### FIXED CODE ###

n,m = map(int,input().split())
a = [[1,int(i)] for i in input().split()]
bc = [[int(i) for i in input().split()] for j in range(m)]
x = a+bc
x.sort(key=lambda y:y[1])
total = 0
ans = 0
for i in reversed(range(n+m)):
    if total >= n:
        break
    else:
        ans += x[i][1]*min(n-total,x[i][0])
        total += x[i][0]
print(ans)
### BUGGY CODE ###

x = int(input())
for i in range(1,x+1):
    if i%3 ==0 or i%10 ==3:
        print(' ',i,end='',sep='')
    else:
        while True:
            if x <= i:
                print()
                break
            else:
                pass

### FIXED CODE ###

A = int(input())
for i in range(3, A + 1):
    if i%3 == 0 or i%10 == 3 or '3' in str(i):
        print('', i , end = '')
print()
### BUGGY CODE ###

n,q=[int(i) for i in input().split()]
g={}
val=[0]*n
for i in range(n-1):
  a,b=[int(i) for i in input().split()]
  if a-1 in g:g[a-1].append(b-1)
  else:g[a-1]=[b-1,]
for i in range(q):
  a,b=[int(i) for i in input().split()]
  val[a-1]+=b
stack=[]
stack.append(0)
while(len(stack)>0):
  p=stack.pop()
  if p in g:
    for i in g[p]:
      val[i]=val[i]+val[p]
      stack.append(i)
for i in val:print(i,end=" ")
print("")


### FIXED CODE ###

n,q=[int(i) for i in input().split()]
g={}
val=[0]*n
vis=[0]*n
for i in range(n-1):
  a,b=[int(i) for i in input().split()]
  if a-1 in g:g[a-1].append(b-1)
  else:g[a-1]=[b-1,]
for i in range(q):
  a,b=[int(i) for i in input().split()]
  val[a-1]+=b
stack=[]
stack.append(0)
vis[0]=1
while(len(stack)>0):
  p=stack.pop()
  if p in g:
    for i in g[p]:
      if vis[i]==0 :
        val[i]=val[i]+val[p]
        stack.append(i)
        vis[i]=1
for i in val:print(i,end=" ")
print(" ")
### BUGGY CODE ###

from functools import reduce


def gcd(a, b):
    """
    return gcd of a,b
    ユークリッド
    """
    while b:
        a, b = b, a % b
    return a


def list_gcd(l):
    """
    l: list
    l のgcd を返す
    """
    return reduce(gcd, l)


def lcm(a, b):
    """
    a,bの最小公倍数
    """
    return a*b//gcd(a, b)


def list_lcm(l):
    """
    l:list
    lのlcmを返す
    """
    return reduce(lcm, l)


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

LCM = list_lcm(L)
print(sum([LCM//v for v in L])%(10**9+7))


### FIXED CODE ###

from functools import reduce

MOD = 10**9+7


def gcd(a, b):
    """
    return gcd of a,b
    ユークリッド
    """
    while b:
        a, b = b, a % b
    return a


def list_gcd(l):
    """
    l: list
    l のgcd を返す
    """
    return reduce(gcd, l)


def lcm(a, b):
    """
    a,bの最小公倍数
    """
    return a*b//gcd(a, b)


def list_lcm(l):
    """
    l:list
    lのlcmを返す
    """
    return reduce(lcm, l)


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

LCM = list_lcm(L)
print(sum([LCM//v for v in L]) % MOD)
### BUGGY CODE ###


#AのリストにCのリストを加えて大きい順に並べ替えてNまでの和を求める

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

#AとCをリストとして持つ
A_list = list(map(int,input().split()))

C_list = []

for i in range(M):
    bi,ci = map(int,input().split())
    for j in range(bi):
        C_list.append(ci)

#A_listにC_listを追加する
A_list.extend(C_list)

#A_Listを大きい順に並べ替える
A_list=sorted(A_list,reverse=True)

#N番目までの総和を求める
print(sum(A_list[0:N]))


### FIXED CODE ###


#AのリストにCのリストを加えて大きい順に並べ替えてNまでの和を求める
N,M = map(int,input().split())

#Aの入力
A_list = list(map(int,input().split()))

C_list = []

#Cのリストに追加する
for i in range(M):
    bi,ci = map(int,input().split())
    C_list.append([bi,ci])

#C_listをCの値でソート
C_list=sorted(C_list, reverse=True, key=lambda x:x[1])

count = 0
for bi,ci in C_list:
    count += bi
    if count > N:
        #countがNより大きくなったらNより大きくなった分だけ使う
        bi = N - count + bi
    A_list.extend([ci]*bi)

#A_Listを大きい順に並べ替える
A_list=sorted(A_list,reverse=True)

#N番目までの総和を求める
print(sum(A_list[0:N]))
### BUGGY CODE ###

from itertools import combinations,product

n,k = map(int,input().split())
l = list(map(int,input().split()))

ln = [x for x in l if x<0]
lz = [x for x in l if x==0]
lp = [x for x in l if x>0]

a = len(ln)
b = len(lz)
c = len(lp)

nn = a*c
nz = int(b*(a+c) + b*(b-1)/2)
np = int(a*(a-1)/2 + c*(c-1)/2)

if k<=nn:
    resl = [x*y for x,y in product(ln,lp)]
    resl.sort()
    print(resl[k-1])
elif nn<k<=nn+nz:
    print(0)
else:
    resl = [x*y for x,y in combinations(ln,2)] + [x*y for x,y in combinations(lp,2)]
    resl.sort()
    print(resl[k-nn-nz-1])

### FIXED CODE ###

import numpy as np

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

a.sort()
pos = a[a>0]
zero = a[a==0]
neg = a[a<0]
negpos = (neg*(-1))[::-1]

lenn = len(neg)
lenz = len(zero)
lenp = len(pos)

nnres = lenn * lenp
nzres = int(lenz*(lenn+lenp)+lenz*(lenz-1)/2)
npres = int(lenn*(lenn-1)/2 + lenp*(lenp-1)/2)

if k<=nnres:
    def count_nnres(x):
        cnt = np.searchsorted(neg,x//pos,side='right').sum()
        return int(cnt)
    left = -10**18
    right = -1
    while left+1<right:
        mid = (left+right)//2
        nebefore = count_nnres(mid)
        if nebefore >= k:
            right = mid
        elif nebefore < k:
            left = mid
    print(right)
    
elif nnres<k<=nnres+nzres:
    print(0)
    
elif nnres+nzres<k:
    def count_npres(x):
        cnt = 0
        cnt += int(np.searchsorted(pos,x//pos,side='right').sum() - ((x//pos)>=pos).sum())//2
        cnt += int(np.searchsorted(negpos,x//negpos,side='right').sum() - ((x//negpos)>=negpos).sum())//2
        return cnt
    k -= nnres+nzres
    left = 1
    right = 10**18
    while left+1<right:
        mid = (left+right)//2
        nebefore = count_npres(mid)
        if nebefore >= k:
            right = mid
        elif nebefore < k:
            left = mid
    print(right)
### BUGGY CODE ###

if __name__ == '__main__':
	N = int(input())
	ls = [int(a) for a in input().split()]
	c = 0
	stack = []
	for i in range(N):
		h = ls[i]
		if i > 0:
			c += stack.count(i-h)
		stack.append(h+i)

	print(c)

### FIXED CODE ###

if __name__ == '__main__':
	N = int(input())
	ls = [int(a) for a in input().split()]
	c = 0
	dic = {}
	for i in range(N):
		h = ls[i]
		if i > 0:
			c += dic.get(i-h,0)
		v = dic.get(i+h,0)
		if v == 0:
			dic[i+h] = 1
		else:
			dic[i+h] += 1

	print(c)
### BUGGY CODE ###

a,b,c,d,e,f = map(int, input().split())


maxab = f //100
maxcd = f*e //(100+e)

res =[]

for i in range(maxab//a +1):
    for j in range(maxab//b +1):
        if 0 < (a*i + b*j)*100 < f:
            for k in range(maxcd):
                for l in range(maxcd):
                    if (c*k + d*l <= (a*i + b*j)*e) and (a*i + b*j)*100+(c*k + d*l) <= f:
                        g = (c*k + d*l)/((a*i + b*j)*100+(c*k + d*l))
                        res.append([g,(a*i + b*j)*100+(c*k + d*l),(c*k + d*l)])
        else:
            pass

resr = sorted(res,key=lambda x: x[0], reverse=True)

print(resr[0][1],resr[0][2])

### FIXED CODE ###

a,b,c,d,e,f = map(int, input().split())


maxab = f //100
maxcd = f*e //(100+e)

res =[]

for i in range(maxab//a +1):
    for j in range(maxab//b +1):
        wa = a*i + b*j
        if 0 < wa*100 < f:
            for k in range(maxcd//c +1):
                for l in range(maxcd//d +1):
                    su = c*k + d*l
                    if (su <= wa*e) and wa*100+su <= f:
                        g = su/(wa*100+su)
                        res.append([g,wa*100+su,su])
        else:
            pass

resr = sorted(res,key=lambda x: x[0], reverse=True)

print(resr[0][1],resr[0][2])
### BUGGY CODE ###

t = int(input())
a = []
for i in range(t):
  a.append(list(map(int,input().split())))
for j in a:
  b = j[0]
  for k in range(j[1]):
    if j[0] < j[1]:
      print("No")
      break
    j[0] %= j[1]
    if j[0] <= j[2]:
      j[0] += j[3]
    else:
      print("No")
      break
    if j[0] < j[1]:
      print("No")
      break
    if k == j[1]-1:
      print("Yes")
    

### FIXED CODE ###

def gcd(x, y):
	while y:
		x, y = y, x % y
	return x

t = int(input())
a = []
d = 0
for i in range(t):
  a.append(list(map(int,input().split())))
for j in a:
  if j[0] < j[1] or j[1] > j[3]:
    print("No")
  else:
    b = j[0] % j[1]
    k = gcd(j[1],j[3])
    c = j[0] % k
    d = j[2] % k
    if c > d:
      e = j[2] + c - d
    else:
      e = j[2] + k + c - d

    if j[1] > e:
      print("No")
    else:
      print("Yes")
### BUGGY CODE ###

while True:
    n = int(raw_input())
    if n == 0:
        break
    numbers = []
    for i in range(n):
        numbers.append(int(raw_input()))
    sigmas = []
    for i in range(1,n+1):
        for j in range(n+1-i):
            sigmas.append(reduce(lambda x,y:x+y,numbers[j:j+i+1]))
    print max(sigmas)

### FIXED CODE ###

while True:
    n = int(raw_input())
    if n == 0:
        break
    numbers = [int(raw_input()) for i in range(n)]
    if max(numbers) <= 0:
        print max(numbers)
    else:
        ans = 0
        for i in range(n):
            tmp = 0
            for j in range(i,n):
                tmp += numbers[j]
                if(ans<tmp):
                    ans = tmp
        print ans
### BUGGY CODE ###

x, y, a, b, c = map(int, input().split())

red = sorted(list(map(int, input().split())), reverse=True)
gre = sorted(list(map(int, input().split())), reverse=True)
non = sorted(list(map(int, input().split())), reverse=True)

eat = []

for i in range(x):
    eat.append(red.pop(0))

for i in range(y):
    eat.append(gre.pop(0))

eat.sort()

for i in range(len(non)):
    n = non.pop(0)
    if eat[i] < n:
        eat[i] = n
    else:
        break

print(sum(eat))

### FIXED CODE ###

x, y, a, b, c = map(int, input().split())

red = sorted(list(map(int, input().split())), reverse=True)
gre = sorted(list(map(int, input().split())), reverse=True)
non = sorted(list(map(int, input().split())), reverse=True)

red = red[0:x]
gre = gre[0:y]

eat = red + gre + non

eat.sort(reverse=True)

print(sum(eat[0:x+y]))
### BUGGY CODE ###

n = int(input())
a = [0] * (n+1)
for i in range(n):
    a[i+1] = tuple(map(int, input().split()))
todo = [0] * (n+1)
days = 0
while True:
    update = []
    for i in range(1, n+1):
        if todo[i] < n - 1 and i not in update:
            p = a[i][todo[i]]
            if a[p][todo[p]] == i and p not in update:
                update.append(i)
                update.append(p)
                todo[i] += 1
                todo[p] += 1
    days += 1
    #print(todo)
    if update == []:
        days = -1
        break
    elif todo[1:] == [n - 1] * n:
        break
print(days)

### FIXED CODE ###

n = int(input())
a = []
for _ in range(n+1):
    a.append([-1])
for i in range(n):
    inp = list(map(int, input().split()))
    for j in range(n-2, -1, -1):
        a[i+1].append(inp[j])
matched = [i for i in range(1, n+1)]
finish = 0
days = 0
while True:
    used = set()
    while matched != []:
        i = matched.pop()
        p = a[i][-1]
        if p != -1 and a[p][-1] == i and (i not in used) and (p not in used) :
            a[i].pop()
            a[p].pop()
            used.add(i)
            used.add(p)
            if a[i][-1] == -1:
                finish += 1
            if a[p][-1] == -1:
                finish += 1
    days += 1
    matched = list(used)
    if len(used) == 0:
        days = -1
        break
    elif finish == n:
        break
print(days)
### BUGGY CODE ###


if __name__ == '__main__':
    n,m = list(map(int, input().split()))
    a = list(map(int, input().split()))
    for i in range(m):
        b, c = list(map(int, input().split()))
        a += [c] * b
            
    a.sort(reverse=True)

    s = 0
    for i in range(n):
        s += a[i]
    
    print(s)


### FIXED CODE ###


if __name__ == '__main__':
    n,m = list(map(int, input().split()))
    a = list(map(int, input().split()))
    bc = []
    for i in range(m):
        bc.append(list(map(int, input().split())))

    bc.sort(key=lambda x: x[1], reverse=True)
    a.sort()

    bcn = 0
    for i in range(n):
        if(a[i] < bc[bcn][1]):
            a[i] = bc[bcn][1]
            bc[bcn][0] -= 1
            if(bc[bcn][0] == 0):
                bcn += 1
                if(bcn == m):
                    break

    print(sum(a))
### BUGGY CODE ###

class cmbs(object):
    def __init__(self, mod):
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 10 ** 6 + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)

    def cmb(self, n, r):
        if n > 10 ** 6:
            return self.cmbl(n, r)
        return self.cmbr(n, r)

    def cmbr(self, n, r):
        if r < 0 or r > n:
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.mod

    def cmbl(self, n, r):
        t = 1
        r = min(r, n-r)
        for i in range(n - r + 1, n + 1):
            t = t * i % self.mod
        return t * self.g2[r] % self.mod
def main():
    N = int(input())
    mod = 10**9 + 7
    C = list(map(int, input().split()))
    C.sort()
    c = cmbs(mod)
    r = 0
    for i, v in enumerate(C):
        t = 0
        for j in range(i, N):
            t += (j - i + 1) * c.cmb(N-i-1, j-i)
        t *= v * pow(2, i, mod)
        r += t
    r *= pow(2, N, mod)
    r %= mod
    return r
print(main())


### FIXED CODE ###

class cmbs(object):
    def __init__(self, mod):
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 10 ** 6 + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)

    def cmb(self, n, r):
        if n > 10 ** 6:
            return self.cmbl(n, r)
        return self.cmbr(n, r)

    def cmbr(self, n, r):
        if r < 0 or r > n:
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.mod

    def cmbl(self, n, r):
        t = 1
        r = min(r, n-r)
        for i in range(n - r + 1, n + 1):
            t = t * i % self.mod
        return t * self.g2[r] % self.mod
def main():
    N = int(input())
    mod = 10**9 + 7
    C = list(map(int, input().split()))
    C.sort()
    r = 0
    for i, v in enumerate(C[:-1]):
        t = pow(2, N-i-2, mod) * (N- i + 1)
        t *= v * pow(2, i, mod)
        r += t
    r += C[-1] * pow(2, N-1, mod)
    r *= pow(2, N, mod)
    r %= mod
    return r
print(main())
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

def main():
    S = input()
    T = input()
    for i in range(len(S)):
        if S[i] != T[i]:
            S = S.translate(str.maketrans({S[i]: T[i], T[i]: S[i]}))
    
    if S == T:
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

def main():
    S = input()
    T = input()
    pair = {}
    pair2 = {}
    for i in range(len(S)):
        if S[i] not in pair.keys():
            pair[S[i]] = T[i]
        else:
            if pair[S[i]] != T[i]:
                print('No')
                return
        if T[i] not in pair2.keys():
            pair2[T[i]] = S[i]
        else:
            if pair2[T[i]] != S[i]:
                print('No')
                return
        
    
    print('Yes')


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

n,q = map(int,input().split())
s = list(input())
t = []

for i in range(q):
    l,r = map(int,input().split())
    s1 = s[l-1:r]
    s2 = "".join(s1)
    t1 = s2.count("AC")
    t.append(t1)
for x in range(len(t)):
        print(t[x])

### FIXED CODE ###

n,q = map(int,input().split())
s = list(input())
l = [0]*(n)
for i in range(n-1):
        if s[i] == "A" and s[i+1] == "C":
                l[i+1] = l[i] + 1
        else:
                l[i+1] = l[i]  
for j in range(q):
        k,t = map(int,input().split())
        print(l[t-1] - l[k-1])
### BUGGY CODE ###

def main():
    import sys

    input = sys.stdin.readline

    x, y, z, k = map(int, input().split())
    A = tuple(map(int, input().split()))
    B = tuple(map(int, input().split()))
    C = tuple(map(int, input().split()))

    AB = sorted((a + b for a in A for b in B), reverse=True)[:k]
    ret = sorted((ab + c for ab in AB for c in C), reverse=True)[:k]

    print(*ret, sep='\n')


main()


### FIXED CODE ###

# https://www.kumilog.net/entry/python-speed-comp#input-%E3%81%A8-sysstdinreadline
# https://teratail.com/questions/88396

from heapq import heapify, heappush, heappop
import sys

input = sys.stdin.readline


class Data:
    def __init__(self, value, indices):
        self.value = value
        self.indices = indices

    def __lt__(self, other):
        return self.value < other.value


X, Y, Z, K = map(int, input().split())
a = map(int, input().split())
b = map(int, input().split())
c = map(int, input().split())

a = list(sorted(a, reverse=True))
b = list(sorted(b, reverse=True))
c = list(sorted(c, reverse=True))

hq = []
heapify(hq)

t = a[0] + b[0] + c[0]
t *= -1

d = Data(t, (0, 0, 0))

heappush(hq, d)

dtpls = ((1, 0, 0), (0, 1, 0), (0, 0, 1))

st = set()

cnt = 0
for _ in range(K):
    d = heappop(hq)
    print(-d.value)
    for dtpl in dtpls:
        na = d.indices[0] + dtpl[0]
        if na >= X: continue
        nb = d.indices[1] + dtpl[1]
        if nb >= Y: continue
        nc = d.indices[2] + dtpl[2]
        if nc >= Z: continue

        nt = a[na] + b[nb] + c[nc]
        nt *= - 1

        ntpl = (na, nb, nc)
        if ntpl in st: continue
        heappush(hq, Data(nt, ntpl))
        st.add(ntpl)
### BUGGY CODE ###

while True:
    n = input()
    if n == 0: break
    ans = [0,0,0,0,0,0,0]
    for i in xrange(n):
        age = input()
        if age <= 9:
            ans[0] = ans[0]+1
        elif age <= 19:
            ans[1] = ans[1]+1
        elif age <= 29:
            ans[2] = ans[2]+1
        elif age <= 39:
            ans[3] = ans[3]+1
        elif age <= 49:
            ans[4] = ans[4]+1
        elif age <= 59:
            ans[5] = ans[5]+1
        else:
            ans[6] = ans[6]+1
    else:
        for c in ans:
            print c

### FIXED CODE ###

while True:
    n = int(raw_input())
    if n == 0: break
    ans = [0 for i in range(7)]
    for i in xrange(n):
        age = int(raw_input())
        if age <= 9:
            ans[0] += 1
        elif age <= 19:
            ans[1] += 1
        elif age <= 29:
            ans[2] += 1
        elif age <= 39:
            ans[3] += 1
        elif age <= 49:
            ans[4] += 1
        elif age <= 59:
            ans[5] += 1
        else:
            ans[6] += 1
    for c in ans:
        print c
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
check = "AC"
for i in range(Q):
    l,r = map(int,input().split())
    cnt = S[l-1:r].count(check)
    print(cnt)

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
T = [0]*(N+1)
for i in range(N):
    T[i+1] = T[i] + (1 if S[i : i + 2] == "AC" else 0)
for i in range(Q):
    l,r = map(int,input().split())
    print(T[r-1] - T[l-1])
### BUGGY CODE ###

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

print(ans)

### FIXED CODE ###

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

import sys
input=sys.stdin.readline
h,w = map(int, input().split())
a=[list(map(int,input().split())) for i in range(h)]
b=[list(map(int,input().split())) for i in range(h)]
d=[]
for i in range(h):
    lis=[]
    for j in range(w):
        lis.append(abs(a[i][j]-b[i][j]))
    d.append(lis)

NUM=80*160+1
dp = [[[0 for _ in range(80*160+1)] for _ in range(w)] for _ in range(h)]
dp[0][0][d[0][0]]=1

for i in range(h):
    for j in range(w):
        for k in range(80*160+1):
            if dp[i][j][k]==1:
                if j+1<w:
                    nxt=d[i][j+1]
                    dp[i][j+1][k+nxt] = 1
                    dp[i][j+1][abs(k-nxt)] = 1
                if i+1<h:
                    nxt=d[i+1][j]
                    dp[i+1][j][k+nxt] = 1
                    dp[i+1][j][abs(k-nxt)] = 1


for ind in range(len(dp[h-1][w-1])):
    if dp[h-1][w-1][ind]==1:
        print(ind)
        exit()

### FIXED CODE ###

h,w = map(int, input().split())
a=[list(map(int,input().split())) for i in range(h)]
b=[list(map(int,input().split())) for i in range(h)]
d = [[0 for j in range(w)] for i in range(h)]
for i in range(h):
    for j in range(w):
        d[i][j] = abs(a[i][j]-b[i][j])

dp = [[0 for _ in range(6400)] for _ in range(h*w)]
dp[0][d[0][0]]=1

for i in range(h*w):
    nowh,noww = divmod(i,w)
    for k in range(6400):
        if not dp[nowh*w + noww][k]==1:
            continue
        nxth,nxtw=nowh+1, noww+1
        if nxtw<w:
            if k+d[nowh][nxtw] < 6400:
                dp[nowh*w + nxtw][k+d[nowh][nxtw]] = 1
            dp[nowh*w + nxtw][abs(k-d[nowh][nxtw])] = 1
        if nxth<h:
            if k+ d[nxth][noww]< 6400:
                dp[nxth*w + noww][k+d[nxth][noww]] = 1
            dp[nxth*w + noww][abs(k-d[nxth][noww])] = 1


for k in range(6400):
    if dp[-1][k]==1:
        print(k)
        exit()