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

k,s=[int(a) for a in 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=[int(a) for a in 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
#from scipy.special import comb
#from scipy.misc import comb

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

sys.setrecursionlimit(100000)
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

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

A = [0]*M

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

A.append(N+1)

def step_comb(L):
    c = 0
    if L==1 or L == 0:
        c = 1
    else:
        for i in range(L//2 +1):
            j = L - 2*i
            #c += comb(j+i, i, exact=True)
            c += cmb(j+i, i)
    return c

total_comb = 1
NOW = 0
for a in A:
    if NOW == a:
        print(0)
        sys.exit()
    L = a-1-NOW
    total_comb *= step_comb(L)
    NOW = a + 1
    
print(total_comb % 1000000007 )


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)

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

if M == 0:
    A = []
else:
    A = [0]*M
    for i in range(M):
        A[i] = int(input())

A.append(N+1)

# DP version
DP = [0]*(N+1)
DP[0] = 1
# １段の階段を登るやり方の数
DP[1] = 1
# 2段の階段を登るやり方の数
#DP[2] = 2

for i in range(2,N+1):
    DP[i] = DP[i-1] + DP[i-2]

def step_comb(L):
    if DP[L]>0:
        return DP[L]
    DP[L] = step_comb(L-1) + step_comb(L-2)
    return DP[L]
    
total_comb = 1
NOW = 0
for a in A:
    if NOW == a:
        print(0)
        sys.exit()
    L = a-1-NOW
    total_comb *= step_comb(L)
    NOW = a + 1
    if NOW == N:
        break
    
print(total_comb % 1000000007 )
### BUGGY CODE ###

def update(rt, ra, t, a):
    while rt * a != ra * t:
        if rt * a < ra * t:
            a += 1
        else:
            t += 1
    return t, a

n = int(input())
data = []
for i in range(n):
    elems = input().split()
    t, a = int(elems[0]), int(elems[1])
    data.append((t, a))

t, a = data[0]

for i in range(1, n):
    t, a = update(data[i][0], data[i][1], t, a)

print(t + a)


### FIXED CODE ###

from math import ceil

n = int(input())
data = []
for i in range(n):
    elems = input().split()
    t, a = int(elems[0]), int(elems[1])
    data.append((t, a))

t, a = data[0]

def calcn(r, x):
    n = int(x / r)
    while n * r > x:
        n -= 1
    while n * r < x:
        n += 1
    return n

for i in range(1, n):
    rt, ra = data[i][0], data[i][1]
    na = int(calcn(ra, a))
    nt = int(calcn(rt, t))
    n = max(na, nt)
    t = n * rt
    a = n * ra

print(t + a)
### BUGGY CODE ###

x=int(input())
s={2}
if x==2:
	print(2)
else:
	for i in range(3,10**6):
		if all(i%j!=0 for j in s):
			s.add(i)
			if i>=x:
				print(i)
				break


### FIXED CODE ###

x=int(input())
counter=0
while counter==0:
	counter=1
	for i in range(2,x):
		if x%i==0:
			counter=0
	if counter==1:
		print(x)
	else:
		x+=1
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))
ans = 1

for i in range(1, N):
    tmp_P = P[:i]
    if min(tmp_P) >= P[i]:
        ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
ans = 1

min_P = P[0]

for i in range(1, N):
    if min_P >= P[i]:
        ans += 1
        min_P = P[i]

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

import math
a, b, n = map(int, input().split())
ans = 0
for x in range(n, -1, -1):
    ans = max(ans, math.floor(a*x/b) - a*math.floor(x/b))
print(ans)

### FIXED CODE ###

from math import floor
a, b, n = map(int, input().split())
def f(x):
    return floor(a*x/b) - a*floor(x/b)
print(f(min(n, b-1)))
### BUGGY CODE ###

#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
#mod = 10**9 + 7

mod=2019
l,r=MI()
mn=inf
mods=[]
for i in range(l,r+1):
    mods.append(i%mod)
#print(mods)
if l-r>=2019:
    ans=0
else:
    for i in range(r-l+1):
        for j in range(i+1,r-l+1):
            u=(mods[i])*(mods[j])%mod
            if u<mn:
                mn=u
    ans=mn
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import math

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

l,r=MI()
mod=[]
if r-l>=2019:
    rm=0
    print(rm)
    sys.exit()
else:
    for i in range(l,r+1):
        mod.append(i%2019)
#print(mod)
mn=10**7
for i in range(len(mod)-1):
    for j in range(i+1,len(mod)):
        #print(mod[i],end=" ")
        #print(mod[j])
        ans=(mod[i]*mod[j])%2019
        if ans<mn:
            mn=ans
print(mn)
### BUGGY CODE ###

def d_static_sushi(N, C, Sushi):
    sushi_pos_cw = [row[0] for row in Sushi]
    sushi_pos_ccw = [abs(row[0] - C) for row in Sushi][::-1]
    sushi_value_cw = [row[1] for row in Sushi]
    sushi_value_ccw = sushi_value_cw[::-1]

    # 時計回り
    f1 = [sum(sushi_value_cw[:i + 1]) - sushi_pos_cw[i] for i in range(N)]
    g1 = [max(f1[:i + 1]) for i in range(N)]
    f2 = [sum(sushi_value_ccw[:i + 1]) - sushi_pos_ccw[i] for i in range(N)]
    g2 = [max(f2[:i + 1]) for i in range(N)]

    tmp1 = 0
    for b in range(N + 1):  # b:反時計回りに歩いて食べる寿司の個数
        if b == 0:
            cal = g1[N - 1]
        elif b == N:
            cal = f2[b - 1]
        else:
            cal = g1[N - b - 1] + f2[b - 1] - sushi_pos_ccw[b - 1]
        tmp1 = max(tmp1, cal)

    tmp2 = 0
    for a in range(N + 1):  # a:時計回りに歩いて食べる寿司の個数
        if a == 0:
            cal = g2[N - 1]
        elif a == N:
            cal = f1[a - 1]
        else:
            cal = g2[N - a - 1] + f1[a - 1] - sushi_pos_cw[a - 1]
        tmp2 = max(tmp2, cal)
    ans = max(tmp1, tmp2)
    return ans

N,C = [int(i) for i in input().split()]
Sushi = [[int(i) for i in input().split()] for j in range(N)]
print(d_static_sushi(N, C, Sushi))

### FIXED CODE ###

def d_static_sushi(N, C, Sushi):
    sushi_pos_cw = [row[0] for row in Sushi]
    sushi_pos_ccw = [abs(row[0] - C) for row in Sushi][::-1]
    sushi_value_cw = [row[1] for row in Sushi]
    sushi_value_ccw = sushi_value_cw[::-1]

    # 時計回り
    f1,g1,f2,g2=[],[],[],[]
    s1,s2=0,0
    for i in range(N):
        s1+=sushi_value_cw[i]-sushi_pos_cw[i]
        f1.append(s1)
        g1.append(s1)
        s1+=sushi_pos_cw[i]
        s2+=sushi_value_ccw[i]-sushi_pos_ccw[i]
        f2.append(s2)
        g2.append(s2)
        s2+=sushi_pos_ccw[i]
    for i in range(1,N):
        if g1[i]<g1[i-1]:
            g1[i]=g1[i-1]
        if g2[i]<g2[i-1]:
            g2[i]=g2[i-1]
    # print(f1,g1,f2,g2)
    # f1 = [sum(sushi_value_cw[:i + 1]) - sushi_pos_cw[i] for i in range(N)]
    # g1 = [max(f1[:i + 1]) for i in range(N)]
    # #反時計回り
    # f2 = [sum(sushi_value_ccw[:i + 1]) - sushi_pos_ccw[i] for i in range(N)]
    # g2 = [max(f2[:i + 1]) for i in range(N)]
    # print(f1,g1,f2,g2)
    tmp1 = 0
    for b in range(N + 1):  # b:反時計回りに歩いて食べる寿司の個数
        if b == 0:
            cal = g1[N - 1]
        elif b == N:
            cal = f2[b - 1]
        else:
            cal = g1[N - b - 1] + f2[b - 1] - sushi_pos_ccw[b - 1]
        tmp1 = max(tmp1, cal)

    tmp2 = 0
    for a in range(N + 1):  # a:時計回りに歩いて食べる寿司の個数
        if a == 0:
            cal = g2[N - 1]
        elif a == N:
            cal = f1[a - 1]
        else:
            cal = g2[N - a - 1] + f1[a - 1] - sushi_pos_cw[a - 1]
        tmp2 = max(tmp2, cal)
    ans = max(tmp1, tmp2)
    return ans

N,C = [int(i) for i in input().split()]
Sushi = [[int(i) for i in input().split()] for j in range(N)]
print(d_static_sushi(N, C, Sushi))
### BUGGY CODE ###

def mixing_experiment(N: int, Ma: int, Mb: int, drags: list)->int:
    INF = float('inf')

    max_A = N * max(a for a, _, _ in drags)
    max_B = N * max(b for _, b, _ in drags)

    dp = [[INF] * (max_B+1) for _ in range(max_A+1)]
    dp[0][0] = 0

    for (a, b, c) in drags:
        for ca in range(max_A-a, -1, -1):
            for cb in range(max_B-b, -1, -1):
                dp[ca+a][cb+b] = \
                    min(dp[ca+a][cb+b], dp[ca][cb] + c)
        dp[a][b] = min(dp[a][b], c)

    ans = min(
        dp[ca][cb]
        for ca in range(1, max_A+1)
        for cb in range(1, max_B+1)
        if ca * Mb == cb * Ma)
    # print(dp)

    return ans if 0 < ans and ans < INF else -1


if __name__ == "__main__":
    N = 0
    N, Ma, Mb = map(int, input().split())
    drags = [tuple(int(s) for s in input().split()) for _ in range(N)]
    ans = mixing_experiment(N, Ma, Mb, drags)
    print(ans)


### FIXED CODE ###

# import time


def mixing_experiment(N: int, Ma: int, Mb: int, drags: list)->int:
    INF = float('inf')

    max_A = min(100, N * max(a for a, _, _ in drags))
    max_B = min(100, N * max(b for _, b, _ in drags))

    dp = [[INF] * (max_B+1) for _ in range(max_A+1)]
    dp[0][0] = 0

    # print(max_A, max_B)
    # t1 = time.time()

    # op = 0
    for (a, b, c) in drags:
        for ca in range(max_A-a, -1, -1):
            for cb in range(max_B-b, -1, -1):
                dp[ca+a][cb+b] = \
                    min(dp[ca+a][cb+b], dp[ca][cb] + c)
                # dp[ca+a][cb+b] = 0
                # op += 1
        dp[a][b] = min(dp[a][b], c)

    # t2 = time.time()
    # print('dp: {} [s]'.format(t2 - t1))

    ans = INF
    for ca in range(1, max_A+1):
        for cb in range(1, max_B+1):
            if ca * Mb != cb * Ma:
                continue
            ans = min(ans, dp[ca][cb])

    # t3 = time.time()
    # print('min: {} [s]'.format(t3 - t2))

    return ans if 0 < ans and ans < INF else -1


if __name__ == "__main__":
    N = 0
    N, Ma, Mb = map(int, input().split())
    drags = [tuple(int(s) for s in input().split()) for _ in range(N)]
    ans = mixing_experiment(N, Ma, Mb, drags)
    print(ans)
### BUGGY CODE ###

from re import search


# f = open("./16/input_c2_2.txt")


# def input():
#     return f.readline().rstrip()


def main():
    S = input()

    while True:
        result_1 = search('dreamer$', S)
        result_2 = search('eraser$', S)
        result_3 = search('erase$', S)
        result_4 = search('dream$', S)

        if result_1:
            S = S[:result_1.start()]
        elif result_2:
            S = S[:result_2.start()]
        elif result_3:
            S = S[:result_3.start()]
        elif result_4:
            S = S[:result_4.start()]
        else:
            print("NO")
            break

        if len(S) == 0:
            print("YES")
            break


if __name__ == "__main__":
    main()


### FIXED CODE ###


def main():
    S = input()
    while True:
        if S[-7:] == "dreamer":
            S = S[:-7]
        elif S[-6:] == "eraser":
            S = S[:-6]
        elif S[-5:] == "erase":
            S = S[:-5]
        elif S[-5:] == "dream":
            S = S[:-5]
        else:
            print("NO")
            break

        if len(S) == 0:
            print("YES")
            break


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

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

a = 0  # 1000
b = 0  # 5000
c = 0  # 10000

c = y//10000
b = (y - c*10000)//5000
a = (y - c*10000 - b*5000)//1000

flag = True

while (a+b+c) <= n:
    num = a+b+c
#    print(num)
#    print(c,b,a)
    if num == n:
        flag = False
        break
    else:
        if num + 9 <= n and c > 0:
            c -= 1
            a += 10
            continue
        elif num + 4 <= n and b > 0:
            b -= 1
            a += 5
            continue
        elif num + 1 <= n and c > 0:
            c -= 1
            b += 2
            continue

if flag:
    print(-1, -1, -1)
else:
    print(c, b, a)




### FIXED CODE ###

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

a = 0  # 1000
b = 0  # 5000
c = 0  # 10000

c = y//10000
b = (y - c*10000)//5000
a = (y - c*10000 - b*5000)//1000

flag = True

while (a+b+c) <= n:
    num = a+b+c
#    print(num)
#    print(c,b,a)
    if num == n:
        flag = False
        break
    else:
        if num + 9 <= n and c > 0:
            c -= 1
            a += 10
            continue
        elif num + 4 <= n and b > 0:
            b -= 1
            a += 5
            continue
        elif num + 1 <= n and c > 0:
            c -= 1
            b += 2
            continue
        else:
            break
if flag:
    print(-1, -1, -1)
else:
    print(c, b, a)
### BUGGY CODE ###

def sub(a, b, n):
 r = a[:]
 for i in range(len(b)):
  r[i] -= b[i] * n
 return r

def mult(a, n):
 r = a[:]
 for i in range(len(a)):
  r[i] *= n
 return r

def pm(matr):
 return ""

def rref(matr):
 if len(matr) == 0 or len(matr[0]) == 0:
  return matr
 pivotCt = 0
 for d in range(max(len(matr), len(matr[0])-1)):
  #scan for first pivot
  pivot = None
  for i in range(len(matr)):
   allZeroes = True
   for j in range(d):
    if matr[i][j] != 0:
     allZeroes = False
     break
   if matr[i][d] != 0 and allZeroes:
    pivot = mult(matr[i], 1/matr[i][d])
    del matr[i]
    matr.insert(pivotCt, pivot)
    break
  if pivot != None:
   for i in range(len(matr)):
    if i != pivotCt and matr[i][d] != 0:
     matr[i] = sub(matr[i], pivot, matr[i][d])
   pivotCt += 1
 return matr

s = raw_input().split(" ")
vs = int(s[0])
es = int(s[1])

matr = []
for i in range(es):
 matr.append([0] * (vs + 1))
 q = raw_input().split(" ")
 x = int(q[0])
 y = int(q[1])
 z = int(q[2])
 matr[i][x] = 1
 matr[i][y] = -1
 matr[i][-1] = z

matr = rref(matr)
bad = False
for i in range(len(matr)):
 allZeroes = True
 for j in range(len(matr[0])-1):
  if matr[i][j] != 0:
   allZeroes = False
   break
 if allZeroes and matr[i][-1] != 0:
   bad = True
   break

if bad:
 print "No"
else:
 print "Yes"

### FIXED CODE ###

n, m = map(int, input().split())
inf = 10**10
G = [{} for i in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    G[l-1][r-1] = d
    G[r-1][l-1] = -d
V = [False for i in range(n)]
D = [inf for i in range(n)]
for i in range(n):
    if V[i]:
        continue
    Q = [i]
    D[i] = 0
    while Q:
        j = Q.pop()
        V[j] = True
        for k in G[j].keys():
            if not V[k]:
                Q.append(k)
            if D[k] == inf:
                D[k] = D[j]+G[j][k]
            elif D[k] != D[j]+G[j][k]:
                print('No')
                exit()
print('Yes')
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

from collections import defaultdict
G = defaultdict(list)

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

from bisect import bisect
ansl = [0 for i in range(n)]
dp = [float("inf") for _ in range(n+1)]
dp[0] = -1
used = [0 for i in range(n)]
used[0] = 1

p = 0
stack = []
def dfs(pos, dp):
    global p
    if p == n:
        return
    idx = bisect(dp, al[pos] - 1)
    stack.append((idx, dp[idx]))
    dp[idx] = min(al[pos], dp[idx])
    ansl[pos] = max(i for i in range(n+1) if dp[i] < float("inf"))
    for v in G[pos]:
        if used[v] == 0:
            used[v] = 1
            p += 1
            dfs(v, dp)
            idx, k = stack.pop()
            dp[idx] = k


dfs(0, dp)
flag = False
for i in range(n):
    print(ansl[i])




### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

import sys
input = sys.stdin.readline

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

from collections import defaultdict
G = defaultdict(list)

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

from bisect import bisect
ansl = [0 for i in range(n)]
dp = [float("inf") for _ in range(n+1)]
dp[0] = -1
used = [0 for i in range(n)]
used[0] = 1


stack = []
def dfs(pos):
    idx = bisect(dp, al[pos] - 1)
    stack.append((idx, dp[idx]))
    dp[idx] = min(al[pos], dp[idx])
    ansl[pos] = bisect(dp, 10**18) - 1
    for v in G[pos]:
        if used[v] == 0:
            used[v] = 1
            dfs(v)
            idx, k = stack.pop()
            dp[idx] = k


dfs(0)
flag = False
for i in range(n):
    print(ansl[i])
### BUGGY CODE ###

R, G, B, n=map(int, input().split())

r=n//R
g=n//G
b=n//B

cnt=0
for i in range(r+1):
    for j in range(g+1):
        tmp = i*R + j*G
        if (n-tmp)%B == 0 and 0 <= (n-tmp)//B :
            cnt+=1


print(cnt)

### FIXED CODE ###

R, G, B, n=map(int, input().split())

r=n//R
g=n//G
b=n//B

cnt=0
for i in range(r+1):
    for j in range(g+1):
        tmp = i*R + j*G
        if (n-tmp)%B == 0 and 0 <= (n-tmp)//B <= b:
            cnt+=1


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

N,K = map(int,input().split())
hitpoint = list(map(int,input().split()))
hitpoint.sort(reverse=True)
if N<=K:
    print(0)
else:
    for i in range(K):
        del hitpoint[0]
    print(sum(hitpoint))

### FIXED CODE ###

N,K = map(int,input().split())
hitpoint = list(map(int,input().split()))
hitpoint.sort(reverse=True)
if N<=K:
    print(0)
else:
    print(sum(hitpoint[K:]))
### BUGGY CODE ###

n = int(input())
a = sorted(list(map(int,input().split())))
b = sorted(list(map(int,input().split())))
c = sorted(list(map(int,input().split())))
p = [0]*n
q = [0]*n
k = 0
for i in range(n):
  while k<n:
    if a[k]<b[i]:
      k += 1
    else:
      break
  p[i] = k
k = 0
for i in range(n):
  while k<n:
    if b[k]<c[i]:
      k += 1
    else:
      break
  q[i] = sum(p[:k])
print(sum(q))


### FIXED CODE ###

n = int(input())
a = sorted(list(map(int,input().split())))
b = sorted(list(map(int,input().split())))
c = sorted(list(map(int,input().split())))
p = [0]*n
q = [0]*n
k = 0
for i in range(n):
  while k<n:
    if a[k]<b[i]:
      k += 1
    else:
      break
  p[i] = k
k = 0
s = 0
ans = 0
for i in range(n):
  while k<n:
    if b[k]<c[i]:
      s += p[k]
      k += 1
    else:
      break
  ans += s
print(ans)
### BUGGY CODE ###

N = int(input())
li = []
for i in range(N):
    k = input()
    if not k in li :
        li.append(k)
print(len(li))

### FIXED CODE ###

N = int(input())
li = []
for i in range(N):
    li.append(input())
print(len(set(li)))
### 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

        ans += k*(k+1)//2

        s = s[:l] + "BC"*k + "A"*k + s[r:]

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 = int(input())
a, b = map(int, input().split())
for i in range(n - 1):
    c, d = map(int, input().split())
    while a * d != b * c:
        if a * d > b * c:
            b += 1
        elif a * d < b * c:
            a += 1

print(a + b)

### FIXED CODE ###

from decimal import *
import math
n = int(input())
a, b = map(int, input().split())
for i in range(n - 1):
    c, d = map(int, input().split())
    q = Decimal(max(math.ceil(a / c), math.ceil(b / d)))
    a, b = c * q, d * q

print(a + b)
### BUGGY CODE ###

import numpy as np


n, m = [int(x) for x in input().split()]

costs = []
masks = []

for _ in range(m):
    costs.append(int(input().split()[0]))

    boxes = {int(x)-1 for x in input().split()}
    mask = ['1' if idx in boxes else '0' for idx in range(n)][::-1]
    mask = int(''.join(mask), 2)
    masks.append(mask)

INF = int(10e8 + 1)
dp = np.full(1 << n, INF, dtype=int)
dp[0] = 0

for j in range(m):
    for i in range(1 << n):
        dp[i | masks[j]] = min(
                dp[i | masks[j]],
                dp[i] + costs[j]
            )

res = dp[-1] if dp[-1] != INF else -1
print(res)


### FIXED CODE ###

n, m = [int(x) for x in input().split()]

INF = int(10e8 + 1)
dp = [INF] * (1 << n)
dp[0] = 0

for j in range(m):
    cost = int(input().split()[0])

    boxes = [int(x)-1 for x in input().split()]
    mask = 0

    mask = sum(1 << box for box in boxes)
    
    for i in range(1 << n):
        if dp[i] + cost < dp[i | mask]:
            dp[i | mask] = dp[i] + cost

res = dp[-1] if dp[-1] != INF else -1
print(res)
### BUGGY CODE ###

N=int(input())
List = list(map(int, input().split()))
res=0
for i in range(N-1):
  a = List[i] % 1000000007
  for j in range(i+1,N):
    b =  List[j] % 1000000007
    res += a*b
print(res%1000000007)

### FIXED CODE ###

N=int(input())
List = list(map(int, input().split()))
midList = [0]*(N-1)
mid = 0
for i in range(N-2,-1,-1):
  mid += List[i+1]
  midList[i] = mid
res=0
for i in range(N-1):
  a = List[i] % 1000000007
  b =  midList[i] % 1000000007
  res += a*b
print(res%1000000007)
### BUGGY CODE ###

import sys

# inputを高速化する。
input = sys.stdin.readline

# 入力
N, W = map(int, input().split())

dp = [0] * (W + 1)

for _ in range(N):
    weight, value = map(int, input().split())
    for wk in range(W, weight-1, -1):
        tv = dp[wk - weight] + value
        if tv > dp[wk]:
            dp[wk] = tv

print(dp[-1])

### FIXED CODE ###


import sys

input = sys.stdin.readline

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

dp = [0] * (W + 1)
def knapsack(n, w):
    for _ in range(N):
        w, v = map(int, input().split())
        for wk in range(W, w-1, -1):
            tv = dp[wk - w] + v
            if tv > dp[wk]:
                dp[wk] = tv
    return dp[-1]

print(knapsack(N, W))