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

from collections import deque


def main():
    height, width = map(int, input().split())
    grid = [list(input()) for _ in range(height)]
    q = deque([])
    change_time = [[float("inf") for _ in range(width)] for _ in range(height)]
    for i in range(height):
        for j in range(width):
            if grid[i][j] == "#":
                q.append([i, j, 0])
                change_time[i][j] = 0
    d = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    answer = 0
    while q:
        y, x, time = q.popleft()
        grid[y][x] = "#"
        for dy, dx in d:
            new_y = y + dy
            new_x = x + dx
            if 0 <= new_y < height and 0 <= new_x < width and grid[new_y][new_x] == ".":
                change_time[new_y][new_x] = min(change_time[new_y][new_x], change_time[y][x] + 1)
                q.append([new_y, new_x, change_time[new_y][new_x]])
                answer = max(answer, change_time[new_y][new_x])
    print(answer)


if __name__ == '__main__':
    main()



### FIXED CODE ###

from collections import deque
from sys import stdin


def main():
    height, width = map(int, stdin.readline().split())
    q = deque([])
    grid = [stdin.readline() for _ in range(height)]
    distance = [[-1 for _ in range(width)] for _ in range(height)]
    for i in range(height):
        for j in range(width):
            if grid[i][j] == "#":
                q.append((i, j))
                distance[i][j] = 0
    answer = 0
    delta = ((0, 1), (1, 0), (0, -1), (-1, 0))
    while q:
        y, x = q.popleft()
        answer = distance[y][x]
        for dy, dx in delta:
            new_y = y + dy
            new_x = x + dx
            if 0 <= new_y < height and 0 <= new_x < width and distance[new_y][new_x] < 0:
                distance[new_y][new_x] = answer + 1
                q.append((new_y, new_x))
    print(answer)


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

import math

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

max_num = 0
for x in range(1, N+1):
    t = math.floor(A * x / B) - A * math.floor(x / B)
    if t > max_num:
        max_num = t

print(max_num)

### FIXED CODE ###

def main():
    A, B, N = map(int, input().split())
    x = min(B-1, N)
    ans = int((A*x)/B) - A*int(x/B)
    print(ans)


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

s=input()
c=0
while True:
  a=s.count('BW')
  if a:
    c+=a
    s=s.replace('BW','WB')
  else:
    break
print(c)

### FIXED CODE ###

s=list(input())
c=0
b=0
for i in s:
  if i=='B':
    b+=1
  if i=='W':
    c+=b
print(c)
### BUGGY CODE ###

import math

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

if M == 0:
    a = [-1 , N+1]
else :
    a = [-1] * (M+2)

    for i in range(1,M+1) :
        a[i] = int(input())

flag = True # 可能かどうか
for i in range(0,M+1) :
    if a[i] + 1 == a[i+1] :
        flag = False
        break

if flag :
    a[M+1] = N + 1

    ans = 1

    for i in range(M+1) :
        length = a[i+1] - a[i] - 2 # 上がる長さ
        max2step = math.floor(length / 2) # 2段の回数
        count = 1
        for j in range(1,max2step+1) :
            if length - 2 * j < 0 :
                break
            step2 = math.factorial(j)
            step1 = math.factorial(int(length-2*j))
            count += math.factorial(length - j) // step1 // step2
        ans *= count

    print(int(ans % 1000000007))
else :
    print(0)

### FIXED CODE ###

import math

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

if M == 0:
    a = [-1 , N+1]
else :
    a = [-1] * (M+2)

    for i in range(1,M+1) :
        a[i] = int(input())


flag = True # 可能かどうか
for i in range(0,M+1) :
    if a[i] + 1 == a[i+1] :
        flag = False
        break

fib = [1] * (N+1) # フィボナッチ数列
for i in range(2,N+1) :
    fib[i] = fib[i-1] + fib[i-2]

if flag :
    a[M+1] = N + 1

    ans = 1

    for i in range(M+1) :
        length = a[i+1] - a[i] - 2 # 上がる長さ
        ans *= fib[length]

    print(ans % 1000000007)
else :
    print(0)
### BUGGY CODE ###

from collections import deque

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())

g = []
for i in range(h):
  s = list(input())
  g.append(s)
inf = float("inf")
dist = [[inf]*w for i in range(h)]
queue = deque()
start = [ch-1,cw-1,0]
queue.append(start)
while queue:
    y, x,wapu = queue.popleft()
    dist[y][x] = wapu
    for new_y, new_x in ([y+1, x], [y-1, x], [y, x+1], [y, x-1]):
        if 0 <= new_y <= h-1 and 0 <= new_x <= w-1:
            if g[new_y][new_x] == '#':
                continue           
            elif wapu < dist[new_y][new_x]:
                dist[new_y][new_x] = wapu
                queue.append([new_y, new_x,wapu])
    for new_y, new_x in ([y+1, x+1], [y+1, x-1], [y-1, x+1], [y-1, x-1], [y+2, x-1], [y-2, x-1], [y-2, x], [y+2, x], [y+2, x+1], [y-2, x+1], [y-1, x+2], [y, x+2], [y+1, x+2], [y+2, x+2], [y-2, x-2], [y-2, x+2], [y+2, x-2], [y-1, x-2], [y, x-2], [y+1, x-2]):
      if 0 <= new_y <= h-1 and 0 <= new_x <= w-1:
            if g[new_y][new_x] == '#':
                continue       
            else:
                 new_wapu= wapu +1
            if new_wapu < dist[new_y][new_x]:
                dist[new_y][new_x] = new_wapu
                queue.append([new_y, new_x,new_wapu])
ans = dist[dh-1][dw-1]
if ans == inf:
  print(-1)
else:
  print(dist[dh-1][dw-1])

### FIXED CODE ###

from collections import deque


H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)
### BUGGY CODE ###

INF = float("inf")

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

dp = [INF] * (2 ** N)
dp[0] = 0

for _ in range(M):
    a, b = map(int, input().split())
    C = [int(i) for i in input().split()]
    mask = sum(1 << (c - 1) for c in C)
    for i in range(len(dp)):
        dp[i | mask] = min(dp[i | mask], dp[i] + a)

ans = dp[-1]
print(-1 if ans == INF else ans)


### FIXED CODE ###

INF = float("inf")

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

dp = [INF] * (2 ** N)
dp[0] = 0

for _ in range(M):
    a, b = map(int, input().split())
    C = [int(i) for i in input().split()]
    mask = sum(1 << (c - 1) for c in C)
    for i in range(len(dp)):
        if dp[i | mask] > dp[i] + a:
            dp[i | mask] = dp[i] + a

ans = dp[-1]
print(-1 if ans == INF else ans)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
from bisect import bisect_left

n = int(sys.stdin.readline().strip())
l = [ int(x) for x in sys.stdin.readline().strip().split() ]
l.sort()

c = 0
for i in range(1,n):
    for j in range(i+1,n):
        k = bisect_left(l,l[j]-l[i]+1,hi=i)
        if k==i: continue
        c += i-k
#
print(c)



### FIXED CODE ###

#!/usr/bin/env python3

import sys
from bisect import bisect_left

n = int(sys.stdin.readline().strip())
l = list(map(int,sys.stdin.readline().strip().split()))
    
l.sort()
c = 0
n1 = n - 1
for i in range(n-2):
    li = l[i]
    for j in range(i+1,n1):
        k = bisect_left(l,l[j]+li,lo=j)
        c += k-j-1
#
print(c)
### BUGGY CODE ###

from collections import defaultdict, deque
def solve():
    N, X, Y = map(int, input().split())
    cnter = [0] * N

    for start in range(N-1):
        deq = deque()
        deq.append(start)
        n_step = [float('inf')] * N
        n_step[start] = 0
        visited = [False] * N

        while len(deq) > 0:
            fr = deq.popleft()
            visited[fr] = True

            if fr == X-1:
                if not visited[Y-1] or n_step[Y-1] > n_step[X-1]+1:
                    n_step[Y-1] = n_step[X-1]+1
                    deq.append(Y-1)
                    visited[Y-1] = True

            if fr == Y-1:
                if not visited[X-1] or n_step[X-1] > n_step[Y-1]+1:
                    n_step[X-1] = n_step[Y-1]+1
                    deq.append(X-1)
                    visited[X-1] = True
                    
            if fr != N-1:
                if not visited[fr+1] or n_step[fr+1] > n_step[fr]+1:
                    deq.append(fr+1)
                    n_step[fr+1] = n_step[fr]+1
                    visited[fr+1] = True

            if fr != 0:
                if not visited[fr-1] or n_step[fr-1] > n_step[fr]+1:
                    deq.append(fr-1)
                    n_step[fr-1] = n_step[fr]+1
                    visited[fr-1] = True
        
        for i in range(start,N):
            cnter[n_step[i]] += 1
            
    for i in range(1,N):
        print(cnter[i])

if __name__ == '__main__':
    solve()


### FIXED CODE ###

from collections import defaultdict, deque
def solve():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1
    cnter = defaultdict(int)

    for i in range(N):
        for j in range(i,N):
            n_step = min(abs(j-i), abs(X-i)+1+abs(Y-j), abs(Y-i)+1+abs(j-X))
            cnter[n_step] += 1
    
    for i in range(1,N):
        print(cnter[i])


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

import itertools
N, M, Q = map(int, input().split())
List = [list(map(int, input().split())) for i in range(Q)]
Max = 0

for a in itertools.combinations_with_replacement(range(1, M+1), N):
  A = list(a)
  A.sort()
  point = 0
  for i in range(Q):
    ai = List[i][0]
    bi = List[i][1]
    if ai < 1 or N < ai or bi < 1 or N < bi:
      continue
    if A[bi-1]-A[ai-1] == List[i][2]:
      point += List[i][3]
  if Max < point:
    Max = point

print(Max)

### FIXED CODE ###

import itertools
N, M, Q = map(int, input().split())
List = [list(map(int, input().split())) for i in range(Q)]
Max = 0
 
for a in itertools.combinations_with_replacement(range(1, M+1), N):
  A = list(a)
  A.sort()
  point = 0
  for i in range(Q):
    ai = List[i][0]
    bi = List[i][1]
    if ai < 1 or N < ai or bi < 1 or N < bi:
      continue
    if A[bi-1]-A[ai-1] == List[i][2]:
      point += List[i][3]
  if Max < point:
    Max = point
 
print(Max)
### BUGGY CODE ###

def n_gram(target,n):
    return [int(target[idx:idx + n]) for idx in range(len(target) - n + 1)]

count = 0
s = input()
n = 4
while n <= len(s):
    for num in n_gram(s,n):
        if int(num) % 2019 == 0:
            count += 1
    n += 1
print(count)

### FIXED CODE ###

s = input()[::-1]

count = [0]*2019
count[0] = 1  # そもそもあまりが0ってことは2019の倍数確定なので

num, d = 0, 1  # 初期化

for char in s:
    num += int(char)*d
    num %= 2019
    d *= 10
    d %= 2019
    count[num] += 1  # 2019で割ったあまりをキーとして値を追加していく

ans = 0
for c in count:
    ans += c*(c-1)//2
print(ans)
### BUGGY CODE ###

import sys


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


def main():

    N = int(my_input())
    S = my_input()

    ans = 0
    for i in range(1000):
        d1 = (i // 100) % 10
        d2 = (i // 10) % 10
        d3 = i % 10
        d1_flag = True
        d2_flag = True

        for i in range(N):

            now = int(S[i])
            if d1_flag:
                if d1 == now:
                    d1_flag = False
                continue

            if d2_flag:
                if d2 == now:
                    d2_flag = False
                continue

            if d3 == now:
                ans += 1
                break

    print(ans)


if __name__ == '__main__':

    main()


### FIXED CODE ###

n = int(input())
s = list(input())

ans = 0


for i in range(10):
    for j in range(10):
        for k in range(10):
            flag1 = 0
            flag2 = 0
            
            for l in range(n):
                if flag1 == 0 and s[l] == str(i):
                    flag1 = 1
                    continue
                
                if flag1 == 1 and flag2 == 0 and s[l] == str(j):
                    flag2 = 1
                    continue
                
                if flag1 == 1 and flag2 == 1 and s[l] == str(k):
                    ans += 1
                    break
                
print(ans)
### BUGGY CODE ###

def DI(n):
    D = []
    for i in range(1,int(n**0.5)+1):
        if n % i == 0:
            D.append(i)
            if i != n//i:
                D.append(n//i)
    return D
X = int(input())
D = DI(X)
flag = False
for i in range(len(D)):
    for a in range((D[i]+1)//2):
        b = -(D[i] - a)
        if a**5 - b**5 == X:
            print(str(a) + ' ' + str(b))
            flag = True
            break
    if flag:
        break

### FIXED CODE ###

X = int(input())
flag = False
for i in range(-120,120):
    for j in range(-120,120):
        if i**5 - j**5 == X:
            print(str(i) + ' ' + str(j))
            flag = True
            break
    if flag:
        break
### BUGGY CODE ###

N=int(input())
num = input()
n = list(map(int, num.split()))

n_sorted = sorted(n)

for i in range(N)[::-1]:
    value = n_sorted[i]
    j = n.index(value)
    for k in range(j+1, N):
        if n[k]-value< -1:
            print("No")
            exit()
print("Yes")

### FIXED CODE ###

n=int(input())
h=[int(i) for i in input().split()]
f=1
h[0]-=1
for i in range(1,n):
    if h[i]-h[i-1]>=1:h[i]+=-1
    elif h[i]-h[i-1]==0:h[i]+=0
    else:
        f=0
        print("No")
        break
if f==1:print("Yes")
### BUGGY CODE ###

from bisect import bisect_left
M = 200001
n = int(input())
l = [None] * n
ans = 10 ** 18
for i in range(n):
    x, y, u = input().split()
    u = ('R', 'D', 'L', 'U').index(u)
    l[i] = (int(x), int(y), u)
for _ in range(4):
    l.sort()
    xy = [[] for _ in range(M * 2 - 1)]
    yx = [[] for _ in range(M * 2 - 1)]
    xs = [[] for _ in range(M)]
    k = []
    for i, t in enumerate(l):
        x, y, u = t
        u %= 4
        if u == 3:
            xy[x + y].append(x)
        elif u == 1:
            yx[x - y + M - 1].append(x)
        elif u == 2:
            xs[y].append(x)
        else:
            k.append((x, y))
        l[i] = (y, -x + M - 1, u + 1)
    for x, y in k:
        idx = bisect_left(xs[y], x)
        if idx < len(xs[y]):
            ans = min(ans, (xs[y][idx] - x) * 5)
        idx = bisect_left(xy[x + y], x)
        if idx < len(xy[x + y]):
            ans = min(ans, (xy[x + y][idx] - x) * 10)
        idx = bisect_left(yx[x - y + M - 1], x)
        if idx < len(yx[x - y + M - 1]):
            ans = min(ans, (yx[x - y + M - 1][idx] - x) * 10)
if ans == 10 ** 18:
    print('SAFE')
else:
    print(ans)


### FIXED CODE ###

from bisect import bisect_left
import sys
input = sys.stdin.readline
M = 200001
n = int(input())
l = [None] * n
ans = 10 ** 18
for i in range(n):
    x, y, u = input().split()
    u = ('R', 'D', 'L', 'U').index(u)
    l[i] = (int(x), int(y), u)
for _ in range(3):
    l.sort(key=lambda x: x[0])
    xy = [[] for _ in range(M * 2 - 1)]
    yx = [[] for _ in range(M * 2 - 1)]
    xs = [[] for _ in range(M)]
    k = []
    for i, t in enumerate(l):
        x, y, u = t
        u %= 4
        if u == 3:
            xy[x + y].append(x)
        elif u == 1:
            yx[x - y + M - 1].append(x)
        elif u == 2:
            xs[y].append(x)
        elif u == 0:
            k.append((x, y))
        l[i] = (y, -x + M - 1, u + 1)
    for x, y in k:
        idx = bisect_left(xs[y], x)
        if idx < len(xs[y]):
            ans = min(ans, (xs[y][idx] - x) * 5)
        idx = bisect_left(xy[x + y], x)
        if idx < len(xy[x + y]):
            ans = min(ans, (xy[x + y][idx] - x) * 10)
        idx = bisect_left(yx[x - y + M - 1], x)
        if idx < len(yx[x - y + M - 1]):
            ans = min(ans, (yx[x - y + M - 1][idx] - x) * 10)
if ans == 10 ** 18:
    print('SAFE')
else:
    print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
a_list = list(map(int, input().split()))

items = {
    1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6
}
dp = [0] * (N + 1)

b_list = []
for a in a_list:
    need = items[a]
    if need <= N:
        dp[need] = a
        b_list.append(a)

M = len(b_list)
b_list.sort()
for i in range(N + 1):
    for b in b_list:
        if i - items[b] >= 0:
            if dp[i - items[b]] != 0:
                tmp = max(b * (10 ** len(str(dp[i - items[b]]))) + dp[i - items[b]], dp[i - items[b]] * 10 + b)
                dp[i] = max(tmp, dp[i])
print(dp[N])


### FIXED CODE ###

N, M = map(int, input().split())
a_list = list(map(int, input().split()))

items = {
    1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6
}

dp = [-float("inf")] * (N + 1)
b_list = []
for a in a_list:
    need = items[a]
    if need <= N:
        dp[need] = 1
        b_list.append(a)

M = len(b_list)
dp[0] = 0
for i in range(N + 1):
    for b in b_list:
        if i - items[b] >= 0:
            if dp[i - items[b]] != -float("inf"):
                dp[i] = max(dp[i], dp[i - items[b]] + 1)

b_list.sort(reverse=True)
ans = ""

for i in range(dp[N]):
    for b in b_list:
        if dp[N - items[b]] == dp[N] - 1:
            ans += str(b)
            N -= items[b]
            break
print(ans)
### BUGGY CODE ###

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

for k in range(K):
  if A>0 and B!=0:
    A+=-1
  elif A==0 and B>0:
    B+=-1
  elif A==0 & B==0:
    break
print(A, B)




### FIXED CODE ###

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

if K<=A:
  print(A-K, B)
elif A<K<=(A+B):
  print(0, B-(K-A))
else:
  print(0,0)
"""
for k in range(K):
  if A>0 and B!=0:
    A+=-1
  elif A==0 and B>0:
    B+=-1
  elif A==0 & B==0:
    break
print(A, B)
"""
### BUGGY CODE ###

from collections import deque

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

m = [[0 for _ in range(W)] for _ in range(H)]
root = []
for i in range(H):
    # m.append(list(map(lambda x: 0 if x=="#" else 1, input()))）
    for j, c in enumerate(input()):
        if c == "#":
            m[i][j] = 1
            root.append([i, j])

# print(m)
# print(root)

queue = deque(root)
def bfs():
    new_queue = deque([])
    while queue:
        p = queue.popleft()
        for i, j in ([-1, 0], [1, 0], [0, 1], [0, -1]):
            next_p = [p[0] + i, p[1] + j]
            if (0 <= next_p[0] < H) and (0 <= next_p[1] < W):
                if not m[next_p[0]][next_p[1]]:
                    m[next_p[0]][next_p[1]] = 1
                    new_queue.append(next_p)
    return new_queue

ans = 0
if len(root) != H*W:
    while queue:
        # print(queue)
        queue = bfs()
        ans += 1
    ans -= 1

print(ans)


### FIXED CODE ###

from collections import deque

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

m = [[0 for _ in range(W)] for _ in range(H)]
root = []
for i in range(H):
    # m.append(list(map(lambda x: 0 if x=="#" else 1, input()))）
    for j, c in enumerate(input()):
        if c == "#":
            m[i][j] = 1
            root.append((i, j))

# print(m)
# print(root)

queue = deque(root)
visited = deque(root)
visited_extend = visited.extend
ans = 0
while len(visited) < H*W:
    # print(visited)
    ans += 1
    new_queue = deque([])
    while queue:
        p = queue.popleft()
        for i, j in ([-1, 0], [1, 0], [0, 1], [0, -1]):
            next_p = (p[0] + i, p[1] + j)
            if (0 <= next_p[0] < H) and (0 <= next_p[1] < W):
                if not m[next_p[0]][next_p[1]]:
                    m[next_p[0]][next_p[1]] = 1
                    new_queue.append(next_p)
    visited_extend(new_queue)
    queue = new_queue
print(ans)
### BUGGY CODE ###

def main():
  s = input()
  t = input()
  sn, tn = len(s), len(t)
  dp = [[""]*(tn+1) for _ in range(sn+1)]
  for i, si in enumerate(s):
    di, di2 = dp[i], dp[i+1]
    for j, ti in enumerate(t):
      ji = j+1
      if si == ti:
        di2[ji] = di[j] + si
      else:
          if len(di[ji]) > len(di2[j]):
              di2[ji] = di[ji]
          else:
              di2[ji] = di2[j]
    dp[i+1] = di2
  print(dp[sn][tn])

if __name__ == "__main__":
  main()

### FIXED CODE ###

def main():
  s = input()
  t = input()
  sn, tn = len(s), len(t)
  dp = [[0]*(tn+1) for _ in range(sn+1)]
  for i, si in enumerate(s):
    di, di2 = dp[i], dp[i+1]
    for j, ti in enumerate(t):
      if si == ti:
        di2[j+1] = di[j] + 1
      else:
          if di[j+1] > di[j]:
              di2[j+1] = di[j+1]
          else:
              di2[j+1] = di2[j]
    dp[i+1] = di2
  ans = ""
  while sn and tn:
    di = dp[sn][tn]
    if di == dp[sn][tn-1]:
      tn -= 1
    elif di == dp[sn-1][tn]:
      sn -= 1
    else:
      tn -= 1
      sn -= 1
      ans += s[sn]
      
  print(ans[::-1])

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


import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return map(lambda x: x + d, A)
def ldec(A, d=1): return map(lambda x: x - d, A)

N = n1()
A = nn()

A.sort(reverse=True)

tbl = [A[0], A[1]]
cft = A[0]

for i in range(2, N):
    c = 0
    d = -1
    for j in range(0, len(tbl)):
        tmp = min(tbl[(j)%len(tbl)], tbl[(j+1)%len(tbl)])
        if tmp > c:
            c = tmp
            d = j

    cft += c
    tbl = tbl[:d+1] + [A[i]] + tbl[d+1:]
    #print(tbl, c, cft)

print(cft)

### FIXED CODE ###


import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return map(lambda x: x + d, A)
def ldec(A, d=1): return map(lambda x: x - d, A)

N = n1()
A = nn()

A.sort(reverse=True)

ans = 0
for i in range(1, N):
    j = i // 2
    ans += A[j]

print(ans)