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

n,W=map(int,input().split())
w_list=[]
v_list=[]
dp=[]
for i in range(n):
    w,v=map(int,input().split())
    w_list.append(w)
    v_list.append(v)
for i in range(n+1):
    dp_sub=[]
    for j in range(W+1):
        dp_sub.append(-1)
    dp.append(dp_sub)
def f(i,w):
    if dp[i][w]>=0:
        return dp[i][w]
    else:
        if i==n:
            return 0
        else:
            if w_list[i]<=w:
                a=max(f(i+1,w),f(i+1,w-w_list[i])+v_list[i])
            else:
                a=f(i+1,w)
            dp[i][w]=a
            return a
print(f(0,W))




### FIXED CODE ###

n,W=map(int,input().split())
w_list=[]
v_list=[]
dp=[]
for i in range(n):
    w,v=map(int,input().split())
    w_list.append(w)
    v_list.append(v)
for i in range(n):
    dp_sub=[]
    for j in range(W+1):
        dp_sub.append(-1)
    dp.append(dp_sub)
dp_sub=[]
for j in range(W+1):
    dp_sub.append(0)
dp.append(dp_sub)
for i in range(n):
    i_=n-1-i
    for j in range(W+1):
        if w_list[i_]<=j:
            dp[i_][j]=max(dp[i_+1][j],dp[i_+1][j-w_list[i_]]+v_list[i_])
        else:
            dp[i_][j]=dp[i_+1][j]
print(dp[0][W])
### BUGGY CODE ###

n =int(input())
a = list(int(i) for i in input().split())
ct = 0
for j in range(n):
 a2=[0]
 for i in a: 
  if (a2[-1]+i) == 0:ct += 1
  a2.append(a2[-1]+i)
 a.pop(0)
print(ct)

### FIXED CODE ###

from math import factorial
import sys
input = sys.stdin.readline
def ncr(n):
 if n <= 1:
  return 0
 elif n == 2:
  return 1
 else:
  return  (factorial(n) // 2) // factorial(n - 2)

n= int(input())
a = list(int(i) for i in input().split())
s = [0]
for i in range(n):
  s.append(s[i]+a[i])
s = sorted(s,reverse =True)
ans = 0
tmp = 1
for i in range(len(s)-1):
  if s[i] == s[i+1]:
   tmp += 1
  else:
   ans += ncr(tmp)
   tmp = 1
ans += ncr(tmp)
print(ans)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split(" ")))
a = 1
for i in range(n):
    a = a*l[i]
if a>10**18:
    print("-1")
else:
    print(a)

### FIXED CODE ###

import sys
n = int(input())
l = list(map(int, input().split(" ")))
l.sort()
a = 1
for i in range(n):
    if a <= 10**18:
        a = a*l[i]
    elif a > 10**18:
        print("-1")
        sys.exit()
if a > 10**18:
    print("-1")
else:
    print(a)
### BUGGY CODE ###

a,b = map(int,input().split())
#素数列挙
sosu = [2]
li = min(a,b)
for i in range(3,li+1):
    if all(i%j != 0 for j in sosu):
        sosu.append(i)

sosu.append(1)
ans = 0
for i in sosu:
    if a%i == 0 and b%i == 0:
        ans += 1

print(ans)


### FIXED CODE ###

a,b = map(int,input().split())
def gcd(x,y):
    if y == 0:
        return x
    return gcd(y,x%y)

n = gcd(a,b)
ans = 0
i = 2
while i*i <= n:
    if n%i == 0:
        while n%i == 0:
            n /= i
        ans += 1
    i += 1
if n != 1:
    ans += 1
print(ans+1)
### BUGGY CODE ###

# coding: utf-8
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            if L[i] + L[j] > L[k]:
                ans += 1
print(ans)

### FIXED CODE ###

# coding: utf-8
from bisect import bisect_left
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(N-2):
    a = L[i]
    for j in range(i+1, N-1):
        b = L[j]
        ans += bisect_left(L, a+b) - 1 - j
print(ans)
### BUGGY CODE ###

import copy
import queue


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

    q = queue.Queue()
    q.put((B, []))

    def bfs(arr, indexes):
        if len(arr) == 0:
            return indexes

        for i in range(len(arr)):
            if i+1 == arr[i]:
                _indexes = copy.copy(indexes)
                _indexes.append(i)
                q.put((arr[:i] + arr[i+1:], _indexes))

        return False

    while not q.empty():
        item = q.get()
        res = bfs(item[0], item[1])
        if res:
            for i in reversed(res):
                print(i+1)
            return
    print(-1)
    return


main()


### FIXED CODE ###

import copy

N = int(input())
B = [int(i) for i in input().split()]


def dfs(arr, indexes):
    if len(arr) == 0:
        return indexes

    for idx, elm in enumerate(arr):
        if idx+1 < elm:
            return False

    for i in reversed(range(len(arr))):
        if i+1 == arr[i]:
            _indexes = copy.copy(indexes)
            _indexes.append(i)
            res = dfs(arr[:i] + arr[i+1:], _indexes)
            if res:
                return res
    return False


res = dfs(B, [])
if res:
    for i in reversed(res):
        print(i+1)
else:
    print(-1)
### BUGGY CODE ###

n,a = map(int,input().split())
x = list(map(int,input().split()))
ans = 0
for i in range(2**n):
  y = []
  item = 0
  for j in range(n):
    if ((i >> j) & 1):
      y.append(x[j])
      item += 1
  if item != 0 and sum(y) == item*a:
    ans += 1
print(ans)

### FIXED CODE ###

n,a = map(int,input().split())
x = list(map(int,input().split()))
max_x = max(x)
dp = [[[0]*(n*max_x+1) for i in range(n+1)] for j in range(n+1)]
dp[0][0][0] = 1
for i in range(n+1):
  for j in range(n+1):
    for k in range(n*max_x+1):
      if i>=1 and k < x[i-1]:
        dp[i][j][k] = dp[i-1][j][k]
      elif i>=1 and j>= 1 and k>= x[i-1]:
        dp[i][j][k] = dp[i-1][j][k]+dp[i-1][j-1][k-x[i-1]]
      else:
        continue
ans = 0
for j in range(1,n+1):
  if j*a <= n*max_x+1:
    ans += dp[n][j][j*a]
print(ans)
### BUGGY CODE ###

from collections import Counter
import sys
input = sys.stdin.readline

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

c = Counter(a)
l = len(c)
cnt = 0
if k < l:
    i = -1
    for _ in range(l-k):
        cnt += c.most_common()[i][1]
        i -= 1
print(cnt)

### FIXED CODE ###

from collections import Counter
import heapq
n, k = map(int,input().split())
a = list(map(int,input().split()))
c = Counter(a)
heapc = list(c.values())
heapq.heapify(heapc)
l = len(c)
cnt = 0
if k < l:
    for _ in range(l-k):
        cnt += heapq.heappop(heapc)
print(cnt)
### BUGGY CODE ###

n,m = map(int,input().split())
a_ls = list(map(int, input().split()))
for i in range(m):
    b,c = map(int,input().split())
    for _ in range(b):
        a_ls.append(c)

a_ls.sort(reverse = True)
print(sum(a_ls[:n]))

### FIXED CODE ###

from collections import Counter
n,m = map(int,input().split())
a_ls = list(map(int, input().split()))
counter = Counter(a_ls)
for i in range(m):
    b,c = map(int,input().split())
    counter[c] += b

cards = sorted(counter.items(), key = lambda x:x[0], reverse=True)
rest = n
Sum = 0
for num, count in cards:
    if count < rest:
        Sum += num * count
        rest -= count
    else:
        Sum += rest * num
        break
print(Sum)
### BUGGY CODE ###

#!/usr/bin/env python3

def func(n):
    cnt = 0
    for x in range(1, 13):
        if x * x > n:
            break
        for y in range(1, 13):
            if y * y > n:
                break
            for z in range(1, 13):
                if z * z > n:
                    break
                if x * x + y * y + z * z + x * y + y * z + z * x == n:
                    cnt += 1
                    break
    return cnt


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

    for i in range(1, N + 1):
        print(func(i))


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

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

    ans = [0] * (N + 1)

    for x in range(1, 100):
        for y in range(1, 100):
            for z in range(1, 100):
                f = x * x + y * y + z * z + x * y + y * z + z * x
                if f < N + 1:
                    ans[f] += 1
    ans.remove(0)
    print('\n'.join(map(str, ans)))


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

from collections import defaultdict, deque
import sys
sys.setrecursionlimit(200000)
N, Q = map(int, input().split())

connection = defaultdict(list)
for i in range(N-1):
    a,b =  map(int, input().split())
    connection[a].append(b)
    connection[b].append(a)

operations = defaultdict(int)
for i in range(Q):
    p,q =  map(int, input().split())
    operations[p] += q

ans = defaultdict(int)

def func(node,p_node):
    ans[node] += operations[node]
    if p_node != 0:
        connection[node].remove(p_node)
    for c_node in connection[node]:
        ans[c_node] += ans[node]
        func(c_node, node)

func(1, 0)

print(' '.join(map(str, ans.values())))

### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)
from collections import deque

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

connection = [[] for i in range(N)]
for i in range(N-1):
    a,b =  map(int, input().split())
    connection[a-1].append(b)
    connection[b-1].append(a)

operations = [0] * N
for i in range(Q):
    p,q =  map(int, input().split())
    operations[p-1] += q

ans = [0] * N

stack = deque([1])
while len(stack)>0:
    node = stack.pop()
    ans[node-1] += operations[node-1]
    for node_c in connection[node-1]:
        connection[node_c-1].remove(node)
        ans[node_c-1] += ans[node-1]
        stack.append(node_c)

print(' '.join(map(str, ans)))
### BUGGY CODE ###

n,k = map(int, input().split())
a = list(map(int, input().split()))
setA = set(a)
countNum = {}
ans = 0
for i in setA:
    countNum[i] = a.count(i)
max_v = max(countNum.values())

keys = [k for k, v in countNum.items() if v == max_v]
for w, v in sorted(countNum.items(), key=lambda x: x[1]):
    if k < len(set(a)):
        while w in a:
            aIndex = a.index(w)
            a.pop(aIndex)
            ans+=1
print(ans)


### FIXED CODE ###

from collections import Counter

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

c = Counter(A)
d = sorted(c.values())
l = len(d)
print(sum(d[0:l-K]))
### BUGGY CODE ###

def main():
  H,W,K = map(int,input().split())
  import numpy as np
  from collections import deque
  ans = 10000
  S = np.array([list(map(int,list(input()))) for _ in range(H)])
  cum = [[0]*W for _ in range(H+1)]
  for j in range(W):
    for i in range(1,H+1):
      cum[i][j] = cum[i-1][j]+S[i-1][j]

  cum = np.array(cum)
  for i in range(2**(H-1)):
    q = deque([0])
    for h in range(H):
      if (i>>h)&1:
        q.append(h+1)
    q.append(H)
    q = list(q)
    p = deque()
    judge = False
    for a in range(len(q)-1):
      x = cum[q[a+1]]-cum[q[a]]
      if (x>K).any():
        judge = True
        break
      else:
        p.append(list(x))

    if judge:
      continue
    p = list(p)
    p.sort(key=lambda x:sum(x),reverse=True)
    t_a = len(q)-2
    n = len(p)
    l = [0]*n
    for w in range(W):
      for x,a in enumerate(p):
        y = l[x]+a[w]
        if y>K:
          t_a+=1
          l = [0]*n
          for z,b in enumerate(p):
            l[z] = b[w]
          break
        else:
          l[x]=y
    ans = min(ans,t_a)

  print(ans)
  
main()

### FIXED CODE ###

def main():
  H,W,K = map(int,input().split())
  import numpy as np
  from collections import deque
  ans = 10000
  S = np.array([list(map(int,list(input()))) for _ in range(H)])
  cum = [[0]*W for _ in range(H+1)]
  for j in range(W):
    for i in range(1,H+1):
      cum[i][j] = cum[i-1][j]+S[i-1][j]

  cum = np.array(cum)
  for i in range(2**(H-1)):
    j = 0
    q = deque([0])
    for h in range(H):
      if (i>>h)&1:
        q.append(h+1)
    q.append(H)
    t_a = len(q)-2
    if t_a>=ans:
      continue
    p = deque()
    judge = False
    for a in range(len(q)-1):
      x = cum[q[a+1]]-cum[q[a]]
      if (x>K).any():
        judge = True
        break
      else:
        p.append(list(x))

    if judge:
      continue
    n = len(p)
    l = [0]*n
    for w in range(W):
      y = [l[j]+p[j][w] for j in range(n)]
      if max(y)>K:
        t_a+=1
        l = [p[j][w] for j in range(n)]
        if t_a>=ans:
          judge = True
          break
      else:
        l = y
    if judge:
      continue
    ans = min(ans,t_a)

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

#!/usr/bin/env python3
 
import sys
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
#ABC138 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

s = input()
t = input()
n = len(s)
m = len(t)
f = [False]*26
f2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(n):
    f[alpha.index(s[i])] = True
for i in range(m):
    f2[alpha.index(t[i])] = True
for i in range(26):
    if not f[i] and f2[i]:
        print(-1)
        quit()
ans = 0
inde = s.index(t[0])
ans += inde+1
for i in range(1,m):
    s = s[inde+1:] + s[:inde+1]
    inde = s.index(t[i])
    ans += inde+1
print(ans)
### BUGGY CODE ###

def inpl(): return [int(i) for i in input().split()]
from collections import defaultdict

N,M = inpl()
edge = defaultdict(lambda: [])
for _ in range(M):
    a, b = inpl()
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

Qu = [0] 
ctr = 1
color = [0 for _ in range(N)]
color[0] = -1
while ctr < N:
    st = Qu.pop()
    for i in edge[st]:
        if color[st] == -color[i]:
            Qu.append(i)
            continue
        if color[i] == 0:
            color[i] = -color[st]
            Qu.append(i)
            ctr += 1
sumc = sum(color)
ans =(N**2-sumc**2)//4-M
for i in range(N):
    for j in edge[i]:
        if color[i] == color[j]:
            ans = N*(N-1)//2-M
            break
    else:
        continue
    break
print(ans)

### FIXED CODE ###

def inpl(): return [int(i) for i in input().split()]
from collections import defaultdict

N,M = inpl()
edge = defaultdict(lambda: [])
for _ in range(M):
    a, b = inpl()
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

Qu = [0] 
ctr = 1
color = [0 for _ in range(N)]
color[0] = -1
while ctr < N:
    st = Qu.pop()
    for i in edge[st]:
        if color[st] == -color[i]:
            continue
        if color[i] == 0:
            color[i] = -color[st]
            Qu.append(i)
            ctr += 1
sumc = sum(color)
ans =(N**2-sumc**2)//4-M
for i in range(N):
    for j in edge[i]:
        if color[i] == color[j]:
            ans = N*(N-1)//2-M
            break
    else:
        continue
    break
print(ans)
### BUGGY CODE ###

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

A = [2147483647] * n

def update(i, x):
    A[i] = x

def find(s, t):
    print(min(A[s:t+1]))


for i in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        update(x, y)
    else:
        find(x, y)

### FIXED CODE ###

import math

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

# make a list whose length is 2^i - 1.
n = 2 ** math.ceil(math.log(n, 2))
max_v = 2147483647

A = [max_v for i in range(2 * n - 1)]


def update(i, x):
    i += n - 1
    A[i] = x

    while i > 0:
        i = (i - 1) // 2
        A[i] = min(A[i * 2 + 1], A[i * 2 + 2])

def find(a, b, k, l, r):
    if r <= a or b <= l:
        return max_v
    elif a <= l and r <= b:
        return A[k]
    else:
        vl = find(a, b, k * 2 + 1, l, (l + r) // 2)
        vr = find(a, b, k * 2 + 2, (l + r) // 2, r)
        return min(vl, vr)


for i in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        update(x, y)
    else:
        ans = find(x, y + 1, 0, 0, n)
        print(ans)
### BUGGY CODE ###

from decimal import Decimal

def main():
    a, b, n = list(map(int, input().split()))
    
    floor_list = []
    
    for i in range(n+1):
        floor_1 = int(Decimal(a*i/b))
        floor_2 = a * int(Decimal(i/b))
        floor_list.append(floor_1 - floor_2)
    
    print(max(floor_list))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    a, b, n = list(map(int, input().split()))
    
    limit = 0
    if n >= b-1:
        limit = b-1
    else:
        limit = n
    
    floor_sub = int(limit * a / b) - int(limit / b) * a
    print(floor_sub)

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

n,W = map(int,input().split())
li = [list(map(int,input().split())) for _ in range(n)]

dp = [[0]*(W+1) for _ in range(n+1)]

for i in range(n):
    w = li[i][0]
    v = li[i][1]
    for k in range(W+1):
        if  w>k:
            dp[i+1][k] = dp[i][k]
            continue
        dp[i+1][k] = max(dp[i][k-w]+v,dp[i][k])
print(dp[n][W])

### FIXED CODE ###

n,W = map(int,input().split())
li = [list(map(int,input().split())) for _ in range(n)]

dp = [[0]*(W+1) for _ in range(n+1)]

for i in range(n):
    w = li[i][0]
    v = li[i][1]
    for k in range(W+1):
        if  w>k:
            dp[i+1][k] = dp[i][k]
            continue
        dp[i+1][k] = max(dp[i][k-w]+v,dp[i][k])
print(dp[n][W])
### BUGGY CODE ###

def getinputdata():
    array_result = []
    data = input()
    array_result.append(data.split(" "))
    flg = 1
    try:
        while flg:
            data = input()
            array_temp = []
            if(data != ""):
                array_result.append(data.split(" "))
                flg = 1
            else:
                flg = 0
    finally:
        return array_result

arr_data = getinputdata()
n = int(arr_data[0][0])
arr = [x for x  in arr_data[1]]

b = []
for i in range(0, n):
    b.append(arr[i])
    b.reverse()
        
print(" ".join(b))

### FIXED CODE ###

def getinputdata():

    array_result = []
    
    data = input()
    
    array_result.append(data.split(" "))

    flg = 1

    try:

        while flg:

            data = input()

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = 1

            else:

                flg = 0
    finally:

        return array_result

arr_data = getinputdata()

n = int(arr_data[0][0])
arr = arr_data[1]

arr1=[]
for i in range(n-1,-1,-2):
    arr1.append(arr[i])
    
sposi=0 if n % 2==0 else 1

for j in range(sposi,n,2):
    arr1.append(arr[j])

print(" ".join(arr1))
### BUGGY CODE ###

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

count = 0
while all(i%2 == 0 for i in A ):
    N = [i/2 for i in A]
    count += 1
print(count)

### FIXED CODE ###

n = input()
a = list(map(int, input().split()))
cnt = 0
while all(i%2==0 for i in a):
    a = [i/2 for i in a]
    cnt += 1
print(cnt)
### BUGGY CODE ###

m = int(input())
dc = [list(map(int, input().split())) for _ in range(m)]

def zero(n):
    return n - 1, "0"

def one(n):
    ret = 0
    while n // 10:
        q, r = divmod(n, 10)
        n = q + r
        ret += 10 * q
    return ret, "1" * n

def two(n):
    ret = 0
    q, r = divmod(n, 5)
    ret += 5 * q
    one_cnt, ones = one(q)
    ret += one_cnt
    return ret, ones + "2" * r

def three(n):
    ret = 0
    while n // 4:
        q, r = divmod(n, 4)
        n = q + r
        ret += 4 * q
    return ret, "3" * n

def four(n):
    ret = 0
    q, r = divmod(n, 3)
    ret += 3 * q
    three_cnt, threes = three(q)
    ret += three_cnt
    return ret, threes + "4" * r

def five(n):
    ret = 0
    q, r = divmod(n, 2)
    ret += 2 * q
    one_cnt, ones = one(q)
    ret += one_cnt
    return ret, ones + "5" * r

def six(n):
    ret = 0
    q, r = divmod(n, 2)
    ret += 2 * q
    three_cnt, threes = three(q)
    ret += three_cnt
    return ret, threes + "6" * r

def seven(n):
    ret = 0
    q, r = divmod(n, 2)
    ret += 2 * q
    five_cnt, fives = five(q)
    ret += five_cnt
    return ret, fives + "7" * r

def eight(n):
    ret = 0
    q, r = divmod(n, 2)
    ret += 2 * q
    one_cnt, ones = seven(q)
    ret += one_cnt
    return ret, ones + "8" * r

def nine(n):
    ret = 0
    while n // 2:
        q, r = divmod(n, 2)
        n = q + r
        ret += 2 * q
    return ret, "9" * n

new_dc = []
fs = [zero, one, two, three, four, five, six, seven, eight, nine]
for d, c in dc:
    cnt, s = fs[d](c)
    new_dc.append([cnt, s])

s = ""
cnt = 0
for d, c in new_dc:
    s += c
    cnt += d

while len(s) > 1:
    tmp = int(s[-1]) + int(s[-2])
    s = s[:-2] + str(tmp)
    cnt += 1

print(cnt)


### FIXED CODE ###

m = int(input())
dc = [list(map(int, input().split())) for _ in range(m)]

sm = 0
n = 0
for d, c in dc:
    sm += d * c
    n += c

ans = n - 1 + (sm - 1) // 9
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
s1 = s
s2 = s

flag = True

if s[0] == '#':
    flag = False
else:
    for i in range(n-1):
        if s[i] == '.' and s[i+1] == '#':
            s = s[i+1:]
            flag = False
            break
if flag == False:
    a = s.count('.')
else:
    a = 0

flag = True

if s1[n-1] == '.':
    flag = False
else:
    for i in range(n-1):
        if s1[n-i-1] == '#' and s1[n-i-2] == '.':
            s1 = s1[:n-i-1]
            flag = False
            break

if flag == False:
    b = s1.count('#')
else:
    b = 0

c = min(a,b)

for i in range(n-1):
    if s2[i] == '.' and s2[i+1] == '#':
        s3 = s[:i+1]
        s4 = s[i+1:]
        d = s3.count('#') + s4.count('.')
        c = min(c,d)


print(c)


### FIXED CODE ###

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

a = s.count('.')
b = 0

ans = a

for i in range(n):
    if s[i] == '#':
        b += 1
    else:
        a -= 1
    ans = min(ans,a+b)

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

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

table = []
for _ in range(H):
    table.append(["k"] + list(input()) + ["k"])
    
table = [["k"]*(W+2)] + table + [["k"]*(W+2)]

import queue
q = queue.Queue()

min_memo = [[None]*(W+2) for _ in range(H+2)]

all_cnt = 0
for y, r in enumerate(table):
    for x, c in enumerate(r):
        if c == "#":
            q.put([y,x,0])
            min_memo[y][x] = 0
            all_cnt += 1

            
while True:
    y, x, cnt = q.get()
    for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
        if table[y+dy][x+dx] == ".":
            if min_memo[y+dy][x+dx] == None:
                min_memo[y+dy][x+dx] = cnt+1
                q.put([y+dy, x+dx, cnt+1])
                all_cnt += 1
    if all_cnt == H*W:
        if cnt == 0:
            print(cnt)
        else:
            print(cnt+1)
        break

### FIXED CODE ###

from collections import deque

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

table = []
for _ in range(H):
    table.append(["k"] + list(input()) + ["k"])
    
table = [["k"]*(W+2)] + table + [["k"]*(W+2)]

q = deque()

min_memo = [[None]*(W+2) for _ in range(H+2)]

all_cnt = 0
for y, r in enumerate(table):
    for x, c in enumerate(r):
        if c == "#":
            q.append([y,x,0])
            min_memo[y][x] = 0
            all_cnt += 1

if all_cnt == H*W:
    print(0)
else:          
    while True:
        y, x, cnt = q.popleft()
        for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
            if table[y+dy][x+dx] == ".":
                if min_memo[y+dy][x+dx] == None:
                    min_memo[y+dy][x+dx] = cnt+1
                    q.append([y+dy, x+dx, cnt+1])
                    all_cnt += 1
        if all_cnt >= H*W:
            print(cnt+1)
            break
### BUGGY CODE ###

from itertools import product

N = int(input())

for h, n in product(range(1, 3501), range(1, 3501)):
    a = ((4 * h * n) - (N * n) - (N * h))
    if a > 0:
        if (N * h * n) % a == 0:
            w = (N * h * n) // a
            ans = [w, h, n]
            print(*ans)
            break

### FIXED CODE ###

N = int(input())

for h in range(1, 3501):
    for n in range(1, 3501):
        if ((4 * h * n) - (N * n) - (N * h)) > 0:
            if (N * h * n) % ((4 * h * n) - (N * n) - (N * h)) == 0:
                print(h, n, (N * h * n) // ((4 * h * n) - (N * n) - (N * h)))
                exit()