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

N=int(input())
p=[]
count=0
for i in range (N):
  a=int(input())
  if a in p:
    p.remove(a)
    count-=1
    p.append(0)
  else:
    p.append(a)
    count+=1
print(count)

### FIXED CODE ###

N=int(input())
p=[]
count=0
for i in range (N):
  a=int(input())
  p.append(a)
list.sort(p)
flag=1
for j in range (N-1):
  if p[j]==p[j+1]:
    flag*=-1
  else:
    if flag>0:
      count+=1
    flag=1
if flag>0:
  count+=1
print(count)
### BUGGY CODE ###

numberOfInput=int(input())
numberForStock=[]
index=0
while index<numberOfInput:
    inputNumber=int(input())
    numberForStock.append(inputNumber)
    index+=1

numberForReturn=-10**9
for indexForMax in range(1,numberOfInput):
    for indexForMin in range(0,indexForMax):
        if numberForReturn<numberForStock[indexForMax]-numberForStock[indexForMin]:
            numberForReturn=numberForStock[indexForMax]-numberForStock[indexForMin]
            
        
print(numberForReturn)


### FIXED CODE ###

n = int(input())
index=0
minL=[]
moneyL=[]
while index < n:
    inputN = int(input())
    moneyL.append(inputN)
    if index==0:
        minL.append(inputN)
    else:
        if minL[index-1] < inputN:
            minL.append(minL[index-1])
        else:
            minL.append(inputN)
    index+=1

index2=1
maxProfit = -10**9
while index2 < len(moneyL):
    if moneyL[index2] - minL[index2-1] > maxProfit:
        maxProfit = moneyL[index2] - minL[index2-1]
    else:
        pass
    index2+=1

print(maxProfit)
### BUGGY CODE ###

n = int(input())


al = []

for i in range(n):
    a = int(input())
    if al.count(a) > 0:
        al.remove(a)
    else:
        al.append(a)

print(len(al))


### FIXED CODE ###

n = int(input())
al = list(int(input()) for _ in range(n))

s = set()

for a in al:
    s ^= {a}

print(len(s))
### BUGGY CODE ###

n,d,a = map(int,input().split())
L = []
s = 0
for i in range(n):
    t = list(map(int,input().split()))
    s += t[1]
    L.append(t)
L.sort()
ans = 0
temp = 0
while s != 0:
    if L[temp][1] != 0:
        if L[temp][1]%a == 0:
            times = L[temp][1]//a
        else:
            times = L[temp][1]//a+1
        ans += times
        s -= L[temp][1]
        damage = a*times
        ran = L[temp][0]+2*d
        next = temp+1
        for i in range(temp+1, n):
            if L[i][0] <= ran:
                if L[i][1] > damage:
                    L[i][1] -= damage
                    s -= damage
                    next = min(next, i)
                else:
                    s -= L[i][1]
                    L[i][1] = 0
            else:
                break
        temp = next
    else:
        temp += 1
print(ans)


### FIXED CODE ###

import math
import bisect
n,d,a = map(int,input().split())
L = []
kyo = []
for i in range(n):
    x,h = map(int,input().split())
    L.append([x,h])
    kyo.append(x)
L.sort()
kyo.sort()
ans = 0
imos = [0]*(n+1)
cur = 0
ran = 2*d
for i in range(n):
    if imos[cur] < L[cur][1]:
        t = int(math.ceil((L[cur][1]-imos[cur])/a))
        ans += t
        imos[cur] += t*a
        lim = bisect.bisect_right(kyo, kyo[cur]+ran)
        imos[lim] -= t*a
    imos[i+1] += imos[i]
    cur += 1
print(ans)
### BUGGY CODE ###

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

res = 0

for i in range(N-1):
    for j in range(i+1, N):
        res += A[i] * A[j]
        res = res % (10 ** 9 + 7)
print(res)

### FIXED CODE ###

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

mod = 10 ** 9 + 7
ans = 0

A_sum = [A[0] for i in range(N)]
for i in range(1, N):
    A_sum[i] = A_sum[i-1] + A[i]

for i in range(1, N):
    ans += A[i] * A_sum[i-1]
    ans %= mod

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

# https://abc096.contest.atcoder.jp/tasks/abc096_d

import itertools


def is_prime(n):
    if n < 2: return False
    if n == 2: return True
    if n % 2 == 0: return False

    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1

    return True


N = int(input())


l = []

n = 2
while len(l) < N * 10:
    if is_prime(n):
        l.append(n)
    n += 1


for a in itertools.combinations(l, N):
    # print(a)
    is_ok = True
    for c in itertools.combinations(a, 5):
        if is_prime(sum(c)):
            # print(str(c) + ' is prime = ' + str(sum(c)))
            is_ok = False
            break
    if is_ok:
        print(' '.join(map(str, a)))
        break



### FIXED CODE ###


def is_prime(n):
    if n < 2: return False
    if n == 2: return True
    if n % 2 == 0: return False

    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1

    return True


N = int(input())


l = []

n = 2
while len(l) < N:
    if is_prime(n) and n % 5 == 1:
        l.append(n)
    n += 1

print(' '.join(map(str, l)))
### BUGGY CODE ###

def solve(n):
	ans=0
	for a in range(int(n/4)+1):
		for b in range(a,int(n/3)+1):
			for c in range(b,int(n/2)+1):
				for d in range(c,n+1):
					if a+b+c+d==n:
						if a==b==c==d:
							ans+=1
						elif a==b==c or b==c==d:
							ans+=4
						elif a==b and c==d:
							ans+=6
						elif (a==b and c!=d) or (b==c) or (a!=b and c==d):
							ans+=12
						else:
							ans+=24
	return ans 


while True:
	try:
		n=int(input())
		print(solve(n))
	except EOFError:
		break

### FIXED CODE ###

M = 1000
DM = M * 2 + 1
 
def count(n):
    global M
    res = n + 1
    if n > M:
        res -= (n-M) * 2
    return res
 
def solve(n):
    cnt = 0
    for a in range(min(DM, n), -1, -1):
        b = n - a
        if b > DM:
            break
        cnt += count(a) * count(b)
    return cnt
 
while True:
    try:
        l = input()
    except EOFError:
        break
    nm = int(l)
    print(solve(nm))
### BUGGY CODE ###

s=raw_input()
K=input()
l=len(s)

a=set()
for diff in range(1,l+1):
	for i in range(l):
		a.add(s[i:i+diff])
b=list(a)
b.sort()

print b[K-1]


### FIXED CODE ###

s=raw_input()
K=input()
l=len(s)

a=set()
for diff in range(1,5+1):
	for i in range(l):
		a.add(s[i:i+diff])

b=list(a)
b.sort()

print b[K-1]
### BUGGY CODE ###

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

sum=0
for i in range(n):
    o = i+1
    while (o<n):
        sum=(a[i]%1000000007*a[o]%1000000007+sum)%1000000007
        o=o+1

print(sum)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
mod=1000000007
sum=0
tmp=0
o=0
while(o<n):
    tmp = (a[o]%mod + tmp%mod)%mod
    o += 1

for i in range(n):
    tmp=(tmp%mod-a[i]%mod)%mod
    sum=((a[i]%mod)*tmp)%mod+sum%mod



print(sum%mod)
### BUGGY CODE ###

from sys import stdin
H,W = [int(x) for x in stdin.readline().rstrip().split()]
grid = []
for i in range(H):
    grid.append(list(input()))


tate = [[0]*W for i in range(H)]
yoko = [[0]*W for i in range(H)]

for i in range(H):
    cnt = 0
    for j in range(W):
        if grid[i][j] == ".":
            cnt += 1
            yoko[i][j] = cnt
        else:
            cnt = 0
    cnt = 0
    for j in range(W-1,-1,-1):
        if grid[i][j] == ".":
            cnt = max(cnt,yoko[i][j])
            yoko[i][j] = cnt
        else:
            cnt = 0

            
            
for j in range(W):
    cnt = 0
    for i in range(H):
        if grid[i][j] == ".":
            cnt += 1
            tate[i][j] = cnt
        else:
            cnt = 0
    cnt = 0
    for i in range(H-1,-1,-1):
        if grid[i][j] == ".":
            cnt = max(cnt,tate[i][j])
            tate[i][j] = cnt
        else:
            cnt = 0

ans = 0

for i in range(H):
    for j in range(W):
        tmp = tate[i][j] + yoko[i][j] - 1
        ans = max(ans,tmp)

print(ans)

### FIXED CODE ###

from sys import stdin
H,W = [int(x) for x in stdin.readline().rstrip().split()]
grid = []
for i in range(H):
    grid.append(list(input()))


tate = [[0]*W for i in range(H)]
yoko = [[0]*W for i in range(H)]

for i in range(H):
    cnt = 0
    for j in range(W):
        if grid[i][j] == ".":
            cnt += 1
            yoko[i][j] = cnt
        else:
            cnt = 0
    cnt = 0
    for j in range(W-1,-1,-1):
        if grid[i][j] == ".":
            cnt = max(cnt,yoko[i][j])
            yoko[i][j] = cnt
        else:
            cnt = 0

            
            
for j in range(W):
    cnt = 0
    for i in range(H):
        if grid[i][j] == ".":
            cnt += 1
            tate[i][j] = cnt
        else:
            cnt = 0
    cnt = 0
    for i in range(H-1,-1,-1):
        if grid[i][j] == ".":
            cnt = max(cnt,tate[i][j])
            tate[i][j] = cnt
        else:
            cnt = 0

ans = 0

for i in range(H):
    for j in range(W):
        tmp = tate[i][j] + yoko[i][j] - 1
        ans = max(ans,tmp)

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

from collections import Counter
n=int(input())
s=[input() for _ in range(n)]
d=Counter(s)
keys = [k for k,v in d.items() if v==max(d.values())]
print("\n".join(sorted(keys)))

### FIXED CODE ###

from collections import Counter
n=int(input())
s=[input() for _ in range(n)]
d=Counter(s)
m=max(d.values())
keys = [k for k,v in d.items() if v==m]
print("\n".join(sorted(keys)))
### BUGGY CODE ###

def solve(N,W,wv):
    dp=[-1]*(W+1)
    dp[0]=0
    for i in range(N):
        cur_w=wv[i][0]
        cur_v=wv[i][1]
        for j in range(W-cur_w,-1,-1):
            if dp[j]>=0:
                dp[j+cur_w]=max(dp[j+cur_w],dp[j]+cur_v)
    return max(dp)


N,W=map(int,input().split())
wv=tuple(tuple(map(int,input().split())) for _ in range(N))
print(solve(N,W,wv))

### FIXED CODE ###

def solve(N,W,wv):
    dp=[-1]*(W+1)
    dp[0]=0
    for i in range(N):
        cur_w=wv[i][0]
        cur_v=wv[i][1]
        for j in range(W-cur_w,-1,-1):
            if dp[j]==-1:
                continue
            if dp[j+cur_w]<dp[j]+cur_v:
                dp[j+cur_w]=dp[j]+cur_v
    return max(dp)


N,W=map(int,input().split())
wv=tuple(tuple(map(int,input().split())) for _ in range(N))
print(solve(N,W,wv))
### BUGGY CODE ###

import math

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

def C(N,P):
    if N == 1: return P
    a=P
    N1=2
    while N >= N1:
        N1*=2
        a=math.sqrt(a)

    res=1
    for i in range(2,int(a)+2):
        if i**N > P : break
        if P % i**N == 0 : res = i

    return res

print(C(n,p))

### FIXED CODE ###

n,p = list(map(int,input().split())) 
i = a = o = 1
m = round(p**(1/n))
for i in range(m,0,-1):
    a = i**n
    if p%a==0:
        print(i)
        exit()
### BUGGY CODE ###

#!/usr/bin/env python
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()))
D = [int(b+c) for c in C for b in B]
D.sort(reverse=True)
E = [int(a+d) for d in D[:k] for a in A]
E.sort(reverse=True)
for e in E[:k]:
    print(e)

### FIXED CODE ###

#!/usr/bin/env python
import numpy as np
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()))
D = []
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
for i in range(min(K,X)):
    for j in range(min((K//(i+1),Y))):
        for k in range(min(((K//(i+1)+1)//(j+1)),Z)):
            D.append(A[i]+B[j]+C[k])
D.sort(reverse=True)
for i in range(K):
    print(int(D[i]))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from operator import mul
from functools import reduce

def combination(n, r):
    if n < r:
        return 0
    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

n = int(input())
s = [''.join(sorted(input())) for _ in range(n)]
ans = 0
for anagram in set(s):
    ans += combination(s.count(anagram), 2)
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from operator import mul
from functools import reduce

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

n = int(input())
s = {}
for i in range(n):
    str = ''.join(sorted(input()))
    if str in s.keys():
        s[str] += 1
    else:
        s[str] = 1
ans = 0
for i in s:
    ans += combination(s[i], 2)
print(ans)
### BUGGY CODE ###


def solve():
    i = L//2019
    ans = 0
    is_ok = False
    if L <= 2019*i <= R:
        is_ok = True
#    print(i)
    if is_ok:
        print(ans)
    else:
        ans = 2020
        for n in range(L,R):
            for m in range(n+1,R+1):
                ans = min(ans, (n*m)%2019)
            if ans == 0:
                break
        print(ans)

if __name__ == "__main__":
    L,R = list(map(int, input().split()))
    solve()


### FIXED CODE ###


def solve():
    i = (L//2019) + 1
    ans = 0
    if L <= 2019*i <= R:
        print(ans)
    else:
        ans = 2020
        for n in range(L,R):
            for m in range(n+1,R+1):
                ans = min(ans, (n*m)%2019)
            if ans == 0:
                break
        print(ans)

if __name__ == "__main__":
    L,R = list(map(int, input().split()))
    solve()
### BUGGY CODE ###

import heapq
def SME(start,end):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        
        if sum(ANS[a[1]:a[1]+L]) < MAX + len(ANS[a[1]:a[1]+L]) - 1 : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] == MAX:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] == MAX : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] == MAX : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
parameter = 0.9999
MAX = 10**9+1
ANS = [MAX]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_D
#??????????????????

def cal(truck_num, cargos):
    p = 0
    for i in range(len(cargos) - truck_num + 1):
        if truck_num > 1:
            r = max(sum(cargos[:i + 1]), cal(truck_num - 1, cargos[i + 1:]))
            if i == 0:
                p = r
            elif p > r:
                p = r
        else:
            return sum(cargos)
    return p

if __name__ == "__main__":
    line = input()
    truck_num = int(line.split(" ")[1])
    line_num = int(line.split(" ")[0])
    cargos = []
    for i in range(line_num):
        cargos.append(int(input()))
    print(cal(truck_num,cargos))

### FIXED CODE ###

#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_D
#??????????????????

def cal(truck_num, cargos):
    p = 0
    
    for i in range(len(cargos) - truck_num + 1):
        if not i == 0 and p < sum(cargos[:i + 1]):
            continue
        if truck_num > 1:
            r = max(sum(cargos[:i + 1]), cal(truck_num - 1, cargos[i + 1:]))
            if i == 0:
                p = r
            elif p > r:
                p = r
        else:
            return sum(cargos)
    return p

def check(truck_num, carogs, target_load):
    
    cur_truck = 1
    cur_weight = 0
    for weight in cargos:
        cur_weight += weight
        if cur_weight > target_load:
            cur_weight = weight
            cur_truck += 1
            if cur_truck > truck_num:
                return False
    return True

def solve(truck_num, cargs):

    max_load = sum(cargos)
    min_load = max(cargos)
    #print(min_load, max_load)
    while min_load < max_load:
        target_load = int((min_load + max_load)/2)
        if check(truck_num, cargos, target_load):
            max_load = target_load
        else:
            min_load = target_load + 1
        #print(min_load, max_load)
        
    return max_load

if __name__ == "__main__":
    line = input()
    truck_num = int(line.split(" ")[1])
    line_num = int(line.split(" ")[0])
    cargos = [int(input()) for i in range(line_num)]
    print(solve(truck_num,cargos))
### BUGGY CODE ###

import numpy as np
n = int(input())
a =  [int(input()) for i in range(n)]
b = set(a)
c = max(b)
for i in range(n):
  if a[i] != c:
    print(c)
  else:
    print(int(max(np.concatenate([a[:i], a[i+1:]]))))

### FIXED CODE ###

import numpy as np
n = int(input())
a =  [int(input()) for i in range(n)]
max_a_num = a.count(max(a))
b = sorted(a, reverse=True)
m1, m2 = b[0], b[1]
for i in range(n):
  if max_a_num == 1:
    if a[i] == m1:
      print(m2)
    else:
      print(m1)
  else:
    print(m2)
### BUGGY CODE ###

class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                # 経路圧縮
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def unite(self, x, y):
        return self._unite(self.find(x), self.find(y))

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            return x


N = int(input())
x, y = [], []
for i in range(N):
    a, b = map(int, input().split())
    x.append([a, i])
    y.append([b, i])
x.sort()
y.sort()

e = []
for i in range(N-1):
    e.append([abs(x[i][0]-x[i+1][0]), x[i][1], x[i+1][1]])
    e.append([abs(y[i][0]-y[i+1][0]), y[i][1], y[i+1][1]])

e.sort()

v = {}
v[0] = 1
ans = 0
while len(v) < N:
    for w, s, t in e:
        if (s in v and t not in v) or (s not in v and t in v):
            v[s] = 1
            v[t] = 1
            ans += w
            break
print(ans)
'''
クラスカル
uft = UnionFindTree()
for i in range(N):
    uft.make(i)

ans = 0
for w, s, t in e:
    if not uft.same(s, t):
        uft.unite(s, t)
        ans += w

print(ans)
'''


### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)


N = int(input())
x, y = [], []
for i in range(N):
    a, b = map(int, input().split())
    x.append([a, i])
    y.append([b, i])
x.sort()
y.sort()

e = []
for i in range(N-1):
    e.append([abs(x[i][0]-x[i+1][0]), x[i][1], x[i+1][1]])
    e.append([abs(y[i][0]-y[i+1][0]), y[i][1], y[i+1][1]])

e.sort()

uft = UnionFind(N)

ans = 0
for w, s, t in e:
    if not uft.same(s, t):
        uft.union(s, t)
        ans += w

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

a, b = [int(i) for i in input().split()]
if 0 <= a and 0 >= b:
    print('Zero')
    exit()
if a > 0:
    print('Positive')
    exit()
c = b
while a != b:
    c *= a
    a += 1
print('Positive' if c > 0 else 'Zero' if c == 0 else 'Negative')


### FIXED CODE ###

a, b = map(int, raw_input().split())
if a * b < 0:
    print 'Zero'
elif a + b < 0 and abs(a - b) & 1 == 0:
    print 'Negative'
else:
    print 'Positive'
### BUGGY CODE ###

import sys
n,m=map(int,input().split())

a=[]
b=[]
l=[]

for i in range(m):
    c=[int(i) for i in input().split()]
    a.append(c[0])
    b.append(c[1])
    if a[i]==1 or b[i]==1:
        l.append(a[i]*b[i])


for i in range(m):
    if a[i] in l and b[i]==n:
        print("POSSIBLE")
        sys.exit()
    if b[i] in l and a[i]==n:
        print("POSSIBLE")
        sys.exit()

print("IMPOSSIBLE")

### FIXED CODE ###

import sys
n,m=map(int,input().split())

a=[]
b=[]
l1=[False for i in range(n)]
ln=[False for i in range(n)]

for i in range(m):
    c=[int(i) for i in input().split()]
    a.append(c[0])
    b.append(c[1])
    if c[0]==1 or c[1]==1:
        l1[c[0]*c[1]]=True
    if c[0]==n or c[1]==n:
        ln[c[0]*c[1]//n]=True

for i in range(n):
    if l1[i] and ln[i]:
        print("POSSIBLE")
        sys.exit()

print("IMPOSSIBLE")
### BUGGY CODE ###

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

weights = [None for i in range(N)]
values = [None for i in range(N)]

# dp[i][j] = maximum value using at most i weight and using elements 1,...,j

dp = [[0 for i in range(N+1)] for j in range(W+1)]

for i in range(N):
    w, v = map(int, input().split())
    weights[i] = w
    values[i] = v
    
for weight in range(W+1):
    for item in range(1,N+1):
        if weights[item-1] > weight: continue

        dp[weight][item] = max([dp[weight][item]] + 
                               [values[item-1] + dp[weight - weights[item-1]][j] for j in range(item)])

        dp[weight][item] = max(dp[weight-1][item], dp[weight][item])
    
print(max(dp[-1]))


### FIXED CODE ###

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

weights = [None for i in range(N)]
values = [None for i in range(N)]

# dp[i][j] = maximum value using at most i weight and using elements 1,...,j

dp = [[0 for i in range(N+1)] for j in range(W+1)]

for i in range(N):
    w, v = map(int, input().split())
    weights[i] = w
    values[i] = v
    
for weight in range(W+1):
    for item in range(1,N+1):

        # Case: dont include item
        dp[weight][item] = max(dp[weight][item],
                               dp[weight][item-1])

        # Case: include item
        dp[weight][item] = max(dp[weight][item],
                               dp[weight-1][item])
        
        if weights[item-1] > weight: continue
 
        # Case: include item
        dp[weight][item] = max(dp[weight][item],
                               values[item-1] + dp[weight - weights[item-1]][item - 1])
    
print(max(dp[-1]))
### BUGGY CODE ###

a,b,c,d = map(int,input().split())
cnt = 0
for i in range(a,b+1):
  if i%c != 0 and i%d !=0:
    cnt+=1
print(cnt)    
    

### FIXED CODE ###

a,b,c,d = map(int,input().split())
def gcd(x, y):
	while y:
		x, y = y, x % y
	return x

def lcm(x, y):
  return x * y // gcd (x, y)  

def cal(n):
  if a%n ==0 and b%n ==0:
    return b//n - a//n + 1
  else:
    return b//n - a//n
    
cd = lcm(c, d)
ans = (b-a+1) - (b//c - (a-1)//c) - (b//d - (a-1)//d) + (b//cd - (a-1)//cd)
print(ans)
### BUGGY CODE ###

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

### FIXED CODE ###

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

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

def GCD(a,b):
  if a % b == 0:
    return b
  return GCD(b, a%b)

A.append(1)
a = A[0]
b = A[1]
lcm = a * b // GCD(a,b)
for i in range(2,N):
  a = lcm
  b = A[i]
  lcm = a * b // GCD(a,b)
ans = 0
for i in range(N):
  ans = (ans + (lcm // A[i])) % MOD
print(ans)


### FIXED CODE ###

import fractions
from functools import reduce

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

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

lcm = lcm_list(A)
ans = 0
for i in range(N):
  ans = (ans + (lcm // A[i]))
print(ans % MOD)