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

#import sys
#input = sys.stdin.readline
 
n = int(input())
a =[int(xi) for xi in input().split()]
b =[int(yi) for yi in input().split()]
 
cnt, prev_cnt = 0, -1
while cnt != prev_cnt:
    prev_cnt = cnt
    for i in range(n):
        
        adj_sum = b[i - 1] + b[(i + 1) % n]
        k = (b[i] - a[i]) // adj_sum
        if k > 0:
            b[i] -= k * adj_sum
            cnt += k
 
print(cnt if a == b else -1)

### FIXED CODE ###

#import sys
#input = sys.stdin.readline

n = int(input())
a = [0]*n
b = [0]*n
a =[int(xi) for xi in input().split()]
b =[int(yi) for yi in input().split()]

cnt, prev_cnt = 0, -1
while cnt != prev_cnt:
    prev_cnt = cnt
    for i in range(n):
        
        adj_sum = b[i - 1] + b[(i + 1) % n]
        k = (b[i] - a[i]) // adj_sum
        if k > 0:
            b[i] -= k * adj_sum
            cnt += k

print(cnt if a == b else -1)
### BUGGY CODE ###

from collections import*
import sys
input=sys.stdin.readline   #input高速化 １文字の時の改行文字に注意+

d=defaultdict(int)
db=defaultdict(int)

d[0]=0
db[0]=0

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

x=[tuple(map(int,input().split()))for i in range(n)]

dp=[]
dp2=[]
for time,value in x:
    for k,v in d.copy().items():
        if k+time<t:
            if d[k+time]<v+value:
                d[k+time]=v+value
    l=[0]
    for i in range(1,t+1):
        if d[i]>l[-1]:
            l.append(d[i])
        else:
            l.append(l[-1])

    dp.append(l)    
        
for time,value in x[::-1]:
    for k,v in db.copy().items():
        if k+time<t:
            if db[k+time]<v+value:
                db[k+time]=v+value
    l=[0]
    for i in range(1,t+1):
        if db[i]>l[-1]:
            l.append(db[i])
        else:
            l.append(l[-1])
        
    dp2.append(l)
dp=[[0]*t,[0]*t]+dp
dp2=([[0]*t,[0]*t]+dp2)[::-1]

ans=0

for i in range(len(dp)):
    for j in range(t):
        if i==0 or i==len(dp)-1:
            tmp=dp[i][j]+dp2[i][t-j-1]
            if ans<tmp:
                ans=tmp
        else:
            tmp=dp[i][j]+dp2[i][t-j-1]+x[i-1][1]
            if tmp>ans:
                ans=tmp
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline   #input高速化 １文字の時の改行文字に注意+

d={i:0 for i in range(3001)}
db={i:0 for i in range(3001)}

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

x=[tuple(map(int,input().split()))for i in n*[0]]
x.sort()
dp=[]
dp2=[]
for time,value in x:
    for k,v in d.copy().items():
        if k+time<t:
            if d[k+time]<v+value:
                d[k+time]=v+value
        else:
            break
    l=[0]
    for i in range(1,t+1):
        if d[i]>l[-1]:
            l.append(d[i])
        else:
            l.append(l[-1])

    dp.append(l)    
        
for time,value in x[::-1]:
    for k,v in db.copy().items():
        if k+time<t:
            if db[k+time]<v+value:
                db[k+time]=v+value
        else:
            break

    l=[0]
    for i in range(1,t+1):
        if db[i]>l[-1]:
            l.append(db[i])
        else:
            l.append(l[-1])
        
    dp2.append(l)
dp=[[0]*t,[0]*t]+dp
dp2=([[0]*t,[0]*t]+dp2)[::-1]

ans=0

for i in range(len(dp)):
    for j in range(t):
        if i==0 or i==len(dp)-1:
            tmp=dp[i][j]+dp2[i][t-j-1]
            if ans<tmp:
                ans=tmp
        else:
            tmp=dp[i][j]+dp2[i][t-j-1]+x[i-1][1]
            if tmp>ans:
                ans=tmp
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
count = 0
if N <= 3:
    print('0')
else:
    Rlist = []
    Glist = []
    Blist = []
    for i in range(N):
        if S[i] == 'R':
            Rlist.append(i)
        elif S[i] == 'G':
            Glist.append(i)
        else:
            Blist.append(i)
    for i in Rlist:
        for j in Glist:
            for k in Blist:
                listijk = sorted([i,j,k])
                if listijk[1] - listijk[0] != listijk[2] -listijk[1]:
                    count += 1
    print(count)

### FIXED CODE ###

N = int(input())
S = input()
if N <= 3:
    print('0')
else:
    minuscount = 0
    Rcount = 0
    Gcount = 0
    Bcount = 0 
    for i in range(N):
        if S[i] == 'R':
            Rcount += 1
        elif S[i] == 'G':
            Gcount += 1
        else:
            Bcount += 1
        for j in range(1,N):
            if i+2*j>=N:
                break
            if S[i] != S[i+j] and S[i+j] != S[i+2*j] and S[i+2*j] != S[i]:
                minuscount += 1

    print(Rcount*Gcount*Bcount-minuscount)
### BUGGY CODE ###

K, S = map(int,input().split())
import itertools

ar = itertools.product(range(K+1), repeat=3)

ans = 0
for a,b,c in ar:
  if a+b+c == S: ans += 1

print(ans)

### FIXED CODE ###

K, S = map(int,input().split())
import itertools

ar = itertools.product(range(K+1), repeat=2)

ans = 0
for a,b in ar:
  if S - a-b <= K and a+b <= S: ans += 1

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

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

count = 0
for i in range(N):
    lists_slice = lists[:i+1]
    cnt = 0
    for j in lists_slice:
        if lists_slice[i] <= j:
            cnt += 1
    if cnt == i+1:
        count+= 1
print(count)

### FIXED CODE ###

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

count = 0
ans = 0
for i in range(N):
    if i == 0:
        ans = lists[i]
        count += 1
    else:
        if ans >= lists[i]:
            count += 1
            ans = min(ans, lists[i])
        else:
            ans = min(ans, lists[i])


    # lists_slice = lists[:i+1]
    # lists_min = min(lists_slice)
    # if lists_min >= lists[i]:
    #     count += 1
print(count)
### BUGGY CODE ###

MOD = 10**9 + 7

import sys
input = sys.stdin.readline

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

# i段目にたどり着く方法
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if 1 not in a else 0

for i in range(2, n+1):
    dp[i] = (dp[i-1] + dp[i-2]) % MOD if i not in a else 0

print(dp[-1])

### FIXED CODE ###

MOD = 10**9 + 7

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = [0] * (n + 1)
for _ in range(m):
    a[int(input())] = 1

# i段目にたどり着く方法
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if a[1] == 0 else 0

for i in range(2, n+1):
    dp[i] = (dp[i-1] + dp[i-2]) % MOD if a[i] == 0 else 0

print(dp[-1])
### BUGGY CODE ###

N = int(input())
sum=0
while N:
    sum+=N%10
    N//=10
    sum%=9
if sum%9==0:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

N=list(str(input()))
sum=0
for i in range(len(N)):
    sum=(sum+int(N[i]))%9
if sum%9==0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

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

for i in range(n):
    b=x.pop(i)
    print(sorted(x)[int(n/2)-1])
    #print(a[int(n/2)-1])
    x.insert(i,b)

### FIXED CODE ###

N = int(input())
arr = list(map(int, input().split()))
X = arr.copy()
arr.sort()
 
for i in range(N):
    if X[i] < arr[int(N/2)]:
        print(arr[int(N/2)])
    else:
        print(arr[int(N/2)-1])
### BUGGY CODE ###

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

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

for i in range(m):
    b, c = map(int, input().split())
    for j in range(b):
        nums.append(c)

count = 0
result = 0
nums.sort(reverse=True)
for i in nums:
    if count >= n:
        break
    result = result + i
    count = count + 1

print(result)

### FIXED CODE ###

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

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

ops = []
for i in nums:
    ops.append([1, i])
    
for i in range(m):
    b, c = map(int, input().split())
    ops.append([b, c])

total = 0
sums = []
for b, c in sorted(ops, key=lambda x:x[1], reverse=True):
    if total > n:
        break
    sums.extend([c]*b)
    total = total + b
print(sum(sums[:n]))
### BUGGY CODE ###

def resolve():
    n=int(input())
    s=input()
    r=[0]*n
    g = [0] * n
    b = [0] * n
    for i in range(n):
        if s[i]=="R":
            r[i]=1
        elif s[i]=="G":
            g[i]=1
        else:
            b[i]=1
    ans=0
    a=[r,g,b]
    for i in range(n):
            if a[0][i]==1:
                for j in range(i+1,n):
                    if a[1][j]==1:
                        ans+=sum(a[2][j+1:n])
                        if 2*j-i<=n-1:
                            if a[2][2*j-i]==1:
                               ans-=1
    a=[r,b,g]
    for i in range(n):
            if a[0][i]==1:
                for j in range(i+1,n):
                    if a[1][j]==1:
                        ans+=sum(a[2][j+1:n])
                        if 2*j-i<=n-1:
                            if a[2][2*j-i]==1:
                               ans-=1
    a=[g,r,b]
    for i in range(n):
            if a[0][i]==1:
                for j in range(i+1,n):
                    if a[1][j]==1:
                        ans+=sum(a[2][j+1:n])
                        if 2*j-i<=n-1:
                            if a[2][2*j-i]==1:
                               ans-=1
    a=[g,b,r]
    for i in range(n):
            if a[0][i]==1:
                for j in range(i+1,n):
                    if a[1][j]==1:
                        ans+=sum(a[2][j+1:n])
                        if 2*j-i<=n-1:
                            if a[2][2*j-i]==1:
                               ans-=1
    a=[b,r,g]
    for i in range(n):
            if a[0][i]==1:
                for j in range(i+1,n):
                    if a[1][j]==1:
                        ans+=sum(a[2][j+1:n])
                        if 2*j-i<=n-1:
                            if a[2][2*j-i]==1:
                               ans-=1
    a=[b,g,r]
    for i in range(n):
            if a[0][i]==1:
                for j in range(i+1,n):
                    if a[1][j]==1:
                        ans+=sum(a[2][j+1:n])
                        if 2*j-i<=n-1:
                            if a[2][2*j-i]==1:
                               ans-=1
    print(ans)
resolve()

### FIXED CODE ###

def resolve():
    n = int(input())
    s = input()
    r = [0] * n
    g = [0] * n
    b = [0] * n
    for i in range(n):
        if s[i] == "R":
            r[i] = 1
        elif s[i] == "G":
            g[i] = 1
        else:
            b[i] = 1
    ans = sum(r)*sum(g)*sum(b)

    for i in range(1, n // 2 + 1):
        j = 0
        while j + 2 * i <= n - 1:
            if {s[j], s[j + i], s[j + 2 * i]} == {"R", "G", "B"}:
                ans -= 1
            j += 1
    print(ans)
resolve()
### BUGGY CODE ###

import sys
import socket

if socket.gethostname() in ['N551J', 'F551C']:
    sys.stdin = open('f1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


def solve():
    n, d, a = read_int_list()
    pairs = [read_int_list() for _ in range(n)]
    pairs.sort()
    x, h = map(list, zip(*pairs))

    res = 0
    damage = 0
    q = []
    for i in range(n):
        while len(q) > 0 and q[0][0] + d < x[i]:
            y, m = q.pop(0)
            damage -= m * a
        if damage < h[i]:
            y = x[i] + d
            quotient, rest = divmod(h[i] - damage, a)
            m = quotient + (rest > 0)
            q.append((y, m))
            damage += m * a
            res += m

    return res



def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import socket
from collections import deque


if socket.gethostname() in ['N551J', 'F551C']:
    in_file = 'f1.in'
    in_file = 'after_contest_01.in'
    sys.stdin = open(in_file)


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


def solve():
    n, d, a = read_int_list()
    pairs = [read_int_list() for _ in range(n)]
    pairs.sort()
    x, h = map(list, zip(*pairs))

    res = 0
    damage = 0
    q = deque()
    for i in range(n):
        # print(i, damage, file=sys.stderr)
        while len(q) > 0 and q[0][0] + d < x[i]:
            y, m = q.popleft()
            damage -= m * a
        if damage < h[i]:
            y = x[i] + d
            quotient, rest = divmod(h[i] - damage, a)
            m = quotient + (rest > 0)
            q.append((y, m))
            damage += m * a
            res += m

    return res



def main():
    res = solve()
    print(res)


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

import math

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())

ans = 0
for a in range(1, K+1):
  for b in range(1, K+1):
    for c in range(1, K+1):
      ans += math.gcd(math.gcd(a, b), c)

print(ans)

### FIXED CODE ###

import math

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())

ans = 0
for a in range(1, K+1):
  for b in range(1, K+1):
    for c in range(1, K+1):
      ans += math.gcd(math.gcd(a, b), c)

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

K = int(input())
x = 7
count = 1

for i in range(100000):
  if x % K == 0:
    print(count)
    exit(0)
  else:
    x = 10*x + 7
    count += 1
print("-1")

### FIXED CODE ###

def calc(k):
    cur = 0
    for i in range(1, 10 ** 7):
        cur *= 10
        cur += 7
        cur %= k
        if cur == 0:
            return i

    return -1


k = int(input())
print(calc(k))
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
mod = 10**9 +7
ans = 0

for i in range(len(a)-1):
    ans +=a[i]*(sum(a[i+1:len(a)]))
print(ans%mod)

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
a.reverse()
mod = 10**9 +7
ans = 0
S=[0]
for i in range(0,N):
    S.append(S[i]+a[i])
ans = 0
for j in range(len(a)):
    ans +=(a[j]*S[j])
print(ans%mod)
### BUGGY CODE ###

def main():
    n, k = map(int, input().split())
    h = tuple(map(int, input().split()))
    inf = float('inf')
    dp = [inf] * n
    r = min(n, k + 1)
    for i1 in range(1, r):
        dp[i1] = abs(h[i1] - h[0])

    for i1 in range(2, n):
        start = max(1, i1 - k)
        cost = dp[start] + abs(h[i1] - h[start])
        for i2 in range(start + 1, i1):
            cost = min(cost, dp[i2] + abs(h[i2] - h[i1]))
        dp[i1] = min(cost, dp[i1])
    print(dp[n - 1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

dp = [0] * n
for i in range(1, n):
  start = max(0, i - k)
  dp[i] = dp[start] + abs(h[start] - h[i])
  for j in range(start+1, i + 1):
    dp[i] = min(dp[i], dp[j] + abs(h[j]-h[i]))
  
print(dp[n-1])
### BUGGY CODE ###

N, K = map(int,input().split())
A = sorted(map(int,input().split()))
start = 0
end = A[-1]
l = (start + end)/2
while int(end) - int(start) >= 1:
   l = (start + end)/2
   count = 0
   for i in range(N):
      q, mod = divmod(A[i], l)
      if mod == 0.0:
         q -= 1
      count += q
   if count > K:
      start = l
   else:
      end = l
ans = (start + end)/2
print(int(end)+1)

### FIXED CODE ###

N, K = map(int,input().split())
A = list(map(int,input().split()))
start = 0
end = 10**9
while end - start > 1:
   l = (start + end)/2
   l = int(l)
   count = 0
   for i in range(N):
      q = A[i]/l
      if q == int(q):
         q -= 1
      count += int(q)
   if count <= K:
      end = l
   else:
      start = l
print(end)
### BUGGY CODE ###

# damedatta
def binsearch(l, r, fn):
    while r - l > 1:
        m = (l + r) // 2
        if fn(m):
            l = m
        else:
            r = m
    return l
import bisect
def main():
    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 = [i + j for i in B for j in C]
    A.sort(reverse=True)
    D.sort(reverse=True)
    def calc(x):
        t = 0
        ii = len(D) - 1
        for i in A:
            while ii >= 0 and D[ii] + i < x:
                ii -= 1
            t += ii + 1
            if t >= K:
                return True
            else:
                return False
    l = binsearch(D[-1] + A[-1], D[0] + A[0], calc)
    ii = len(D) - 1
    rl = []
    for i in A:
        while ii >= 0 and D[ii] + i < l:
            ii -= 1
        if ii < 0:
            break
        rl.extend([i + j for j in D[:ii+1]])
    rl.sort(reverse=True)
    print('\n'.join(str(i) for i in rl[:K]))
main()


### FIXED CODE ###

# damedatta
def binsearch(l, r, fn):
    while r - l > 1:
        m = (l + r) // 2
        if fn(m):
            l = m
        else:
            r = m
    return l
def main():
    X, Y, Z, K = map(int, input().split())
    D = sorted(map(int, input().split()), reverse=True)
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    A = sorted((i + j for i in B for j in C), reverse=True)
    def calc(x):
        t = 0
        ii = len(D) - 1
        for i in A:
            while ii >= 0 and D[ii] + i < x:
                ii -= 1
            t += ii + 1
            if t >= K:
                return True
            if ii < 0:
                return False
        return t >= K
    l = binsearch(D[-1] + A[-1], D[0] + A[0]+1, calc)
    ii = len(D) - 1
    rl = []
    for i in A:
        while ii >= 0 and D[ii] + i < l + 1:
            ii -= 1
        if ii < 0:
            break
        rl.extend(i + j for j in D[:ii+1])
    rl.sort(reverse=True)
    rl += [l] * (K - len(rl))
    print('\n'.join(str(i) for i in rl))
main()
### BUGGY CODE ###

n,m=map(int,input().split())
b=[[int(x) for x in input().split()] for y in range(m)]
u=n*(n-1)//2

s=[]
a=[u]

for i in range(m-1,0,-1):
  x=y=-1
  for j in range(len(s)):
    if b[i][0] in s[j]:
      x = j
    if b[i][1] in s[j]:
      y = j
    if x!=-1 and y!=-1:
      break

  if x==-1 and y==-1:
    s.append(set((b[i][0],b[i][1])))
  elif y==-1:
    s[x].add(b[i][1])
  elif x==-1:
    s[y].add(b[i][0])
  elif x!=y:
    for k in range(len(s[y])):
      s[x].add(s[y].pop())
    s.pop(y)

  t=0
  for j in range(len(s)):
    t += (len(s[j])*(len(s[j])-1))//2
  a.append(u-t)
 
a.reverse()
for i in range(len(a)):
  print(a[i])


### FIXED CODE ###

n, m = map(int, input().split())
e = [[int(x) for x in input().split()] for _ in range(m)]

u = [-1]*(n+1)

def find(x):
  return x if u[x] < 0 else find(u[x])

t = n*(n-1)// 2
s = [t]

for i in range(m-1,0,-1):
  a = find(e[i][0])
  b = find(e[i][1])
  if a > b:
    a, b = b, a
  if a != b:
    t -= u[a]*u[b]
    u[a] += u[b]
    u[b] = a
  s.append(t)

for i in reversed(s):
  print(i)
### BUGGY CODE ###

import math

a, b, c, k = list(map(int, input().split()))

for i in range(k):
  m = b + c
  n = a + c
  o = a + b
  a = m
  b = n
  c = o

if math.fabs(a - b) > 1.0e18:
  print("Unfair")
else:
  print(int(a - b))


### FIXED CODE ###

a, b, c, k = list(map(int, input().split()))

diff = (a - b) * ((-1) ** k)

if diff > 1.0e18:
  print("Unfair")
else:
  print(diff)
### BUGGY CODE ###

def main():
 
    def find(target):
        if parent[target] < 0:
            return target
        else:
            parent[target] = find(parent[target])
            return parent[target]
 
    def is_same(x, y):
        return find(x) == find(y)
 
    def union(x, y):
        root_x = find(x)
        root_y = find(y)
        if root_x == root_y:
            return
        if parent[root_x] > parent[root_y]:
            root_x, root_y = root_y, root_x
        parent[root_x] += parent[root_y]
        parent[root_y] = root_x

    def members(n, x):
        root = find(x)
        return [i for i in range(n) if find(i) == root]
 
    def get_size(x):
        return -parent[find(x)]
 
    def get_root():
        return [i for i, root in enumerate(parent) if root < 0]

    n, m = map(int, input().split())
    parent = [-1 for _ in range(n)]
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        union(a, b)
        # print(parent)
    # ans = 0
    # for i in range(n):
    #     ans = max(ans, get_size(i))
    # print(ans)
    max_member = 0
    for i in get_root():
        # print(i, members(n, i))
        max_member  = max(max_member, len(members(n, i)))
    print(max_member)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
 
    def find(target):
        if parent[target] < 0:
            return target
        else:
            parent[target] = find(parent[target])
            return parent[target]
 
    def is_same(x, y):
        return find(x) == find(y)
 
    def union(x, y):
        root_x = find(x)
        root_y = find(y)
        if root_x == root_y:
            return
        if parent[root_x] > parent[root_y]:
            root_x, root_y = root_y, root_x
        parent[root_x] += parent[root_y]
        parent[root_y] = root_x

    def members(n, x):
        root = find(x)
        return [i for i in range(n) if find(i) == root]
 
    def get_size(x):
        return -parent[find(x)]
 
    def get_root():
        return [i for i, root in enumerate(parent) if root < 0]

    n, m = map(int, input().split())
    parent = [-1 for _ in range(n)]
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        union(a, b)
        # print(parent)
    ans = 0
    for i in range(n):
        ans = max(ans, get_size(i))
    print(ans)
    # 状況理解用
    # max_member = 0
    # for i in get_root():
    #     # print(i, members(n, i))
    #     max_member  = max(max_member, len(members(n, i)))
    # print(max_member)

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

import sys
input=sys.stdin.readline

R,C,K=map(int,input().split())
rcv=[list(map(int,input().split())) for _ in range(K)]

MAP=[[0 for _ in range(C)] for _ in range(R)]
DP=[[[0 for _ in range(4)] for _ in range(C)] for _ in range(R)]
for r,c,v in rcv:
    MAP[r-1][c-1]=v

DP[0][0][1]=MAP[0][0]
for i in range(R):
    for j in range(C):
        for num,point in enumerate([[1,0],[0,1]]):
            x,y=point
            X,Y=i+x,j+y
            if 0<=X<R and 0<=Y<C:
                for k in range(3):
                    if num==0:
                        DP[X][Y][1]=max(DP[X][Y][1],max(DP[i][j])+MAP[X][Y])
                    else:
                        DP[X][Y][k+1]=max(DP[X][Y][k+1],DP[X][Y][k],DP[i][j][k+1],DP[i][j][k]+MAP[X][Y])
print(max(DP[-1][-1]))

### FIXED CODE ###

import sys
input = sys.stdin.readline

R,C,K=map(int,input().split())
J=[tuple(map(int,input().split())) for i in range(K)]

#DP0=[[0]*(C+2) for i in range(R+2)]
DP1=[[0]*(C+2) for i in range(R+2)]
DP2=[[0]*(C+2) for i in range(R+2)]
DP3=[[0]*(C+2) for i in range(R+2)]

MAP=[[0]*C for i in range(R)]

for x,y,v in J:
    MAP[x-1][y-1]=v

for i in range(R):
    for j in range(C):
        DP1[i][j]=max(DP1[i][j-1],DP1[i-1][j]+MAP[i][j],DP2[i-1][j]+MAP[i][j],DP3[i-1][j]+MAP[i][j])
        DP2[i][j]=max(DP2[i][j-1],DP1[i][j-1]+MAP[i][j])
        DP3[i][j]=max(DP3[i][j-1],DP2[i][j-1]+MAP[i][j])

ANS=0
for i in range(R):
    for j in range(C):
        ANS=max(ANS,DP1[i][j],DP2[i][j],DP3[i][j])
print(ANS)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(2*1000000)

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

dp_dict = {}

inf = -1*1000000000


def dp(i, j):
    if j == 1:
        return A[i]
    if i+2 >= N:
        return inf
    if N//2-j < i//2-1:
        return inf
    temp = max([dp(i+2, j-1)+A[i], dp(i+1, j)])
    dp_dict[(i, j)] = temp
    return temp


select = N//2
if select == 1:
    print(max(A))
else:
    print(dp(0, select))

### FIXED CODE ###

N = int(input())
A = [0]+list(map(int, input().split(" ")))

dp_list = [{0, 0}, {0: 0, 1: A[1]}, {0: 0, 1: A[1] if A[1] > A[2] else A[2]}]

for i in range(3, N+1):
    b = (i-1)//2
    f = (i+1)//2
    dp_list.append({})
    for j in range(b, f+1):
        if j in dp_list[i-1]:
            dp_list[i][j] = dp_list[i-2][j-1]+A[i] if dp_list[i -
                                                              2][j-1]+A[i] > dp_list[i-1][j] else dp_list[i-1][j]
        else:
            dp_list[i][j] = dp_list[i-2][j-1]+A[i]

print(dp_list[-1][N//2])