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

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

count = 0
for x in a:
    count += x.count("#")
#print(count)

b = [[100000 for i in range(m)] for i in range(n)]
#print(a)

x = [0, 0, -1, 1]
y = [-1, 1, 0, 0]

queue = deque([[0,0]])
b[0][0] = 1
while queue:
    now = queue.popleft()
    a[now[0]][now[1]] = "#"
    for i in range(4):
        if 0 <= now[0] + y[i] < n and 0 <= now[1] + x[i] < m:
            if a[now[0]+y[i]][now[1]+x[i]] == '.':
                queue.append([now[0]+y[i],now[1]+x[i]])
                b[now[0]+y[i]][now[1]+x[i]] = min(b[now[0]][now[1]] + 1, b[now[0]+y[i]][now[1]+x[i]])


if b[n-1][m-1] == 100000:
    print(-1)
    exit()

ans = n * m - (b[n-1][m-1] + count)
print(ans)



### FIXED CODE ###

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

count = 0
for x in a:
    count += x.count("#")
#print(count)

b = [[-1 for i in range(m)] for i in range(n)]
#print(a)

x = [0, 0, -1, 1]
y = [-1, 1, 0, 0]
queue = deque([[0,0]])
b[0][0] = 1
while queue:
    now = queue.popleft()
    if now == [n-1,m-1]:
        print(n * m - (b[n-1][m-1] + count))
        exit()
    a[now[0]][now[1]] = "#"
    for i in range(4):
        if 0 <= now[0] + y[i] < n and 0 <= now[1] + x[i] < m and b[now[0]+y[i]][now[1]+x[i]] == -1:
            if a[now[0]+y[i]][now[1]+x[i]] == '.':
                queue.append([now[0]+y[i],now[1]+x[i]])
                b[now[0]+y[i]][now[1]+x[i]] = b[now[0]][now[1]] + 1

print(-1)
### BUGGY CODE ###

n=int(input())
s=0
for i in range(n):
    a=int(input())
 #   print(str(a),'DAYO')
    if a==2 or a==3:
        s+=1
    else:
        for j in range(3,a+1,2):
          #  print(str(i), str(j)+'PP')
            if j==a:
                s+=1
            elif a%j==0:
                break

print(s)

### FIXED CODE ###

import math
n=int(input())
s=0
for i in range(n):
    a=int(input())
    b=math.ceil(a**0.5)
    if a==2:
        s+=1
    elif a%2==0 or a < 2:
        continue
    else:
        c=0
        for j in range(3,b+1,2):
            if a%j==0:
                c+=1
                break
        if c==0:
            s+=1
print(s)
### BUGGY CODE ###

# 方針
# 頂点uからvに至る際に通る辺のリストをe[u][v]とする。
# M個の制約からl個(l>=1)選んだ際に，いずれの制約も満たさないために白く塗るべき辺の個数を考える。
# これは,uiからviに至る際に通る辺のリストの和集合の要素の数。

from collections import deque

N = int(input())
adj = [[] for i in range(N + 1)] # 1-ind
ve = {} # 両端の頂点の番号⇒辺の番号
for i in range(1, N) : # 1-ind
    a, b = map(int,input().split())
    adj[a].append(b); adj[b].append(a)
    ve[(a, b)] = ve[(b, a)] = i
# print(adj) #DB
# print(ve) #DB

# 頂点iからスタートし，葉に行き着くまでの通過頂点とそれまでに通過した辺を記録
l = [[set() for j in range(N + 1)] for i in range(N + 1)]
q = deque()
for i in range(1, N + 1):
    r = [False] * (N + 1)
    q.append(i); r[i] = True
    while q:
        u = q.popleft()
        for v in adj[u]:
            if r[v]:
                continue
            l[i][v].update(l[i][u])            
            l[i][v].add(ve[(u, v)])
            q.append(v)
            r[v] = True
# print(l) #DB
'''
for i in range(1, N + 1):
    for j in range(i, N + 1):
        print(i, j, l[i][j])
'''
M = int(input())
c = [set()]
for i in range(1, M + 1): # 1-ind
    u, v = map(int,input().split())
    c.append((u, v))

ans = 2 ** (N - 1)
for k in range(1, 1 << M): # 制約0個の場合を除外 ※初期値で考慮することもできそう
    V = set()
    d = 0 # 考慮する制約の個数
    for i in range(1, M + 1):
        if k >> (i - 1) & 1:
            d += 1
            u, v = c[i]
            V |= l[u][v]
    # print(k, V)
    temp = 2 ** (N - 1 - len(V))
    # print(d, temp)
    if d % 2 == 1:
        ans -= temp
    elif d % 2 == 0:
        ans += temp

print(ans)

### FIXED CODE ###

# 方針
# 頂点uからvに至る際に通る辺のリストをe[u][v]とする。
# M個の制約からl個(l>=1)選んだ際に，いずれの制約も満たさないために白く塗るべき辺の個数を考える。
# これは,uiからviに至る際に通る辺のリストの和集合の要素の数。

from collections import deque

N = int(input())
adj = [[] for i in range(N + 1)] # 1-ind
ve = {} # 両端の頂点の番号⇒辺の番号
for i in range(1, N) : # 1-ind
    a, b = map(int,input().split())
    adj[a].append(b); adj[b].append(a)
    ve[(a, b)] = ve[(b, a)] = i
# print(adj) #DB
# print(ve) #DB

# 頂点iからスタートし，葉に行き着くまでの通過頂点とそれまでに通過した辺を記録
l = [[set() for j in range(N + 1)] for i in range(N + 1)]
q = deque()
for i in range(1, N + 1):
    r = [False] * (N + 1)
    q.append(i); r[i] = True
    while q:
        u = q.popleft()
        for v in adj[u]:
            if r[v]:
                continue
            l[i][v].update(l[i][u])            
            l[i][v].add(ve[(u, v)])
            q.append(v)
            r[v] = True
# print(l) #DB
'''
for i in range(1, N + 1):
    for j in range(i, N + 1):
        print(i, j, l[i][j])
'''
M = int(input())
c = [set()]
for i in range(1, M + 1): # 1-ind
    u, v = map(int,input().split())
    c.append((u, v))

ans = 2 ** (N - 1)
for k in range(1, 1 << M): # 制約0個の場合を除外 ※初期値で考慮することもできそう
    V = set()
    d = 0 # 考慮する制約の個数
    for i in range(1, M + 1):
        if k >> (i - 1) & 1:
            d += 1
            u, v = c[i]
            V |= l[u][v]
    # print(k, V)
    temp = 2 ** (N - 1 - len(V))
    # print(d, temp)
    if d % 2 == 1:
        ans -= temp
    elif d % 2 == 0:
        ans += temp

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

from bisect import bisect_left,bisect
n = int(input())
l = list(map(int,input().split()))
l.sort()
ans = 0
#c - b < a < c + b
for i in range(n-1):
    for j in range(i+1,n):
        sahen = bisect(l,l[j]-l[i])
        uhen = bisect_left(l,l[j]+l[i])
        ans += uhen - sahen
        if sahen <= i <= uhen -1:
            ans -= 1
        if sahen <= j <= uhen -1:
            ans -= 1
print(ans//3)

### FIXED CODE ###

from bisect import bisect_left,bisect
n = int(input())
l = list(map(int,input().split()))
l.sort()
ans = 0
#c - b < a < c + b
for i in range(n-1):
    for j in range(i+1,n):
        sahen = bisect(l,l[j]-l[i])
        uhen = bisect_left(l,l[j]+l[i])
        ans += uhen - sahen
        if sahen <= i <= uhen -1:
            ans -= 1
        if sahen <= j <= uhen -1:
            ans -= 1
print(ans//3)
### BUGGY CODE ###

import bisect, copy

n = int(input())
a = list(map(int, input().split()))
b = copy.copy(a)
ans = []
num = 1
while num != n:
    if max(a) < 0:
        break
    while a[num - 1] > a[num]:
        a2 = copy.copy(a)
        a2.sort()
        temp = a[num - 1] - a[num]
        temp2 = bisect.bisect_left(a2, temp)
        if temp2 == n:
            temp2 -= 1
        ans.append([a.index(a2[temp2]) + 1, num + 1])
        a[num] += a2[temp2]
    num += 1

ans2 = []
num = n - 2
while num != -1:
    if min(b) > 0:
        break
    while b[num] > b[num + 1]:
        b2 = copy.copy(b)
        b2.sort()
        temp = b[num + 1] - b[num]
        temp2 = bisect.bisect_right(b2, temp)
        if temp2 == 0:
            temp2 += 1
        ans2.append([b.index(b2[temp2 - 1]) + 1, num + 1])
        b[num] += b2[temp2 - 1]
    num -= 1

if len(ans) == 0 and len(ans2) == 0:
    print(0)
elif len(ans) == 0:
    print(len(ans2))
    for i in ans2:
        print(i[0], i[1])
elif len(ans2) == 0:
    print(len(ans))
    for i in ans:
        print(i[0], i[1])
else:
    if len(ans) > len(ans2):
        print(len(ans2))
        for i in ans2:
            print(i[0], i[1])
    else:
        print(len(ans))
        for i in ans:
            print(i[0], i[1])

### FIXED CODE ###

import bisect, copy

n = int(input())
a = list(map(int, input().split()))
b = copy.copy(a)
ans = []
num = 1
count = 0
while num != n:
    if max(a) < 0:
        break
    while a[num - 1] > a[num]:
        a2 = copy.copy(a)
        a2.sort()
        temp = a[num - 1] - a[num]
        temp2 = bisect.bisect_left(a2, temp)
        if temp2 == n:
            temp2 -= 1
        ans.append([a.index(a2[temp2]) + 1, num + 1])
        a[num] += a2[temp2]
        count += 1
        if count == n * 2 + 1:
            break
    num += 1
    if count == n * 2 + 1:
        break

ans2 = []
num = n - 2
count2 = 0
while num != -1:
    if min(b) > 0:
        break
    while b[num] > b[num + 1]:
        b2 = copy.copy(b)
        b2.sort()
        temp = b[num + 1] - b[num]
        temp2 = bisect.bisect_right(b2, temp)
        if temp2 == 0:
            temp2 += 1
        ans2.append([b.index(b2[temp2 - 1]) + 1, num + 1])
        b[num] += b2[temp2 - 1]
        count2 += 1
        if count2 == n * 2 + 1:
            break
    num -= 1
    if count2 == n * 2 + 1:
        break

if len(ans) == 0 and len(ans2) == 0:
    print(0)
elif len(ans) == 0:
    print(len(ans2))
    for i in ans2:
        print(i[0], i[1])
elif len(ans2) == 0:
    print(len(ans))
    for i in ans:
        print(i[0], i[1])
else:
    if len(ans) > len(ans2):
        print(len(ans2))
        for i in ans2:
            print(i[0], i[1])
    else:
        print(len(ans))
        for i in ans:
            print(i[0], i[1])
### BUGGY CODE ###

def f(n):
    if n < 2:
        return 0
    lim1 = int((n - 2) ** 0.5 - 1) + 1
    lim2 = int((-2 + (4 - 12 * (1 - n)) ** 0.5) / 6) + 1
    lim3 = int(n / 6) + 1

    result = set()
    for x in range(1, lim3):
        for y in range(1, lim2):
            if x > y:
                continue
            for z in range(1, lim1):
                if y > z:
                    continue
                if x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x == n:
                    tmp = set([x, y, z])
                    if tmp not in result:
                        result.add(tuple(tmp))
    count = 0
    for s in result:
        if len(s) == 1:
            count += 1
        elif len(s) == 2:
            count += 3
        else:
            count += 6
    return count


for i in range(1, int(input()) + 1):
    print(f(i))

### FIXED CODE ###

import numpy as np


def calc(n):
    #     lim = int((n - 2) ** 0.5 - 1) + 1
    lim = 130

    result = np.zeros(n + 1, dtype=int)
    for x in range(1, lim):
        for y in range(1, lim):
            if x > y:
                continue
            for z in range(1, lim):
                if y > z:
                    continue
                index = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
                if index > n:
                    continue
                s = set([x, y, z])
                if len(s) == 1:
                    result[index] += 1
                elif len(s) == 2:
                    result[index] += 3
                else:
                    result[index] += 6

    return result[1:]


for i in calc(int(input())):
    print(i)
### BUGGY CODE ###

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

for i in range(N):
  ans = 0
  tmpA = A[:]
  del tmpA[i]
  setA = set(tmpA)
  for a in setA:
    c = tmpA.count(a)
    if c > 1:
      ans += c * (c-1) // 2
  print(ans)

### FIXED CODE ###

from collections import Counter

N = int(input())
A = list(map(int, input().split()))
countA = Counter(A)
ansA = [v*(v-1)//2 for k,v in countA.items()]
sumA = sum(ansA)

for i in range(N):
  t =  countA[A[i]]
  ans = sumA - t*(t-1)//2 + (t-1)*(t-2)//2
  print(ans)
### BUGGY CODE ###

import sys
import os
import math

def file_input():
    f = open('../Beginner_Contest_165/input.txt', 'r')
    sys.stdin = f

def main():
    #file_input()
    # input()
    A,B,N=map(int, input().split())

    max=0.0
    for x in range(N+1):
        # ans=int(A*x/B)-A*int(x/B)
        min,_=math.modf(x/B)
        # ans=int(A*min)
        # print(min)
        if x==0:
            max=min
        elif min > max:
            max=min
        else:
            break

    print(int(max*A))

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os

def file_input():
    f = open('../Beginner_Contest_165/input.txt', 'r')
    sys.stdin = f

def main():
   # file_input()
    # input()
    A,B,N=map(int, input().split())

    max=0
    # for x in range(N+1):
    #     # ans=int(A*x/B)-A*int(x/B)
    #     min,_=math.modf(x/B)
    #     # ans=int(A*min)
    #     # print(min)
    #     if x==0:
    #         max=min
    #     elif min > max:
    #         max=min
    #     else:
    #         break

    # max=0
    # max_x=0
    # first=0
    #
    # for x in range(N+1):
    #     rem = x%B
    #     if x == 0:
    #         first=rem
    #     elif rem == first:
    #         break
    #     if rem > max:
    #         max=rem
    #         max_x=x

    if N<B:
        max_x=N
    else:
        max_x=B-1

    # min,_=math.modf(max_x/B)

    print(int(A*max_x/B)-A*int(max_x/B))

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

L = list(map(int, input().split()))
 
N = L[0]
K = L[1]
Q = L[2]
 
A = []
 
for _ in range(Q):
    A.append(int(input()))
	
P = [K] * N
 
 
r = 0
 
for i in range(0,len(A)):
	r = A[i] - 1
	P[r] += 1
	P = list(map(lambda x: x-1,P))
	
for i in range(0,len(P)):
	if P[i] > 0:
		print("Yes")
	else:print("No")

### FIXED CODE ###

N,K,Q = map(int, input().split())

P = [0] * N


for i in range(Q):
	A = int(input())
	P[A-1] += 1


for j in range(0,len(P)):
	if K - Q + P[j] > 0:
		print('Yes')
	else:
		print('No')
### BUGGY CODE ###

k = int(input())
lunlun = list(range(1, 10))

for i in range(k-1):
    a = lunlun.pop(0)
    b = a * 10 +  a % 10 
    if a % 10 != 0:
        lunlun.append(b - 1)
    lunlun.append(b)
    if a % 10 != 9:
        lunlun.append(b + 1)

print(lunlun.pop(0))

### FIXED CODE ###

k = int(input())
lunlun = list(range(1, 10))

for i in range(k-1):
    a = lunlun[i]
    b = a * 10 +  a % 10 
    if a % 10 != 0:
        lunlun.append(b - 1)
    lunlun.append(b)
    if a % 10 != 9:
        lunlun.append(b + 1)

print(lunlun[k-1])
### BUGGY CODE ###

mod = 10**9+7
n = int(input())
A = list(map(int,input().split()))
c01 = [[0,0] for i in range(60)]
for a in A:
    for j in range(60):
        if a>>j &1:
            c01[j][1] += 1
        else:
            c01[j][0] += 1
ans = 0
for i in range(60):
    ans += 2**i *c01[i][0]*c01[i][1]
    ans%=mod
print(ans)


### FIXED CODE ###

mod = 10**9+7
n = int(input())
A = list(map(int,input().split()))
c01 = [[0,0] for i in range(60)]
for a in A:
    for j in range(60):
        if a>>j &1:
            c01[j][1] += 1
        else:
            c01[j][0] += 1
ans = 0
for i in range(60):
    ans += 2**i *c01[i][0]*c01[i][1]
    ans%=mod
print(ans)
### BUGGY CODE ###

#python3.4
def inpul(): return list(map(int, input().split()))
import math

N, K = inpul()
A = inpul()

f = 0
f_ans = 0
try:
    serch_int_index = int(math.log2(K))
    serch_int = 2 ** serch_int_index

except Exception as e:
    serch_int = 0

for num in range(serch_int, K+1):
    for item_A in A:
        f = f + (num ^ item_A)
    if(f > f_ans):
        f_ans = f
    f = 0
print(f_ans)


### FIXED CODE ###

n,k = list(map(int, input().split()))
a=list(map(int, input().split()))
x=0
ans = 0
for i in range(45,-1,-1):
  c=0
  for p in a:
    if (p >> i) & 1:
      c += 1
  if n - c > c and x + (1<<i) <= k:
    ans += (n-c) * (1<<i)
    x += 1<<i
  else:
    ans += c * (1<<i)
print(ans)
### BUGGY CODE ###

N,K = (int(T) for T in input().split())
Next = [int(T)-1 for T in input().split()]
GetP = [int(T) for T in input().split()]
DispP = [0]*N
for TN in range(0,N):
    Now   = Next[TN]
    Point = GetP[Now]
    MAXP  = Point
    RoopC = 1
    RoopFlag = False
    for TK in range(1,K):
        Now = Next[Now]
        Point += GetP[Now]
        RoopC += 1
        if Now==TN and Point>=0:
            RoopFlag = True
            break
        elif Now==TN and Point<0:
            RoopFlag = False
            break
        if MAXP<Point:
            MAXP = Point
            MInd = TK
    if RoopFlag:
        Omit = K-RoopC*(K//RoopC)
        PointO = 0
        MAXO = 0
        for TO in range(0,Omit):
            Now = Next[Now]
            PointO += GetP[Now]
            if MAXO<PointO:
                MAXO = PointO
        if Point*(K//RoopC)+MAXO>=Point*((K//RoopC)-1)+MAXP:
            DispP[TN] = Point*(K//RoopC)+MAXO
        else:
            DispP[TN] = Point*((K//RoopC)-1)+MAXP
    else:
        DispP[TN] = MAXP
print(max(DispP))

### FIXED CODE ###

N,K = (int(T) for T in input().split())
Next = [int(T)-1 for T in input().split()]
GetP = [int(T) for T in input().split()]
DispP = [0]*N
for TN in range(0,N):
    Now   = Next[TN]
    Point = GetP[Now]
    MAXP  = Point
    RoopC = 1
    RoopFlag = False
    for TK in range(1,K):
        Now = Next[Now]
        Point += GetP[Now]
        RoopC += 1
        if Now==TN and Point>=0:
            RoopFlag = True
            break
        elif Now==TN and Point<0:
            RoopFlag = False
            break
        if MAXP<Point:
            MAXP = Point
            MInd = TK
    if RoopFlag:
        Omit = K-RoopC*(K//RoopC)
        PointO = 0
        MAXO = 0
        for TO in range(0,Omit):
            Now = Next[Now]
            PointO += GetP[Now]
            if MAXO<PointO:
                MAXO = PointO
        if Point*(K//RoopC)+MAXO>=Point*((K//RoopC)-1)+MAXP:
            DispP[TN] = Point*(K//RoopC)+MAXO
        else:
            DispP[TN] = Point*((K//RoopC)-1)+MAXP
    else:
        DispP[TN] = MAXP
print(max(DispP))
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import deque

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

que = deque()
dist = [float('inf')] * n
prev = [-1] * n
dist[0] = 0
que.append(0)
while que:
    now = que.pop()
    for edge in edges[now]:
        if dist[edge] > dist[now] + 1:
            dist[edge] = dist[now] + 1
            prev[edge] = now + 1
            que.append(edge)


print('Yes')
for i in range(1, n):
    print(prev[i])



### FIXED CODE ###

#!/usr/bin/env python3
from collections import deque
# import sys
# input = sys.std.readline

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

que = deque()
dist = [float('inf')] * n
prev = [-1] * n
dist[0] = 0
que.append(0)
while que:
    now = que.popleft()
    for edge in edges[now]:
        if dist[edge] > dist[now] + 1:
            dist[edge] = dist[now] + 1
            prev[edge] = now + 1
            que.append(edge)


print('Yes')
for i in range(1, n):
    print(prev[i])
### BUGGY CODE ###

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

### FIXED CODE ###

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

import math
A, B, N = map(int, input().split())
x = 0
ans1 = 0
while x <= N and x <= 10**7:
    ans = int((A*x)/B) - A * int(x / B)
    ans1 = max(ans1, ans)
    x += 1

print(ans1)


### FIXED CODE ###

import math

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


ans1 = 0

if N > B - 1:
    x = B-1
    print(int((A * x) / B) - A * int(x / B))
elif N <= B - 1:
    x = N
    print(int((A * x) / B) - A * int(x / B))
### BUGGY CODE ###

def judge(exp,torf,i):
	if i==len(dic):
		return eval(exp)
	else:
		return judge(exp,torf+[True],i+1) or judge(exp,torf+[False],i+1)
while 1:
	exp=list(raw_input())
	if exp[0]=="#":break
	dic=[]
	for i in range(len(exp)):
		if exp[i]=="&":exp[i]="and"
		elif exp[i]=="~":exp[i]="not"
		elif exp[i]=="|":exp[i]="or"
		elif exp[i]!="(" and exp[i]!=")":
			if exp[i] not in dic:
				dic.append(exp[i])
				exp[i]="torf["+str(len(dic)-1)+"]"
			else:
				exp[i]="torf["+str(dic.index(exp[i]))+"]"
	exp=" ".join(map(str,exp))
	print "yes" if judge(exp,[],0) else "no"

### FIXED CODE ###

while 1:
	exps=raw_input().split("|")
	if exps[0]=="#":break
	for exp in exps:
		v=1
		lit=exp[1:-1].split("&")
		for i in range(2):
			for j in range(i+1,3):
				if (lit[i]=="~"+lit[j]) or ("~"+lit[i]==lit[j]):
					v=0
		if v:
			print "yes"
			break
	else:
		print "no"
### BUGGY CODE ###

#!/usr/bin/env python3
N = int(input())

def solve():
    for h in range(1, 3501):
        for w in range(1, 3501):
            a = N * h * w
            b = 4 * h * w - N * h - N * w
            if b >= 1:
                n, m = divmod(a, b)
                if m == 0:
                    print(h, n, w)
                    return

solve()


### FIXED CODE ###

#!/usr/bin/env python3
N = int(input())

def solve():
    for h in range(1, 3501):
        for w in range(h, 3501):
            a = N * h * w
            b = 4 * h * w - N * h - N * w
            if b < 1:
                continue
            n = a / b
            if n == int(n):
                print(h, int(n), w)
                return

solve()
### BUGGY CODE ###

import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    N = int(input())
    A = read_list()
    dp = [[[-10 ** 20 for _ in range(2)] for _ in range(N // 2 + 5)] for _ in range(N + 1)]

    dp[1][0][0] = 0
    dp[1][1][1] = A[0]
    for i in range(1, N):
        for k in range(max(0, i // 2 - 2), i // 2 + 2):
            dp[i + 1][k][0] = max(dp[i][k][1], dp[i][k][0])
            dp[i + 1][k + 1][1] = dp[i][k][0] + A[i]

    print(max(dp[N][N // 2]))


if __name__ == "__main__":
    main()


### FIXED CODE ###

import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    N = int(input())
    A = read_list()
    dp = [[-10 ** 20 for _ in range(2)] for _ in range(N // 2 + 5)] 

    dp[0][0] = 0
    dp[1][1] = A[0]
    for i in range(1, N):
        for k in range(i // 2 + 2, max(0, i // 2 - 2), -1):
            dp[k][0] = max(dp[k][1], dp[k][0])
            dp[k][1] = dp[k - 1][0] + A[i]

    print(max(dp[N // 2]))


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

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

### FIXED CODE ###

N = int(input())
biki = []
bise = {}
for i in range(N):
    S = input()
    biki.append(S)
bise=set(biki)
print(len(bise))
### BUGGY CODE ###

N = int(input())
str = input().split()
A = []
A.append(0)
for i in range(N):
    A.append(int(str[i]))
A.append(0)
SUM = 0
cnt = 0
buf = 0
for i in range(1,N+1):
    for j in range(1,N+1):
        if i == j:
            buf = A.pop(j)
            cnt = j
        SUM = SUM + abs(A[j] - A[j-1])
    A.insert(cnt,buf)
    print(SUM)
    SUM = 0

### FIXED CODE ###

N = int(input())
str = input().split()
A = []
A.append(0)
for i in range(N):
    A.append(int(str[i]))
A.append(0)
SUM = 0
distance = []

for i in range(1,N+2):
    distance.append(abs(A[i] - A[i-1]))
    SUM = SUM + abs(A[i]-A[i-1])

for i in range(1,N+1):
    print(SUM - distance[i] - distance[i-1] + abs(A[i+1] - A[i-1]))
### BUGGY CODE ###

import numpy as np

k = int(input())

a = 0

for i in range(1, k + 1):
    for l in range(1, k + 1):
        for m in range(1, k + 1):
            a += np.gcd.reduce([i, l, m])
print(a)


### FIXED CODE ###

import math
from functools import reduce

k = int(input())
a = 0

for i in range(1, k + 1):
    for l in range(1, k + 1):
        for m in range(1, k + 1):
            a += reduce(math.gcd, [i, l, m])
print(a)