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

import numpy as np
n,k = map(int,input().split())
ls = np.array(list(map(int,input().split())))
dp = [10000000000] *n
dp[0] = 0
dp[1] = abs(ls[1]-ls[0])
for i in range(2,n):
    st = max(0,i-k)
    dp[i] = np.min(dp[st:i]+abs(ls[i]-ls[st:i]))
print(dp[n-1])

### FIXED CODE ###

n,k = map(int,input().split())
ls = list(map(int,input().split()))
dp = [10000000000] *n
dp[0] = 0
dp[1] = abs(ls[1]-ls[0])
p = 10000000000
for i in range(2,n):
    for j in range(i-k,i):
        if (dp[j] >= p) or (abs(ls[j] - ls[i]) >= p):
            pass
        else:
            a = dp[j] + abs(ls[j] - ls[i])
            if a < p:
                p = a
                a = 0
            else:
                a = 0
    dp[i] = p
    p = 10000000000
print(dp[n-1])
### BUGGY CODE ###

import sys 
input= sys.stdin.readline
n,m,v,p=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True)
cnt=p
from bisect import bisect_left
#print(a[5]+m)
for i in range(p,n):
    if (a[i]+m )<a[p-1]:
        break
    # 3 2 2 1 1 0
    if ((a[i]+m)*(i-p+1)-sum(a[p-1:i])+(n-(i-p+1))*m)>=v*m:
        cnt+=1  
print(cnt)

### FIXED CODE ###

def main():
    import sys 
    input= sys.stdin.readline
    n,m,v,p=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort(reverse=True)
    cnt=p
    #from bisect import bisect_left
    #print(a[5]+m)
    s=sum(a[p-1:p])
    for i in range(p,n):
        if (a[i]+m )<a[p-1]:
            break
        # 3 2 2 1 1 0
        
        cnt+= ((a[i]+m)*(i-p+1)-s+(n-(i-p+1))*m)>=v*m
        try: s+=a[i]
        except: continue      
    print(cnt)

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

#! -*- coding: utf-8 -*-

import sys

n = int(raw_input())
print 0
status_0 = raw_input()
check = n / 2
if check % 2 == 1:
    check += 1
if status_0 == "Vacant":
    pass
else:
    while 1:
        print check
        sys.stdout.flush()
        status = raw_input()
        if status == "Vacant":
            break
        elif status == status_0:
            check += check / 2
        else:
            check -= check / 2

quit()


### FIXED CODE ###

#! -*- coding: utf-8 -*-

import sys

n = int(raw_input())
print 0
sys.stdout.flush()
status_0 = raw_input()
start = 0
end = n-1
check = end
i = 1
if status_0 == "Vacant":
    pass
else:
    while 1:
        print check
        sys.stdout.flush()
        status = raw_input()
        if status == "Vacant":
            break
        elif status == status_0:
            if check % 2 == 0:
                start = check
            else:
                end = check
        else:
            if check % 2 == 0:
                end = check
            else:
                start = check
        check = start+(end-start)/2

quit()
### BUGGY CODE ###

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

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

def kitaiti(num):
    result = (num+1)*num/(num*2)
    return result
r = [kitaiti(p[i]) for i in range(n)]

result = []
for i in range(n-k+1):
    result.append(sum(r[i:i+k]))
print(max(result))

### FIXED CODE ###

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

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

def kitaiti(num):
    result = (num+1)*num/(num*2)
    return result
r = [kitaiti(p[i]) for i in range(n)]

result = [sum(r[:k])]
for i in range(k, n):
    result.append(result[-1]-r[i-k]+r[i])
print(max(result))
### BUGGY CODE ###

N = int(input())
TA = [list(map(int, input().split(" "))) for _ in range(N)]

n_t, n_a = 1, 1
for t, a in TA:
    s, b = 0, 0
    while not (n_t <= s and n_a <= b):
        s += t
        b += a
    n_t, n_a = s, b

print(n_t+n_a)

### FIXED CODE ###

N = int(input())
TA = [list(map(int, input().split(" "))) for _ in range(N)]

n_t, n_a = 1, 1
for t, a in TA:
    # print(n_t/t, n_a/a)
    v = max(-(-n_t//t), -(-n_a//a))
    n_t, n_a = t*v, a*v

print(n_t+n_a)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: print('Yes' if b else 'No')
YESNO=lambda b: print('YES' if b else 'NO')

def main():
    N=int(input())
    S=list(input())
    ans=0
    for i in range(N):
        for j in range(i+1,N):
            if S[i]==S[j]:
                continue
            for k in range(j+1,N):
                if S[j]!=S[k] and S[i]!=S[k] and j-i!=k-j:
                    ans+=1
    print(ans)
                

if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: print('Yes' if b else 'No')
YESNO=lambda b: print('YES' if b else 'NO')

def main():
    N=int(input())
    S=list(input())
    c=[0,0,0]
    for i,s in enumerate(S):
        if s=='R':
            c[0]+=1
        elif s=='G':
            c[1]+=1
        else:
            c[2]+=1
    count=0
    for i in range(N):
        for j in range(1,N//2+1):
            if i+j*2>=N:
                continue
            if S[i]!=S[i+j] and S[i]!=S[i+j*2] and S[i+j]!=S[i+j*2]:
                count+=1
    print(c[0]*c[1]*c[2]-count)
                

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

n,m = map(int, input().split())
d = m//n
for i in range(0,d):
    if (m % (d-i) == 0):
        print(d-i)
        break


### FIXED CODE ###

n,m = map(int, input().split())
d = m//n
ans = []
for i in range(1,min(d+1,int(m**0.5)+1)):
    if (m % i == 0):
        ans.append(i)
        if (m//i<=d):
            ans.append(m//i)
print(max(ans))
### BUGGY CODE ###

import math

k = int(input())

ans = 0
for i in range(1, k+1):
    for j in range(1, k+1):
        for l in range(1, k+1):
            ans += math.gcd(math.gcd(i,j), l)

print(ans)


### FIXED CODE ###

import math

k = int(input())

ans = 0
for i in range(1, k+1):
    for j in range(1, k+1):
        ij = math.gcd(i,j)
        for l in range(1, k+1):
            ans += math.gcd(ij, l)

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

import sys
from copy import deepcopy
import numpy as np
readline=sys.stdin.readline
read=sys.stdin.read

def main():
    n=int(readline())
    a=np.array([list(map(int,l.split())) for l in read().splitlines()])
    cost=deepcopy(a)
    for k in range(n):
        arr=np.stack([cost,[cost[k]]+np.transpose([cost[k]])])
        cost=np.amin(arr,axis=0)
    cost2=deepcopy(a)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                cost2[i][j]=min(cost2[i][j],cost2[i][k]+cost2[k][j])
    f=np.sum(cost<a)
    if f:
        print(-1)
        return
    filt=np.sum([([cost[k]]+np.transpose([cost[k]]))==cost for k in range(n)],axis=0)==2
    print(np.sum(a[filt])//2)

if __name__=='__main__':
    main()


### FIXED CODE ###

import sys
from copy import deepcopy
import numpy as np
readline=sys.stdin.readline
read=sys.stdin.read

def main():
    n=int(readline())
    a=np.array([list(map(int,l.split())) for l in read().splitlines()])
    cost=deepcopy(a)
    for k in range(n):
        arr=np.stack([cost,[cost[k]]+np.transpose([cost[k]])])
        cost=np.amin(arr,axis=0)
    cost2=deepcopy(a)
    f=np.sum(cost<a)
    if f:
        print(-1)
        return
    filt=np.sum([([cost[k]]+np.transpose([cost[k]]))==cost for k in range(n)],axis=0)==2
    print(np.sum(a[filt])//2)

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

def main():
    n = int(input())
    ans = 0
    
    for a in range(1, n):
        for b in range(1, n):
            if a * b > n:
                break
            if 1 <= a * b <= n - 1:
                ans += 1
    print(ans)

        
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    ans = 0
    
    for a in range(1, n):
        for b in range(1, n):
            if 1 <= a * b <= n - 1:
                ans += 1
            else:
                break
           
    print(ans)

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

N = int(input())

sum = 0
for num in range(1,N+1):
    if (N//num) == (N%num):
        sum += num

print(sum)

### FIXED CODE ###

N = int(input())

import numpy as np

sum = 0

for n in range(1, int(np.sqrt(N)+1)):
    x = (N - n ) // n
    if ((N - n) % n == 0) and (x > n):
        sum += x

print(sum)
### BUGGY CODE ###

def main():
    n, k, l = map(int, input().split())
    roads = [set([i]) for i in range(n)]
    rails = [set([i]) for i in range(n)]
    for _ in range(k):
        a, b = map(lambda s: int(s) - 1, input().split())
        u = roads[a] | roads[b]
        for i in u:
            roads[i] = u
    for _ in range(l):
        a, b = map(lambda s: int(s) - 1, input().split())
        u = rails[a] | rails[b]
        for i in u:
            rails[i] = u
    res = [len(roads[i] & rails[i]) for i in range(n)]
    print(' '.join(map(str, res)))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def root(parents, i):
    if parents[i] == i:
        return i
    parents[i] = root(parents, parents[i])
    return parents[i]


def main():
    n, k, l = map(int, input().split())
    roads = list(range(n))
    rails = list(range(n))

    for _ in range(k):
        a, b = map(lambda s: int(s) - 1, input().split())
        root_a, root_b = root(roads, a), root(roads, b)
        if root_a != root_b:
            roads[root_a] = root_b

    for _ in range(l):
        a, b = map(lambda s: int(s) - 1, input().split())
        root_a, root_b = root(rails, a), root(rails, b)
        if root_a != root_b:
            rails[root_a] = root_b

    counts = dict()
    for i in range(n):
        pair = (root(roads, i), root(rails, i))
        if not pair in counts:
            counts[pair] = 1
        else:
            counts[pair] += 1

    print(' '.join(
        map(lambda i: str(counts[(root(roads, i), root(rails, i))]), range(n))))


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

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

if a == b:
    print(a)
    exit()

c = 0
d = a
while True:
    if d >= b:
        break
    d += 4
    c += 1

d -= 3
c -= 1

while True:
    if d > b:
        break
    a ^= d
    d += 1
print(a)


### FIXED CODE ###

A,B = map(int,input().split())
 
aa,bb = 0,0
if (A-1) % 2 == 0:
    if ((A-1) //2) % 2 == 0:
        aa = (A-1)^1
    else:
        aa = (A-1)
else:
    if ((A+1) //2) % 2 == 0:
        aa = 1
 
if B % 2 == 0:
    if (B//2) % 2 == 0:
        bb = B^1
    else:
        bb = B
else:
    if ((B+1) //2) % 2 == 0:
        bb = 1
 
print(aa^bb)
### BUGGY CODE ###

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

P=[]
for m in range(M):
    P.append(list(map(int,input().split())))

from itertools import combinations

ans=0
for c in combinations(range(M),N-1):
    visit = [1]
    P_visit=[]
    v=0
    start=visit[0]
    while v < 100:
        v+=1
        for c_ in c:
            if c_ in P_visit:
                continue
            if P[c_][0] == start:
                visit.append(P[c_][1])
                start = P[c_][1]
                P_visit.append(c_)
                
            elif P[c_][1] == start:
                visit.append(P[c_][0])
                start = P[c_][0]
                P_visit.append(c_)
    
    if len(set(visit))== N:
        ans += 1
print(ans)

### FIXED CODE ###

from itertools import permutations

N,M = list(map(int,input().split()))
P=[]
for m in range(M):
    P.append(list(map(int,input().split())))

ad={}
for _ in range(1,N+1):
    ad[_]=set()
    
for p in P:
    ad[p[0]].add(p[1])
    ad[p[1]].add(p[0])

ans=0
for p in permutations(range(2,N+1),N-1):
    ans_flag=True
    start=1
    for p_ in p:
        end=p_
#         print(start,end ,end in ad[start])
        if end not in ad[start]:
#             print('break')
            ans_flag=False
            break
        start=p_
        
    if ans_flag==True:
        ans+=1
        
print(ans)
### BUGGY CODE ###

def solve():
    from bisect import bisect_left
    N, W = map(int, input().split())
    n1 = N//2
    n2 = N-n1
    a = [[tuple(map(int, input().split())) for _ in [0]*n1], [tuple(map(int, input().split())) for _ in [0]*n2]]
    dp = [[(0, 0) for _ in [0]*(2**n1)], [(0, 0) for _ in [0]*(2**n2)]]

    for i in range(2):
        n = len(a[i])
        cdp = dp[i]
        ca = a[i]
        for j in range(n):
            if ca[j][1] > W:
                continue
            for bitset in range(2**j, 2**(j+1)):
                #print(bin(bitset))
                v, w = ca[j]
                for k in range(j):
                    if 2**k & bitset:
                        v += ca[k][0]
                        w += ca[k][1]
                if w <= W:
                    cdp[bitset] = (w, v)
        cdp = sorted(cdp)
        dp[i] = [pair for w in [[-1]] for sa in [w.__setitem__] for pair in cdp if pair[1] > w[0] and not sa(0, pair[1])]

    #print(dp)
    result = 0
    inf = float("inf")
    l = len(dp[1])
    for w, v in dp[0]:
        i = bisect_left(dp[1], (W-w, inf))
        newv = v + dp[1][i-1][1] if i > 0 else 0
        #print(w, v, i, newv)

        if newv > result:
            result = newv

    print(result)

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys
from bisect import bisect_right


def meet_in_the_middle(a: list, limit: int) -> tuple:
    first_v, first_w, second_v, second_w = [], [], [], []
    for items, v_append, w_append in (
            (a[:len(a)//2], first_v.append, first_w.append),
            (a[len(a)//2:], second_v.append, second_w.append)
    ):
        enumerated = [(0, 0)]
        for v, w in items:
            enumerated += [(w+_w, v+_v) for _w, _v in enumerated]

        enumerated.sort()
        enumerated = enumerated[:bisect_right(enumerated, (limit, float("inf")))] + [(limit+1, 0)]
        max_v = -1
        for (cw, cv), (nw, nv) in zip(enumerated, enumerated[1:]):
            if cw < nw and max_v < cv:
                v_append(cv)
                w_append(cw)
                max_v = cv

    return (first_v, first_w), (second_v, second_w)


N, W = map(int, input().split())
a = [list(map(int, l.split())) for l in sys.stdin]

(first_v, first_w), (second_v, second_w) = meet_in_the_middle(a, W)
ans = 0
for v, w in zip(first_v, first_w):
    i = bisect_right(second_w, W-w)-1
    new_v = v + second_v[i]
    if ans < new_v:
        ans = new_v
print(ans)
### BUGGY CODE ###

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

### FIXED CODE ###

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

S=str(input())
N=len(S)
a=[]
y=[]
x=0
a=list(S)


while 'BW' in S :
    a=list(S)
    for y in reversed((a)):

        for i in range (0,N-1):
            if a[i]=='B' and a[i+1]=='W' :
                a[i]='W'
                a[i+1]='B'
                x=x+1
                S=''.join(a)
print(x)


### FIXED CODE ###

S=str(input())
N=len(S)
a=[]
y=0
x=0
z=0
a=list(S)

y=([i for i, p in enumerate(a) if p == 'W'])
z=len(y) #Wの個数
x=sum(y) #Wのi番目の合計

b=(1/2)*z*(z-1)
print(int(x-b))
### BUGGY CODE ###

n = int(input())
ls = input()
q = int(input())
for _ in range(q):
    b, q = map(str, input().split())
    ls = ls.replace(b, q)
    print(sum(map(int, ls.split())))


### FIXED CODE ###

from collections import Counter
n = int(input())
ls = list(map(int, input().split()))
q = int(input())
count = Counter(ls)
sm = sum(ls)

for _ in range(q):
    b, q = map(int, input().split())
    if b in count:
        sm -= count[b] * b
        sm += count[b] * q
        print(sm)
    else:
        print(sm)
    if q in count:
        count[q] += count[b]

        count[b] = 0
    else:
        count[q] = count[b]

        count[b] = 0
### BUGGY CODE ###

import bisect,collections,copy,heapq,itertools,math,string
from collections import defaultdict as D
from functools import reduce
import numpy as np
import sys
import os
from operator import mul

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353    

l,r = LI()
m = 2019

ar = []
for i in range(l,r):
    for j in range(i+1,r+1):
        ar.append((i*j)%m)
print(min(ar))

# ans = (l * r) % m
# print(ans)

# N = I()
#A,B = LI()
#AB = [LI() for _ in range(N)]
#A,B = zip(*AB)
#Ap = np.array(A)
#C = np.zeros(N + 1)

# if ans:
#     print('Yes')
# else:
#     print('No')

### FIXED CODE ###

import bisect,collections,copy,heapq,itertools,math,string
from collections import defaultdict as D
from functools import reduce
import numpy as np
import sys
import os
from operator import mul

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353    

l,r = LI()
m = 2019

end = min(l+2019,r)

ar = []
for i in range(l,end):
    for j in range(i+1,end+1):
        ar.append((i*j)%m)
print(min(ar))

# ans = (l * r) % m
# print(ans)

# N = I()
#A,B = LI()
#AB = [LI() for _ in range(N)]
#A,B = zip(*AB)
#Ap = np.array(A)
#C = np.zeros(N + 1)

# if ans:
#     print('Yes')
# else:
#     print('No')
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n,q=map(int,input().split())
s=input().replace("\n","")
for i in range(q):
    cnt=0
    l,r=map(int,input().split())
    for j in range(l,r):
        #print(s[j-1:j+1])
        if s[j-1:j+1]=="AC":
            cnt+=1
    print(cnt)

### FIXED CODE ###

import sys
input=sys.stdin.readline
n,q=map(int,input().split())
s=input().replace("\n","")
cnt=[0 for i in range(n+1)]
for i in range(1,n+1):
    if s[i-1:i+1]=="AC":
        cnt[i]+=1
    cnt[i]+=cnt[i-1]
#print(cnt)
for i in range(q):
    a,b=map(int,input().split())
    print(cnt[b-1]-cnt[a-1])
### BUGGY CODE ###

import sys
import heapq


def main():
    n, k = [int(s) for s in sys.stdin.readline().strip().split()]
    a = [int(s) for s in sys.stdin.readline().strip().split()]
    f = [int(s) for s in sys.stdin.readline().strip().split()]
    # n, k = 3, 5
    # a = [4, 2,1]
    # f = [2, 3, 1]

    a.sort(reverse=True)
    f.sort()

    heap = []
    for i in range(n):
        ai = a[i]
        fi = f[i]
        heap.append((- ai * fi, ai, fi))
    heapq.heapify(heap)

    for i in range(k):
        prod, ai, fi = heapq.heappop(heap)
        if prod == 0:
            break
        new_prod = - (ai - 1) * fi
        heapq.heappush(heap, (new_prod, ai-1, fi))

    print(- heap[0][0])


main()



### FIXED CODE ###

import sys
import heapq


def main():
    n, k = [int(s) for s in sys.stdin.readline().strip().split()]
    a = [int(s) for s in sys.stdin.readline().strip().split()]
    f = [int(s) for s in sys.stdin.readline().strip().split()]
    # n, k = 3, 5
    # a = [4, 2,1]
    # f = [2, 3, 1]

    a.sort(reverse=True)
    f.sort()

    def possible(x1):
        improved = 0
        for i in range(n):
            before = a[i] * f[i]
            if before > x1:
                needed_to_be_reduced = before - x1
                if needed_to_be_reduced % f[i] == 0:
                    plus_one = 0
                else:
                    plus_one = 1
                improved += (needed_to_be_reduced // f[i]) + plus_one
                if improved > k:
                    return False
        return True

    def b_search():
        lo = 0
        hi = 10 ** 12
        # (lo, hi]
        # hi is always possible
        # lo might be possible

        while lo < hi:
            mid = (lo + hi) // 2
            if possible(mid):
                hi = mid
            else:
                lo = mid+1
        return hi

    ans = b_search()
    print(ans)


main()
### BUGGY CODE ###

n=int(input())
li = list(map(int,input().split()))
ans=0
for i in range(n):
        ans+=(li[i]*sum(li[i+1:]))
print(ans%(10**9+7))

### FIXED CODE ###

n=int(input())
li = list(map(int,input().split()))
ans=0
check=0
ans+=(sum(li))**2
for i in range(n):
    check+=li[i]**2
ans=ans-check
ans//=2
print(ans%((10**9)+7))
### BUGGY CODE ###

from functools import reduce
import fractions

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

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

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

N = int(input().rstrip())
As = input().rstrip().split(" ")
As = [int(p) for p in As]

cand = lcm_list(As)

ans = sum([cand // x for x in As]) % int(1e9+7)
print(ans)


### FIXED CODE ###

from functools import reduce
import fractions

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

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

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

N = int(input().rstrip())
As = input().rstrip().split(" ")
As = [int(p) for p in As]

cand = lcm_list(As)

sum = 0

for num in As:
    sum = sum + cand // num

print(sum % int(1e9+7) )
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()
    s = sum(a)
    t = 1
    m = 2**(s//2+1)
    for c in a:
        t |= t << c
    t %= m

    return s - (len(bin(t)) - 3)


print(main())




### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()
    s = sum(a)
    t = 1
    m = 2**(s//2+1) - 1
    for c in a:
        t |= t << c
    t &= m

    return s - (t.bit_length() - 1)


print(main())