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

h,w = map(int,input().split())
g = []
for i in range(h):
    s = list(input())
    g.append(s)


#left
left = [[0]*w for i in range(h)]
for i in range(h):
    cnt = 0
    for j in range(w):
        if g[i][j] == ".":
            cnt += 1
            left[i][j] =cnt
        else:
            cnt = 0

#right
right = [[0]*w for i in range(h)]
for i in range(h-1,-1,-1):
    cnt = 0
    for j in range(w-1,-1,-1):
        if g[i][j] == ".":
            cnt += 1
            right[i][j] =cnt
        else:
            cnt = 0
#top
top = [[0]*w for i in range(h)]
for j in range(w):
    cnt = 0
    for i in range(h):
        if g[i][j] == ".":
            cnt += 1
            top[i][j] =cnt
        else:
            cnt = 0
#down
down = [[0]*w for i in range(h)]
for j in range(w-1,-1,-1):
    cnt = 0
    for i in range(h-1,-1,-1):
        if g[i][j] == ".":
            cnt += 1
            down[i][j] =cnt
        else:
            cnt = 0

maxans = -1
for i in range(h):
  for j in range(w):
    ans = left[i][j]+right[i][j]+top[i][j]+down[i][j]-3
    maxans = max(ans,maxans)
    
print(maxans)


### FIXED CODE ###

h,w = map(int,input().split())
g = []
for i in range(h):
    s = list(input())
    g.append(s)


#left
left = [[0]*w for i in range(h)]
for i in range(h):
    cnt = 0
    for j in range(w):
        if g[i][j] == ".":
            cnt += 1
            left[i][j] =cnt
        else:
            cnt = 0

#right
right = [[0]*w for i in range(h)]
for i in range(h-1,-1,-1):
    cnt = 0
    for j in range(w-1,-1,-1):
        if g[i][j] == ".":
            cnt += 1
            right[i][j] =cnt
        else:
            cnt = 0
#top
top = [[0]*w for i in range(h)]
for j in range(w):
    cnt = 0
    for i in range(h):
        if g[i][j] == ".":
            cnt += 1
            top[i][j] =cnt
        else:
            cnt = 0
#down
down = [[0]*w for i in range(h)]
for j in range(w-1,-1,-1):
    cnt = 0
    for i in range(h-1,-1,-1):
        if g[i][j] == ".":
            cnt += 1
            down[i][j] =cnt
        else:
            cnt = 0

maxans = -1
for i in range(h):
  for j in range(w):
    if g[i][j] =="#":
      continue
    ans = left[i][j]+right[i][j]+top[i][j]+down[i][j]-3
    maxans = max(ans,maxans)
    
print(maxans)
### BUGGY CODE ###

S = input()
Q = int(input())
P = [input().split() for i in range(Q)]

count = 0

for query in P:
    if query[0]=="1":
        count+=1
    else:
        if query[1]=="1":
            if count%2==0:
                S=query[2]+S
            else:
                S=S+query[2]
        else:
            if count%2==0:
                S=S+query[2]
            else:
                S=query[2]+S
if count%2==1:
    S=S[::-1]
    
print(S)


### FIXED CODE ###

S = input()
Q = int(input())
P = [input().split() for i in range(Q)]

count = 0
left = ""
right = ""
for query in P:
    if query[0]=="1":
        count+=1
    else:
        if query[1]=="1":
            if count%2==0:
                left+=query[2]
            else:
                right+=query[2]
        else:
            if count%2==0:
                right+=query[2]
            else:
                left+=query[2]
                
S = left[::-1]+S+right
if count%2==1:
    S=S[::-1]
    
print(S)
### BUGGY CODE ###

import collections

n = int(input())
s = list(input() for i in range(n))
c = collections.Counter(s)
m = c.most_common()[0][1]

t = []
for i in range(len(c)):
    if c.most_common()[i][1] == m:
        t.append(c.most_common()[i][0])
    else:
        break

t.sort()
for i in range(len(t)):
    print(t[i])

### FIXED CODE ###

import collections

n = int(input())
s = list(input() for i in range(n))
s = sorted(s)
c = collections.Counter(s)
p = max(c.values())
s = sorted(list(set(s)))

for i in range(len(s)):
    if c[s[i]] == p:
        print(s[i])
### BUGGY CODE ###

N = int(input())

L = len(str(N))
S = sum([N // 10**i for i in range(1, N+1)])

if N % S == 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

N = str(input())


S = sum([int(i) for i in N])

if int(N) % S == 0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

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

sum_k = [0] * N
tmp = 0
for i in range(K):
    tmp += p[i]
sum_k[0] = tmp
max_sum = tmp
candidate = 0
for i in range(len(p)-K):
    sum_k[i+1] = sum_k[i] - p[i] + p[i+K]
    if max_sum < sum_k[i+1]:
        max_sum = sum_k[i+1]
        candidate = i+1


ans = 0
for i in range(candidate, candidate + K):
    tmp = 0
    for j in range(1, p[i]+1):
        tmp += j * (1 / p[i])
    ans += tmp
print(ans)

### FIXED CODE ###

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

sum_k = [0] * N
tmp = 0
for i in range(K):
    tmp += p[i]
sum_k[0] = tmp
max_sum = tmp
candidate = 0
for i in range(len(p)-K):
    sum_k[i+1] = sum_k[i] - p[i] + p[i+K]
    if max_sum < sum_k[i+1]:
        max_sum = sum_k[i+1]
        candidate = i+1


dice = [-1] * 10000

ans = 0
for i in range(candidate, candidate + K):
    tmp = 0
    if dice[p[i]+1] != -1:
        ans += dice[p[i]+1]
        continue
    for j in range(1, p[i]+1):
        tmp += j * (1 / p[i])
    dice[p[i]+1] = tmp
    ans += tmp
print(ans)
### BUGGY CODE ###

N=int(input())
H=list(map(int,input().split()))
C=[0]*N
for j in range(N):
  for i in range(N-1-j):
    if H[j+i]>=H[j+i+1]:
      C[j]+=1
    else:
      break
print(max(C))

### FIXED CODE ###

N=int(input())
H=list(map(int,input().split()))
A,a=0,0
C=[0]*N
H=H[::-1]
for i in range(N-1):
  if H[i]<=H[i+1]:
    A+=1
  else:
    C[a]=A
    a+=1
    A=0
C[a]=A
print(max(C))
### BUGGY CODE ###

import fractions
from functools import reduce
import random
import copy

def gcd(numbers):
    return reduce(fractions.gcd, numbers)

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

if n < 100:
  for i in range(n):
    b = copy.copy(a)
    b.pop(i)
    t = gcd(b)
    if ans < t:
      ans = t
else:
  for _ in range(100):
    t = gcd(random.sample(a, n-1))
    if ans < t:
      ans = t

print(ans)

### FIXED CODE ###

import fractions
from functools import reduce
import random
import copy

def gcd(numbers):
    return reduce(fractions.gcd, numbers)

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

if n < 1000:
  for i in range(n):
    b = copy.copy(a)
    b.pop(i)
    t = gcd(b)
    if ans < t:
      ans = t
else:
  for _ in range(200):
    t = gcd(random.sample(a, 500))
    if ans < t:
      ans = t

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

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

for k in range(N):
    print(sorted(X[:k]+X[k+1:])[N//2-1])

### FIXED CODE ###

N = int(input())
X = list(map(int, input().split()))
Y = [[X[k],k] for k in range(N)]
Y.sort()
A = [0 for k in range(N)]

for k in range(N):
    if k >= N//2:
        A[Y[k][1]] = Y[N//2-1][0]
    else:
        A[Y[k][1]] = Y[N//2][0]

for x in A:
    print(x)
### BUGGY CODE ###

N,C=map(int,input().split())
D=[[int(x) for x in input().split()] for y in range(C)]
c=[[int(x)-1 for x in input().split()] for y in range(N)]

a=10**9
for c0 in range(C):
  for c1 in range(c0+1,C):
    for c2 in range(c1+1,C):
      s1,s2,s3=0,0,0
      for i in range(N):
        for j in range(N):
          m = (i+j+2)%3
          if m==0:
            s1 += D[c[i][j]][c0]
            s2 += D[c[i][j]][c1]
            s3 += D[c[i][j]][c2]
          elif m==1:
            s1 += D[c[i][j]][c1]
            s2 += D[c[i][j]][c2]
            s3 += D[c[i][j]][c0]
          else:
            s1 += D[c[i][j]][c2]
            s2 += D[c[i][j]][c0]
            s3 += D[c[i][j]][c1]
      a=min(a,s1,s2,s3)
print(a)


### FIXED CODE ###

N,C=map(int,input().split())
D=[[int(x) for x in input().split()] for y in range(C)]
c=[[int(x)-1 for x in input().split()] for y in range(N)]

d=[[0 for x in range(C)] for y in range(3)]
for i in range(N):
  for j in range(N):
    d[(i+j)%3][c[i][j]] += 1

a=10**9
for c0 in range(C):
  for c1 in range(c0+1,C):
    for c2 in range(c1+1,C):
      s1,s2,s3,s4,s5,s6=0,0,0,0,0,0
      for c in range(C):
        s1 += d[0][c]*D[c][c0]+d[1][c]*D[c][c1]+d[2][c]*D[c][c2]
        s2 += d[0][c]*D[c][c0]+d[1][c]*D[c][c2]+d[2][c]*D[c][c1]
        s3 += d[0][c]*D[c][c1]+d[1][c]*D[c][c0]+d[2][c]*D[c][c2]
        s4 += d[0][c]*D[c][c1]+d[1][c]*D[c][c2]+d[2][c]*D[c][c0]
        s5 += d[0][c]*D[c][c2]+d[1][c]*D[c][c0]+d[2][c]*D[c][c1]
        s6 += d[0][c]*D[c][c2]+d[1][c]*D[c][c1]+d[2][c]*D[c][c0]
      a=min(a,s1,s2,s3,s4,s5,s6)
print(a)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *


def solve(H: int, W: int, A: "List[str]"):
    queue = deque()

    rem = H * W
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                queue.append((i, j, 0))

    ret = 0
    visited = [False] * (W * H)
    while 0 < len(queue) and 0 < rem:
        i, j, n = queue.popleft()
        if visited[i * W + j]:
            continue
        visited[i * W + j] = True
        #ret = max(ret, n)
        ret = n
        rem -= 1

        if 0 < j:
            queue.append((i, j - 1, n + 1))
        if j < W - 1:
            queue.append((i, j + 1, n + 1))
        if 0 < i:
            queue.append((i - 1, j, n + 1))
        if i < H - 1:
            queue.append((i + 1, j, n + 1))
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    result = solve(H, W, A)
    print(result)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *


def solve(H: int, W: int, A: "List[str]"):
    queue = deque()

    rem = H * W
    visited = [True] * ((W+2) * (H+2))
    for i in range(W+2):
        visited[i] = False
        visited[(W + 2) * (H + 1) + i] = False
    for i in range(H+2):
        visited[(W + 2) * i] = False
        visited[(W + 2) * i + (W + 1)] = False

    for i in range(H):
        l = A[i]
        for j in range(W):
            if l[j] == '#':
                queue.append((i+1, j+1, 0))
                k = i * (W + 2) + j
                visited[k] = False

    ret = 0
    while queue:
        i, j, n = queue.popleft()
        k = i * (W + 2) + j
        if not visited[k] and 0 < n:
            continue
        visited[k] = False
        ret = n
        rem -= 1

        if rem == 0:
            break

        if visited[k - 1]:
            queue.append((i, j - 1, n + 1))
        if visited[k + 1]:
            queue.append((i, j + 1, n + 1))

        if visited[k - (W + 2)]:
            queue.append((i - 1, j, n + 1))
        if visited[k + (W + 2)]:
            queue.append((i + 1, j, n + 1))
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    result = solve(H, W, A)
    print(result)

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

S = input()
N = len(S)
MOD = 10 ** 9 + 7

Qs = 3 if S[0] == '?' else 1
A = [0] * N
AB = [0] * N
ABC = [0] * N
if S[0] in 'A?':
    A[0] = 1
a, ab, abc = A[0], AB[0], ABC[0]
for i in range(1, N):
    s = S[i]
    if s == '?':
        A[i] = a * 3 + Qs
        AB[i] = ab * 3 + a
        ABC[i] = abc * 3 + ab
        Qs *= 3
    elif s == 'A':
        A[i] = a + Qs
        AB[i] = ab
        ABC[i] = abc
    elif s == 'B':
        A[i] = a
        AB[i] = ab + a
        ABC[i] = abc
    elif s == 'C':
        A[i] = a
        AB[i] = ab
        ABC[i] = abc + ab
    a, ab, abc = A[i], AB[i], ABC[i]

ans = ABC[-1] % MOD
print(ans)

### FIXED CODE ###

S = input()
N = len(S)
MOD = 10 ** 9 + 7

dp = [0, 0, 0, 0]
dp[0] = 1

for s in S:
    factor = 3 if s == '?' else 1
    for j, c in zip([2, 1, 0], 'CBA'):
        dp[j + 1] = dp[j + 1] * factor % MOD
        if s == c or s == '?':
            dp[j + 1] += dp[j]
    if s == '?':
        dp[0] = (dp[0] * 3) % MOD

ans = dp[-1] % MOD

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

N=int(input()) 
t=[[0]*10]*N
y=[[0]*10]*N

for i in range(N):
  s=input()
  for j in range(10):
    t[i][j]=s[j]
  y[i]=sorted(t[i])
  
count=0

for i in range(0,N-1):
  for j in range(i+1,N):
    #print(i,t[i])
    #print(j,t[1])

    if y[i]==y[j]:
        count+=1

print(count)

### FIXED CODE ###

from collections import Counter

N=int(input())
s=[0]*N
t=[0]*N
d=dict()
cnt=0

for i in range(N):
  s[i]=input()
  t[i]=str(sorted(s[i]))
  if t[i] not in d:
    d[t[i]] =1
    #print(i,d)
  else:
    cnt += d[t[i]]
    d[t[i]] +=1
    #print(i,d)

print(cnt)
### BUGGY CODE ###

def LI():return list(map(int,input().split()))
def yes():print("Yes")
def no():print("No")
from collections import deque
n,m=LI()
edge=[[]*n for i in range(n)]
for i in range(m):
    a,b=LI()
    a-=1
    b-=1
    edge[a].append(b)
    edge[b].append(a)
# print(edge)

ans=[-1]*n
goal=deque([0])
while goal:
    g=goal.popleft()
    for i in range(n):
        v=edge[i]
        if g in v:
            ans[i]=g
            edge[i].clear()
            goal.append(i)

if -1 in ans:
    no()
    exit()
yes()
for i in ans[1:]:
    print(i+1)



### FIXED CODE ###

def LI():return list(map(int,input().split()))
def yes():print("Yes")
def no():print("No")
from collections import deque

def main():
    n,m=LI()
    edge=[[] for i in range(n)]
    for i in range(m):
        a,b=LI()
        a-=1;b-=1
        edge[a].append(b)
        edge[b].append(a)    
    ans=[-1]*(n)
    goal=deque([0])
    while goal:
        g=goal.popleft()
        for i in edge[g]:
            if ans[i]==-1:
                ans[i]=g+1
                goal.append(i)
    yes()
    print(*ans[1:])
main()
### BUGGY CODE ###

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

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

l_target.sort(key=lambda x:x[1])

#print(l_target)

cut_pos=[]
for target in l_target:
    is_ok=False
    for pos in cut_pos:
        if (target[0]<pos<target[1]):
            is_ok=True
            break
    
    if(not is_ok):
        cut_pos.append(target[1]-0.5)

print(len(cut_pos))

### FIXED CODE ###

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

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

l_target.sort(key=lambda x:x[1])

count=0
pre_pos=0
for target in l_target:
    if (target[0]<pre_pos<target[1]):
        continue
    
    count+=1
    pre_pos=target[1]-0.5

print(count)
### BUGGY CODE ###

import sys


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


def main():
    n, k = [int(i) for i in input().split()]
    h = [int(i) for i in input().split()]
    for i in range(k):
        h.append(0)

    dp = [float('inf')] * (n + k)
    dp[0] = 0

    for i in range(n):
        for j in range(1, k + 1):
            dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[i + j]))

    print(dp[n-1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

n, k = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]
for i in range(k):
    h.append(0)

dp = [float('inf')] * (n + k)
dp[0] = 0

for i in range(n):
    for j in range(1, k + 1):
        dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[i + j]))

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

S = input()
N = 10**9 + 7
d = {str(i):[int(i == k) for k in range(10)] for i in range(10) }
d["?"] = [1] * 10 
l = d[S[0]] + [0]*3
#print(l)
for i in range(1, len(S)):
  if S[i] == "?":
    l = [(sum([l[((k - j) * 4)%13] for j in range(10)]))%N for k in range(13)]
  else:
    l = [l[((k - int(S[i])) * 4)%13] for k in range(13)]
  #print(l)
print(l[5])         

### FIXED CODE ###

S = input()
N = 10**9 + 7
d = {str(i):[int(i == k) for k in range(10)] for i in range(10) }
d["?"] = [1] * 10 
l = d[S[0]] + [0]*3
#print(l)
for i in range(1, len(S)):
  if S[i] == "?":
    l = [(sum([l[((k - j) * 4)%13] for j in range(10)]))%N for k in range(13)]
  else:
    l = [l[((k - int(S[i])) * 4)%13] for k in range(13)]
  #print(l)
print(l[5])
### BUGGY CODE ###


N, M = map(int, input().split())
ans = 0

def func(n):
    sum = 1
    for i in range(1, n+1):
        sum *= i
    return sum % (10**9 + 7)

if abs(N - M) == 0:
    ans = 2 * func(N)*func(M)
elif abs(N - M) == 1:
    ans = func(N)*func(M)
    
print(ans % (10**9 + 7))


### FIXED CODE ###

N, M = map(int, input().split())
ans = 0
MOD = 10**9 + 7

def func(n):
    sum = 1
    for i in range(1, n+1):
        sum = sum*i % MOD
    return sum 

if abs(N - M) == 0:
    ans = 2 * func(N)*func(M)
elif abs(N - M) == 1:
    ans = func(N)*func(M)
    
print(ans % MOD)
### BUGGY CODE ###

X=int(input())
bp=1
for b in range(1,X):
    for p in range(2,X):
        if b**p<=X:
            bp=max(bp,b**p)
print(bp)

### FIXED CODE ###

x=int(input())
c=1
for b in range(1,x):
    for p in range(2,x):
        if b**p<=x:
            c=max(c,b**p)
        else:
            break
print(c)
### BUGGY CODE ###

n=int(input())
a=[int(input()) for i in range(n)]

s = list(set(a))
b=[0]*len(s)
for i in range(len(s)):
  b[i]=a.count(s[i])

cnt=0
for i in range(len(s)):
  if b[i]%2==1:
    cnt+=1
print(cnt)

### FIXED CODE ###

import collections
n=int(input())
a=[int(input()) for i in range(n)]
s=list(collections.Counter(a).values())
cnt=0
for i in s:
  if i%2!=0:
    cnt+=1
print(cnt)
### BUGGY CODE ###

N=int(input())

A=1
for i in range(1,N+1):
    A=A*i
print(A%(7+10**9))


### FIXED CODE ###

N=int(input())

A=1
for i in range(1,N+1):
    A=A*i
    A=A%(7+10**9)
print(A)
### BUGGY CODE ###

s=input()
K=int(input())
As=sorted(s)
ans=[]
for A in As:
    if len(ans)>K:break
    for j in range(1,K+1):
        ind=0
        for i in s:
            if i==A:
                if len(s[ind:ind+j])==j and (s[ind:ind+j] not in ans):
                    ans.append(s[ind:ind+j])
            ind+=1
print(sorted(ans)[K-1])



### FIXED CODE ###

s=input()
K=int(input())
As=sorted(set(s))
ans=[]
for A in As:
    ans.append(A)
    if len(ans)>=K:break
    for j in range(2,K+1):
        ind=0
        for i in s:
            if i==A:
                Judge=s[ind:ind+j]
                if len(Judge)==j and (Judge not in ans):
                    ans.append(Judge)
            ind+=1
print(sorted(ans)[K-1])
### BUGGY CODE ###

N, S = map(int, input().split())
A = list(map(int, input().split()))
m = 0
var1 = [0] * (S + 1)
var1[0] = pow(2, N, 998244353)
var2 = pow(2, 998244353 - 2, 998244353)
def func1(xxx, xx):
    if xxx>xx:
        return xx
    else:
        return xxx
for all in A:
    m = all+m
    funcvar1=func1(S, m)
    for val in reversed(range(all,funcvar1+1)):
        var1[val] = (var1[val] + var1[val - all] * var2) % 998244353
print(var1[S])

### FIXED CODE ###

import numpy as np
def finalFunc(n,s,A):
    var=np.array([0 for i in range(min(3001,s+1))])
    var[0]=1
    for i in A:
        tmp=var[:-i].copy()
        var*=2
        var[i:]+=tmp
        var%=998244353
    return var[s]
n,s=map(int,input().split())
A=list(map(int,input().split()))
print(finalFunc(n,s,A))
### BUGGY CODE ###

# N, W = 3, 8
# ARR = [
#     [3, 30],
#     [4, 50],
#     [5, 60],
# ]
#
# N, W, = 6, 15
# ARR = [
#     [6, 5],
#     [5, 6],
#     [6, 4],
#     [6, 6],
#     [3, 5],
#     [7, 2],
# ]


N,W = map(int,input().split())
ARR = []

for i in range(N):
    ARR.append(list(map(int,input().split())))

def calculate(n, w, arr):
    result = [[0] * (w + 1) for i in range(n + 1)]


    for i in range(n):
        width = arr[i][0]
        value = arr[i][1]
        for j in range(w + 1):

            if j >= width:
                result[i + 1][j] = max(result[i][j - width] + value, result[i + 1][j])

            result[i + 1][j] = max(result[i + 1][j], result[i][j])

    # print(result)
    print(result[n][w])


calculate(N, W, ARR)


### FIXED CODE ###

# N, W = 3, 8
# ARR = [
#     [3, 30],
#     [4, 50],
#     [5, 60],
# ]
#
# N, W, = 6, 15
# ARR = [
#     [6, 5],
#     [5, 6],
#     [6, 4],
#     [6, 6],
#     [3, 5],
#     [7, 2],
# ]


N,W = map(int,input().split())
ARR = []

for i in range(N):
    ARR.append(list(map(int,input().split())))

def calculate(n, w, arr):
    result = [[0] * (w + 1) for i in range(n + 1)]


    for i in range(n):
        width = arr[i][0]
        value = arr[i][1]
        for j in range(w + 1):

            if j >= width:
                result[i + 1][j] = max(result[i][j - width] + value, result[i + 1][j])

            result[i + 1][j] = max(result[i + 1][j], result[i][j])

    # print(result)
    print(result[n][w])


calculate(N, W, ARR)
### BUGGY CODE ###

n, m, q = map(int, input().split())
trains = [list(map(int, input().split())) for _ in range(m)]
questions = [list(map(int, input().split())) for _ in range(q)]

for question in questions:
    x, y = question
    cnt = 0
    for train in trains:
        l, r = train
        if x <= l and r <= y: cnt += 1
    print(cnt)


### FIXED CODE ###

n, m, q = map(int, input().split())
cities = [[0 for _ in range(n+1)] for _ in range(n+2)]
trains = [list(map(int, input().split())) for _ in range(m)]
quests = [list(map(int, input().split())) for _ in range(q)]

for train in trains:
    x, y = train[0], train[1]
    cities[x][y] += 1

for i in range(n):
    for j in range(1, n-i+1):
        x = j + i
        cities[j][x] += cities[j][x-1] + cities[j+1][x] - cities[j+1][x-1]

for quest in quests:
    p, q = quest[0], quest[1]
    print(cities[p][q])
### BUGGY CODE ###

n, k = map(int, input().split())
h = [int(i) for i in input().split()]

dp = [0] * n

for i in range(n):
  dp_temp = 0
  for j in range(1, k+1):
    if i-j > -1:
      temp = dp[i-j] + abs(h[i]-h[i-j])
      if dp_temp == 0:
        dp_temp = temp
      else:
        if dp_temp > temp:
          dp_temp = temp
    else:
      break
  dp[i] = dp_temp
print(dp[n-1])
  

### FIXED CODE ###

n, k = map(int, input().split())
h = [int(i) for i in input().split()]

dp = [0] * n

for i in range(n):
  dp_temp = 0
  flag = 0
  for j in range(1, k+1):
    if i-j >= 0:
      temp = dp[i-j] + abs(h[i]-h[i-j])
      if flag == 0:
        dp_temp = temp
        flag = 1
      else:
        if dp_temp >= temp:
          dp_temp = temp
    else:
      break
  dp[i] = dp_temp
print(dp[n-1])
### BUGGY CODE ###

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

A.sort(reverse = True)
circle = [A[0]]
ans = 0

for i in range(1,N):
    max = 0
    l = len(circle)
    for j in range(l):
        if max < min(circle[j],circle[(j+1)%l]):
            ins = j
            max = min(circle[j],circle[(j+1)%l])
    circle.insert(ins,A[i])
    ans += max

print(ans)


### FIXED CODE ###

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

A.sort(reverse = True)


ans2 = A[0]
cnt = 0
j = 1
for i in range(1,N-1):
    if cnt == 2:
        j += 1
        cnt = 0
    ans2 += A[j]
    cnt += 1

print(ans2)