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

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

def find_power(n,mod):
    # 0!からn!までのびっくりを出してくれる関数(ただし、modで割った値に対してである）
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(mod)
    return powlist

def find_inv_power(n):
    #0!からn!までの逆元を素数10**9+7で割ったあまりリストを作る関数
    powlist=find_power(n,10**9+7)
    check=powlist[-1]
    first=1
    uselist=[0]*(n+1)
    secondlist=[0]*30
    secondlist[0]=check
    secondlist[1]=check**2
    for i in range(28):
        secondlist[i+2]=(secondlist[i+1]**2)%(10**9+7)
    a=format(10**9+5,"b")
    for j in range(30):
        if a[29-j]=="1":
            first=(first*secondlist[j])%(10**9+7)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(10**9+7)
    return uselist

mod = 10**9+7
a=find_power(4*10**5+100,mod)
b=find_inv_power(4*10**5+100)

def comb(n,r,mod=10**9+7):
    if n<r:
        return 0
    elif n>=r:
        return (a[n]*b[r]*b[n-r])%(mod)

ans=0
for i in range(k+1):
    zs=i
    sm=comb(n,i) * comb(n-1,i)
    sm %= (10**9+7)
    ans+=sm

print(ans%(10**9+7))

### FIXED CODE ###

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

def find_power(n,mod):
    # 0!からn!までのびっくりを出してくれる関数(ただし、modで割った値に対してである）
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(mod)
    return powlist

def find_inv_power(n):
    #0!からn!までの逆元を素数10**9+7で割ったあまりリストを作る関数
    powlist=find_power(n,10**9+7)
    check=powlist[-1]
    first=1
    uselist=[0]*(n+1)
    secondlist=[0]*30
    secondlist[0]=check
    secondlist[1]=check**2
    for i in range(28):
        secondlist[i+2]=(secondlist[i+1]**2)%(10**9+7)
    a=format(10**9+5,"b")
    for j in range(30):
        if a[29-j]=="1":
            first=(first*secondlist[j])%(10**9+7)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(10**9+7)
    return uselist
mod = 10**9+7
a=find_power(4*10**5+100,mod)
b=find_inv_power(4*10**5+100)

def comb(n,r,mod=10**9+7):
    if n<r:
        return 0
    elif n>=r:
        return (a[n]*b[r]*b[n-r])%(mod)

if n<=k:
    K=comb(2*n-1,n-1,mod)
    print(K)
    exit()

ans=0
for i in range(k+1):
    zs=i
    sm=comb(n,i) * comb(n-1,i)
    sm %= (10**9+7)
    ans+=sm

print(ans%(10**9+7))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from pprint import pprint
 
MOD = 1000000007  # type: int
 
def solve(N: int, M: int, S: "List[int]", T: "List[int]"):
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        dp[i][0] = 1
    for j in range(M + 1):
        dp[0][j] = 1
    for i in range(N):
        for j in range(M):
            dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1]
            if not S[i] == T[j]:
                dp[i + 1][j + 1] -= dp[i][j]
    #pprint(dp)
    ret = dp[N][M] % MOD
    print(ret)
    return
 
 
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    S = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    T = [ int(next(tokens)) for _ in range(M) ]  # type: "List[int]"
    solve(N, M, S, T)
 
if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys
from pprint import pprint

MOD = 1000000007  # type: int

def solve(N: int, M: int, S: "List[int]", T: "List[int]"):
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        dp[i][0] = 1
    for j in range(M + 1):
        dp[0][j] = 1
    for i in range(N):
        for j in range(M):
            dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1]
            if not S[i] == T[j]:
                dp[i + 1][j + 1] -= dp[i][j]
            dp[i + 1][j + 1] %= MOD
    #pprint(dp)
    ret = dp[N][M]
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    S = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    T = [ int(next(tokens)) for _ in range(M) ]  # type: "List[int]"
    solve(N, M, S, T)

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

import sys


def query(S):
    print(S)
    sys.stdout.flush()
    return input()


def main():
    N = int(input())
    base = query(0)
    if base == "Vacant":
        return
    lo = 1
    hi = N-1
    while lo < hi:
        mid = (lo+hi) // 2
        ans = query(mid)
        if ans == "Vacant":
            return
        if (mid % 2 == 0 and ans == base) or \
           (mid % 2 == 1 and ans != base):
            lo = mid + 1
        else:
            hi = mid


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys


def query(S):
    print(S)
    sys.stdout.flush()
    return input()


def main():
    N = int(input())
    base = query(0)
    if base == "Vacant":
        return
    lo = 1
    hi = N-1
    while lo < hi:
        mid = (lo+hi) // 2
        ans = query(mid)
        if ans == "Vacant":
            return
        if (mid % 2 == 0 and ans == base) or \
           (mid % 2 == 1 and ans != base):
            lo = mid + 1
        else:
            hi = mid
    query(lo)


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

from sys import stdin


inp = stdin.readline

n, k = [int(x) for x in inp().strip().split()]

array = [int(x) for x in inp().strip().split()]

distance = [0]*(len(array) + 2)

for i in range(len(array) - 1):
    distance[1+i] = array[i+1] - array[i]
if array[0] == 0:
    distance[k] = 20-array[k-1]
else:
    distance[k] = abs(array[k - 1] - array[0])
distance[0] = distance[-2]
distance[-1] = distance[1]

minimum = 999999999
for i in range(len(distance) - 1):
    if minimum > sum(distance[i:i+k-1]):
        minimum = sum(distance[i:i+k-1])
print(minimum)

### FIXED CODE ###

from sys import stdin


inp = stdin.readline

n, k = [int(x) for x in inp().strip().split()]

array = [int(x) for x in inp().strip().split()]

distance = [0]*(k * 2)

for i in range(k - 1):
    distance[i] = array[i+1] - array[i]

distance[k-1] = n-array[k-1] + array[0]
distance[2*k-1] = n-array[k-1] + array[0]
for i in range(k - 1):
    distance[k+i] = array[i+1] - array[i]

minimum = 999999999

count = 0
total = 0
countLimit = k-1
for i in range(k * 2):
    if count < countLimit:
        total += distance[i]
        count += 1
    else:
        if minimum > total:
            minimum = total
        total += distance[i]
        total -= distance[i-countLimit]

print(minimum)
### BUGGY CODE ###

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

rates = sorted(list(set(D)))
counter = [0] * len(rates)
for i in range(len(rates)):
    counter[i] += D.count(rates[i])

acc = 0
found = False
for i in range(len(counter)):
    acc += counter[i]
    if acc == N/2:
        found = True
        break
    if acc > N/2:
        found = False
        break

if found == False:
    print(0)
else:
    print(rates[i+1]-rates[i])

### FIXED CODE ###

import collections

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

c = collections.Counter(D)
c = sorted(c.items(), key=lambda x:x[0])

rates, counter = list(zip(*c))

acc = 0
found = False
for i in range(len(counter)):
    acc += counter[i]
    if acc == N/2:
        found = True
        break
    if acc > N/2:
        found = False
        break

if found == False:
    print(0)
else:
    print(rates[i+1]-rates[i])
### BUGGY CODE ###

n,a,b = map(int,input().split())
cnt = 0
ans = 0
while cnt <= n:
  ans+=a
  cnt+=a+b
cnt -= a+b
ans-=a
nokori = n - cnt
if nokori >= a:
  ans+=a
else:
  ans+=nokori
print(ans)

### FIXED CODE ###

n,a,b = map(int,input().split())
ans = 0
add = a+b
amari = n%add
cnt = n//add
if amari >= a:
  ans = cnt*a + a
else:
  ans = cnt*a + amari
print(ans)
### BUGGY CODE ###

"""
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = [list(map(int, input().split())) for _ in range(m)]
b.sort(key = lambda x : x[1], reverse = True)
a.sort()
i = 0
j = 0
c = 1
ans = sum(a)
while True:
    if i >= m:
        break
    for _ in range(b[i][0]):
        if j >= n:
            c = 0
            break
        if a[j] < b[i][1]:
            ans += b[i][1] - a[j]
            j += 1
        else:
            c = 0
            break
    i += 1
    if c == 0:
        break
print(ans)
"""
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = [list(map(int, input().split())) for _ in range(m)]
b.sort(key = lambda x : x[1], reverse = True)
c = n
for i in range(m):
    if c - b[i][0] >= 0:
        a = a + ([b[i][1]] * b[i][0])
        c -= b[i][0]
    else:
        a = a + ([b[i][1]] * c)
        break
a.sort(reverse = True)
print(sum(a[0 : n]))

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = [list(map(int, input().split())) for _ in range(m)]
b.sort(key = lambda x : x[1], reverse = True)
a.sort()
i = 0
j = 0
c = 1
ans = sum(a)
while True:
    if i >= m:
        break
    for _ in range(b[i][0]):
        if j >= n:
            c = 0
            break
        if a[j] < b[i][1]:
            ans += b[i][1] - a[j]
            j += 1
        else:
            c = 0
            break
    i += 1
    if c == 0:
        break
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()))
AB=[]
for a in A:
	for b in B:
		AB.append(a+b)
ABC=[]
for ab in sorted(AB, reverse=True)[:K]:
	for c in C:
		ABC.append(ab+c)
for abc in sorted(ABC, reverse=True)[:K]:
	print(abc)


### 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()))
AB=[]
for a in A:
	for b in B:
		AB.append(a+b)
ABC=[]
for ab in sorted(AB, reverse=True)[:K]:
	for c in C:
		ABC.append(ab+c)
for abc in sorted(ABC, reverse=True)[:K]:
	print(abc)
### BUGGY CODE ###

S = input()
T = input()
lenS = len(S)
lenT = len(T)
dp = [[0]*(lenT+1) for _ in range(lenS+1)]
for i in range(1,lenS+1):
    for j in range(1,lenT+1):
        if S[i-1]==T[j-1]:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])
ans = []
while lenS!=0 and lenT!=0:
    if dp[lenS][lenT]==dp[lenS-1][lenT]:
        lenS-=1
    elif dp[lenS][lenT]==dp[lenS][lenT-1]:
        lenT-=1
    else:
        ans.append(S[lenS-1])
        lenS-=1
        lenT-=1
ans = ans[::-1]
print("".join(ans))

### FIXED CODE ###

# LongestCommonSubsequences
import numpy as np
S = np.array([ord(i)-97 for i in input()], dtype=int)
T = np.array([ord(i)-97 for i in input()], dtype=int)
Ns = len(S)
Nt = len(T)
equal = np.equal.outer(S, T).astype(int)

dp = [np.zeros(Nt + 1, dtype=int)]
for i in range(Ns):
    x = dp[-1].copy()
    newDP = x.copy()
    newDP[1:] = np.maximum(x[:-1] + equal[i], newDP[1:])
    np.maximum.accumulate(newDP, out=newDP)
    dp.append(newDP)


ans = ""
i, j = Ns, Nt
while i > 0 and j > 0:
    if S[i-1] == T[j-1]:
        ans += chr(S[i-1]+97)
        i -= 1
        j -= 1
        continue
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    else:
        j -= 1

print(ans[::-1])
### BUGGY CODE ###


N = int(input())

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

dic = {}
ans = 0

for i in range(N):

    if i != N-1 and A[i+1] == A[i]:
        dic[A[i]] = 1
        continue

    j = 1
    flag = True
    while j ** 2 <= A[i]:

        if A[i] % j == 0:
            k = A[i] // j

            if j in dic:
                flag = False
                break
            if k in dic:
                flag = False
                break

        j += 1

    if flag:
        ans += 1
    dic[A[i]] = 1

print (ans)


### FIXED CODE ###


def Sieve(n): #n以下の素数全列挙(O(nloglogn)) retは素数が入ってる。divlisはその数字の素因数が一つ入ってる

    ret = []
    divlis = [-1] * (n+1) #何で割ったかのリスト(初期値は-1)
    
    flag = [True] * (n+1)
    flag[0] = False
    flag[1] = False

    ind = 2
    while ind <= n:

        if flag[ind]:
            ret.append(ind)

            ind2 = ind ** 2

            while ind2 <= n:
                flag[ind2] = False
                divlis[ind2] = ind
                ind2 += ind

        ind += 1

    return ret,divlis

N = int(input())

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

ans = 0
lis = [0] * (10**6+1)
tmp,dl = Sieve(10**6+2)

for i in range(N):

    if i != N-1 and A[i+1] == A[i]:
        lis[A[i]] = 1
        continue

    dic = {}
    now = A[i]
    while dl[A[i]] != -1:

        if dl[A[i]] not in dic:
            dic[dl[A[i]]] = 1
        else:
            dic[dl[A[i]]] += 1
        A[i] //= dl[A[i]]

    if A[i] != 1:
        if A[i] not in dic:
            dic[A[i]] = 1
        else:
            dic[A[i]] += 1

    l1 = [1]
    #print (now,dic)
    for i in dic:
        l2 = [i**j for j in range(dic[i]+1)]

        tmp = len(l1)
        for x in range(tmp):
            for y in l2:
                if y != 1:
                    l1.append(l1[x]*y)

    flag = True
    #print (now , l1)
    for i in l1:
        if lis[i] > 0:
            flag = False
            break

    if flag:
        ans += 1
    lis[now] = 1

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

n=(int)(input())
a = list(map(int, input().split(" ")))
total = 1
for i in range(n):
  total *= a[i]
print(-1) if total > 10 ** 18 else print(total)

### FIXED CODE ###

n=(int)(input())
a = list(map(int, input().split(" ")))
total = 1
if 0 in a:
  print(0)
else:
  for i in range(n):
    total *= a[i]
    if total > 10 ** 18:
      print(-1)
      break
  else:
    print(total)
### BUGGY CODE ###

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

ans = s[n-1]

for c in range(1, n-1):
    dp = s[n-1]
    for k in range(n-1):
        if (k+1) * c >= n-1:
            break
        else:
            dp += s[n - 1 - k * c] + s[k * c]
            if dp > ans:
                if k <= 1:
                    ans = dp
                else:
                    a = n - 1 - k * c
                    b = a - c
                    if a > 2 * b:
                        ans = dp
                    elif a < 2 * b:
                        d = [0] * n
                        t = 0
                        while 1:
                            t += a
                            if t == n-1:
                                ans = dp
                                break
                            elif t > n-1:
                                break
                            d[t] = 1
                            t -= b
                            if d[t] == 1:
                                break
                            else:
                                d[t] = 1

print(ans)


### FIXED CODE ###

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

ans = 0

for d in range(1, n):
    temp = 0
    L = 0
    R = n-1
    if (n-1) % d == 0:
        while L < R:
            temp += s[L] + s[R]
            ans = max(ans, temp)
            L += d
            R -= d
    else:
        while L + d < n-1:
            temp += s[L] + s[R]
            ans = max(ans, temp)
            L += d
            R -= d

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

import heapq
N,Q = map(int,input().split(" "))
querys = []
START = 1
GOAL = 0
GO = 2

for _ in range(N):
    s,t,x = list(map(int,input().split(" ")))
    s -=(x + 0.5)
    t -= (x + 0.5)
    querys.append( (START,s,x) )
    querys.append( (GOAL,t,x) )

for _ in range(Q):
    d = int(input())
    querys.append( (GO,d,-1)  )
koji_place = []
koji_um = set()
heapq.heapify(koji_place)
querys = sorted(querys,key = lambda x:x[1])
for query in querys:
    qtype,time,place = query
    if qtype == START:
        heapq.heappush(koji_place,place)
        koji_um.add(place)
    elif qtype == GOAL:
        koji_um.remove(place)
    elif qtype == GO:
        while len(koji_place) != 0  and koji_place[0] not in koji_um: #更新と最近の場所のチェックを同時に行う
            heapq.heappop(koji_place) #koji place のpopは最大で place分，つまり合計で10 ** 5回行われるため ここのwhile
            # はOに影響を与えない
        if not koji_place:
            print(-1)
        else:
            print(koji_place[0])





### FIXED CODE ###

import bisect
import heapq
import sys
N,Q = [int(x) for x in sys.stdin.readline().split()]

hitos = []
ans = [-1] * Q
queries =[]
jump = [-1] * Q



queries = [[int(x) for x in sys.stdin.readline().split()] for i in range(N)]
hitos = [int(sys.stdin.readline()) for i in range(Q)]


# for i in range(N):
    # S,T,X =list(map(int,input().split(" ")))
    # lt = S -X -0.5
    # rt = T -X -0.5
    # queries.append([lt,rt,X]) #-1 → 挿入クエリ lが時間、-1がクエリの種類、Xが場所


queries.sort(key=lambda x:x[2])





for l,r,x in queries:
     lind  = bisect.bisect_left(hitos,l-x - 0.5)
     rind  = bisect.bisect_left(hitos,r -x - 0.5)
     while lind < rind:
         if ans[lind] == -1:
            ans[lind] = x
            jump[lind] = rind
            lind += 1
         else:
             temp = jump[lind]
             jump[lind] = rind
             lind = temp

for i  in ans:
    print(i)
### BUGGY CODE ###

import itertools
def main():
    n,k = tuple([int(t)for t in input().split()])

    a = tuple([int(t)for t in input().split()])

    for _ in range(min(41,k)):
        b = [0]*(n+1)
        for i in range(n):
            l = max(0,i-a[i])
            r = min(n,i+a[i]+1)
            b[l] += 1
            b[r] -= 1
        a = list(itertools.accumulate(b))[:n]

    print(*a)



if __name__ == "__main__":
    main()

### FIXED CODE ###

import itertools
def main():
    n,k = tuple([int(t)for t in input().split()])

    a = tuple([int(t)for t in input().split()])

    for _ in range(min(41,k)):
        b = [0]*(n+1)
        for i in range(n):
            l = max(0,i-a[i])
            r = min(n,i+a[i]+1)
            b[l] += 1
            b[r] -= 1
        a = list(itertools.accumulate(b))[:n]

    print(*a)



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

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, Q = MAP()
S = input()
lr = [LIST() for _ in range(Q)]

for i in range(Q):
	SS = S[lr[i][0]-1:lr[i][1]]
	cnt = 0
	for j in range(lr[i][1]-lr[i][0]):
		if SS[j] == "A" and SS[j+1] =="C":
			cnt += 1
	print(cnt)

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, Q = MAP()
S = input()
lr = [LIST() for _ in range(Q)]

T = [0]*N
cnt = 0
for i in range(1, N):
	if S[i] == "C" and S[i-1] == "A":
		cnt += 1
		T[i] = cnt
	else:
		T[i] = cnt

for i in range(Q):
	print(T[lr[i][1]-1]-T[lr[i][0]-1])
### BUGGY CODE ###

H,W=map(int,input().split())
S=list(list(input()) for _ in range(H))
ans=0
for i in range(H):
    for j in range(W):
        if S[i][j]!='#' and j!=W-1:
            ans+=1
        elif S[i][j]!='#'and j==W-1 :
            for k in range(ans+1):
                S[i][j-k]=ans+1
            ans=0
        else:
            for k in range(1,ans+1):
                S[i][j-k]=ans
            ans=0
S_t=list(map(list,zip(*S)))
ans=0
for i in range(W):
    for j in range(H):
        if S_t[i][j]!='#' and j!=H-1:
            ans+=1
        elif S_t[i][j]!='#'and j==H-1 :
            for k in range(ans+1):
                S_t[i][j-k]=ans+1+S_t[i][j-k]
            ans=0
        else:
            for k in range(1,ans+1):
                S_t[i][j-k]=ans+S_t[i][j-k]
            ans=0
            S_t[i][j]=0
c=0
for i in S_t:
    c=max(c,max(i))
print(c-1)

### FIXED CODE ###

H,W=map(int,input().split())
S=list(list(input()) for _ in range(H))
ans=0
for i in S:
    for j in range(W):
        if i[j]!='#' and j!=W-1:
            ans+=1
        elif i[j]!='#'and j==W-1 :
            for k in range(ans+1):
                i[j-k]=ans+1
            ans=0
        else:
            for k in range(1,ans+1):
                i[j-k]=ans
            ans=0
S_t=list(map(list,zip(*S)))
ans=0
for i in S_t:
    for j in range(H):
        if i[j]!='#' and j!=H-1:
            ans+=1
        elif i[j]!='#'and j==H-1 :
            for k in range(ans+1):
                i[j-k]+=ans+1
            ans=0
        else:
            for k in range(1,ans+1):
                i[j-k]+=ans
            ans=0
            i[j]=0
c=0
for i in S_t:
    c=max(c,max(i))
print(c-1)
### BUGGY CODE ###

import bisect
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]

MAX_V = sum(x[1] for x in wv)

INF = 1 << 60
dp = [0] + [INF] * MAX_V

for w, v in wv:
    # 退避
    dp_tmp = dp[:]
    for j in range(1, MAX_V + 1):
        prev = max(0, j - v)
        dp_tmp[j] = min(dp[j], dp[prev] + w)
    dp = dp_tmp


print(bisect.bisect_right(dp, W) - 1)

### FIXED CODE ###

import numpy as np

N, W = map(int, input().split())
MAX_V = (10**3) * N + 1
INF = 1 << 60

dp = np.full(MAX_V, INF)
dp[0] = 0

for i in range(N):
    w, v = map(int, input().split())
    np.minimum(dp[v:], dp[:-v] + w, out=dp[v:])

print(np.where(dp <= W)[0].max())
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
s = input()
count = 0
while s.find("ABC") != -1:
    s = s.replace("ABC", "BCA", 1)
    count += 1
print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
s = input()
s = s.replace("BC", "X")
count = 0
a_stack = 0
for idx, char in enumerate(s):
    if char == "A":
        a_stack += 1
    elif char == "X":
        count += a_stack
    else:
        a_stack = 0
print(count)
### BUGGY CODE ###

n,k = map(int,input().split())
s = input()
ls = []

tmp = s[0]
count = 1
for i in range(1,n):
  if s[i] == tmp:
    count += 1
  else:
    tmp = s[i]
    ls.append(count)
    count = 1
ls.append(count)


while k>0 and len(ls)>1:
  tmp = 0
  k-=1
  if len(ls) == 2:
    ls = [ls[0]+ls[1]]
  else:
    tmp += ls.pop(0)
    tmp += ls.pop(0)
    tmp += ls.pop(0)
    ls = [tmp]+ls
  
print(n-len(ls))

### FIXED CODE ###

n,k = map(int,input().split())
s = input()
ls = []

tmp = s[0]
count = 1
for i in range(1,n):
  if s[i] == tmp:
    count += 1
  else:
    tmp = s[i]
    ls.append(count)
    count = 1
ls.append(count)

length = len(ls)
for i in range(k):
  if length==1: break
  tmp = 0
  if length == 2:
    ls = [ls[0]+ls[1]]
    break
  else:
    tmp += ls.pop(0)
    tmp += ls.pop(0)
    ls[0] += tmp
    length -= 2
  
print(n-len(ls))
### BUGGY CODE ###

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

C = 0

if M == 1:
    l1, r1 = map(int, input().split())
    print(r1 - l1 + 1)
else:
    l1, r1 = map(int, input().split())
    for _ in range(M-1):
        l2, r2 = map(int, input().split())

        A = list(range(l1,r1+1))
        B = list(range(l2, r2+1))

        C = len(set(A) & set(B))
    print(C)


### FIXED CODE ###

N, M = map(int, input().split())
left= []
right = []
for _ in range(M):
    L, R = map(int, input().split())
    left.append(L)
    right.append(R)

min_right = min(right)
max_left = max(left)
if min_right < max_left:
    print(0)
else:
    print(min_right - max_left + 1)