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

from collections import deque
h, w = list(map(int, input().split()))

s = []
for i in range(h):
    line = input()
    s.append(line)

ans = []
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue

        for k in range(i, h):
            for l in range(w):
                if s[k][l] == '#' or i == k and j == l or k <= i and l <= j:
                    continue
                start = (i, j)
                goal = (k, l)
                d = [[1<<10 for x in range(w)] for y in range(h)]

                stack = deque([])
                stack.append((start[0], start[1]))
                d[start[0]][start[1]] = 0
                while stack:
                    y, x = stack.popleft()
                    if y == goal[0] and x == goal[1]:
                        break
                    if y > 0 and s[y-1][x] == '.' and d[y-1][x] > d[y][x]+1:
                        d[y-1][x] = d[y][x] + 1
                        stack.append((y-1, x))
                    if x < w-1 and s[y][x+1] == '.' and d[y][x+1] > d[y][x]+1:
                        d[y][x+1] = d[y][x] + 1
                        stack.append((y, x+1))
                    if y < h-1 and s[y+1][x] == '.' and d[y+1][x] > d[y][x]+1:
                        d[y+1][x] = d[y][x] + 1
                        stack.append((y+1, x))
                    if x > 0 and s[y][x-1] == '.' and d[y][x-1] > d[y][x]+1:
                        d[y][x-1] = d[y][x] + 1
                        stack.append((y, x-1))
                ans.append(d[goal[0]][goal[1]])
ans.sort()
print(ans[-1])


### FIXED CODE ###

import collections
h, w = list(map(int, input().split()))

s = []
for i in range(h):
    line = input()
    s.append(line)

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue
        d = [[False for x in range(w)] for y in range(h)]

        stack = collections.deque()
        stack.append((i, j, 0))
        d[i][j] = True
        while stack:
            y, x, score = stack.popleft()
            if y > 0 and s[y-1][x] == '.' and not d[y-1][x]:
                stack.append((y-1, x, score+1))
                d[y-1][x] = True
            if x < w-1 and s[y][x+1] == '.' and not d[y][x+1]:
                stack.append((y, x+1, score+1))
                d[y][x+1] = True
            if y < h-1 and s[y+1][x] == '.' and not d[y+1][x]:
                stack.append((y+1, x, score+1))
                d[y+1][x] = True
            if x > 0 and s[y][x-1] == '.' and not d[y][x-1]:
                stack.append((y, x-1, score+1))
                d[y][x-1] = True
            if score > ans:
                ans = score
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n, m = [int(item) for item in input().split()]
if m % 2 != 0:
    print(-1)
    exit()
visited_e = [False] * m
edge = [[] for _ in range(n)]
for i in range(m):
    a, b = [int(item) for item in input().split()]
    a -= 1; b -= 1
    edge[a].append([b, i])
    edge[b].append([a, i])
 
ans = []
def dfs(prev, n):
    child_num = 0
    for v, index in edge[n]:
        if prev == v:
            continue
        if visited_e[index]:
            continue
        visited_e[index] = True
        if dfs(n, v) == 1:
            child_num += 1
            ans.append([n+1, v+1])
    if child_num % 2 == 0:
        return 1
    else:
        ans.append([n+1, prev+1])
        return 0
 
dfs(-1, 0)
print("\n".join([str(f) + " " + str(t) for f, t in ans]))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n, m = [int(item) for item in input().split()]
if m % 2 != 0:
    print(-1)
    exit()
visited_e = [False] * m
visited_v = [False] * n
edge = [[] for _ in range(n)]
for i in range(m):
    a, b = [int(item) for item in input().split()]
    a -= 1; b -= 1
    edge[a].append([b, i])
    edge[b].append([a, i])
 
ans = []
def dfs(prev, n):
    if visited_v[n]:
        return 1
    visited_v[n] = True
    child_num = 0
    for v, index in edge[n]:
        if visited_e[index]:
            continue
        visited_e[index] = True
        if dfs(n, v) == 1:
            child_num += 1
            ans.append([n+1, v+1])
    if child_num % 2 == 0:
        return 1
    else:
        ans.append([n+1, prev+1])
        return 0
 
dfs(-1, 0)
print("\n".join([str(f) + " " + str(t) for f, t in ans]))
### BUGGY CODE ###

import sys

readline = sys.stdin.buffer.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

def solve():
  s = list(ns())
  ls = len(s)
  lk = ni()
  dp = [[[0]*ls for _ in range(ls)] for i in range(2)]
  ans = 0
  for i in range(ls):
    dp[0][i][i] = 1
  for k in range(lk+1):
    v = k & 1
    for dis in range(1, ls):
      for i in range(ls - dis):
        j = i + dis
        dp[v][i][j] = 0
        if s[i] == s[j]:
          dp[v][i][j] = dp[v][i+1][j-1] + 2
        elif k:
          dp[v][i][j] = dp[v^1][i+1][j-1] + 2
        dp[v][i][j] = max(dp[v][i][j], dp[v][i+1][j], dp[v][i][j-1])
    ans = max(ans, dp[v][0][-1])

  print(ans)
  return

solve()

### FIXED CODE ###

import sys

readline = sys.stdin.buffer.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

def solve():
  s = list(ns())
  ls = len(s)
  lk = ni()
  dp = [[[0]*ls for _ in range(ls)] for i in range(2)]
  ans = 0
  for i in range(ls):
    dp[0][i][i] = 1
  for k in range(lk+1):
    v = k & 1
    for dis in range(1, ls):
      for i in range(ls - dis):
        j = i + dis
        dp[v][i][j] = 0
        if s[i] == s[j]:
          dp[v][i][j] = dp[v][i+1][j-1] + 2
        elif k:
          dp[v][i][j] = dp[v^1][i+1][j-1] + 2
        dp[v][i][j] = max(dp[v][i][j], dp[v][i+1][j], dp[v][i][j-1])
    ans = max(ans, dp[v][0][-1])

  print(ans)
  return

solve()
### BUGGY CODE ###

a,b=map(int,input().split())
c=1
for i in range(a,b+1):
    if i==0:
        print('Zero')
        exit()
    c*=i

if c>0:
    print('Positive')
else:
    print('Negative')


### FIXED CODE ###

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

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

n += 5

sa = set(a)
sb = set(b)

count = [0] * n
counta = [0] * n
countb = [0] * n
for v in a:
    count[v] += 1
    counta[v] += 1
for v in b:
    count[v] += 1
    countb[v] += 1

outA = dict()
for v in a:
    outA[v] = []

import heapq
q = []
for v in range(n):
    heapq.heappush(q,(-count[v],v))
    
while q[0][0] < 0:
    c, v = heapq.heappop(q)
    if count[v] + c:
        heapq.heappush(q,(-count[v],v))
        continue
    if counta[v]:
        for v2 in sb:
            if v2 != v:
                break
        else:
            print('No')
            exit()
        outA[v].append(v2)
        count[v] -= 1
        count[v2] -= 1
        counta[v] -= 1
        countb[v2] -= 1
        if counta[v] == 0:
            sa.remove(v)
        if countb[v2] == 0:
            sb.remove(v2)
    else:
        for v2 in sa:
            if v2 != v:
                break
        else:
            print('No')
            exit()
        outA[v2].append(v)
        count[v] -= 1
        count[v2] -= 1
        counta[v2] -= 1
        countb[v] -= 1
        if counta[v2] == 0:
            sa.remove(v2)
        if countb[v] == 0:
            sb.remove(v)
    heapq.heappush(q, (-count[v], v))

out = []
for v in a:
    out.append(outA[v].pop())
print('Yes')
print(' '.join(map(str,out)))


### FIXED CODE ###

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

sa = set(a)
sb = set(b)

count = [0] * (n + 1)
counta = [0] * (n + 1)
countb = [0] * (n + 1)

for v in a:
    count[v] += 1
    counta[v] += 1
for v in b:
    count[v] += 1
    countb[v] += 1

for v in count:
    if v > n:
        print('No')
        exit()

outA = dict()
for v in a:
    outA[v] = []

import heapq
q = []
for v in range(n + 1):
    if count[v]:
        heapq.heappush(q,(-count[v],v))
    
while q[0][0] < 0:
    c, v = heapq.heappop(q)
    if count[v] + c:
        heapq.heappush(q,(-count[v],v))
        continue
    if counta[v]:
        for v2 in sb:
            if v2 != v:
                break
        else:
            print('No')
            exit()
        outA[v].append(v2)
        count[v] -= 1
        count[v2] -= 1
        counta[v] -= 1
        countb[v2] -= 1
        if counta[v] == 0:
            sa.remove(v)
        if countb[v2] == 0:
            sb.remove(v2)
    else:
        for v2 in sa:
            if v2 != v:
                break
        else:
            print('No')
            exit()
        outA[v2].append(v)
        count[v] -= 1
        count[v2] -= 1
        counta[v2] -= 1
        countb[v] -= 1
        if counta[v2] == 0:
            sa.remove(v2)
        if countb[v] == 0:
            sb.remove(v)
    if count[v]:
        heapq.heappush(q, (-count[v], v))

out = []
for v in a:
    out.append(outA[v].pop())
print('Yes')
print(' '.join(map(str,out)))
### BUGGY CODE ###

def wa(a,x,y):
    S = 0
    for i in range(x,y+1):
        S = S + a[i]
    return S

n = int(input())
while n != 0:
    a = []
    for i in range(n):
        a.append(int(input()))
    ans = a[0]
    for i in range(n):
        for j in range(i+1,n):
            ans = max(wa(a,i,j),ans)
    print(ans)
    n = int(input())



### FIXED CODE ###

import math

def sign(x):
    if x >= 0:
        return True
    else:
        return False

n = int(input())
while n != 0:
    a = []
    for i in range(n):
        a.append(int(input()))
    b = []
    b.append(a[0])
    for i in range(1,len(a)):
        if b[len(b)-1] > 0 and a[i] > 0:
            b[len(b)-1] = b[len(b)-1] + a[i]
        else:
            b.append(a[i])

    ans = b[0]
    for i in range(len(b)):
        S = 0
        for j in range(i,len(b)):
            S = S + b[j]
            ans = max(S, ans)
    print(ans)
    n = int(input())
### BUGGY CODE ###

N = int(input())
S = input()
dp = [[0]*N for _ in range(N)]
ans = 0
for i in range(N-1,0,-1):
    for j in range(i-1,-1,-1):
        if S[i] == S[j]:
            if i < N-1 and j < i-1:
                dp[i][j] = min(dp[i+1][j+1]+1, i-j)
            else:
                dp[i][j] = 1
        ans = max(ans, dp[i][j])
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
dp = [[0]*N for _ in range(N)]
ans = 0
for i in range(N-1,0,-1):
    for j in range(i-1,-1,-1):
        if S[i] == S[j]:
            if i < N-1 and j < i-1:
                dp[i][j] = min(dp[i+1][j+1]+1, i-j)
            else:
                dp[i][j] = 1
        ans = max(ans, dp[i][j])
print(ans)
### BUGGY CODE ###

def main():
  import sys
  input = sys.stdin.readline
  N=int(input())
  A=list(map(int,input().split()))
  def lcm(a,N):
      from fractions import gcd
      x = a[0]
      y=  a[N//2]
      for i in range(1, N//2):
          x = (x * a[i]) // gcd(x, a[i])
          y = (y * a[i+N//2]) // gcd(y, a[i+N//2])
      y = (y * a[-1]) // gcd(y, a[-1])
      return (x*y)//gcd(x,y)
  z=lcm(A,N)
  MOD=10**9+7
  ans=0
  for i in range(N):
    ans+=z//A[i]%MOD
  print(ans%MOD)
  
if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  MOD=10**9+7
  N=int(input())
  A=list(map(int,input().split()))
  def lcm(a,N):
      from fractions import gcd
      x = a[0]
      y=  a[N//2]
      for i in range(1, N//2):
          x = (x * a[i]) // gcd(x, a[i])
          y = (y * a[i+N//2]) // gcd(y, a[i+N//2])
      y = (y * a[-1]) // gcd(y, a[-1])
      return (x*y)//gcd(x,y)
  z=lcm(A,N)
  ans=0
  for i in range(N):
    ans+=z//A[i]
  print(ans%MOD)
  
if __name__=='__main__':
  main()
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
n = int(input())
a = list(map(int,input().split()))
ans = 0
mod = (10**9 +7)
for j in range(61):# 2**j 桁に対して1なものの数を求める
    num_one = 0
    for i in range(len(a)):
        if a[i] & 2**j: 
            num_one += 1
    #print(j,num_one)
    ans += (2**j % mod) * (n-num_one)*(num_one) % mod
    #print(ans)
print(ans%mod)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
n = int(input())
a = list(map(int,input().split()))
ans = 0
mod = (10**9 +7)
for j in range(61):# 2**j 桁に対して1なものの数を求める
    num_one = 0
    for i in range(len(a)):
        if a[i] & 2**j: 
            num_one += 1
    #print(j,num_one)
    ans += (2**j % mod) * (n-num_one)*(num_one) % mod
    #print(ans)
print(ans%mod)
### BUGGY CODE ###

S = input()
q = int(input())
Q = list()
for i in range(q):
    Q.append(list(map(str, input().split())))

flag = False
for i in range(q):
    if Q[i][0] == '1':
        flag = not flag
    elif (Q[i][1] == '1' and flag) or (Q[i][1] == '2' and not flag):
        S += Q[i][2]
    else:
        S = Q[i][2] + S

print(S[::-1] if flag else S)


### FIXED CODE ###

from collections import deque

S = deque(input())
Q = int(input())

flag = False
for _ in range(Q):
    q = input()
    if q[0] == '1':
        flag = not flag
    else:
        _, f, c = q.split()
        if flag:
            if f == '2':
                S.appendleft(c)
            else:
                S.append(c)
        else:
            if f == '1':
                S.appendleft(c)
            else:
                S.append(c)

if flag:
    S.reverse()
print(''.join(S))
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-



import numpy as np


H, W, D = map(int, input().split())

A = []

for i in range(H):
    A.append(list(map(int, input().split())))

A = np.array(A)

Q = int(input())

for i in range(Q):
    L, R = map(int, input().split())
    cost = 0
    start = False
    while L != R:
        start = np.where(A==L) if start == False else start
        stop  = np.where(A==L+D)
        cost += abs(start[0][0] - stop[0][0]) + abs(abs(start[1][0] - stop[1][0]))
        start = stop
        L += D
    print(cost, flush=True)


### FIXED CODE ###

# speed-test
# https://abc089.contest.atcoder.jp/submissions/2206669

h,w,d = map(int,input().split())
 
dic = {}
for i in range(h):
    a = input().split()
    for j in range(w):
        dic[int(a[j])] = (i+1,j+1)
        
q = int(input())
c = [0]*(h*w+1)
for i in range(d+1,h*w+1):
    pi,pj = dic[i]; qi,qj = dic[i-d]
    c[i] = c[i-d] + abs(pi-qi) + abs(pj-qj)
    
for i in range(q):
    l,r = map(int,input().split())
    print(c[r]-c[l])
### BUGGY CODE ###

from fractions import gcd

def main():
    A, B = [int(i) for i in input().split()]
    G = gcd(A, B)
    factor = set()
    i = 2
    while G > 1:
        while True:
            if G % i == 0:
                factor.add(i)
                G = G // i
            else:
                break
        i += 1
    print(len(list(factor))+1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from fractions import gcd
import copy


def coprime2(a, b):
    return gcd(a, b) == 1


def main():
    A, B = [int(i) for i in input().split()]

    A_l = divisor(A)
    B_l = divisor(B)
    AB_l = set()
    for a in A_l:
        if a in B_l:
            AB_l.add(a)
    AB_l = sorted(list(AB_l))
    tmp = set(AB_l)
    ans = []
    for i, a in enumerate(AB_l):
        if a not in tmp:
            continue
        try:
            tmp.remove(a)
        except:
            pass
        for b in list(tmp):
            if gcd(a, b) != 1:
                try:
                    tmp.remove(b)
                except:
                    pass
        else:
            ans.append(a)

    print(len(ans))


def divisor(n):
    i = 1
    table = set()
    while i * i <= n:
        if n % i == 0:
            table.add(i)
            table.add(n//i)
        i += 1
    return table


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

N,K=map(int,input().split())
h=list(map(int,input().split()))
DP=[1000000000]*N
DP[0]=0
for i in range(1,N):
  #j=1
  #while j<=K and j<=i:
  #  DP[i]=min(DP[i],abs(h[i]-h[i-j])+DP[i-j])
  #for j in range(max(0, i-K),i):
    #DP[i]=min(DP[i],abs(h[i]-h[j])+DP[j])
  DP[i]=min([abs(h[i]-h[j])+DP[j] for j in range(max(0, i-K),i)])
print(DP[-1])




### FIXED CODE ###

def main():
  #import sys
  #input = sys.stdin.readline
  N,K=map(int,input().split())
  h=list(map(int,input().split()))
  DP=[0]*N
  DP[0]=0
  for i in range(1,N):
  #j=1
  #while j<=K and j<=i:
  #  DP[i]=min(DP[i],abs(h[i]-h[i-j])+DP[i-j])
  #for j in range(max(0, i-K),i):
    #DP[i]=min(DP[i],abs(h[i]-h[j])+DP[j])
    r=max(0, i-K)
    DP[i]=min([abs(h[i]-h[j])+DP[j] for j in range(r,i)])
  print(DP[-1])
if __name__ == '__main__':
  main()
### BUGGY CODE ###

import numpy as np

if __name__ == '__main__':
	N = int(input())
	dam = np.array(list(map(int, input().split())))
	
	index_ = np.array([1 if i % 2 == 0 else -1 for i in range(N)])
	ans = []
	for i in range(N):
		ans.append(str(np.dot(dam, index_)))
		index_ = np.roll(index_, 1)
	
	print(' '.join(ans))


### FIXED CODE ###

import numpy as np

if __name__ == '__main__':
	N = int(input())
	dam = np.array(list(map(int, input().split())))
	
	index_ = np.array([1 if i % 2 == 0 else -1 for i in range(N)])
	ans = [int(np.dot(dam, index_))]
	for i in range(N-1):
		ans.append(2 * (dam[i] - ans[i]//2))
	ans = [str(i) for i in ans]
	print(' '.join(ans))
### BUGGY CODE ###

N = int(input())
L = []
D = {}
for _ in range(N):
    x = input()
    L.append(x)

for x in L:
    D[x] = 0
    
for x in L:
    D[x] += 1

max_k_list = [kv[0] for kv in D.items() if kv[1] == max(D.values())]
print("\n".join(sorted(max_k_list)))


### FIXED CODE ###

N = int(input())
L = []
D = {}
for _ in range(N):
    x = input()
    L.append(x)

for x in L:
    D[x] = 0
    
for x in L:
    D[x] += 1

SortD = sorted(D.items(), key=lambda x:x[1])
maxD = SortD[-1][1]
ans = []
for x in reversed(SortD):
    if x[1] == maxD:
        ans.append(x[0])
    else:
        break
for x in sorted(ans):
    print(x)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
a = [0] + a
c = [1]

while c.count(c[-1]) == 1:
    c.append(a[c[-1]])

t = c.index(c[-1])
if k <= t:
    ans = c[k]
else:
    ans = c[t + ((k-t) % (len(c)-1-t))]

print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
a = [0] + a
c = [1]
x = True
y = [1, 1] + [0]*(n-1)

while x:
    c.append(a[c[-1]])
    y[c[-1]] += 1
    if y[c[-1]] == 2:
        x = False

t = c.index(c[-1])
if k <= t:
    ans = c[k]
else:
    ans = c[t + ((k-t) % (len(c)-1-t))]

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

from sys import stdin, gettrace
import sys
sys.setrecursionlimit(100000)
if not gettrace():
    def input():
        return next(stdin)[:-1]
 
 
# def input():
#    return stdin.buffer.readline()

def recursion(s1,s2,i,j,n1,n2,dp):
    if i>=n1 or j>=n2:
        return ""   
    if s1[i]==s2[j]:
        if dp[i+1][j+1]==-1:
            string=recursion(s1,s2,i+1,j+1,n1,n2,dp)
            dp[i+1][j+1]=string
        else:
            string=dp[i+1][j+1]
        return s1[i]+string
    else:
        if dp[i+1][j]==-1:
            x=recursion(s1,s2,i+1,j,n1,n2,dp)
            dp[i+1][j]=x
        else:
            x=dp[i+1][j]
        if dp[i][j+1]==-1:
            y=recursion(s1,s2,i,j+1,n1,n2,dp)
            dp[i][j+1]=y
        else:
            y=dp[i][j+1]
        if len(x)>len(y):
            return x
        else:
            return y

def main():
    s1=input()
    s2=input()
    n1,n2=len(s1),len(s2)
    dp=[[-1 for j in range(n2+1)] for i in range(n1+1)]
    print(recursion(s1,s2,0,0,len(s1),len(s2),dp))
 
 
if __name__ == "__main__":
    main()

### FIXED CODE ###

s1=input()
s2=input()
n1,n2=len(s1),len(s2)
dp=[[-1 for j in range(n2+1)] for i in range(n1+1)]
for i in range(n1,-1,-1):
    for j in range(n2,-1,-1):
        if i==n1 or j==n2:
            dp[i][j]=0
        else:
            if s1[i]==s2[j]:
                dp[i][j]=1+dp[i+1][j+1]
            else:
                dp[i][j]=max(dp[i][j+1],dp[i+1][j])
n=""
i,j=0,0
while i<n1 and j<n2:
    if dp[i][j]==dp[i+1][j]:
        i+=1
    elif dp[i][j]==dp[i][j+1]:
        j+=1
    else:
        n+=s1[i]
        i+=1
        j+=1
print(n)
### BUGGY CODE ###

from sys import stdin,stdout,setrecursionlimit
from collections import Counter as C
setrecursionlimit(10**6)
M = 1000000007
input = stdin.readline
def write(n,sep="\n"):
	stdout.write(str(n))
	stdout.write(sep)
def gil():
	return list(map(int, input().split()))
	
n = int(input())
a, b, c = [], [], []
for i in range(n):
    x,y,z = gil()
    a.append(x)
    b.append(y)
    c.append(z)
    
mem = {}
def rp(i, p, h):
    global a,b,c,n
    if i >= n:
        return h
    
    av = [rp(i+1, 0, h+a[i]), rp(i+1, 1, h+b[i]), rp(i+1, 2, h+c[i])]
    if p != -1:
        av[p] = 0
    ans = max(av)
    return ans
ans = rp(0, -1, 0)
print(ans)
        
    
 


### FIXED CODE ###

from sys import stdin,stdout,setrecursionlimit
from collections import Counter as C
setrecursionlimit(10**6)
M = 1000000007
input = stdin.readline
def write(n,sep="\n"):
	stdout.write(str(n))
	stdout.write(sep)
def gil():
	return list(map(int, input().split()))
	
n = int(input())
a, b, c = [], [], []
for i in range(n):
    x,y,z = gil()
    a.append(x)
    b.append(y)
    c.append(z)
    
mem = [[-1 for _ in range(3)] for _ in range(n+1)]
def rp(i, p):
    global a,b,c,n
    if i >= n:
        return 0
    if mem[i][p] != -1:
        return mem[i][p]
    av = [a[i] + rp(i+1, 0), b[i] + rp(i+1, 1), c[i] + rp(i+1, 2)]
    if p != -1:
        av[p] = 0
    ans = max(av)
    mem[i][p] = ans
    return ans
ans = rp(0, -1)
print(ans)
        
    
# on recursive mem sols, build the solution from the base case,
# ie, return 0 on basecase, and build up the solution.
# maybe because the values that come later on decide more on what you choose?
### BUGGY CODE ###

def InsertionSort(A, N, g):
    global cnt
    for i in range(g, N):
        key = A[i]
        j = i-g
        while j >= 0 and A[j] > key:
            A[j+g] = A[j]
            j = j-g
            cnt += 1    
        A[j+g] = key
    return A

def ShellSort(A, N):
    G = [len(A)]
    i = 0
    while True:
        if G[i] == 1:
            break
        G.append(G[i]//2)
        i += 1

    for i in range(len(G)):
        InsertionSort(A, N, G[i])
    return G

N = int(input())
A = []
cnt = 0
for i in range(N):
    A.append(int(input()))
ShellSort(A,N)
print(len(ShellSort(A,N)))
print(*ShellSort(A,N))
print(cnt)
print(*A, sep='\n')

### FIXED CODE ###

import math
def InsertionSort(A, N, g):
    global cnt
    for i in range(g, N):
        key = A[i]
        j = i-g
        while j >= 0 and A[j] > key:
            A[j+g] = A[j]
            j = j-g
            cnt += 1    
        A[j+g] = key
    return A

def ShellSort(A, N):
    G = []
    i = 1
    while True:
        if  3**i -1 > N*2:
            break
        G.insert(0, int((3**i-1)/2))
        i += 1


    for i in range(len(G)):
        InsertionSort(A, N, G[i])
    return G

N = int(input())
A = []
cnt = 0
for i in range(N):
    A.append(int(input()))
ShellSort(A,N)
print(len(ShellSort(A,N)))
print(*ShellSort(A,N))
print(cnt)
print(*A, sep='\n')
### BUGGY CODE ###

import sys
input = sys.stdin.readline

# D - Not Divisible
n = int(input())
a = list(map(int, input().split()))
dic = dict()

for ai in a:
	dic.setdefault(ai, 0)
	dic[ai] += 1

multiples = set()
upper = 10 ** 6

for k in dic.keys():
  i = 2
  
  while True:
    if k * i <= upper:
      multiples.add(k * i)
      i += 1
    else:
      break

ans = 0

for k, v in dic.items():
  if v == 1:
    if not k in multiples:
      ans += 1

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

# D - Not Divisible
n = int(input())
a = list(map(int, input().split()))
dic = dict()

for ai in a:
	dic.setdefault(ai, 0)
	dic[ai] += 1

multiples = set()
upper = 10 ** 6

for k in dic.keys():
  i = 2
  
  while True:
    if k * i <= upper:
      multiples.add(k * i)
      i += 1
    else:
      break

ans = 0

for k, v in dic.items():
  if v == 1:
    if not k in multiples:
      ans += 1

print(ans)