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

def main():
  import sys
  input=sys.stdin.readline
  h,w,k=map(int,input().split())
  H=range(h)
  W=range(w)
  dp=[[[0]*4 for j in W] for i in H]
  for _ in range(k):
    r,c,v=map(int,input().split())
    dp[r-1][c-1][0]=v
  if dp[0][0][0]!=0:
    dp[0][0][1]=dp[0][0][0]
    dp[0][0][0]=0
  for y in H:
    for x in W:
      v=dp[y][x][0]
      dp[y][x][0]=0
      for i in range(4):
        if 0<x:
          if dp[y][x][i]<dp[y][x-1][i]:
            dp[y][x][i]=dp[y][x-1][i]
          if 0<i and v!=0 and dp[y][x][i]<dp[y][x-1][i-1]+v:
            dp[y][x][i]=dp[y][x-1][i-1]+v
        if 0<y:
          if dp[y][x][0]<dp[y-1][x][i]:
            dp[y][x][0]=dp[y-1][x][i]
          if v!=0 and dp[y][x][1]<dp[y-1][x][i]+v:
            dp[y][x][1]=dp[y-1][x][i]+v
  print(max(dp[h-1][w-1]))
main()

### FIXED CODE ###

def main():
  import sys
  input=sys.stdin.readline
  h,w,k=map(int,input().split())
  H=range(h)
  W=range(w)
  dp=[[[0]*w for j in H] for i in range(4)]
  for _ in range(k):
    r,c,v=map(int,input().split())
    dp[0][r-1][c-1]=v
  if dp[0][0][0]!=0:
    dp[1][0][0]=dp[0][0][0]
    dp[0][0][0]=0
  for y in H:
    for x in W:
      v=dp[0][y][x]
      dp[0][y][x]=0
      for i in range(4):
        if 0<x:
          if dp[i][y][x]<dp[i][y][x-1]:
            dp[i][y][x]=dp[i][y][x-1]
          if 0<i and v!=0 and dp[i][y][x]<dp[i-1][y][x-1]+v:
            dp[i][y][x]=dp[i-1][y][x-1]+v
        if 0<y:
          if dp[0][y][x]<dp[i][y-1][x]:
            dp[0][y][x]=dp[i][y-1][x]
          if v!=0 and dp[1][y][x]<dp[i][y-1][x]+v:
            dp[1][y][x]=dp[i][y-1][x]+v
  print(max([dp[i][h-1][w-1] for i in range(4)]))
main()
### BUGGY CODE ###

n,m=map(int,input().split())
x=sorted([int(i) for i in input().split()])
if n>=m:
    print(0)
else:
    r=[]
    for i in range(m-1):
        r.append(x[i+1]-x[i])
    for i in range(n-1):
        r.remove(max(r))
    print(sum(r))


### FIXED CODE ###

n,m=map(int,input().split())
x=sorted([int(i) for i in input().split()])
if n>=m:
    print(0)
else:
    r=[]
    for i in range(m-1):
        r.append(x[i+1]-x[i])
    r.sort()
    if n!=1:
        print(sum(r[:-n+1]))
    else:
        print(sum(r))
### BUGGY CODE ###

N, Z, W = list(map(int, input().split()))
A = [W] + list(map(int, input().split()))

S = set(A)
GX = {s:[None]*N + [abs(A[N]-s)] for s in S}
GY = {s:[None]*N + [abs(A[N]-s)] for s in S}
minGX = {s:10**10 for s in S}
maxGY = {s:0      for s in S}

for k in range(N-1, -1, -1):
    for s in S:
        GX[s][k] = max(GY[A[k]][k+1], maxGY[A[k]])
        GY[s][k] = min(GX[A[k]][k+1], minGX[A[k]])

    for s in S:
        maxGY[s] = max(GY[s][k+1], maxGY[s])
        minGX[s] = min(GX[s][k+1], minGX[s])

print(GX[W][0])

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, Z, W = list(map(int, input().split()))
A = [W] + list(map(int, input().split())) # A[0]=W, A[i]=ai

GX = [None]*N # GX[i] := YがA[i] を取った直後の状況から到達しうる最大のスコア
GY = [None]*N # GY[i] := XがA[i] を取った直後の状況から到達しうる最小のスコア
minGX = 10**20
maxGY = 0

for k in range(N-1, -1, -1):
    GX[k] = max(abs(A[k]-A[N]), maxGY)
    GY[k] = min(abs(A[k]-A[N]), minGX)
    minGX = min(minGX, GX[k])
    maxGY = max(maxGY, GY[k])

print(GX[0])
### BUGGY CODE ###

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

cnt=0
for i in range(1,n+1):
  if min(l[:i])==l[i-1]:
    cnt+=1
  
    
print(cnt)

### FIXED CODE ###

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

cnt=0
num=max(l)

for i in l:
  num=min(num,i)
  if num==i:
    cnt+=1
    
print(cnt)
### BUGGY CODE ###

import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if is_prime[i]:
            for j in range(i*2, n+1, i):
                is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]

def primeFactorization(n, primes):
    ans = []
    temp = n
    for p in primes:
        while temp%p == 0:
            ans.append(p)
            temp //= p
    if temp > 1:
        ans.append(temp)
    return collections.Counter(ans)

def resolve():
    N = I()
    A = LI()

    # pairwiseについて、Aを走査して今までに出てきた素因数を記録すればわかる
    primes = sieve(max(A))
    factor = set()
    is_pc = True
    for i in A:
        pf = primeFactorization(i, primes)
        for j in pf.keys():
            if j in factor:
                is_pc = False
                break
            factor.add(j)
        if not is_pc:
            break
    
    is_sc = False
    if not is_pc:
        gcd = A[0]
        for i in A[1:]:
            gcd = math.gcd(i, gcd)
        if gcd == 1:
            is_sc = True

    if is_pc:
        print('pairwise coprime')
    elif is_sc:
        print('setwise coprime')
    else:
        print('not coprime')

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def primeFactorization(n):
    D = list(range(n + 1))
    for i in range(2, int(n ** 0.5) + 1):
        if D[i] == i:
            for j in range(i, n + 1, i):
                if D[j] == j:
                    D[j] = i
    return D

def resolve():
    N = I()
    A = LI()

    # pairwise判定
    is_pc = True
    D = primeFactorization(max(A))
    pf = set()
    for i in A:
        tmp = i
        cnt = collections.Counter()
        while tmp != 1:
            cnt[D[tmp]] += 1
            tmp //= D[tmp]
        fact = set(cnt.keys())
        if pf & fact:
            is_pc = False
            break
        else:
            pf |= fact
    
    # setwise判定
    is_sc = False
    if not is_pc:
        gcd = A[0]
        for i in A[1:]:
            gcd = math.gcd(i, gcd)
        if gcd == 1:
            is_sc = True

    if is_pc:
        print('pairwise coprime')
    elif is_sc:
        print('setwise coprime')
    else:
        print('not coprime')

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

from collections import deque

N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
W = N - V

def isOk(n):
    if n < P:
        return True
    b = A[n]

    D = [max(0, a - b) for a in A][P - 1:]
    D = deque([d for d in D if d > 0])
    cnt = 0

    while D:
        cnt += 1
        E = []
        for _ in range(min(W, len(D))):
            E.append(D.pop())
        for e in E:
            e -= 1
            if e > 0:
                D.append(e)

    return cnt <= M

ok = -1
ng = N
while ng - ok > 1:
    mid = (ng + ok) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(ng)

### FIXED CODE ###

N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
W = N - V

def isOk(n):
    if n < P:
        return True
    b = A[n]

    D = [max(0, a - b) for a in A][P - 1:]
    cnt = -(-(sum(D) - W) // W) + 1

    return max(max(D), cnt) <= M

ok = -1
ng = N
while ng - ok > 1:
    mid = (ng + ok) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(ng)
### BUGGY CODE ###

import sys
import bisect
from collections import deque
sys.setrecursionlimit(4100000)
input = sys.stdin.readline


def main():
    N = int(input())
    A = list(map(int, input().split()))
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)
        edge[v].append(u)
    LIS = [A[0]]
    dist = [-1]*N
    dist[0] = 0
    ans = [0] * N
    ans[0] = 1
    queue = deque()
    queue_append = queue.append
    queue_append((0,LIS))
    while queue:
        now, LIS_tmp = queue.popleft()
        d = dist[now]
        for i in edge[now]:
            tmp = LIS_tmp[:]
            tmp_append = tmp.append
            A_now = A[i]
            if dist[i] > -1:
                continue
            dist[i] = d + 1
            if A_now > tmp[-1]:
                tmp_append(A_now)
            else:
                tmp[bisect.bisect_left(tmp, A_now)] = A_now
            queue_append((i,tmp))
            ans[i] = len(tmp)

    for i in range(N):
        print(ans[i])

    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import bisect
from collections import deque
sys.setrecursionlimit(4100000)
input = sys.stdin.readline

def main():
    N = int(input())
    A = list(map(int, input().split()))
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)
        edge[v].append(u)

    ans = [0] * (N + 1)
    LIS = [-1]
    
    def dfs(v, p = N):
        if A[v] > LIS[-1]:
            LIS.append(A[v])
            ans[v] = ans[p] + 1
            for u in edge[v]:
                if u == p:
                    continue
                dfs(u,v)
            LIS.pop()
        else:
            ans[v] = ans[p]
            idx = bisect.bisect_left(LIS, A[v])
            old = LIS[idx]
            LIS[idx] = A[v]
            for u in edge[v]:
                if u == p:
                    continue
                dfs(u,v)
            LIS[idx] = old
    dfs(0)
    for i in range(N):
        print(ans[i])

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

N = int(input())
a = list(map(int,input().split()))
count = [0]*(10**5+1)
ans = 0
for X in range(10**5+2):
  for i in range(N):
    if X == a[i] or X == a[i]+1 or X == a[i]-1:
      count[X] += 1
ans = max(count)
print(ans)

### FIXED CODE ###

import collections
N = int(input())
a = list(map(int,input().split()))
count = []
ans = 0
for i in range(N):
  count.append(a[i]-1)
  count.append(a[i])
  count.append(a[i]+1)
ans = max(collections.Counter(count).values())
print(ans)
### BUGGY CODE ###

s = str(input())
l = len(s)
while '01' in s or '10' in s:
    s = s.replace('01', '').replace('10', '')
print(l - len(s))


### FIXED CODE ###

s = str(input())
z = sum([str(x)=='0' for x in s])
o = sum([str(x)=='1' for x in s])
print(2*min(z, o))
### BUGGY CODE ###

n, m, k = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))

C = [0]
D = [0]
for a in A:
    C.append(C[-1] + a)
for b in B:
    D.append(D[-1] + b)

p = n
for i in range(n + 1):
    if C[i] > k:
        p = i - 1
        break

_max = 0
keep = 0
for i in range(p, -1, -1):
    for j in range(keep, m + 1):
        if C[i] + D[j] > k:
            keep = j - 1
            break
        elif _max < i + j:
            _max = i + j
print(_max)

### FIXED CODE ###

n, m, k = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))

C = [0]
D = [0]
for a in A:
    C.append(C[-1] + a)
for b in B:
    D.append(D[-1] + b)

p = n
for i in range(n + 1):
    if C[i] > k:
        p = i - 1
        break

_max = p
keep = 0
for i in range(p, -1, -1):
    for j in range(keep, m + 1):
        if C[i] + D[j] > k:
            keep = j - 1
            break
        elif _max < i + j:
            _max = i + j
    if j == m:
        break
print(_max)
### BUGGY CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K, *A = map(int, read().split())

    A = [(a - 1) % K for a in A]

    csum = [0] * (N + 1)
    for i in range(N):
        csum[i + 1] = (csum[i] + A[i]) % K

    indices = [[] for _ in range(K)]
    for i in range(N + 1):
        indices[csum[i]].append(i)

    ans = 0
    for vec in indices:
        right = 0
        for left in range(len(vec)):
            while right + 1 < len(vec) and vec[right + 1] - vec[left] < K:
                right += 1

            ans += right - left
            if left == right:
                right += 1

    print(ans)

    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import defaultdict

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K, *A = map(int, read().split())

    A = [(a - 1) % K for a in A]

    csum = [0] * (N + 1)
    for i in range(N):
        csum[i + 1] = (csum[i] + A[i]) % K

    indices = defaultdict(list)
    for i in range(N + 1):
        indices[csum[i]].append(i)

    ans = 0
    for vec in indices.values():
        right = 0
        for left in range(len(vec)):
            while right + 1 < len(vec) and vec[right + 1] - vec[left] < K:
                right += 1

            ans += right - left
            if left == right:
                right += 1

    print(ans)

    return


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

s=str(input())
s=list(s)
q=int(input())
temp=0
for i in range(q):
  temp=str(input())
  temp=list(temp)
  if temp[0]=="1":
    s=s[::-1]
  else:
    if temp[2]=="1":
      s.insert(0,temp[4])
    else:
      s.append(temp[4])
print("".join(s))

### FIXED CODE ###

s=str(input())
s=list(s)
q=int(input())
sb=[0]*(q+1)
sa=[0]*(q+1)
sbi=0
sai=0
ta=0
for i in range(q):
  temp=str(input())
  temp=list(temp)
  if temp[0]=="1":
    ta=ta+1
  else:
    if (temp[2]=="1" and ta%2==0) or (temp[2]=="2" and ta%2!=0):
      sb[sbi]=temp[4]
      sbi=sbi+1
    else:
      sa[sai]=temp[4]
      sai=sai+1
lsb=sb.index(0)
lsa=sa.index(0)
sb.reverse()
ans=sb[len(sb)-lsb:len(sb)]+s+sa[0:lsa]
if ta%2!=0:
  ans.reverse()
print("".join(ans))
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
MOD = 1000000007
sum_n = 0
for i in range(N):
  for j in range(i+1,N):
    sum_n = sum_n + a[i] * a[j]
    
print(sum_n % MOD)

### FIXED CODE ###

N = int(input())
b = list(map(int, input().split()))
MOD = 1000000007
sum_n = 0
a = []
for i in b:
  a.append(i%MOD)
sum_sum = sum(a[1:])
for i in range(N):

  sum_n = (sum_n + (a[i] * sum_sum) % MOD) % MOD
  if i+1 < N:
  	sum_sum = sum_sum - a[i+1]
print(sum_n % MOD)
### BUGGY CODE ###

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

S=0
ans =-1

if 1 in A:    
    for i in range(1,N+1):
        if i in A[S::]:
            S=A.index(i,S)
            ans =N-i
        else:
            break

print(ans)
    

### FIXED CODE ###

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

S=0
ans =-1
x=1

if 1 in A:
    ans = 0
    for i in A:
        if i ==x :
            x += 1
    ans = N - x +1
            
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
m, j = 1, 0
for i in range(n):
    m*=a[i]
    if i>=k:
        n1 = m//a[i]
        m//=a[j]
        j+=1
        if n1<m: print('Yes')
        else: print('No')

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
    if i>=k:
      if a[i]>a[i-k]: print('Yes')
      else: print('No')
### BUGGY CODE ###

N = int(input())
max = 0
for j in range(N+1):
    sum = 0
    N_list = list(str(j))
    for i in N_list:
        sum += int(i)
    if max < sum:
        max = sum

print (max)

### FIXED CODE ###

N_list = [int (i) for i in list(input())]
digit = 0
dflag = False
max = 0
for i in N_list:
    max += i

for i in N_list:
    if i == 9:
        dflag = True
    else:
        break

    digit += 1

if dflag:
    N_list[digit-1] -=1
    for i in range(digit, len(N_list)):
        N_list[i] = 9

else:
    N_list[digit] -=1
    for i in range(digit+1, len(N_list)):
        N_list[i] = 9

sum = 0

for i in N_list:
    sum += i

if sum > max:
    max = sum
print (max)
### BUGGY CODE ###

k, s = map(int, input().split())
n = k + 1
count = 0
for i in range(n):
    for j in range(n):
        for l in range(n):
            if i + j + l == s:
                count += 1
print(count)

### FIXED CODE ###

k, s = map(int, input().split())
n = k + 1
count = 0
for i in range(n):
    for j in range(n):
        if ( 0 <= s - i - j <= k):
          count += 1
print(count)
### BUGGY CODE ###

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

Query = [input() for i in range(Q)]

for q in Query:
    query = q.split(' ')
    if q == '1':
        S = S[::-1]
    elif query[0]=='2':
        if query[1]=='1':
            S = query[2] + S
        elif query[1]=='2':
            S = S + query[2]
        
print(S)

### FIXED CODE ###

import collections

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

Query = [input() for i in range(Q)]

deq = collections.deque(S)

flg = False
for q in Query:
    query = q.split(' ')
    if query[0]=='1':
        flg = not flg

    elif query[0] == '2':
        if query[1] == '1':
            if flg == True:
                deq.append(query[2])
            else:
                deq.appendleft(query[2])
        else:
            if flg==True:
               deq.appendleft(query[2])
            else:
               deq.append(query[2]) 
if flg == True:
    deq.reverse()        
print(''.join(deq))
### BUGGY CODE ###

s = input()
k = int(input())
l = []
for i in range(1,len(s)+1):
    for j in range(len(s)-i+1):
        l.append(s[j:j+i])


l = list(set(l))
l.sort()
print(l[k-1])

### FIXED CODE ###

s = input()
k = int(input())
l = []
for i in range(1,k+1):
    for j in range(len(s)-i+1):
        l.append(s[j:j+i])


l = list(set(l))
l.sort()
print(l[k-1])
### BUGGY CODE ###

import copy
import collections
n = int(input())
a = list(map(int, input().split()))
c = collections.Counter(a)
total = 0
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

for v in c.values():
    if v >= 2:
        total += cmb(v, 2)
# print(total)

for ai in a:
    if c[ai] >= 2:
        # print('Y')
        ans = total - cmb(c[ai], 2)
        if c[ai] - 1 >= 2:
            ans += cmb(c[ai] - 1, 2)
    else:
        ans = total
    print(ans)
    # ans = 0
    # temp = copy.copy(c)
    # temp[ai] = temp[ai] - 1

    # for v in temp.values():
    #     # print(v)
    #     if v >= 2:
    #         ans += cmb(v, 2)
    # print(ans)
# temp = copy.copy(c)
# temp[1] = temp[1] - 1
# print(c)
# print(temp)

### FIXED CODE ###

import copy
import collections
n = int(input())
a = list(map(int, input().split()))
c = collections.Counter(a)
total = 0
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
    
for v in c.values():
    if v >= 2:
        total += cmb(v, 2)
# print(total)

for ai in a:
    if c[ai] >= 2:
        # print('Y')
        ans = total - cmb(c[ai], 2)
        if c[ai] - 1 >= 2:
            ans += cmb(c[ai] - 1, 2)
    else:
        ans = total
    print(ans)
    # ans = 0
    # temp = copy.copy(c)
    # temp[ai] = temp[ai] - 1

    # for v in temp.values():
    #     # print(v)
    #     if v >= 2:
    #         ans += cmb(v, 2)
    # print(ans)
# temp = copy.copy(c)
# temp[1] = temp[1] - 1
# print(c)
# print(temp)
### BUGGY CODE ###

# Splitting Pile
N = int(input())
a = list(map(int, input().split()))

s = [abs(sum(a[:i+1])-sum(a[i+1:])) for i in range(N-2)] 
if len(a)==2:
    print(abs(a[0]-a[1]))
else:
    print(min(s))

### FIXED CODE ###

# Splitting Pile
N = int(input())
a = list(map(int, input().split()))
 
s = [sum(a[1:]) - a[0]]
for i in range(N-2):
    s.append( s[i]- 2*a[i+1] )
a = list(map(abs, s))
print(min(a))
### BUGGY CODE ###

import queue
import copy
 
def ngoin(bo,now):
    return 0 <= now[0] and now[0] < len(bo) and 0 <= now[1] and now[1] < len(bo[0])
 
def minido(bo,si,sj):
    tb = [[False for i in range(len(bo[0]))] for j in range(len(bo))]
    q = queue.Queue()
    q.put([si,sj,0])
    ret = 0
    while not q.empty():
        now = q.get()
        ret = now[2]
        if tb[now[0]][now[1]]:
            continue
        tb[now[0]][now[1]] = True
        tb[now[0]][now[1]] = True
        if ngoin(bo,[now[0]-1,now[1]]):
            if bo[now[0]-1][now[1]]:
                q.put([now[0]-1,now[1],now[2]+1])
        if ngoin(bo,[now[0],now[1]+1]):
            if bo[now[0]][now[1]+1]:
                q.put([now[0],now[1]+1,now[2]+1])
        if ngoin(bo,[now[0]+1,now[1]]):
            if bo[now[0]+1][now[1]]:
                q.put([now[0]+1,now[1],now[2]+1])
        if ngoin(bo,[now[0],now[1]-1]):
            if bo[now[0]][now[1]-1]:
                q.put([now[0],now[1]-1,now[2]+1])
    return ret
            
 
h,w = map(int,input().split())
bo = [[True if x == '.' else False for x in input()] for i in range(h)]
grap = [[float('inf') for i in range(h*w)] for j in range(h*w)]
ans = 0
for i in range(h*w):
    grap[i][i] = 0
for si in range(h):
    for sj in range(w):
        if not bo[si][sj]:
            continue
        ans = max(ans,minido(bo,si,sj)-1)
                
print(ans)


### FIXED CODE ###

import queue
import copy
 
def ngoin(bo,now):
    return 0 <= now[0] and now[0] < len(bo) and 0 <= now[1] and now[1] < len(bo[0])
 
def minido(bo,si,sj):
    tb = [[False for i in range(len(bo[0]))] for j in range(len(bo))]
    q = queue.Queue()
    q.put([si,sj,0])
    tb[si][sj] = True
    ret = 0
    while not q.empty():
        now = q.get()
        ret = now[2]
        if ngoin(bo,[now[0]-1,now[1]]):
            if bo[now[0]-1][now[1]] and not tb[now[0]-1][now[1]]:
                q.put([now[0]-1,now[1],now[2]+1])
                tb[now[0]-1][now[1]] = True
                
        if ngoin(bo,[now[0],now[1]+1]):
            if bo[now[0]][now[1]+1] and not tb[now[0]][now[1]+1]:
                q.put([now[0],now[1]+1,now[2]+1])
                tb[now[0]][now[1]+1] = True
                
        if ngoin(bo,[now[0]+1,now[1]]):
            if bo[now[0]+1][now[1]] and not tb[now[0]+1][now[1]]:
                q.put([now[0]+1,now[1],now[2]+1])
                tb[now[0]+1][now[1]] = True
                
        if ngoin(bo,[now[0],now[1]-1]):
            if bo[now[0]][now[1]-1] and not tb[now[0]][now[1]-1]:
                q.put([now[0],now[1]-1,now[2]+1])
                tb[now[0]][now[1]-1] = True
    return ret
            
 
h,w = map(int,input().split())
bo = [[True if x == '.' else False for x in input()] for i in range(h)]
grap = [[float('inf') for i in range(h*w)] for j in range(h*w)]
ans = 0
for i in range(h*w):
    grap[i][i] = 0
for si in range(h):
    for sj in range(w):
        if not bo[si][sj]:
            continue
        ans = max(ans,minido(bo,si,sj))
                
print(ans)
### BUGGY CODE ###

n, a, b = [int(i) for i in input().split()]
s = []
for _ in range(n//(a+b)+1):
    s += [1 for _ in range(a)] + [0 for _ in range(b)]
print(sum(s[:n]))


### FIXED CODE ###


n, a, b = [int(i) for i in input().split()]
sy = n // (a+b)
am = n % (a+b)
print(sy*a + min(am, a))