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

import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


def choose_abc_range(s):
    ranges = []
    cur = 0
    while cur < len(s):
        if s[cur:cur+3] == "ABC":
            st = cur
            j = cur

            while s[j:j+3] == "ABC":
                j += 3

            ed = j

            ranges.append([st, ed])
            cur = j

        else:
            cur += 1

    return ranges

def get_a(sa):
    a = 0
    for sai in sa:
        if sai == "A":
            a += 1
        else:
            break

    return a

def get_bc(sb):
    b = 0
    for sbi in sb[::2]:
        if sbi == "bc":
            b += 1
        else:
            break

    return b

s = ns()
ans = 0
while "ABC" in s:

    ranges = choose_abc_range(s)
    for l, r in ranges:
        k = (r-l+1)//3
        a = get_a(s[l-1::-1])
        b = get_bc(s[r:])

        ans += k*(k+1)//2 + max(a*k + b*(k+a), b*k, a*(k+b))

        s = s[:l-a] + "BC"*(k+b) + "A"*(k+a) + s[r+2*b:]

print(ans)

### FIXED CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


s = ns()

cur = 0
anum = 0
bcnum = 0
ans = 0

while cur < len(s):
    if s[cur:cur+1] == "A":
        anum += 1
        cur += 1

    elif s[cur:cur+2] == "BC":
        bcnum += 1
        ans += anum
        cur += 2

    else:
        anum = 0
        bcnum = 0
        cur += 1

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

n, x, y = map(int, input().split())
a = []

for i in range(1, n + 1):
    if i == 1:
        a.append([2])
    elif i == n:
        a.append([n - 1])
    else:
        a.append([i - 1, i + 1])
a[x - 1].append(y)
a[y - 1].append(x)

d = {}
for i in range(n - 1):
    d[i + 1] = 0

pair = set()
def solve(s):
    que = [a[s - 1]]
    visit = set()
    visit.add(s)
    depth = 0

    while que != []:
        depth += 1
        nn = que[0]
        que = que[1:]
        adj = []
        for i in nn:
            if i not in visit:
                if (i, s) not in pair:
                    d[depth] += 1
                    pair.add((s, i))
                adj = adj + a[i-1]
            visit.add(i)
        if adj != []:
            que.append(adj)

for i in range(n):
    solve(i + 1)

for i in range(n - 1):
    print(d[i + 1])


### FIXED CODE ###

from collections import deque

n, x, y = map(int, input().split())
a = []

for i in range(1, n + 1):
    if i == 1:
        a.append([2])
    elif i == n:
        a.append([n - 1])
    else:
        a.append([i - 1, i + 1])
a[x - 1].append(y)
a[y - 1].append(x)

d = {}
for i in range(n - 1):
    d[i + 1] = 0

def solve(s):
    queue = deque()
    queue.append(a[s - 1])
    visit = set()
    visit.add(s)
    depth = 0

    while queue:
        depth += 1
        nn = queue.popleft()
        adj = []
        for i in nn:
            if i not in visit:
                d[depth] += 1
                adj = adj + a[i-1]
            visit.add(i)
        if adj != []:
            queue.append(adj)

for i in range(n):
    solve(i + 1)

for i in range(n - 1):
    print(d[i + 1] // 2)
### BUGGY CODE ###

N = int(input())
L = [[int(x) for x in input().split()] for _ in range(N-1)]

dic = {}
for i in range(N-1):
    if L[i][0] in dic:
        dic[L[i][0]].append([L[i][1], L[i][2]])
    else:
        dic[L[i][0]] = [[L[i][1], L[i][2]]]
    if L[i][1] in dic:
        dic[L[i][1]].append([L[i][0], L[i][2]])
    else:
        dic[L[i][1]] = [[L[i][0], L[i][2]]]

ans_list = ["0"]*(N+1)
q = [[1, 0]]
visited = [0]*(N+1)
while len(q) > 0:
    t = q.pop(0)
    v = t[0]
    d = t[1]
    for i in range(len(dic[v])):
        if visited[dic[v][i][0]] == 0:
            q.append([dic[v][i][0], d+dic[v][i][1]])
            visited[dic[v][i][0]] = 1
            if (d+dic[v][i][1])%2 == 1:
                ans_list[dic[v][i][0]] = "1"
                
for i in range(1, N+1):
    print(ans_list[i])

### FIXED CODE ###

from collections import deque

N = int(input())
edge = [[] for _ in range(N)]
for _ in range(N-1):
    u, v, w = map(int, input().split())
    edge[u-1].append([v-1, w])
    edge[v-1].append([u-1, w])
    
d = [0]*(N)

q = deque()
q.append([0, 0])
visited = [0]*(N)
while q:
    temp = q.pop()
    for L in edge[temp[0]]:
        if visited[L[0]] == 0:
            d[L[0]] = L[1] + temp[1]
            q.append([L[0], d[L[0]]])
            visited[L[0]] = 1
            
for i in range(N):
    print(d[i]%2)
### BUGGY CODE ###

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


from collections import deque
label=[-1]*n

i=0
for start in range(n):
    if label[start]!=-1:
        continue
    else:
        i+=1
        label[start]=i    
    dist_friends=[-1]*n
    dist_friends[start]=0
    f=deque([start])

    while f:
        v=f.popleft()        

        for e in edge[v]:
            if dist_friends[e]==-1 and label[e]==-1:
                dist_friends[e]=dist_friends[v]+1
                label[e]=i
                f.append(e)   

Renketsu=[0]*(n+1)

for i in label:
    Renketsu[i]+=1

Block=[0]*n
for _ in range(k):
    c,d=map(int,input().split())
    c,d=c-1,d-1
    if label[c]==label[d]:
        Block[c]+=1
        Block[d]+=1

ans=[]
for k in range(n):
    ans.append(Renketsu[label[k]]-1 - len(edge[k]) - Block[k])
print(*ans)

### FIXED CODE ###

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

from collections import deque
label=[-1]*n

i=0
for start in range(n):
    if label[start]!=-1:
        continue
    else:
        i+=1
        label[start]=i    
    f=deque([start])
    while f:
        v=f.popleft()        
        for e in edge[v]:
            if label[e]==-1:
                label[e]=i
                f.append(e)   

Renketsu=[0]*(n+1)

for i in label:
    Renketsu[i]+=1

Block=[0]*n
for _ in range(k):
    c,d=map(int,input().split())
    c,d=c-1,d-1
    if label[c]==label[d]:
        Block[c]+=1
        Block[d]+=1

ans=[]
for k in range(n):
    ans.append(Renketsu[label[k]]-1 - len(edge[k]) - Block[k])
print(*ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2**20)

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

dp = [[[-1] * (N+1) for j in range(N+1)] for k in range(N+1)]
dp[0][0][0] = 0

S = [0] * 3
for a in A:
  S[a-1] += 1

def calc(i, j, k):
  if dp[i][j][k] >= 0: return dp[i][j][k]
  dp[i][j][k] = (i * (calc(i-1, j, k) if i > 0 else 0) + j * (calc(i+1, j-1, k) if j > 0 else 0) + k * (calc(i, j+1, k-1) if k > 0 else 0) + N) / (i + j + k)
  return dp[i][j][k]

print(calc(*S))

### FIXED CODE ###

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

S = [0] * 3
for a in A:
  S[a-1] += 1
I, J, K = S

dp = [[[0.0] * (N+1) for j in range(N+1)] for i in range(N+1)]

for k in range(S[2] + 1):
  for j in range(S[1] + S[2] - k + 1):
    for i in range(S[0] + S[1] + S[2] - j - k + 1):
      if i == j == k == 0: continue
      dp[i][j][k] = (i * (dp[i-1][j][k] if i > 0 else 0) + j * (dp[i+1][j-1][k] if j > 0 else 0) + k * (dp[i][j+1][k-1] if k > 0 else 0) + N) / (i + j + k)

print(dp[I][J][K])
### BUGGY CODE ###

n, m, k =map(int, input().split())
a=list(map(int, input().split()))
b=list(map(int, input().split()))
ta=sum(a)
a.append(0)
tb=0
ans=0

for i in range(n+1):
    ta -= a[n-i]
    if ta>k:
        continue
    for j in range(m):
        tb += b[j]
        if tb + ta >k:
            break
        if j==m-1:
            j +=1

    ans=max(ans,n-i+j)
    tb=0
print(ans)


### FIXED CODE ###

n, m, k =map(int, input().split())
a=list(map(int, input().split()))
b=list(map(int, input().split()))
ta=sum(a)
a.append(0)
tb=0
ans=0
j=0
for i in range(n+1):
    ta -= a[n-i]
    if ta>k:
        continue
    while tb + ta<=k:

        if j ==m:
            ans=max(ans,n-i+j)
            break
        ans=max(ans,n-i+j)
        tb += b[j]
        j +=1

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

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

plist = list(map(int,input().split()))

maxval = 0


def expectedval(inp):
	return (1 + inp) /2

maxcomb = []
maxsum = 0
bestpos = 0

for i in range(n-(k-1)):
	summ = 0
	for j in range (k):
		summ += plist[i + j]
	if summ > maxsum:
		maxsum = summ
		bestpos = i

res = 0
for j in range (k):
	res += expectedval(plist[bestpos + j])

print(res)

### FIXED CODE ###

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

plist = list(map(int,input().split()))

maxval = 0

temp = -1

def expectedval(inp):
	return (1 + inp) /2

for i in range(n-(k-1)):
	# print(i, k)
	summ = 0
	if temp == -1:
		for j in range (k):
			summ += expectedval(plist[i + j])
		temp = summ
	else:
		# print(plist[i-1], plist[i+k -1], expectedval(plist[i - 1]), expectedval(plist[i + k - 1]))
		summ = temp - expectedval(plist[i - 1]) + expectedval(plist[i + k - 1])
		temp = summ
	# print(summ)
	maxval = max(summ, maxval)

print(maxval)
### BUGGY CODE ###

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

sum = 0
a_3 = int(a[3])
a_0 = a[0]
a_1 = a[1]

for i in range (a_3):
    if a_0 > 0:
        sum += 1
        a_0 -= 1
    elif a_0 == 0 and a_1 > 0:
        sum += 0
        a_1 -= 1
    else: sum -= 1
    
print(sum)

### FIXED CODE ###

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

sum = 0
a_3 = a[3]
a_0 = a[0]
a_1 = a[1]
a_2 = a[2]


if a_3 <= a_0:
    print (a_3)
    
elif a_3 > a_0 and a_3 <= (a_0 + a_1):
    print (a_0)
    
else:
    sum = a_0 - (a_3 - a_0 - a_1)
    print(sum)
### BUGGY CODE ###

from decimal import Decimal
X= int(input())

B=1
b=0
while True:
    
    print(b)
    
    a= Decimal((X+b**5)**(1/5))
   
    if int(a)==a and a>b:
        print(a,b)
        break
    else:
        if X+(b-1)**5<0:
            break
        else:
            b=b-1
while True:
    print(B)
   
    A= Decimal((X+B**5)**(1/5))
   
    if int(A)==A and A>B:
        print(A,B)
        break
    else:
        B=B+1

### FIXED CODE ###

#D
X=int(input())
for i in range(1000):
    for a in range(1000):
        if a**5-(a-i)**5==X:
            print(a,a-i)
            break
### BUGGY CODE ###

import sys
from operator import itemgetter
import numpy as np
read = sys.stdin.read

N, M, *LRC = map(int, read().split())
dp = np.full(N + 1, np.inf)
dp[1] = 0

for L, R, C in sorted(list(zip(*[iter(LRC)] * 3)), key=itemgetter(0, 1)):
    dp[L + 1:R + 1] = np.minimum(dp[L + 1:R + 1], dp[L] + C)
    dp[L + 1:R + 1] = np.minimum(dp[L + 1:R + 1], np.minimum.accumulate(dp[L + 1:R + 1] + C))

if dp[N] == np.inf:
    print(-1)
else:
    print(int(dp[N]))

### FIXED CODE ###

import sys
from heapq import heapify, heappush, heappop
read = sys.stdin.read


def main():
    N, M, *LRC = map(int, read().split())
    graph = [[(0, i - 1)] for i in range(N + 1)]
    graph[1] = []

    for L, R, C in zip(*[iter(LRC)] * 3):
        graph[L].append((C, R))

    distance = [-1] * (N + 1)
    queue = []
    heapify(queue)
    heappush(queue, (0, 1))

    while queue:
        cost, node = heappop(queue)
        if distance[node] == -1:
            distance[node] = cost
            for add_cost, next_node in graph[node]:
                if distance[next_node] == -1:
                    heappush(queue, (cost + add_cost, next_node))

    print(distance[-1])


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

n=int(input())
a=list(map(int,input().split()))
l=[]
for x in range(1,n+1):
    l.append(str(a.index(x)+1))
print(" ".join(l))

### FIXED CODE ###

n=int(input())
s=list(map(int,input().split()))
d={}
for x in range(len(s)):
    d[x]=s[x]
d=sorted(d.items(),key=lambda e: e[1])
p=list(map(str,[i+1 for i,j in d]))
print(" ".join(p))
### BUGGY CODE ###

def is_ok(mid, gen=None, diff=0):
    print(mid, flush=True)
    res = input()
    if res == "Vacant":
        sys.exit()
    if gen is None:
        return res
    if diff % 2 == 0:
        return gen == res
    else:
        return gen != res


def meguru_bisect_kai(ng, ok, gen):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid, gen, ok - mid):
            ok = mid
        else:
            ng = mid
            if gen == "Male":
                gen = "Female"
            else:
                gen = "Male"
    return ok


n = int(input())
gen = is_ok(0)
is_ok(n - 1)
meguru_bisect_kai(0, n - 1, gen)

### FIXED CODE ###

n = int(input())

print(0, flush=True)
res = input()
if res == "Vacant":
    exit()

left = 0
right = n
gen = res


while True:
    mid = (left + right) // 2
    print(mid, flush=True)
    res = input()

    if res == "Vacant":
        exit()

    if gen == res:
        if (mid - left) % 2:
            right = mid
        else:
            left = mid
    else:
        if (mid - left) % 2:
            left = mid
            gen = res
        else:
            right = mid
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
from collections import defaultdict
ns = defaultdict(set)
for _ in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)
    ns[v].add(u)
dp = [[(-1,0)]*n for _ in range(11)]
q = int(input())
qs = [None]*q
for i in range(q):
    v,d,c = tuple(map(int, input().split()))
    v -= 1
    qs[i] = (i,v,d,c)
for i0 in range(10, -1, -1):
    for i,v,d,_ in qs:
        if i0<=d:
            dp[0][v] = (i,d)
    for i in range(1,11):
        for u in range(n):
            if dp[i-1][u][0]>dp[i][u][0]:
                ind0, d0 = dp[i-1][u]
            else:
                ind0, d0 = dp[i][u]
            for v in ns[u]:
                ind,d = dp[i-1][v]
                if ind>ind0 and d>0:# and i0<=i+d:
                    ind0, d0 = ind, d-1
            dp[i][u] = (ind0, d0)
#     print(dp[10])
write("\n".join(map(str, ((qs[dp[10][u][0]][3] if dp[10][u][0]>=0 else 0) for u in range(n)))))

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

n,m = list(map(int, input().split()))
from collections import defaultdict
ns = defaultdict(list)
for _ in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].append(v)
    ns[v].append(u)
    
dp = [[-1]*n for _ in range(11)]
q = int(input())
qs = [None]*q
for i in range(q):
    v,d,c = tuple(map(int, input().split()))
    v -= 1
    qs[i] = (i,v,d,c)
    dp[d][v] = i
from itertools import product
for i,u in product(range(10,0,-1), range(n)):
    if dp[i][u]>=0:
        dp[i-1][u] = max(dp[i-1][u], dp[i][u])
        for v in ns[u]:
            dp[i-1][v] = max(dp[i-1][v], dp[i][u])

write("\n".join(map(str, ((qs[dp[0][u]][3] if dp[0][u]>=0 else 0) for u in range(n)))))
### BUGGY CODE ###

A,B,C,X= [int(input()) for x in range(4)] 
ans = 0
for a in range(1<<A):
	for b in range(1<<B):
		for c in range(1<<C):
			if 500*a+100*b+50*c == X:
				ans += 1
print(ans)

### FIXED CODE ###

A,B,C,X= [int(input()) for x in range(4)] 
print([500*a+100*b+50*c for c in range(C+1) for b in range(B+1) for a in range(A+1)].count(X))
### BUGGY CODE ###

from collections import defaultdict
def main():
    s = list(input())
    n = len(s)
    dp = [0 for _ in range(2019)]
    dp[0] += 1
    for i in range(n):
        dp[int(''.join(s[i:]))%2019] += 1
    ans = 0
    for i in range(2019):
        ans += (dp[i]*(dp[i]-1))//2
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    s = input()
    n = len(s)
    dp = [0 for _ in range(2019)]
    dp[0] += 1
    x = 0
    for i in range(n):
        x = (x+int(s[n-1-i])*pow(10,i,2019))%2019
        dp[x] += 1
    ans = 0
    for i in range(2019):
        ans += (dp[i]*(dp[i]-1))//2
    print(ans)

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

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

st = 1
for i in range(K):
    st *= A[i]

for i in range(K, N):
    heru = A[i-K]
    hueru = A[i]
    if heru<hueru:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

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

for i in range(K, N):
    if A[i-K]<A[i]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from math import sqrt

N,K=map(int,input().split())
M=[tuple(map(int,input().split())) for i in range(N)]

def cross_coor(x0,y0,c0,x1,y1,c1): # 二円の交点
    if (c1-c0)**2<=(x1-x0)**2+(y1-y0)**2<=(c0+c1)**2:
        x2,y2=x1-x0,y1-y0
        a=(x2**2+y2**2+c0**2-c1**2)/2

        xa=(a*x2+y2*sqrt((x2**2+y2**2)*(c0**2)-a**2))/(x2**2+y2**2)+x0
        ya=(a*y2-x2*sqrt((x2**2+y2**2)*(c0**2)-a**2))/(x2**2+y2**2)+y0

        xb=(a*x2-y2*sqrt((x2**2+y2**2)*(c0**2)-a**2))/(x2**2+y2**2)+x0
        yb=(a*y2+x2*sqrt((x2**2+y2**2)*(c0**2)-a**2))/(x2**2+y2**2)+y0

        return [(xa,ya),(xb,yb)]
    else:
        return False

OK=1<<18
NG=0

while OK-NG>10**(-8):
    mid=(OK+NG)/2
    
    CANDI=[]
    for i in range(N):
        x0,y0,c0=M[i]
        CANDI.append((x0,y0))
        for j in range(i+1,N):
            x1,y1,c1=M[j]
            CR=cross_coor(x0,y0,mid/c0,x1,y1,mid/c1)
            if CR:
                CANDI.extend(CR)

    for z,w in CANDI:
        count=0
        for x,y,c in M:
            if (c**2)*((x-z)**2+(y-w)**2)<=(mid+10**(-8))**2:
                count+=1
            
        if count>=K:
            OK=mid
            break
    else:
        NG=mid

print((OK+NG)/2)



### FIXED CODE ###

import sys
input = sys.stdin.readline
from math import sqrt

N,K=map(int,input().split())
M=[tuple(map(int,input().split())) for i in range(N)]

def cross_coor(x0,y0,c0,x1,y1,c1): # 二円の交点
    if (c1-c0)**2<=(x1-x0)**2+(y1-y0)**2<=(c0+c1)**2:
        x2,y2=x1-x0,y1-y0
        a=(x2**2+y2**2+c0**2-c1**2)/2

        xa=(a*x2+y2*sqrt((x2**2+y2**2)*(c0**2)-a**2))/(x2**2+y2**2)+x0
        ya=(a*y2-x2*sqrt((x2**2+y2**2)*(c0**2)-a**2))/(x2**2+y2**2)+y0

        xb=(a*x2-y2*sqrt((x2**2+y2**2)*(c0**2)-a**2))/(x2**2+y2**2)+x0
        yb=(a*y2+x2*sqrt((x2**2+y2**2)*(c0**2)-a**2))/(x2**2+y2**2)+y0

        return [(xa,ya),(xb,yb)]
    else:
        return False

OK=1<<31
NG=0

while OK-NG>10**(-8):
    mid=(OK+NG)/2
    
    CANDI=[]
    for i in range(N):
        x0,y0,c0=M[i]
        CANDI.append((x0,y0))
        for j in range(i+1,N):
            x1,y1,c1=M[j]
            CR=cross_coor(x0,y0,mid/c0,x1,y1,mid/c1)
            if CR:
                CANDI.extend(CR)

    for z,w in CANDI:
        count=0
        for x,y,c in M:
            if (c**2)*((x-z)**2+(y-w)**2)<=(mid+10**(-8))**2:
                count+=1
            
        if count>=K:
            OK=mid
            break
    else:
        NG=mid

print((OK+NG)/2)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
mod = 2019
def main():
    s = tuple([int(x) for x in input().rstrip()])
    n = len(s)
    ans = 0
    d = {}
    T = 0
    T1 = 0
    for i in range(n):
        T1 = s[n-1-i]*10**i+T
        T = T1
        t = T%mod
        if t in d:
            d[t] += 1
        else:
            d[t] = 1
    for k in d:
        if k != 0:
            ans += d[k]*(d[k]-1)//2
        else:
            ans += d[k]
    print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
mod = 2019
def main():
    s = input().rstrip()
    n = len(s)
    d = {}
    d[0] = 1
    ten = 1
    T = 0
    for x in reversed(s):
        T += ten*int(x)
        ten *= 10
        T %= mod
        ten %= mod
        if T in d:
            d[T] += 1
        else:
            d[T] = 1

    print(sum(i*(i-1)//2 for i in d.values()))
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N, W, *t = map( int, open( 0 ).read().split() )
d = [[ 0 for _ in range( W + 1 ) ] for _ in range( N + 1 ) ]
ans = 0

i = 0
for w, v in zip( *[ iter( t )] * 2 ):
  for j in range( 1, W + 1 ):
    d[ i + 1 ][ j ] = d[ i ][ j ]
    if j - w >= 0:
      d[ i + 1 ][ j ] = max( d[ i ][ j - w ] + v, d[ i ][ j ] )
  i += 1
print( d[N][W])

### FIXED CODE ###

N, W, *t = map( int, open( 0 ).read().split() )
d = [[ 0 for _ in range( W + 1 ) ] for _ in range( N + 1 ) ]
ans = 0
 
i = 0
for w, v in zip( *[ iter( t )] * 2 ):
  for j in range( 1, W + 1 ):
    d[ i + 1 ][ j ] = d[ i ][ j ]
    if j - w >= 0:
      d[ i + 1 ][ j ] = max( d[ i ][ j - w ] + v, d[ i ][ j ] )
  i += 1
print( d[N][W])
### BUGGY CODE ###

N, X, Y = map(int,input().split())
dis = Y-X

lists = [0 for i in range(N-1)]
for i in range(1,N+1):
    for j in range(i+1,N+1):
        if i <= X and Y <= j:
            pro = j-i-dis+1
            lists[pro-1] += 1
        elif i <= X and X <= j <= Y:
            pro = X+Y-i-j+1
            sta = j-i
            lists[min(pro,sta)-1] += 1
        elif X <= i <= Y and Y <= j:
            pro = i+j-X-Y+1
            sta = j-i
            lists[min(pro,sta)-1] += 1
        elif X <= i <= Y and X <= j <= Y:
            pro = i-j-X+Y+1
            sta = j-i
            lists[min(pro,sta)-1] += 1
        else:
            lists[j-i-1] += 1
            
for i in lists:
    print(i)

### FIXED CODE ###

N, X, Y = map(int,input().split())
dis = Y-X

lists = [0 for i in range(N-1)]
for i in range(1,Y):
    for j in range(i+1,N+1):
        if i <= X and Y <= j:
            pro = j-i-dis+1
            lists[pro-1] += 1
        elif i <= X and X <= j <= Y:
            pro = X+Y-i-j+1
            sta = j-i
            lists[min(pro,sta)-1] += 1
        elif X <= i <= Y and Y <= j:
            pro = i+j-X-Y+1
            sta = j-i
            lists[min(pro,sta)-1] += 1
        elif X <= i <= Y and X <= j <= Y:
            pro = i-j-X+Y+1
            sta = j-i
            lists[min(pro,sta)-1] += 1
        else:
            lists[j-i-1] += 1

for i in range(1,N-Y+1):
    lists[i-1] += N-Y-i+1
    
for i in lists:
    print(i)
### BUGGY CODE ###

from itertools import combinations

n= int(input())

l = [100,101,102,103,104,105]
res = [comb for i in range(1,10**5) for comb in combinations(l, i) if sum(comb) == n]

if len(res) >= 1:
  print(1)
else:
  print(0)

### FIXED CODE ###

x = int(input())

n = x%100

q,r=divmod(n,5)

if r:
  q+=1

if x//100 >= q:
  print(1)
else:
  print(0)
### BUGGY CODE ###

input()
a=list(input())
while a[0]=="R":
  del a[0]
  if a==[]:break
b=a.count('R')
print(b-a[:b].count('R'))

### FIXED CODE ###

input()
a=input()
if 'W'not in a:print(0);exit()
a=a[a.index('W'):]
b=a.count('R')
print(b-a[:b].count('R'))
### BUGGY CODE ###

S = input()
Q = int(input())
cnt = 0
for i in range(Q):
  x = list(input().split())
  if(int(x[0]) == 1):
    cnt += 1
  else:
    if((cnt+int(x[1])) % 2 == 1):
      S = x[2] + S
    else:
      S = S + x[2]
if(cnt % 2 == 1):
  print(S[::-1])
else:
  print(S)

### FIXED CODE ###

from collections import deque
S = deque(input())
Q = int(input())
cnt = 0
for i in range(Q):
  x = list(input().split())
  if(int(x[0]) == 1):
    cnt += 1
  else:
    if((cnt+int(x[1])) % 2 == 1):
      S.appendleft(x[2])
    else:
      S.append(x[2])

S = list(S)
if(cnt % 2 == 1):
  S = S[::-1]
print("".join(S))