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

from functools import lru_cache
import sys

sys.setrecursionlimit(10**5)

def solve(nums, s):
    @lru_cache(None)
    def dfs(i, k):
        if k < 0:
            return []
        if k == 0:
            return [i-1]
        if i >= n:
            return []
        if k == s:
            return dfs(i+1, k-nums[i])
        return dfs(i+1, k-nums[i]) + dfs(i+1, k)

    ans = 0
    n = len(nums)
    for i in range(n):
        for e in dfs(i, s):
            ans = (ans + (i+1)*(n-e)) % 998244353
    return ans


def main():
    n, s = map(int, input().split())
    nums = [int(c) for c in input().split()]
    print(solve(nums, s))


if __name__ == "__main__":
    main()



### FIXED CODE ###

import numpy as np

def main():
    n, s = map(int, input().split())
    nums = [int(c) for c in input().split()]
    mod = 998244353
    dp = np.zeros(s+1, dtype=np.int)
    ans = 0

    for i, num in enumerate(nums, 1):
        dp[0] = i
        if num <= s:
            dp[num:] = dp[num:] + dp[:-num]
            # print(dp)
        dp %= mod
        ans = (ans + dp[-1]) % mod
    print(ans)


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

S = input()
 
cnt = 0
S = S[::-1]
for i in range(0, len(S)-4):
    found_step = 0
    for j in range(i+5, len(S)+1):
        s = int(S[i+found_step:j][::-1])
        if s < 12114:
            continue
        elif s % 2019 == 0:
            found_step = j - i
            cnt += 1
print(cnt)


### FIXED CODE ###

S = input()
 
mods = [0 for _ in range(2019)]
mods[0] = 1
t = 0
mod10 = 1
for s in reversed(S):
    t += int(s) * mod10
    t = t % 2019
    mod10 *= 10
    mod10 %= 2019
    mods[t] += 1

cnt = sum([m*(m-1)/2 for m in mods])
print(int(cnt))
### BUGGY CODE ###

from collections import Counter

N = int(input())
C = tuple(map(lambda x: int(x)-1,input().split()))

adj = [list() for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    adj[a-1].append(b-1)
    adj[b-1].append(a-1)


parent = [None]*N
parent[0] = -1

stack = [0]
order = []
while stack:
    p = stack.pop()
    order.append(p)
    for c in adj[p]:
        if parent[c] is None:
            parent[c] = p
            stack.append(c)

dp = [Counter() for _ in range(N)] # color-wise counter
subtreesize = [0]*N
cnt = [N*(N+1)//2]*N

for c in reversed(order):
    p = parent[c]
    if p >= 0:
        dp[c][C[c]] = subtreesize[c]+1
        x = subtreesize[c]-dp[c][C[p]]+1
        cnt[C[p]] -= x*(x+1)//2
        subtreesize[p] += subtreesize[c]+1

        a,b = dp[p],dp[c]
        if len(a) > len(b):
            a += b
            dp[p] = a
        else:
            b += a
            dp[p] = b
        dp[c] = None

dp[0][C[0]] = subtreesize[0]+1
for c in range(N):
    x = subtreesize[0]-dp[0][c]+1
    cnt[c] -= x*(x+1)//2

print(*cnt, sep='\n')


### FIXED CODE ###

from collections import defaultdict
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

N = int(readline())
C = tuple(map(lambda x: int(x)-1, readline().split()))

temp = map(int,read().split())
temp = zip(temp,temp)

adj = [list() for _ in range(N)]
for a,b in temp:
    adj[a-1].append(b-1)
    adj[b-1].append(a-1)


parent = [None]*N
parent[0] = -1

stack = [0]
order = []
while stack:
    p = stack.pop()
    order.append(p)
    for c in adj[p]:
        if parent[c] is None:
            parent[c] = p
            stack.append(c)

def merge(a,b):
    if len(a) > len(b):
        a,b = b,a
    for k,v in a.items():
        b[k] += v
    return b

dp = [defaultdict(int) for _ in range(N)] # color-wise counter
subtreesize = [0]*N
cnt = [N*(N+1)//2]*N

for c in reversed(order):
    p = parent[c]
    if p >= 0:
        dp[c][C[c]] = subtreesize[c]+1
        x = subtreesize[c]-dp[c][C[p]]+1
        cnt[C[p]] -= x*(x+1)//2
        subtreesize[p] += subtreesize[c]+1

        dp[p] = merge(dp[c],dp[p])
        dp[c] = None

dp[0][C[0]] = subtreesize[0]+1
for c in range(N):
    x = subtreesize[0]-dp[0][c]+1
    cnt[c] -= x*(x+1)//2

print(*cnt, sep='\n')
### BUGGY CODE ###

import functools
import fractions

# 最大公約数
def gcd(m, n):
    r = m % n
    return gcd(n, r) if r else n

def gcd_list(nums):
    return functools.reduce(gcd, nums)

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

left = [0]
right = []
for i in range(N):
    tmp_left = A[:i+1]
    tmp_right = A[i:]
    left.append(gcd_list(tmp_left))
    right.append(gcd_list(tmp_right))
right += [0]
#print(left)
#print(right)

ans = 0
for i in range(N):
    ans = max(ans,fractions.gcd(left[i],right[i+1]))
print(ans)

### FIXED CODE ###

import fractions

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

left = [0]*(N+1)
right = [0]*(N+1)
for i in range(N):
    left[i+1] = (fractions.gcd(left[i],A[i]))
    right[N-i-1] = fractions.gcd(right[N-i],A[N-1-i])

ans = 0
for i in range(N):
    ans = max(ans,fractions.gcd(left[i],right[i+1]))
print(ans)
### BUGGY CODE ###

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

ans = 0
for i in range(A, B + 1):
    ans ^= i
print(ans)

### FIXED CODE ###

A, B = map(int, input().split())
digits = len(format(B, 'b'))
A -= 1
ans = 0
for k in range(digits):
    na = (A // (2 << k)) * (1 << k) + max(0, A % (2 << k) - (1 << k) + 1)
    nb = (B // (2 << k)) * (1 << k) + max(0, B % (2 << k) - (1 << k) + 1)
    x = (nb - na) % 2
    ans += x << k

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

#coding: utf-8
from math import ceil
R, G, B, N = map(int, input().split())
ans = 0
for r in range(ceil(N/R) + 1):
	for g in range(ceil(N/G) + 1):
		for b in range(ceil(N/B) + 1):
			if r * R + g * G + b * B == N:
				ans += 1
print(ans)

### FIXED CODE ###

#coding: utf-8
from math import ceil
R, G, B, N = map(int, input().split())
ans = 0
for r in list(range(ceil(N/R) + 1))[::-1]:
	for g in range(ceil(N/G) + 1):
		if (N - r*R - g*G) % B == 0 and N >= r*R + g*G:
			ans += 1
print(ans)
### BUGGY CODE ###

N,M = map(int, input().split())
l_table = [False for _ in range(N)]
lr_table = {}
for _ in range(M):
    l_n, r_n = map(int, input().split())
    l_table[l_n-1] = True
    lr_table[(l_n-1,r_n-1)] = True

ret = 0
lefts = []
for i in range(N):
    if lefts and any([(left,i) in lr_table and lr_table[(left,i)] for left in lefts]):
        # print(i,lefts)
        ret += 1
        lefts = []
    if l_table[i]:
        lefts.append(i)

print(ret)

### FIXED CODE ###

N,M = map(int, input().split())
r_table = [-1]*N
for _ in range(M):
    l_n, r_n = map(int, input().split())
    r_table[r_n-1] = max(l_n-1, r_table[r_n-1])

ret = 0
left = -1
for i in range(N):
    if left < r_table[i]:
        ret += 1
        left = i-1

print(ret)
### BUGGY CODE ###

n = int(input())
li = list(map(int,input().split()))
ans = 0
lgcd = [li[0]]
rgcd = [li[-1]]

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

for i in range(n-1):
    lgcd.append(gcd(lgcd[-1],li[i+1]))
    rgcd.insert(0,gcd(rgcd[0],li[-(i+2)]))

gcd_list = [lgcd[-2],rgcd[1]]

for i in range(n-2):
    gcd_list.append(gcd(lgcd[i],rgcd[i+2]))

print(max(gcd_list))


### FIXED CODE ###

n = int(input())
li = list(map(int,input().split()))
ans = 0
lgcd = [0]*n
rgcd = [0]*n
lgcd[0] = li[0]
rgcd[-1] = li[-1]

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

for i in range(n-1):
    lgcd[i+1] = gcd(lgcd[i],li[i+1])
    rgcd[-i-2] = gcd(rgcd[-i-1],li[-(i+2)])

gcd_list = [gcd(lgcd[i],rgcd[i+2]) for i in range(n-2)]

gcd_list.append(lgcd[-2])
gcd_list.append(rgcd[1])

print(max(gcd_list))
### BUGGY CODE ###

a, b, k = map(int, input().split())
for x in range(k):
    if a >= 1:
         a -= 1
    elif a == 0 and b >=1:
        b = b - 1
    elif a == 0 and b==0:
        pass
print(a, b)

### FIXED CODE ###

a, b, k = map(int, input().split())
if a + b >= k:
    if a > k:
        print(a-k,b)
    elif k >= a and a+b >= k:
        print(0,a + b -k)
else:
    print(0,0)
### BUGGY CODE ###

import heapq
def SME(start,end):
    count = 0
    ANS = [heapq.heappush(A,[x,i]) for i,x in enumerate(Whole)]
    for j in range(start,end):
        a = heapq.heappop(A)
        if None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] : continue
        else : 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()]
A = []
parameter = 0.98
ANS = [None]*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 ###



N=int(input())
A=[int(input()) for i in range(N)]
A=list(map(int,A))
i=0
while i < N:
    cont=A[i]
    del A[i]
    print(max(A))
    A.insert(i,cont)
    i += 1


### FIXED CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
B=sorted(A,reverse=True)
maxA=B[0]
secondA=B[1]
i=0
for i in range(N):
    if A[i] == maxA:
        print(secondA)
    else:
        print(maxA)
    i += 1
### BUGGY CODE ###

import sys,math,copy
# import numpy as np
input = sys.stdin.readline
S = ''.join(reversed(input().strip()))

# dp = np.zeros((13), dtype=int)
# dp_ = np.zeros((13), dtype=int)
dp = [0] * 13
dp_ = [0] * 13
mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
list10 = list(range(10))
list13 = list(range(13))
divisor = 10 ** 9 + 7
dp_[0] = 1
mul = 1
for s in S:
    if s == '?':
        for d in list10:
            m = mod13_list[(d * mul)]
            for pm in list13:
                dp[mod13_list[(pm+m)]] += dp_[pm]

    else:
        si = int(s)
        m = mod13_list[(si * mul)]
        for pm in list13:
            dp[mod13_list[(pm+m)]] = dp_[pm]

    # dp_ = dp % divisor
    # dp = dp * 0 # np.zeros((13), dtype=int)
    for i in list13:
        dp_[i] = dp[i] % divisor
        dp[i] = 0
    mul = mod13_list[(mul * 10)]
print(dp_[5])

### FIXED CODE ###

import sys,math,copy

def main():
    # import numpy as np
    input = sys.stdin.readline
    S = ''.join(reversed(input().strip()))

    # dp = np.zeros((13), dtype=int)
    # dp_ = np.zeros((13), dtype=int)
    dp = [0] * 13
    dp_ = [0] * 13
    mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
    list10 = list(range(10))
    list13 = list(range(13))
    divisor = 10 ** 9 + 7
    dp_[0] = 1
    mul = 1
    for i in range(len(S)):
        s = S[i]
        if s == '?':
            for d in list10:
                m = mod13_list[(d * mul)]
                for pm in list13:
                    dp[mod13_list[(pm+m)]] += dp_[pm]

        else:
            si = int(s)
            m = mod13_list[(si * mul)]
            for pm in list13:
                dp[mod13_list[(pm+m)]] = dp_[pm]

        # dp_ = dp % divisor
        # dp = dp * 0 # np.zeros((13), dtype=int)
        for j in list13:
            dp_[j] = dp[j] % divisor
            dp[j] = 0
        mul = mod13_list[(mul * 10)]
    print(dp_[5])

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

from collections import Counter
n = int(input())
s = []
for i in range(n):
    s.append(input())
"""
def func(seq):
    seen = []
    list2 = [x for x in seq if x not in seen and not seen.append(x)]
    return len(list2)
"""
count = 0
list1 = []
for i in range(n):
    list1.append(Counter(s[i]))
for i in range(n-1):
    for j in range(i+1,n):
        if list1[i] == list1[j] and i != j:
            count += 1
print(count)


### FIXED CODE ###

from functools import lru_cache
import sys
sys.setrecursionlimit(1000000)
n = int(input())
list1 = [''.join(sorted(input())) for i in range(n)]
dict1 = dict()
cout = 0
@lru_cache(maxsize = None)
def func(s):
	if s == 2:
		return 1 #2個の場合は1パターン
	return s-1 + func(s-1)

for i in range(n):
	if list1[i] in dict1:
		dict1[list1[i]] += 1
	else:
		dict1[list1[i]] = 1

for i in dict1:
	if dict1[i] != 1:
		cout += func(dict1[i])

print(cout)
### BUGGY CODE ###

#055 B
N = int(input())
ans =1
for i in range(1,N+1):
    if N ==1:
        print(1%((10**9)+7))
        exit()
    else:
        ans =ans * i
print(ans%((10**9)+7))

### FIXED CODE ###

#055 B
N=int(input())
ans = 1
w = (10**9) +7
for i in range(1,N+1):
    ans *=i
    if ans >=w:
        ans %= w
print(ans)
### BUGGY CODE ###

N = int(input())

S = {}

for i in range(N):
  word = input()
  if word in S:
  	S[word] += 1
  else:
    S[word] = 1
    
max_S = [kv[0] for kv in S.items() if kv[1] == max(S.values())]

max_S.sort()
for out in max_S:
  print(out)

### FIXED CODE ###

N = int(input())
 
S = {}
max = 0
 
for i in range(N):
  word = input()
  if word in S:
  	S[word] += 1
  else:
    S[word] = 1
  if S[word] > max:
    S_list = []
    max = S[word]
    S_list.append(word)
  elif S[word] == max:
    S_list.append(word)
    
S_list.sort()
for out in S_list:
  print(out)
### BUGGY CODE ###

size, jumps = map(int, input().split())
array = list(map(int, input().split()))
dp = [999999999] * size
dp[0]= 0
dp[1] = abs(array[0] - array[1])
for i in range(size):
    for j in range(i+1,1+i+jumps):
        if j < size:
            dp[j] = min(dp[j], dp[i]+abs(array[i] - array[j]))
print(dp[size-1])


### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


def main():
    size, jumps = map(int, input().split())
    array = list(map(int, input().split()))
    dp = [999999999] * size
    dp[0]= 0
    dp[1] = abs(array[0]- array[1])
    for i in range(2,size):
        dp[i] = min(abs(array[i] - array[j]) + dp[j] for j in range(max(0, i - jumps), i))
    print(dp[size-1])

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

n, *bc = map(int, open(0).read().split())
a = [bc.pop(0) for _ in range(n)]
q = bc.pop(0)

d = {}
for x in a:
    if x in d:
        d[x] += 1
    else:
        d[x] = 1
for i in range(0, min(q*2, len(bc)), 2):
    b = bc[i]
    c = bc[i+1]
    if b in d:
        if c in d:
            d[c] += d.pop(b)
        else:
            d[c] = d.pop(b)
    ret = sum([k * v for k, v in d.items()])
    print(ret)

### FIXED CODE ###

n, r = open(0).read().split(maxsplit=1)
n = int(n)
*a, r = r.split(maxsplit=n)
a = list(map(int, a))
q, *bc = map(int, r.split())

d = {}
for x in a:
    if x in d:
        d[x] += 1
    else:
        d[x] = 1
ret = sum(a)
for i in range(0, min(q*2, len(bc)), 2):
    b = bc[i]
    c = bc[i+1]
    if b in d:
        v = d.pop(b)
        if c in d:
            d[c] += v
        else:
            d[c] = v
        ret += c * v - b * v
    #ret = sum([k * v for k, v in d.items()])
    print(ret)
### BUGGY CODE ###

n, *x = map(int, open(0).read().split())
y = sorted(x)[::-1]
cnt = 0
for i in range(n - 2):
    a = y[i]
    for j in range(i + 1, n - 1):
        b = y[j]
        c = j + 1
        while c < n and a < b + y[c]:
            cnt += 1
            c += 1
print(cnt)


### FIXED CODE ###

import bisect
N = int(input())
L = sorted(list(map(int, input().split())))
cnt = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        a = L[i]
        b = L[j]
        v = bisect.bisect_left(L, a + b)
        cnt += v - j - 1
print(cnt)
### BUGGY CODE ###

from queue import Queue
import sys

inf = float("inf")

class Node:
    def __init__(self):
        self.to = []
        self.cost = []
        self.value = inf
        self.done = False

    def __str__(self):
        return "to = {0}, cost = {1}, value = {2}".format(self.to, self.cost, self.value)

N, M = list(map(int, input().split()))
I = [Node() for x in range(N+1)]

for i in range(M):
    l, r, d = list(map(int, input().split()))
    I[l].to.append(r)
    I[l].cost.append(d)
    I[r].to.append(l)
    I[r].cost.append(-d)

for i in I:
    if i.done: continue
    
    i.value = 0
    q = Queue()
    q.put(i)
    while not q.empty():
        tmp = q.get()
        for j in range(len(tmp.to)):
            nxt = I[tmp.to[j]]
            nxt_val = tmp.value + tmp.cost[j]
            if nxt.done:
                if nxt.value == nxt_val: continue
                print("No")
                sys.exit()
            nxt.value = nxt_val
            nxt.done = True
            q.put(nxt)
print("Yes")

### FIXED CODE ###

from queue import Queue
import sys

inf = float("inf")
N, M = list(map(int, input().split()))
dist = [[] for x in range(N+1)]
value = [inf for x in range(N+1)]

for i in range(M):
    l, r, d = list(map(int, input().split()))
    dist[l].append((r, d))
    dist[r].append((l, -d))

for i in range(1, N+1):
    if value[i] != inf: continue
    
    value[i] = 0
    q = Queue()
    q.put(i)
    while not q.empty():
        tmp = q.get()
        for x in dist[tmp]:
            nxt = x[0]
            nxt_val = value[tmp] + x[1]
            if value[nxt] != inf:
                if value[nxt] == nxt_val: continue
                print("No")
                sys.exit()
            value[nxt] = nxt_val
            q.put(nxt)
print("Yes")
### BUGGY CODE ###

import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input
N = int(input())

A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

dp = [0] * (N+1)
for a, b in ((a, b) for a, b in zip(A, B) if a < b):
    for w in range(a, N+1):
        dp[w] = max(dp[w], dp[w-a] + b-a)

M = max(dp) + N
dp = [0] * (M+1)
for a, b in ((a, b) for a, b in zip(A, B) if a > b):
    for w in range(b, M+1):
        dp[w] = max(dp[w], dp[w-b] + a-b)

print(max(dp) + M)


### FIXED CODE ###

import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input
N = int(input())

A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

dp = [0] * (N+1)
for a, b in ((a, b) for a, b in zip(A, B) if a < b):
    for w in range(a, N+1):
        dp[w] = max(dp[w], dp[w-a] + b-a)

M = max(dp) + N
dp = [0] * (M+1)
for a, b in ((a, b) for a, b in zip(A, B) if a > b):
    for w in range(b, M+1):
        dp[w] = max(dp[w], dp[w-b] + a-b)

print(max(dp) + M)
### BUGGY CODE ###

from collections import deque

d = deque(list(input()))
for _ in range(int(input())):
    a = input()
    if a[0] == '1':
        d.reverse()
    elif a[2] == '1':
        d.appendleft(a[4])
    else:
        d.append(a[4])
print(*d, sep='')


### FIXED CODE ###

from collections import deque

d = deque(list(input()))
flag = 1
for _ in range(int(input())):
    a = input()
    if a[0] == '1':
        flag *= -1
    elif a[2] == '1' and flag == 1:
        d.appendleft(a[4])
    elif a[2] == '1' and flag == -1:
        d.append(a[4])
    elif a[2] == '2' and flag == 1:
        d.append(a[4])
    else:
        d.appendleft(a[4])
if flag == -1:
    d.reverse()
print(*d, sep='')
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from math import atan, tan, pi

a, b, x = map(int, readline().split())


def max_v(si):
    si = si / 180 * pi
    if si < atan(b / a):
        area = a * b - a ** 2 * tan(si) / 2
    else:
        area = b * (b / tan(si) / 2)
    return area * a


low = 0
high = 90
while high - low > 1e-7:
    mid = (low + high) // 2
    if max_v(mid) <= x:
        high = mid
    else:
        low = mid
print((high + low) / 2)


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from math import atan, tan, pi

a, b, x = map(int, readline().split())


def max_v(si):
    si = si / 180 * pi
    if si < atan(b / a):
        area = a * b - a ** 2 * tan(si) / 2
    else:
        area = b * (b / tan(si) / 2)
    return area * a


low = 0
high = 90
while high - low > 1e-7:
    mid = (low + high) / 2
    if max_v(mid) <= x:
        high = mid
    else:
        low = mid
print((high + low) / 2)
### BUGGY CODE ###

from collections import deque

H, W = map(lambda x: int(x)+4, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())

grid = '#' * W * 2
for _ in range(H-4):
  grid += '##' + input() + '##'
grid += '#' * W * 2

magic_list = []
for i in range(5):
  for j in range(5):
    if (i, j) in [(2, 2), (1, 2), (2, 1), (2, 3), (3, 2)]:
      continue
    else:
      magic_list.append(i-2 + W*(j-2))

move_list = [-1, 1, W, -W]

def bfs(start):
  INF = 10 ** 9
  dist = [INF] * (H*W)
  dist[start] = 0
  q = deque([start])
  while q:
    v = q.popleft()
    dv = dist[v]
    for move in move_list:
      w = v + move
      if grid[w] == '#':
        continue
      dw = dv
      if dw >= dist[w]:
        continue
      dist[w] = dw
      q.appendleft(w)
    for magic in magic_list:
      w = v + magic
      if grid[w] == '#':
        continue
      dw = dv + 1
      if dw >= dist[w]:
        continue
      dist[w] = dw
      q.append(w)
  return dist

ans = bfs( (Ch+1)*W + Cw+1 )[(Dh+1)*W + Dw+1]

if ans == 10**9:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

from collections import deque

H, W = map(lambda x: int(x)+4, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())

grid = '#' * W * 2
for _ in range(H-4):
  grid += '##' + input() + '##'
grid += '#' * W * 2

magic_list = []
for i in range(5):
  for j in range(5):
    if (i, j) in [(2, 2), (1, 2), (2, 1), (2, 3), (3, 2)]:
      continue
    else:
      magic_list.append(i-2 + W*(j-2))

move_list = [-1, 1, W, -W]

def bfs(start):
  INF = 10 ** 9
  dist = [INF] * (H*W)
  dist[start] = 0
  q = deque([start])
  while q:
    v = q.popleft()
    dv = dist[v]
    for move in move_list:
      w = v + move
      if grid[w] == '#':
        continue
      dw = dv
      if dw >= dist[w]:
        continue
      dist[w] = dw
      q.appendleft(w)
    for magic in magic_list:
      w = v + magic
      if grid[w] == '#':
        continue
      dw = dv + 1
      if dw >= dist[w]:
        continue
      dist[w] = dw
      q.append(w)
  return dist

ans = bfs( (Ch+1)*W + Cw+1 )[(Dh+1)*W + Dw+1]

if ans == 10**9:
  print(-1)
else:
  print(ans)
### BUGGY CODE ###

INF = -1000000000000001

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

a = int(n/2)

dpa = [[INF]*(a+1) for i in range(n+1)]

dpa[0][0] = 0
dpa[1][0] = 0
dpa[1][1] = l[0]
for i in range(2,n+1):
	if i % 2 == 0:
		j = int(i / 2)
		dpa[i][j] = max(dpa[i-2][j-1]+l[i-1],dpa[i-1][j])
#		print(i,j,dpa[i][j])
	else:
		j = int((i-1)/2)
		dpa[i][j] = max(dpa[i-2][j-1]+l[i-1],dpa[i-1][j])
#		print(i,j,dpa[i][j])
		if (i != n):
			j += 1
#			print(i,j,dpa[i][j])
#			print("   ",i-2,j-1,dpa[i-2][j-1],"")
			dpa[i][j] = dpa[i-2][j-1]+l[i-1]

#print(dpa)
print(dpa[n][a])

### FIXED CODE ###

from collections import defaultdict
INF = -1000000000000001

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

a = int(n/2)

dpa = defaultdict(lambda: -INF)
#dpa = [[0 for j in range(a+1)] for i in range(n+1)]

dpa[(0,0)] = 0
dpa[(1,0)] = 0
dpa[(1,1)] = l[0]
j = 1
for i in range(2,n+1):
	if i == j*2:
		dpa[(i,j)] = max(dpa[(i-2,j-1)]+l[i-1],dpa[(i-1,j)])
#		print(i,j,dpa[(i,j)])
	else:
		dpa[(i,j)] = max(dpa[(i-2,j-1)]+l[i-1],dpa[(i-1,j)])
#		print(i,j,dpa[(i,j)])
		if (i != n):
			j += 1
#			print(i,j,dpa[(i,j)])
#			print("   ",i-2,j-1,dpa[(i-2,j-1)],"")
			dpa[(i,j)] = dpa[(i-2,j-1)]+l[i-1]

#print(dpa)
print(dpa[n,a])