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

N=int(input())
A=list(map(int,input().split()))
x=0
for i in range(N):
  x+=A[i]*(sum(A)-A[i])
print(x//2%1000000007)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
x=0
x=sum(A)**2
for i in A:
  x-=i**2
print(x//2%1000000007)
### BUGGY CODE ###

K,S=map(int,input().split())
ans=0
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):ans+=1 if i+j+k==S else 0
print(ans)

### FIXED CODE ###

K,S=map(int,input().split())
ans=0
for i in range(K+1):
    for j in range(K+1):
        if S-i-j<=K and 0<=S-i-j:ans+=1
print(ans)
### BUGGY CODE ###

from collections import defaultdict

S = input()
n = len(S)

mp = defaultdict(int)
mp[0] += 1
for i in range(0, n):
    s = S[i:]
    m = int(s) % 2019
    mp[m] += 1

ans = 0
for m in mp.values():
    ans += m * (m - 1) // 2

print(ans)



### FIXED CODE ###

from collections import defaultdict
import random

S = input()
n = len(S)

mp = defaultdict(int)
mp[0] += 1
x = 0
y = 1
for i, s in enumerate(reversed(S)):
    x = (x + int(s) * y) % 2019
    y = (y * 10) % 2019
    mp[x] += 1

ans = 0
for m in mp.values():
    ans += m * (m - 1) // 2

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

import itertools

N,K=list(map(int,raw_input().split()))
a = []
for i in range(N):
    a.append(map(int,raw_input().split()))
#print "# a"
#print a


b=[]
for i in range(N):
	for j in range(N):
		#print i,j,a[i][0],a[j][1]
		b.append([a[i][0],a[j][1]])

#print "# b"
#print b
#print len(b)


c=[]
c=list(itertools.combinations(b, 2))
#print "# c"
#print c
#print len(c)

area=[]
for i in range(len(c)):
	area.append(abs(c[i][0][0]-c[i][1][0])*abs(c[i][0][1]-c[i][1][1]))

#print area

for i in range(len(c)):
	cnt=0
	x1=c[i][0][0]
	x2=c[i][1][0]
	y1=c[i][0][1]
	y2=c[i][1][1]
	#print x1,y1,x2,y2
	for j in range(len(a)):
		#print a[j][0],a[j][1]
		if (a[j][0]>=x1 and a[j][0]<=x2) or (a[j][0]>=x2 and a[j][0]<=x1):
			if (a[j][1]>=y1 and a[j][1]<=y2) or (a[j][1]>=y2 and a[j][1]<=y1):
				cnt+=1
	#print cnt
	if cnt<K:
		area[i]=-1

#print area

min=0
for i in range(len(area)):
	if area[i]==-1:
		continue
	elif min==0:
		min=area[i]
	elif area[i]<min:
		min=area[i]

print min



### FIXED CODE ###

import itertools

N,K=list(map(int,raw_input().split()))
x=[]
y=[]
pts=[]
for i in range(N):
	a1,a2=map(int,raw_input().split())
	x.append(a1)
	y.append(a2)
	pts.append([a1,a2])

#print "# x,y"
x.sort()
y.sort()
#print x
#print y

#print "# pts"
#print pts
pts.sort(key=lambda x:x[0])
#print pts

ans=10**20


for y1 in y:
	for y2 in y:
		if y1>=y2:
			continue
		for x1 in x:
			cnt=0
			for p in pts:
				if p[0]>=x1 and p[1]>=y1 and p[1]<=y2:
					#print p[0],p[1],x1,y1,y2
					cnt+=1
					if cnt==K:
						x2=p[0]
						#print x1,y1,x2,y2,cnt,abs(x2-x1)*abs(y2-y1)
						ans=min(ans,abs(x2-x1)*abs(y2-y1))
						break

print ans
### BUGGY CODE ###

n = int(input())
ans = 1
for i in range(1,n+1):
    ans *= i
ans = ans % (10 ** 9 + 7)
print(ans)

### FIXED CODE ###

import math
n = int(input())
ans = math.factorial(n) % (10 ** 9 + 7)
print(ans)
### BUGGY CODE ###

n = int(input())
a_list = [int(x) for x in input().split()]
b = []
for i, a in enumerate(a_list):
    if i % 2 == 0:
        # b = b + [a]
        b.append(a)
    else:
        # b = [a] + b
        b.insert(0, a)
if n % 2 == 1:
    b = list(reversed(b))
print(*b)

### FIXED CODE ###

from collections import deque
n = int(input())
a_list = [int(x) for x in input().split()]
left_flag = n % 2 == 1
d = deque()
for a in a_list:
    if left_flag:
        d.appendleft(a)
    else:
        d.append(a)
    left_flag = not left_flag
print(*d)
### BUGGY CODE ###

in_list = input().split()
A, B, K = int(in_list[0]), int(in_list[1]), int(in_list[2])

for k in range(K):
  if A > 0:
    A -= 1
  elif B > 0:
    B -= 1
  else:
    pass

print(A, B)


### FIXED CODE ###

import sys

def stdin_parse_int():
    a = list(map(int,input().split()))
    return a

list = stdin_parse_int()
A = list[0]
B = list[1]
K = list[2]

if A > K:
    print(str(A-K) + " " + str(B))
elif A+B > K:
    print(str(0) + " " + str(A+B-K))
else:
    print("0 0")
### BUGGY CODE ###

import sys
from collections import Counter
from functools import lru_cache

import numpy as np

sys.setrecursionlimit(2147483647)
INF = float('inf')

MOD = 10 ** 9 + 7
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))


def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    :return:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


factorials = get_factorials(N + 1, MOD)


# @lru_cache(maxsize=None)
def ncr(n, r, mod=None):
    """
    scipy.misc.comb または scipy.special.comb と同じ
    組み合わせの数 nCr
    :param int n:
    :param int r:
    :param int mod: 3 以上の素数であること
    :rtype: int
    """
    if n < r:
        return 0

    def inv(a):
        """
        a の逆元
        :param a:
        :return:
        """
        return pow(a, mod - 2, mod)

    if mod:
        return factorials[n] * inv(factorials[r]) * inv(factorials[n - r]) % mod
    else:
        return factorials[n] // factorials[r] // factorials[n - r]


# どことどこが一緒？
A = np.array(A)
dup, _ = Counter(A).most_common(1)[0]
L, r = np.where(A == dup)[0]

# dup より端から i 個選ぶ組み合わせ
sides = np.array([ncr(L + N - r, i, MOD) for i in range(N + 2)])

for k in range(1, N + 2):
    c = ncr(N + 1, k, MOD)
    # 選びすぎを引く
    # dup を 1 つ選び、その他は全部 dup より端から選ぶ組み合わせ
    c -= sides[k - 1]
    print(c % MOD)


### FIXED CODE ###

import sys
from collections import Counter

import numpy as np

sys.setrecursionlimit(2147483647)
INF = float('inf')

MOD = 10 ** 9 + 7
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))


def mod_invs(max, mod):
    invs = [1] * (max + 1)
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def get_ncrs(n):
    invs = mod_invs(N + 1, MOD)
    ret = [1]
    ncr = 1
    for i in range(1, n + 1):
        ncr = ((ncr * (n - i + 1) % MOD) * invs[i]) % MOD
        ret.append(ncr)
    return ret


# どことどこが一緒？
A = np.array(A)
dup, _ = Counter(A).most_common(1)[0]
L, r = np.where(A == dup)[0]

# dup より端から i 個選ぶ組み合わせ
side_ncrs = get_ncrs(L + N - r)
while len(side_ncrs) < N + 2:
    side_ncrs.append(0)

# 全部選んで選びすぎを引く
# dup を 1 つ選び、その他を dup より端から選ぶ組み合わせが重複する
ans_ncrs = get_ncrs(N + 1)
while len(ans_ncrs) < N + 2:
    ans_ncrs.append(0)
ans = [(ans_ncrs[k] - side_ncrs[k - 1]) % MOD for k in range(1, N + 2)]

print('\n'.join(map(str, ans)))
### BUGGY CODE ###

N = int(input())
a = [int(input()) for _ in range(N)]
each_a = set(a)
count = 0
for i in each_a:
    if a.count(i) % 2 == 1:
        count += 1
print(count)

### FIXED CODE ###

N = int(input())
a = {}
for i in range(N):
    j = int(input())
    if j in a:
        a[j] += 1
    else:
        a[j] = 1
count = 0
for v in a.values():
    if v % 2 == 1:
        count += 1
print(count)
### BUGGY CODE ###

S = [c for c in input()]
N = int(input())
r = 0

for i in range(N):
	values = input().split()
	if values[0] == '1':
		r ^= 1
	else:
		f = int(values[1]) - 1
		if f == r:
			S.insert(0, values[2])
		else:
			S.append(values[2])

if r == 0:
	print(''.join(S))
else:
	print(''.join(S)[::-1])






### FIXED CODE ###

S = [c for c in input()]
N = int(input())
r = 0

B = []

for i in range(N):
	values = input().split()
	if values[0] == '1':
		r ^= 1
	else:
		f = int(values[1]) - 1
		if f == r:
			B.append(values[2])
		else:
			S.append(values[2])

if r == 0:
	print(''.join(B[::-1] + S))
else:
	print(''.join(S[::-1] + B))
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import numpy as np
N = int(input())
A = np.array(list(map(int,input().split())))
table = []
 
for i, a in enumerate(A):
    table.append([a,i])
table.sort()
dp = [[0 for i in range(N+1)]for j in range(N+1)]
for i in range(1,N+1):
    baby,pos = table.pop()
    dp[i][0]=dp[i-1][0]+baby*abs(pos-i+1)
    dp[0][i] = dp[0][i-1] + baby * abs(pos-(N-i))
    for x in range(1,i):
        y = i-x
        dp[x][y]=  max(dp[x-1][y] + baby * abs(pos-x+1),dp[x][y-1] + baby * abs(pos-(N-y)))
print(max(dp[k][N-k] for k in range(N+1)))
    

### FIXED CODE ###

# coding: utf-8
# Your code here!
#import numpy as np
N = int(input())
A = list(map(int,input().split()))
table = []
 
for i, a in enumerate(A):
    table.append([a,i])
table.sort()
dp = [[0for i in range(N+1)]for j in range(N+1)]
for i in range(1,N+1):
    baby,pos = table.pop()
    dp[i][0]=dp[i-1][0]+baby*abs(pos-i+1)
    dp[0][i] = dp[0][i-1] + baby * abs(pos-(N-i))
    for x in range(1,i):
        y = i-x
        dp[x][y]= max(dp[x-1][y] + baby * abs(pos-x+1),dp[x][y-1] + baby * abs(pos-(N-y)))
print(int(max(dp[k][N-k] for k in range(N+1))))
### BUGGY CODE ###

from collections import defaultdict

n, m = map(int, input().split())
ac = 0
wa = 0
a = []
b = defaultdict(int)
for _ in range(m):
    q, j = input().split()
    if q in a:
        continue
    if q not in a and j == 'AC':
        ac += 1
        a.append(q)
        if q in b:
            wa += b[q]
    else:
        b[q] += 1
print(ac, wa)


### FIXED CODE ###

import sys
from collections import defaultdict
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    ac = 0
    wa = 0
    b = defaultdict(lambda: 0)
    for _ in range(m):
        q, j = input().split()
        if b[q] != -1 and j == 'AC':
            ac += 1
            if q in b:
                wa += b[q]
                b[q] = -1
        else:
            if b[q] != -1:
                b[q] += 1
    print(ac, wa)

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

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

DP = [0 for k in range(K+1)] #和がkとなる部分集合の数
DP[0] = 1
for a in A:
  for k in range(K-a,-1,-1):
    DP[k+a] += DP[k]

"""
for k in range(1,2*K+1): #累積和へ変換
  DP[k] += DP[k-1]
print(DP)
"""
"""
if sum(DP[0:K]) == 2**N:
  print(N)
  sys.exit()
"""
#print(DP)  
ans = 0
DP_rev = [0 for _ in range(K)] #戻すDP!!!
for a in A:
  flag = True
  if a >= K: continue
  for i in range(K):
    DP_rev[i] = DP[i] 
    if i-a >= 0:
      DP_rev[i] -= DP_rev[i-a]
    if i >= K-a and DP_rev[i] > 0:
      #print(i,a)
      flag = False
      break
  if flag:
    ans += 1
  #print(a, DP_rev)
    
print(ans)
  
  
  
  


### FIXED CODE ###

import sys
N, K = map(int, input().split())
A = list(map(int, input().split()))
#A = [i for i in range(1,2)] + [i for i in range(2,1001)] * 4
A.sort()

DP = [0 for k in range(K+1)] #和がkとなる部分集合の数
DP[0] = 1
for a in A:
  for k in range(K-a,-1,-1):
    DP[k+a] += DP[k]

"""
for k in range(1,2*K+1): #累積和へ変換
  DP[k] += DP[k-1]
print(DP)
"""
"""
if sum(DP[0:K]) == 2**N:
  print(N)
  sys.exit()
"""
#print(DP)  


def det(t):
  a = A[t]
  if a >= K:
    return False
  DP_rev = [0 for _ in range(K)] #戻すDP!!!
  ans = True
  for i in range(K):
    DP_rev[i] = DP[i] 
    if i-a >= 0:
      DP_rev[i] -= DP_rev[i-a]
    if i >= K-a and DP_rev[i] > 0:
      ans = False
      break
  del DP_rev
  return ans

lt = 0
rt = N-1
if not det(lt):
  print(0)
  sys.exit()
if det(rt):
  print(rt+1)
  sys.exit()

while rt - lt > 1:
  ct = (lt + rt) // 2
  if det(ct):
    lt = ct
  else:
    rt = ct
print(rt)
### BUGGY CODE ###

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

min_sum = -1
i_atmin = -1

# for i in range(0, 2*(10**5) + 2) :
i = 0
while(1) : 
    sum_over = 0
    sum_over_minus = 0
    
    for j in range(N) :
        sum_over += abs(a[j] - (i + j))
        
    for j in range(N) :
        sum_over_minus += abs(a[j] - (j - i))
        
    if min_sum != -1 and min(sum_over, sum_over_minus) > min_sum :
        break
        
    if min_sum == -1 or min(sum_over, sum_over_minus) < min_sum :
        min_sum = min(sum_over, sum_over_minus)
        
    i += 1
        
print(min_sum)

### FIXED CODE ###

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

B = [y - x - 1 for x, y in enumerate(a)]
B_s = sorted(B)

# if odd 
if N % 2 == 1 :  
    median = [B_s[int(N / 2)]]
else :
    median = [B_s[int(N / 2)], B_s[int(N / 2) + 1]]

min_sum = None 

for m in median :
    sum_over = 0
    
    for i, j in enumerate(a) :
        sum_over += abs(j - (m + i + 1))

    if min_sum == None or sum_over < min_sum :
        min_sum = sum_over
        
print(min_sum)
### BUGGY CODE ###

list1=[2,3,5,7,11,13,17,19]
for i in range(21,100000,2):
    flag=0
    for j in range(3,318):
        if i%2==0:
            flag=1
            break
        elif i<j**2:
            break
        elif i%j==0:
            flag=1
            break
    #print(i,flag)
    if flag==0:
        list1.append(i)
#print(list1)

N=int(input())
for k in range(N):
    A=input()
    A=A.rstrip().split(" ")
    A1=int(A[0])
    A2=int(A[1])
#print(A1,A2)
    cnt=0
    for l in list1:
        if A1<= l <=A2 and (int((l+1)/2) in list1) :
            cnt+=1
    print(cnt)
    

### FIXED CODE ###

listS=[1]*100005
listS[0]=0
listS[1]=0
for i in range(2,100003):
    if listS[i]==1:
        for j in range(2*i,100000,i):
            listS[j]=0
list2017=[0]
for k in range(1,100001):
    if listS[k]==1 and listS[int((k+1)/2)]==1:
        list2017.append(list2017[k-1]+1)
    else:
        list2017.append(list2017[k-1])

N=int(input())
for x in range(N):
    l,m=map(int,input().split())
    print(list2017[m]-list2017[l-1])
### BUGGY CODE ###

n, m = map(int, input().split())
A = sorted(list(map(int, input().split())))
C = []
for _ in range(m):
    b, c = map(int, input().split())
    for _ in range(b):
        C.append(c)
C = sorted(C, reverse=True)

ans = 0
for i in range(n):
    try:
        ans += max(A[i], C[i])
    except IndexError:
        ans += A[i]

print(ans)


### FIXED CODE ###

n, m = map(int, input().split())
A = sorted(list(map(int, input().split())))
BC = sorted([list(map(int, input().split())) for _ in range(m)], key=lambda x: x[1], reverse=True)

ans = 0
j = 0
for b, c in BC:
    for i in range(b):
        if j < n:
            ans += max(c, A[j])
            j += 1
        else:
            break

if j < n:
    for i in range(n - j):
        ans += A[n - 1 - i]

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

import collections

N = int(input())

a = list()

for i in range(N):
    S = input()
    a.append(S)

c = collections.Counter(a)

#print(c.most_common()[0][1])

b =list()

if(N == len(c)):
    b = list(set(a))
    b.sort()
    for i in range(len(b)):
        print(b[i])
else:
    for i in range(len(c)):
        if (int(c.most_common()[0][1]) == int(c.most_common()[i][1])):
            b.append(c.most_common()[i][0])

    b.sort()

    for i in range(len(b)):
        print(b[i])


### FIXED CODE ###

from collections import*
_,*s=open(0)
c=Counter(s).most_common()
print(*sorted(a*(b==c[0][1])for a,b in c))
### BUGGY CODE ###

import heapq
X, Y, Z, K = map(int, raw_input().split())
A = map(int, raw_input().split())
B = map(int, raw_input().split())
C = map(int, raw_input().split())

h1 = []
for a in A:
  for b in B:
    heapq.heappush(h1, -a - b)

h2 = []
for _ in range(min(K, X * Y)):
  ab = -heapq.heappop(h1)
  for c in C:
    heapq.heappush(h2, -ab - c)

for _ in range(K):
  print -heapq.heappop(h2)

### FIXED CODE ###

import heapq
X, Y, Z, K = map(int, raw_input().split())
A = map(int, raw_input().split())
B = map(int, raw_input().split())
C = map(int, raw_input().split())

h1 = []
for a in A:
  for b in B:
    heapq.heappush(h1, -a - b)

h2 = []
for _ in range(min(K, X * Y)):
  ab = -heapq.heappop(h1)
  for c in C:
    heapq.heappush(h2, -ab - c)

for _ in range(K):
  print -heapq.heappop(h2)
### BUGGY CODE ###

#!/usr/bin/python3
import copy

def minOp(h, w, k, yl, s):
    xl = []
    ks = [ 0 for i in range(len(yl) + 1) ]

    for x in range(w):
        py = 0
        cks = [ 0 for i in range(len(yl) + 1) ]
        for idx, y in enumerate(yl + [h - 1]):
            for yy in range(py, y + 1):
                if s[yy][x] == '1':
                    cks[idx] += 1

            py = y + 1

        over = False
        for idx, kk in enumerate(ks):
            if kk + cks[idx] > k:
                over = True

        if over:
            xl.append(x - 1)
            ks = copy.copy(cks)
        else:
            ks = list(map(lambda a, b: a + b, ks, cks))

    return len(xl) + len(yl)
    

def devideVertical(h, w, k, cy, yl, s):
    m = (h - 1) + (w - 1)
    for y in range(cy, h - 1):
        nyl = copy.copy(yl)
        nyl.append(y)
        m = min(m, devideVertical(h, w, k, y + 1, nyl, s))
    
    m = min(m, minOp(h, w, k, yl, s))
    return m

(h, w, k) = map(int, input().split())
s = []
for i in range(h):
    s.append(input())

print(devideVertical(h, w, k, 0, [], s))




### FIXED CODE ###

#!/usr/bin/python3
import copy

def minOp(h, w, k, yl, s):
    xl = []
    ks = [ 0 for i in range(len(yl) + 1) ]

    for x in range(w):
        py = 0
        cks = [ 0 for i in range(len(yl) + 1) ]
        for idx, y in enumerate(yl + [h - 1]):
            for yy in range(py, y + 1):
                if s[yy][x] == '1':
                    cks[idx] += 1

            py = y + 1

        over = False
        for idx, kk in enumerate(ks):
            if kk + cks[idx] > k:
                over = True

        if over:
            for ck in cks:
                if ck > k:
                    return (h - 1) + (w - 1)
            xl.append(x - 1)
            ks = copy.copy(cks)
        else:
            ks = list(map(lambda a, b: a + b, ks, cks))
            
    return len(xl) + len(yl)
    

def devideVertical(h, w, k, cy, yl, s):
    m = (h - 1) + (w - 1)
    for y in range(cy, h - 1):
        nyl = copy.copy(yl)
        nyl.append(y)
        m = min(m, devideVertical(h, w, k, y + 1, nyl, s))
    
    m = min(m, minOp(h, w, k, yl, s))
    return m

(h, w, k) = map(int, input().split())
s = []
for i in range(h):
    s.append(input())

print(devideVertical(h, w, k, 0, [], s))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
a.sort()
p = 0

for i in range(n):
    for j in range(n):
        if i == j:
            pass
        elif a[i] % a[j] == 0:
            break
        else:
            pass
        if j == n - 1:
                p += 1

print(p)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
m = max(a)
flag = [True]*(m+1)
c = [0]*(m+1)
b = list(sorted(a))
for i in b:
    x = i + i
    while x <= m:
        flag[x] = False
        x += i
    c[i] += 1
ans = 0
x = 0
l = []
ans = 0
for i in a:
    if flag[i] and c[i] <= 1:
        ans += 1
print(ans)
### BUGGY CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

def invalid(a, b):
    if a > b:
        a, b = b, a
    return (b % a == 0 and ((b - a) // 2) % a != 0)

def main():
    N, M = map(int, input().split())
    A = list(set(map(int, input().split())))
    A.sort(reverse=True)
    if len(A) == 1:
        l = A[0]
    else:
        if invalid(A[0], A[1]):
            return 0
        l = lcm(A[0], A[1])
        for i in A[2:]:
            if invalid(l, i):
                return 0
            if l % i == 0:
                continue
            l = lcm(l, i)
    return (M + l // 2) // l

print(main())


### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

def invalid(a, b):
    if a > b:
        a, b = b, a
    return (b % a == 0 and ((b - a) // 2) % a != 0)

def main():
    N, M = map(int, input().split())
    A = list(set(map(int, input().split())))
    A.sort(reverse=True)
    if len(A) == 1:
        l = A[0]
    else:
        if invalid(A[0], A[1]):
            return 0
        l = lcm(A[0], A[1])
        for i in A[2:]:
            if invalid(l, i):
                return 0
            if l % i == 0:
                continue
            if l // 2 > M:
                return 0
            l = lcm(l, i)
    return (M + l // 2) // l

print(main())
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
    N,W = map(int,input().split())
    w,v = [0]*N,[0]*N
    for i in range(N):
        w[i],v[i] = map(int,input().split())
    v_max = sum(v)
    dp = [[0 if i == 0 else float("inf") for i in range(v_max+1)] for _ in range(N)]
    dp[0][v[0]] = w[0]
    for i in range(1,N):
        for j in range(v_max+1):
            if j<v[i]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = min(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
    ans = 0
    for i in range(v_max+1):
        if dp[-1][i]<=W:
            ans = i
        else:
            pass
    print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    # input
    N,W = map(int,input().split())
    w,v = [0]*N,[0]*N
    for i in range(N):
        w[i],v[i] = map(int,input().split())
    
    # init dp
    v_max = sum(v)
    dp = [[float("inf") for i in range(v_max+1)] for _ in range(N)]
    dp[0][v[0]] = w[0]
    for i in range(N):
        dp[i][0] = 0

    for i in range(1,N):
        for j in range(v_max+1):
            if j<v[i]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = min(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
    ans = 0
    for i in range(v_max+1):
        if dp[-1][i]<=W:
            ans = i
        else:
            pass
    print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(5000)
def max(a,b):
    if a >= b:
        return a
    return b
def min(a,b):
    if a <= b:
        return a
    return b

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

dp = [[-1]*(n+1) for i in range(n)]

def rec(i=0, j=n):
    if i == j:
        return 0
    if dp[i][j] != -1:
        return dp[i][j]
    # 太郎
    if (n - (j-i))%2==0:
        dp[i][j] = max(a[i] + rec(i+1,j), a[j-1] +rec(i,j-1))
    else:
        dp[i][j] = min(-a[i] + rec(i+1,j), -a[j-1] +rec(i,j-1))
    return dp[i][j]
print(rec())

### FIXED CODE ###

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

dp = [[0]*(n+1) for i in range(n+1)]
for l in range(1,n+1):
    for i in range(n+1-l):
        j = i+l
        if (n-l)%2 == 0:
            dp[i][j] = max(dp[i+1][j]+a[i], dp[i][j-1]+a[j-1])
        else:
            dp[i][j] = min(dp[i+1][j]-a[i], dp[i][j-1]-a[j-1])
print(dp[0][-1])
### BUGGY CODE ###

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

if min(a,b)<0 and max(a,b)>0:
    print("Zero")
    exit()
if min(a,b)>0:
    print("Positive")
    exit()

cnt = 0
for i in range(min(a,b),max(a,b)+1):
    if i<0:
        cnt += 1

if cnt%2==0:
    print("Positive")
else:
    print("Negative")

### FIXED CODE ###

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

if min(a,b)<0 and max(a,b)>0:
    print("Zero")
    exit()
if min(a,b)>0:
    print("Positive")
    exit()


c = -min(a,b) - max(a,b) + 1

if c%2==0:
    print("Positive")
else:
    print("Negative")
### BUGGY CODE ###

N=int(input())
S=input()
r=S.count('R')
g=S.count('G')
b=S.count('B')
c=0
for i in range(N):
  for j in range(i+1,N):
    if 2*j-i<=N-1:
      if S[i]!=S[j] and S[i]!=S[2*j-i] and S[j]!=S[2*j-i]:
        c+=1
ans=r*g*b-c
print(ans)

### FIXED CODE ###

N=int(input())
S=input()
r=S.count('R')
g=S.count('G')
b=S.count('B')
c=0
for i in range(N):
  for j in range(i+1,N):
    h=2*j-i
    if h>=N:
      break
    if S[i]!=S[j] and S[i]!=S[h] and S[j]!=S[h]:
      c+=1
ans=r*g*b-c
print(ans)