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

import fractions
K = int(input())
ans = 0
for i in range(1,K+1):
	for j in range(1,K+1):
		for n in range(1,K+1):
			tmp = fractions.gcd(i,j)
			ans += fractions.gcd(tmp,n)
print(ans)

### FIXED CODE ###

import math
K = int(input())
ans = 0
for i in range(1,K+1):
	for j in range(1,K+1):
		tmp = math.gcd(i,j)
		for n in range(1,K+1):
			ans += math.gcd(tmp,n)
print(ans)
### BUGGY CODE ###

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

def func(x): return (A * x) // B - A * (x // B)

ans = 0
for i in range(1, min(B, N)+1):
    ans = max(ans, func(i))
print(ans)

### FIXED CODE ###

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

def func(x): return (A * x) // B - A * (x // B)

ans = func(min(B - 1, N))
print(ans)
### BUGGY CODE ###

N, K = [int(i) for i in input().rstrip().split(' ')]
H = [int(i) for i in input().rstrip().split(' ')]
H.sort(reverse=True)
if len(H) <= K:print(0)
else:
    for hit in range(K):
        if len(H) == 0: break
        H.pop(0)
    print(sum(H))


### FIXED CODE ###

N, K = [int(i) for i in input().rstrip().split(' ')]
H = [int(i) for i in input().rstrip().split(' ')]
H.sort(reverse=True)
if len(H) <= K:print(0)
else:
    lst = [h for k, h in enumerate(H) if k >= K]
    print(sum(lst))
### BUGGY CODE ###

n = int(input())
A = [int(num) for num in input().split()]

for i in range(n):
  B = [0] + A[:i] + A[i+1:] + [0]
  ans = 0
  for j in range(n):
    ans += abs(B[j] - B[j+1])
  print(ans)

### FIXED CODE ###

n = int(input())
A = [0] + [int(num) for num in input().split()] + [0]

cost = 0
for j in range(n+1):
  cost += abs(A[j] - A[j+1])

for i in range(1, n+1):
  print(cost - abs(A[i] - A[i-1]) - abs(A[i+1] - A[i]) + abs(A[i+1] -A[i-1]))
### BUGGY CODE ###

N, M = map(int,input().split())
AB = []
for m in range(M):
    a,b = map(int,input().split())
    AB.append((a,b))

AB = sorted(AB)

first = []
for a,b in AB:
    if a == 1:
        first.append(b)
    else:
        break

AB = sorted(AB, key=lambda x:x[1], reverse=True)
sec = []
for a,b in AB:
    if b == N:
        sec.append(a)
    else:
        break

for f in first:
    if f in sec:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')


### FIXED CODE ###

import bisect

N, M = map(int,input().split())
AB = []
for m in range(M):
    a,b = map(int,input().split())
    AB.append((a,b))

AB = sorted(AB)

first = []
for a,b in AB:
    if a == 1:
        first.append(b)
    else:
        break

AB = sorted(AB, key=lambda x:x[1], reverse=True)
sec = []
for a,b in AB:
    if b == N:
        sec.append(a)
    else:
        break

if len(sec) >= 100:
    for f in first:
        ind = bisect.bisect_left(sec, f, 0, len(sec))
        if sec[ind] == f:
            print('POSSIBLE')
            exit()
else:
    for f in first:
        if f in sec:
            print('POSSIBLE')
            exit()

print('IMPOSSIBLE')
### BUGGY CODE ###




import fractions


mod = 1000000007

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def modpower(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod

def powerX(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 
    else            : return power(x, y//2)**2 * x

def power(x,y):
    return x ** y


def div(a, b):
    return mul(a, modpower(b, mod-2))

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

htgcd = fractions.gcd(H,T)
wtgcd = fractions.gcd(W,T)
n = htgcd * wtgcd

p = ( modpower(2, ( H // htgcd)) + modpower(2, (W // wtgcd)) - 3)
p += modpower(2 , fractions.gcd( H // htgcd , W // wtgcd))

#print (p,n)

ans = modpower(p , n)

print (ans)

### FIXED CODE ###




import fractions


mod = 1000000007

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def modpower(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod

def powerX(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 
    else            : return power(x, y//2)**2 * x

def power(x,y):
    return x ** y


def div(a, b):
    return mul(a, modpower(b, mod-2))

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

htgcd = fractions.gcd(H,T)
wtgcd = fractions.gcd(W,T)
n = htgcd * wtgcd

p = pow( 2, ( H // htgcd) ,mod ) +pow( 2, (W // wtgcd) , mod) - 3
p += pow(2,fractions.gcd( H // htgcd , W // wtgcd),mod)

#print (p,n)

ans = pow( p , n , mod )

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

N = int(input(""))
M = []
n = 0

for i in range(N):
    p = input("")
    if p not in M:
        M.append(p)
        n += 1

print(n)


### FIXED CODE ###

N = int(input(""))
M = []
n = 0

for i in range(N):
    p = input("")
    M.append(p)

Mm = list(set(M))

print(len(Mm))
### BUGGY CODE ###

from collections import defaultdict
from heapq import heappush, heappop
N = int(input())
dic = defaultdict(list)
toNum = {}
cnt = 0
L = N*(N-1)//2
for i in range(N):
  for j in range(i+1,N):
    toNum[(i,j)] = cnt
    cnt += 1
used = [True]*L
for i in range(N):
  inf = [int(c)-1 for c in input().split()]
  pa = min(i,inf[0])
  pb = max(i,inf[0])
  pnum = toNum[(pa,pb)]
  for j in range(1,N-1):
    a = min(i,inf[j])
    b = max(i,inf[j])
    num = toNum[(a,b)]
    used[num] = False
    dic[pnum]  += [num]
    pa = a
    pb = b
    pnum = num

hq = []
dist = [0]*L
for i in range(L):
  if used[i]:
    heappush(hq,(1,i))
if hq==[]:
  print(-1)
  import sys
  sys.exit()
cnt = 0
ans = 0
while hq:
  c, n = heappop(hq)
  if dist[n]>=c:
    continue
  dist[n] = c
  cnt += 1
  for m in dic[n]:
    if dist[m]>=c+1:
      continue
    if ans<c+1:
      ans = c+1
    heappush(hq,(c+1,m))
  if ans>L:
    print(-1)
    break
else:
  print(ans)


### FIXED CODE ###

N = int(input())
es = [[] for i in range(N)]
cand = set()
for i in range(N):
  es[i] = [int(i)-1 for i in input().split()][::-1]
def check(i):
  if es[i]==[]:
    return
  j = es[i][-1]
  if es[j]==[]:
    return
  if es[j][-1]==i:
    cand.add(i)
    cand.add(j)

for i in range(N):
  check(i)
day = 0
while cand:
  day += 1
  precand = cand.copy()
  cand = set()
  for i in precand:
    x = es[i].pop()
  for i in precand:
    check(i)
for i in range(N):
  if len(es[i])!=0:
    print(-1)
    break
else:
  print(day)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, K: int, h: "List[int]"):
    INF = 10000000000
    dp = [INF]* (N+1)
    dp[0] = 0
    dp[1] = abs(h[1]-h[0])
    for i in range(2,N):
        for t in range(1,K+1):
            if(i-t >= 0):
                dp[i] = min(dp[i], dp[i-t]+abs(h[i]-h[i-t]))
        # print(dp)
    print(dp[N-1])
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    h = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, K, h)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, K: int, h: "List[int]"):
    INF = 10000000000
    dp = [INF]* (N+1)
    dp[0] = 0
    dp[1] = abs(h[1]-h[0])
    for i in range(2,N):
        for t in range(1,K+1):
            if(i-t >= 0):
                dp[i] = min(dp[i], dp[i-t]+abs(h[i]-h[i-t]))
        # print(dp)
    print(dp[N-1])
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    h = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, K, h)

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

import sys,bisect,math
sys.setrecursionlimit(15000)

s = sys.stdin.readline().rstrip()
cum = [0]*(len(s)+1)#cumulative sum
import collections
d = collections.defaultdict(int)
d[0] = 1
ret = 0
dig = 1
for i in range(len(s))[::-1]:
    cum[i]=(int(s[i])*dig+cum[i+1])%2019
    dig *= 10
    #cum[i+1]=int(s[i:])%2019
    if cum[i] in d:
        ret += d[cum[i]]
    d[cum[i]] += 1
#print(d,cum,ret)
print(ret)

### FIXED CODE ###

# n = int(sys.stdin.readline())
import sys,bisect,math
sys.setrecursionlimit(15000)

s = sys.stdin.readline().rstrip()
cum = [0]*(len(s)+1)#cumulative sum
import collections
d = collections.defaultdict(int)
d[0] = 1
ret = 0
dig = 1
for i in range(len(s))[::-1]:
    cum[i]=(int(s[i])*dig+cum[i+1])%2019
    dig = (dig*10)%2019
    #cum[i+1]=int(s[i:])%2019
    if cum[i] in d:
        ret += d[cum[i]]
    d[cum[i]] += 1
#print(d,cum,ret)
print(ret)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(4100000)

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

ans_cand = []

def dfs(a_i, b_i, ans, time):
    if time == K:
        ans_cand.append(ans)
        return 0

    if time > K:
        ans_cand.append(ans - 1)
        return 0

    if a_i < N:
        dfs(a_i + 1, b_i, ans + 1, time + A[a_i])
    if b_i < M:
        dfs(a_i, b_i + 1, ans + 1, time + B[b_i])
    return 0


dfs(0, 0, 0, 0)

print(max(ans_cand))


### FIXED CODE ###

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

a, b = [0], [0]
for i in range(N):
    a.append(a[i] + A[i])
for i in range(M):
    b.append(b[i] + B[i])

ans = 0
j = M

for i in range(N + 1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i + j)

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

# coding: utf-8

n, k = map(int, input().rstrip().split())    # 2 <= n <= 10^5, 1 <= k <= 100
h = list(map(int, input().rstrip().split()))

dp = [0] * 100010
for i in range(1, n):
    c = float('inf')
    for j in range(1, k + 1):
        if j > i:
            break
        else:
            c_ = dp[i - j] + abs(h[i - j] - h[i])
            if c_ < c:
                c = c_
    dp[i] = c
print(dp[i])


### FIXED CODE ###

# coding: utf-8

def f(n, k, h):
    dp = [0 for _ in range(n)]
    for i in range(1, n):
        js = max(i - k, 0)
        dp[i] = min(dp[j] + abs(h[i] - h[j]) \
            for j in range(js, i))
        # print(dp)
    return(dp[i])

n, k = map(int, input().rstrip().split())    # 2 <= n <= 10^5, 1 <= k <= 100
h = list(map(int, input().rstrip().split()))

print(f(n, k, h))
### BUGGY CODE ###

import math
from functools import reduce


def gcd(*numbers):
    return reduce(math.gcd, numbers)


def main():
    K = int(input())

    total = 0
    for a in range(1, K + 1):
        for b in range(1, K + 1):
            for c in range(1, K + 1):
                total += gcd(a, b, c)

    print(total)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
from collections import defaultdict
from functools import reduce

memo = defaultdict(int)


def gcd(*numbers):
    return reduce(math.gcd, numbers)


def gcd_with_memo(x, y):
    key = tuple(sorted([x, y]))
    if memo[key] != 0:
        value = memo[key]
    else:
        value = math.gcd(x, y)
        memo[key] = value
    return value


# def main():
#     K = int(input())
#     total = 0
#     for a in range(1, K + 1):
#         for b in range(1, K + 1):
#             for c in range(1, K + 1):
#                 total += gcd_with_memo(a, gcd_with_memo(b, c))
#     print(total)

def main():
    K = int(input())

    total = 0

    # 1
    for i in range(1, K + 1):
        total += i

    # print(total)

    # 2 kind
    for i in range(1, K + 1):
        for j in range(i + 1, K + 1):
            total += 6 * gcd(i, j)

    # print(total)

    # 3kind
    for i in range(1, K + 1):
        for j in range(i+1, K + 1):
            for k in range(j+1, K + 1):
                total += 6 * gcd(i, j, k)

    print(total)


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

import sys
from itertools import groupby, chain
def input(): return sys.stdin.readline().rstrip()


def trans(l_2d):
    return [list(x) for x in zip(*l_2d)]


def lamp(arr):
    count = [[] for i in range(len(arr))]
    for i in range(len(arr)):
        lamps = []
        for key, value in groupby(arr[i]):
            n = int(len(list(value)))
            if key == '.':
                lamps += [n]*n
            else:
                lamps += [0]*n
        count[i] = lamps
    return count


def main():
    h, w = map(int, input().split())
    s = [list(input()) for i in range(h)]
    tate = list(chain.from_iterable(lamp(s)))
    yoko = list(chain.from_iterable(trans(lamp(trans(s)))))
    ans=0
    for a,b in zip(tate,yoko):
        ans=max(ans,a+b-1)
    print(ans)
        


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from itertools import groupby, chain
def input(): return sys.stdin.readline().rstrip()


def trans(l_2d):
    return [list(x) for x in zip(*l_2d)]


def lamp(arr):
    count = [[] for i in range(len(arr))]
    for i in range(len(arr)):
        lamps = []
        for key, value in groupby(arr[i]):
            n = int(len(list(value)))
            if key == '.':
                lamps += [n]*n
            else:
                lamps += [0]*n
        count[i] = lamps
    return count


def main():
    h, w = map(int, input().split())
    s = [list(input()) for i in range(h)]
    tate = lamp(s)
    yoko = lamp(trans(s))
    ans=0
    for hh in range(h):
        for ww in range(w):
            ans=max(ans,tate[hh][ww]+yoko[ww][hh]-1)
    print(ans)
        


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

from collections import deque
def bfs(si):
  q = deque()
  q.append([si,-1])
  used.add(si)
  while len(q)>0:
    prvi, prvcol = q.popleft()
    col = 1 
    for i in g[prvi]:
      if i in used:continue
      if col == prvcol: col += 1
      cols[eds.index(sorted([i,prvi]))] = col
      q.append([i,col])
      used.add(i)
      col += 1

N = int(input())
g = {i:[] for i in range(N)}
eds = []
for _ in range(N-1):
  a,b = map(int,input().split())
  eds.append([a-1,b-1])
  g[a-1].append(b-1)
  g[b-1].append(a-1)

cols = [-1 for _ in range(N-1)]
used = set([])
bfs(0)
print(max(cols))
[print(col) for col in cols]

### FIXED CODE ###

from collections import deque
def bfs(si):
  q = deque()
  q.append([si,-1])
  used.add(si)
  while len(q)>0:
    prvi, prvcol = q.popleft()
    col = 1 
    for i in g[prvi]:
      if i in used:continue
      if col == prvcol: col += 1
      cols[eds[str(min(prvi,i))+'-'+str(max(prvi,i))]] = col
      q.append([i,col])
      used.add(i)
      col += 1

N = int(input())
g = {i:[] for i in range(N)}
eds = {}
for i in range(N-1):
  a,b = map(int,input().split())
  eds[str(a-1)+'-'+str(b-1)] = i
  g[a-1].append(b-1)
  g[b-1].append(a-1)

used = set([])
cols = [-1 for _ in range(N-1)]  
bfs(0)
print(max(cols))
[print(col) for col in cols]
### BUGGY CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp= [0]*n

for i in range(1,n):
  tmp = float('inf')
  for j in range(1,min(i+1,k+1)):    
    d = dp[i-j] + abs(h[i] - h[i-j])    
    tmp = min(tmp,d)  
  dp[i] = tmp
  
print(dp[-1])  

### FIXED CODE ###

# TLE
n,k = map(int,input().split())
h = list(map(int,input().split()))
dp= [0]*n

for i in range(1,n):
  tmp = float('inf')
  for j in range(1,min(i+1,k+1)):    
    d = dp[i-j] + abs(h[i] - h[i-j])    
    tmp = min(tmp,d)  
  dp[i] = tmp
  
print(dp[-1])
### BUGGY CODE ###

s=list(input())
# ABCACCBABCBCAABCB
n=len(s)
ans=0
na,nb,nc=0,0,0

i=0
while i<n:
  if s[i]=='A':
    na+=1
    i+=1
  elif s[i]=='B' and i<n-1 and s[i+1]=='C' and na>0:
    ans+=na
    s[i-na]='B'
    s[i+1-na]='c'
    for j in range(i+2-na,i+2):
      s[j]='A'
    i+=2
  else:
    na=0
    i+=1
print(ans)


### FIXED CODE ###

def main(s):
  n=len(s)
  ans=0
  na=0
  i=0
  while i<n:
    if s[i]=='A':
      na+=1
      i+=1
    elif s[i]=='B' and i<n-1 and s[i+1]=='C' and na>0:
      ans+=na
      i+=2
    else:
      na=0
      i+=1
  print(ans)
if __name__=='__main__':
  s=list(input())
  main(s)
### BUGGY CODE ###

import sys,math,collections,itertools
input = sys.stdin.readline

s = input().rstrip()
K = int(input())
ls = len(s)
cs = collections.deque()
for i in range(ls):
    for j in range(i+1,ls+1):
        cs.append(s[i:j])
os = sorted(cs)
count = 0
lis = []
for i in os:
    if i not in lis:
        lis.append(i)
        count +=1
    else:
        continue
    if count == K:
        print(i)
        exit()
    

### FIXED CODE ###

import sys,collections
input = sys.stdin.readline

s = input().rstrip()
K = int(input())
ls = len(s)
cs = collections.deque()
for i in range(ls):
    for j in range(i+1,i+1+K):
        cs.append(s[i:j])
os = sorted(cs)
count = 0
lis = []
for i in os:
    if i not in lis:
        lis.append(i)
        count +=1
    else:
        continue
    if count == K:
        print(i)
        exit()
### BUGGY CODE ###

import sys

n,m = map(int, input().split())
adj_list = [[] for i in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    adj_list[l-1].append((r-1, d))
    adj_list[r-1].append((l-1, -d))
def search(start, goal):
    q = [[start]]
    q_d = [0]
    d_set = set()
    while(len(q) > 0):
        path = q.pop(0)
        dist = q_d.pop(0)
        w = path[len(path) - 1]
        if w == goal:
            d_set.add(dist)
            if len(d_set) > 1:
                return False
        else:
            for x in adj_list[w]:
                if x[0] not in path:
                    new_path = path[:]
                    new_path.append(x[0])
                    q.append(new_path)
                    q_d.append(dist + x[1])
    return True
for i in range(n):
    for j in range(i + 1):
        if not search(i, j):
            print('No')
            exit(0)
print('Yes')


### FIXED CODE ###

import sys
from collections import deque

n,m = map(int, input().split())
adj_list = [[] for i in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    adj_list[l-1].append((r-1, d))
    adj_list[r-1].append((l-1, -d))
def search(start, dist_all):
    q = deque([start])
    dist_all[i] = 0
    while(len(q) > 0):
        w = q.popleft()
        for x in adj_list[w]:
            if dist_all[x[0]] is None:
                dist_all[x[0]] = dist_all[w] + x[1]
                q.append(x[0])
            elif dist_all[x[0]] != dist_all[w] + x[1]:
                return False
    return True
dist_all = [None for i in range(n)]
for i in range(n):
    if dist_all[i] is None:
        if not search(i, dist_all):
            print('No')
            exit(0)
print('Yes')
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
Acum = 0
mod = 10 ** 9 + 7


dp = [0]*(K+1)
dp[0] = 1

for a in A:
    Acum += a
    newDP = [0]*(K+1)
    for i in range(min(Acum, K) + 1):
        if i == 0:
            newDP[i] = 1
            continue
        dp[i] += dp[i - 1]
        newDP[i] = dp[i]
        if i > a:
            newDP[i] -= dp[i - a - 1]
        newDP[i] %= mod
    dp = newDP[::]

ans = dp[K]
print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
Acum = 0
mod = 10 ** 9 + 7


dp = [0]*(K+1)
dp[0] = 1

for a in A:
    Acum += a
    newDP = [0]*(K+1)
    for i in range(min(Acum, K) + 1):
        if i == 0:
            newDP[i] = 1
            continue
        dp[i] += dp[i - 1]
        newDP[i] = dp[i]
        if i > a:
            newDP[i] -= dp[i - a - 1]
        newDP[i] %= mod
    dp = newDP[::]

ans = dp[K]
print(ans)
### BUGGY CODE ###

import sys
from collections import deque
import numpy as np

sys.setrecursionlimit(10**9)

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

# 最短距離で行って通ったところ以外を黒マスにする
# . : 0, # : 1
S = np.zeros((H + 2, W + 2), dtype='int')
S[0, :] = 1
S[-1, :] = 1
S[:, 0] = 1
S[:, -1] = 1

cost = np.zeros((H + 2, W + 2), dtype='int')
cost[:, :] = -1

subset = S[1:-1, 1:-1]
for h in range(H):
    s = list(input())
    subset[h:] = np.array([0 if i == '.' else 1 for i in s], dtype='i')

q = deque()
qq = deque()
q.append((1, 1))

i = 0
while len(q) > 0:
    while len(q) > 0:
        x, y = q.popleft()
        cost[x, y] = i
        if x == H and y == W:
            break
        for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nx = x + dx
            ny = y + dy
            if S[nx, ny] == 0 and cost[nx, ny] == -1:
                qq.append((nx, ny))
    q = qq
    qq = deque()
    i += 1

if cost[H, W] == -1:
    print(-1)
    exit()

ans = (H + 2) * (W + 2) - (S == 1).sum() - cost[H, W] - 1
print(ans)


### FIXED CODE ###

import sys
from collections import deque
import numpy as np

sys.setrecursionlimit(10**9)

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

# 最短距離で行って通ったところ以外を黒マスにする
# . : 0, # : 1
S = np.zeros((H + 2, W + 2), dtype='int')
S[0, :] = 1
S[-1, :] = 1
S[:, 0] = 1
S[:, -1] = 1

cost = np.zeros((H + 2, W + 2), dtype='int')
cost[:, :] = -1

subset = S[1:-1, 1:-1]
for h in range(H):
    s = list(input())
    subset[h:] = np.array([0 if i == '.' else 1 for i in s], dtype='i')

dd = ((-1, 0), (1, 0), (0, -1), (0, 1))
q = deque([(1, 1)])
cost[1, 1] = 0

while q:
    x, y = q.popleft()
    for dx, dy in dd:
        nx = x + dx
        ny = y + dy
        if S[nx, ny] == 0 and cost[nx, ny] == -1:
            cost[nx, ny] = cost[x, y] + 1
            q.append((nx, ny))

if cost[H, W] == -1:
    print(-1)
    exit()

ans = (H + 2) * (W + 2) - (S == 1).sum() - cost[H, W] - 1
print(ans)
### BUGGY CODE ###

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

ans = 0
for i in range(N-K+1):
    n = 0
    for j in range(K):
        n += 1/2.0*(P[i+j]+1)
    if ans < n:
        ans = n

print(ans)


### FIXED CODE ###

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

cml_sum = [(P[0]+1)/2.0]
for i in range(1, N):
    cml_sum.append(cml_sum[i-1] + (P[i]+1)/2.0)

ans = cml_sum[K-1]
for i in range(N-K):
    target = cml_sum[i+K] - cml_sum[i]
    if ans < target:
        ans = target

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

s = input()
result = 0

for i in range(int(s)//2019):
  b = (i+1) * 2019
  result += s.count(str(b))

print(result)

### FIXED CODE ###

s = input()[::-1]

# 0が2019個からなるリスト。modを保管する
cnts = [0] * 2019
cnts[0] = 1
mod_num = 0
d = 1

for c in s:
  t = d * int(c)
  mod_num += t
  mod_num %= 2019
  cnts[mod_num] += 1
  d *= 10
  d %= 2019

result = 0
for cnt in cnts:
  result += cnt * (cnt - 1) // 2

print(result)
### BUGGY CODE ###

K,S= list(map(int, input().split()))
ans=0
for i in range(K+1):
    for j in range(i+1):
        if i+j>S:
            break
        for k in range(j+1):
            if i+j+k==S:
                if i==j==k:
                    ans+=1
                elif i==j or j==k:
                    ans+=3
                else:
                    ans+=6
                break
print(ans)

### FIXED CODE ###

K,S= list(map(int, input().split()))
ans=0
for i in range(S//3,K+1):
    for j in range(i+1):
        if i+j>S:
            break
        if i+j*2<S:
            continue
        if S-i-j<=j:
            k=S-i-j
            if i==j==k:
                ans+=1
            elif i==j or j==k:
                ans+=3
            else:
                ans+=6
print(ans)
### BUGGY CODE ###

n,a,b=map(int,input().split())
full=[]
while len(full)<n:
    for _ in range(a):
        full.append("b")
    for _ in range(b):
        full.append("r")
if len(full)>n:
    del full[n:-1]
print(full.count("b"))


### FIXED CODE ###

N, A, B = map(int, input().split())
 
m = N%(A+B)
 
print((N//(A+B))*A + (A if m > A else m))