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

h, w, k = map(int, input().split())
s = [list(map(int, list(input()))) for _ in range(h)]
result = []
if h*w<=k:
    result.append(0)
else:
    for i in range(2**(h-1)):
        checker, num, p = 0, i ,[0]
        for _ in range(h):
            p.append(p[-1]+num%2)
            checker += num%2
            num >>= 1
        x = 0
        c = [0 for _ in range(checker+1)]
        for j in range(w):
            num = i
            nex = [0 for _ in range(checker+1)]
            for m in range(h):
                nex[p[m]] += s[m][j]
            if max(nex) > k:
                x = float('inf')
                break            
            for m in range(checker+1):
                c[m] += nex[m]
                if c[m]>k:
                    c = nex
                    x += 1
                    break
        result.append(checker+x)
print(min(result))

### FIXED CODE ###

h, w, k = map(int, input().split())
s = [list(map(int, list(input()))) for _ in range(h)]
result = []
if h*w<=k:
    result.append(0)
else:
    for i in range(2**(h-1)):
        checker, num = 0, i
        while num > 0:
            checker += num%2
            num >>= 1
        x = 0
        c = [0 for _ in range(checker+1)]
        
        num = i
        p = 0
        nex = [0 for _ in range(checker+1)]
        for m in range(h):
            nex[p] += s[m][0]
            p += num%2
            num = num >> 1
        if max(nex) > k:
            x = float('inf')
            continue

        if all(nex[m]+c[m] <= k for m in range(checker+1)):
            c = [c[I]+nex[I] for I in range(checker+1)]
        else:
            x += 1

        for j in range(1, w):
            num = i
            p = 0
            nex = [0 for _ in range(checker+1)]
            for m in range(h):
                nex[p] += s[m][j]
                p += num%2
                num = num >> 1
            if max(nex) > k:
                x = float('inf')
                break            
            
            if all(nex[m]+c[m] <= k for m in range(checker+1)):
                c = [c[I]+nex[I] for I in range(checker+1)]
            else:
                x += 1
                c = nex
        result.append(checker+x)
print(min(result))
### BUGGY CODE ###

r,g,b,n = map(int,input().split())
res = 0
for rr in range(0, n // r + 1):
    for gg in range(0, (n - rr) // g + 1):
        if (n - r*rr - g*gg) < 0:
            break
        if (n - r*rr - g*gg) % b == 0:
            res += 1
print(res)


### FIXED CODE ###

import math
r,g,b,n = map(int, input().split())
count = 0
r,g,b = sorted((r,g,b), reverse=True)
for x in range( math.ceil((n / r)) + 1):
    for y in range( math.ceil( (n - (r*x) ) / g) + 1):
        if (n - (r*x) - (y*g)) < 0:
            break
        if ((n - (r*x) - (g * y)) % b) == 0:
            count = count + 1
print(count)
### BUGGY CODE ###

import bisect

N, M = map(int, input().split())
B = [int(x) for x in input().split()]
A = sorted(B)

# print(A)
for i in range(M):
    value = A.pop(N-1)
    value = value//2
    bisect.insort_left(A, value)
# print(A)
ans = sum(A)
print(ans)


### FIXED CODE ###

# 他参加者の回答を参考にした．現在のAtcoderでのpythonのバージョンではdequeにinsertできないので（全ての値に-1をかけて）heapqがよさそう？
import bisect
N, M = map(int, input().split())
B = [int(x) for x in input().split()]
A = sorted(B, reverse=True)
ite = 0
for i in range(M):
    A[ite] //= 2
    if ite < N - 1:
        if A[ite] < A[ite + 1] and A[0] < A[ite+1]:
            ite += 1
        else:
            A = sorted(A, reverse=True)
            ite = 0
    else:
        A = sorted(A, reverse=True)
        ite = 0

ans = sum(A)
print(ans)
### BUGGY CODE ###

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

l=[[] for x in range(n)]
v=[[10**7 for x in range(2**n)] for y in range(2)]
v[0][0]=0

#print(v)
for i in range(m):
  a,b = map(int,input().split())
  c = [int(x) for x in input().split()]
  s = 0
  for j in c:
    s += 2**(j-1)
  for j in c:
    l[j-1].append([a,s])

for i in range(n):
  for j in range(2**n):
    v[(i+1)%2][j] = v[i%2][j]
  for j in range(2**n):
    for k in l[i]:
      if v[i%2][j] != 10**7:
          v[(i+1)%2][j|k[1]] = min(v[(i+1)%2][j|k[1]], v[i%2][j]+k[0])

print(v[(i+1)%2][2**n-1] if v[(i+1)%2][2**n-1] != 10**7 else -1)


### FIXED CODE ###

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

f=[10**7 for x in range(2**n)]
for i in range(m):
  a,b = map(int,input().split())
  c = [int(x) for x in input().split()]
  s = 0
  for j in c:
    s += 2**(j-1)
  f[s]=min(f[s],a)

l=[]
for i in range(2**n):
  if f[i] != 10**7:
    l.append([i,f[i]])

v=[10**7 for x in range(2**n)]
v[0]=0

for s,a in l:
  for j in range(2**n):
    if v[j] != 10**7:
      v[j|s] = min(v[j|s], v[j]+a)

print(v[2**n-1] if v[2**n-1] != 10**7 else -1)
### BUGGY CODE ###

def prog(x):
    n = len(x)
    y = [int(i * 10**9) for i in x]
    #y

    def count25(n):
        two = five = 0
        while n % 2 == 0:
            two += 1
            n //= 2
        while n % 5 == 0:
            five += 1
            n //= 5
        return two, five

    two = [0] * n
    five = [0] * n
    for i in range(n):
        two[i], five[i] = count25(y[i])
    count = 0
    for i in range(n - 1):
        two_i = 18 - two[i]
        five_i = 18 - five[i]
        for j in range(i + 1, n):
            #if min(two[i] + two[j], five[i] + five[j]) >= 18:
            if two[j] >= two_i and five[j] >= five_i:
                #print(min(two1,two2) + min(five1, five2), two1, two2, five1, five2)
                #print(y[i] * y[j], (y[i] * y[j]) / 10**18)
                #print(y[i] / 10**9, y[j] / 10**9)
                #print('=================')
                count += 1
    print(count)

n = int(input())
x = [0] * n
x = [float(input()) for i in range(n)]
prog(x)



### FIXED CODE ###

def conv(s):
    if s.find('.') == -1:
        s += '.'
    s = s.rstrip('0')
    t = len(s) - s.find('.') - 1
    a = int(s.replace('.', ''))
    if a == 0:
        return (0, 0)
    x, y = -t, -t
    while a % 5 == 0:
        x += 1
        a //= 5
    while a % 2 == 0:
        y += 1
        a //= 2
    return (x, y)


N, *A = open(0).read().split()
N = int(N)

d = {}
for a in A:
    t = conv(a)
    d.setdefault(t, 0)
    d[t] += 1

result = 0
xs = list(d.keys())
for i in range(len(xs)):
    x, y = xs[i]
    t = d[xs[i]]
    if x >= 0 and y >= 0:
        result += t * (t - 1) // 2
    for j in range(i + 1, len(xs)):
        m, n = xs[j]
        if x + m >= 0 and y + n >= 0:
            result += t * d[xs[j]]
print(result)
### BUGGY CODE ###

from collections import Counter


def d(P):
    c = Counter()
    i = 2
    while (P > 1):
        if P % i == 0:
            c.update([i])
            P //= i
            i -= 1
        i += 1
    return c


def solve(N, P):
    c = d(P)
    ans = 1
    for k in [k for k, v in c.items() if v >= N]:
        ans *= k ** (c[k] // N)
    return ans


if __name__ == "__main__":
    N, X = tuple(map(int, input().split(" ")))
    print(solve(N, X))


### FIXED CODE ###

from collections import Counter


def d(P):
    c = Counter()
    i = 2
    while (P > 1):
        if P % i == 0:
            c.update([i])
            P //= i
            i -= 1
        i += 1
        if i > P ** 0.5:
            c.update([P])
            break
    return c


def solve(N, P):
    c = d(P)
    ans = 1
    for k in [k for k, v in c.items() if v >= N]:
        ans *= k ** (c[k] // N)
    return ans

if __name__ == "__main__":
    N, X = tuple(map(int, input().split(" ")))
    print(solve(N, X))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)

S, T = map(int, input().split())

def f7(seq):
    seen = set()
    seen_add = seen.add
    return [ x for x in seq if x not in seen and not seen_add(x)]

ans = 0
queue = [S]
visit = [False]*(N+1)
while len(queue) > 0:
    queuetemp = []
    for now in queue:
        if visit[now]:
            continue
        visit[now] = True
        queuenext = graph[now][:]
        for _ in range(2):
            nextqueue = []
            for next in queuenext:
                nextqueue.extend(graph[next])
            queuenext = f7(nextqueue)
        queuetemp.extend(queuenext)
    queue = f7(queuetemp)
    if visit[T]:
        break
    ans += 1



if visit[T]:
    print(ans)
else:
    print(-1)


### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)

S, T = map(int, input().split())

inf = 10**6
ans = [[inf, inf, inf] for i in range(N+1)]

q = deque([S])
ans[S][0] = 0
while q:
    now = q.popleft()
    for next in graph[now]:
        flag = 0
        for i in range(3):
            if ans[now][i] != inf:
                if ans[next][(i+1)%3] > ans[now][i] + 1:
                    flag = 1
                    ans[next][(i+1)%3] = ans[now][i] + 1
        if flag == 1:
            q.append(next)

if ans[T][0] == inf:
    print(-1)
else:
    print(ans[T][0]//3)
### BUGGY CODE ###

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

ans = 0
for i in range(len(a)):
    for j in range(i+1,len(a)):
        ans += a[i]*a[j]

print(ans%(10**9+7))


### FIXED CODE ###

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

s = sum(a)
aa = [a[i]*a[i] for i in range(n)]
s2 = sum(aa)

print((s**2 - s2) //2%(10**9+7))
### BUGGY CODE ###

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

for i in range(1,N + 1):
  ans = 0
  for j in A:
    if i == j:
      ans += 1
    
  print(ans)

### FIXED CODE ###

import collections

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

for i in range(1, N + 1):
  print(a[i])
### BUGGY CODE ###

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

whites = []
grid = []
for i in range(H):
    row = list(input(""))
    grid.append(row)

    for idx, r in enumerate(row):
        if r == ".":
            whites.append([i,idx])

c = 0
while len(whites) > 0:
    c += 1

    next_whites = []
    delete_whites = []
    while len(whites) > 0:
        w = whites.pop()

        top = w[0]-1
        bottom = w[0]+1
        left = w[1]-1
        right = w[1]+1

        flag = False
        if top >= 0:
            if grid[top][w[1]] == "#":
                flag = True
        if bottom < H:
            if grid[bottom][w[1]] == "#":
                flag = True
        if left >= 0:
            if grid[w[0]][left] == "#":
                flag = True
        if right < W:
            if grid[w[0]][right] == "#":
                flag = True

        if not flag:
            next_whites.append(w)
        else:
            delete_whites.append(w)

    for w in delete_whites:
        grid[w[0]][w[1]] = "#"

    whites = next_whites

print(c)


### FIXED CODE ###

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

grid = []
blacks = []
for i in range(H):
    row = list(input(""))
    grid.append(row)

    for idx, r in enumerate(row):
        if r == "#":
            blacks.append((i, idx))

c = 0
while len(blacks) > 0:
    c += 1

    new_blacks = []
    for b in blacks:
        top = b[0] - 1
        bottom = b[0] + 1
        left = b[1] - 1
        right = b[1] + 1

        if top >= 0:
            if grid[top][b[1]] == ".":
                grid[top][b[1]] = "#"
                new_blacks.append((top, b[1]))
        if bottom < H:
            if grid[bottom][b[1]] == ".":
                grid[bottom][b[1]] = "#"
                new_blacks.append((bottom, b[1]))
        if left >= 0:
            if grid[b[0]][left] == ".":
                grid[b[0]][left] = "#"
                new_blacks.append((b[0], left))
        if right < W:
            if grid[b[0]][right] == ".":
                grid[b[0]][right] = "#"
                new_blacks.append((b[0], right))

    blacks = new_blacks

print(c - 1)
### BUGGY CODE ###

def main():
    n, m = map(int, input().split())
    a_list = list(map(int, input().split()))
    sorted_a_list = sorted(a_list, reverse=True)

    for _ in range(m):
        sorted_a_list[0] = int(sorted_a_list[0]/2)
        sorted_a_list = sorted(sorted_a_list, reverse=True)

    print(sum(sorted_a_list))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import heapq


def main():
    n, m = map(int, input().split())
    a_list = list(map(lambda x: -int(x), input().split()))

    heapq.heapify(a_list)
    for _ in range(m):
        a = heapq.heappop(a_list)
        heapq.heappush(a_list, -(-a // 2))

    print(-sum(a_list))


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

N = int(input())

def calc(n):
    ans = 0
    for x in range(1,n+1):
        a = x**2
        if a>=n:
            break
        for y in range(1,1+n):
            b = y**2
            if b>=n:
                break
            for z in range(1,1+n):
                c = z**2
                if c>=n:
                    break
                f = a+b+c+x*y+y*z+z*x
                if f>n:
                    break
                if f==n:
                    ans += 1
    return ans

for i in range(N):
    print(calc(i+1))

### FIXED CODE ###

N = int(input())

def calc(n):
    ans = [0 for i in range(n+1)]
    for x in range(1,n+1):
        a = x**2
        if a>=n:
            break
        for y in range(1,1+n):
            b = y**2
            if b>=n:
                break
            for z in range(1,1+n):
                c = z**2
                if c>=n:
                    break
                f = a+b+c+x*y+y*z+z*x
                if f>n:
                    break
                ans[f]+=1
    return ans

res = calc(N)
for i in range(N):
    print(res[i+1])
### BUGGY CODE ###

#ceilevenoddformula
import math
import bisect
import copy
import time
from collections import Counter
from itertools import combinations
#map(int,input().split())
#int(x) for x in input().split()
n,m=map(int,input().split())
d={i:set() for i in range(1,n+1)}
for i in range(m):
	x,y=map(int,input().split())
	d[x].add(y)
	d[y].add(x)


vis=set()
for u,v in d.items():
	d[u]=list(v)
count=0
que=[]
for i in range(1,n+1):
	if i not in vis:
		que=[]
		c=1
		vis.add(i)
		que.append(i)
		while len(que)!=0:
			x=que.pop(0)
			for j in d[x]:
				if j not in vis:
					vis.add(j)
					c+=1
					que.append(j)
		count=max(c,count)

print(count)













































### FIXED CODE ###

#ceilevenoddformula
import math
import bisect
import copy
import time
from collections import Counter
from itertools import combinations
#map(int,input().split())
#int(x) for x in input().split()
n,m=map(int,input().split())
d={i:set() for i in range(1,n+1)}
for i in range(m):
	x,y=map(int,input().split())
	d[x].add(y)
	d[y].add(x)


vis={i:False for i in range(1,n+1)}
for u,v in d.items():
	d[u]=list(v)
count=0
que=[]
for i in range(1,n+1):
	if not vis[i]:
		que=[]
		c=1
		vis[i]=True
		que.append(i)
		while len(que)!=0:
			x=que.pop(0)
			for j in d[x]:
				if not vis[j]:
					vis[j]=True
					c+=1
					que.append(j)
		count=max(c,count)

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

import sys
input = sys.stdin.readline

n,k = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)

def isOk(x):
    cost = 0
    for a, f in zip(A,F):
        eatable = x//f
        if eatable >= a:
            continue
        cost += a - eatable
    if cost <= k:
        return True
    return False

left = -1
right = A[-1] * F[0]
while left+1 < right:
    mid = (left+right)//2
    if isOk(mid):
        right = mid
    else:
        left = mid
print(right)

### FIXED CODE ###

n,k = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)

def isOk(x):
    cost = 0
    for a, f in zip(A,F):
        eatable = x//f
        if eatable >= a:
            continue
        cost += a - eatable
    if cost <= k:
        return True
    return False

left = -1
right = A[-1] * F[0]
while left+1 < right:
    # mid = int(left + (right-left)//2)
    mid = (left+right)//2
    if isOk(mid):
        right = mid
    else:
        left = mid
print(right)
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
tmp=[]
change=[]
for i in range(m):
    q,r=map(int,input().split())
    tmp.append([r,q])
tmp.sort(reverse=True)

for i in range(0,m):
    t=0
    cnt=0
    while t<tmp[i][1]:
        change.append(tmp[i][0])
        t+=1
        cnt+=1
    i+=cnt

for i in range(0,min(n,len(change))):
    a[i]=max(a[i],change[i])

print(sum(a))


### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
rep=[]
for i in range(m):
    b,c=map(int,input().split())
    rep.append([c,b])
rep.sort(reverse=True)
Card=[0]*n
cnt=0
fg=0
while fg<n and cnt<m:
    tt=0
    while tt<rep[cnt][1] and fg+tt <n :
        Card[fg+tt]=rep[cnt][0]
        tt+=1
    fg+=tt
    cnt+=1

a.sort()
ans=[]
for i in range(n):
    ans.append(max(a[i],Card[i]))

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

def resolve():
    N, M = map(int, input().split())
    H = list(map(int, input().split()))

    A = [[]] * N
    for i in range(M):
        pp, ss = map(int, input().split())
        ss -= 1
        pp -= 1
        A[pp] = A[pp] + [ss]
        A[ss] = A[ss] + [pp]

    # print(A)

    ans = 0
    for j in range(N):
        now = H[j]
        # print(now, A[j], ans)
        if not A[j]:
            ans += 1
            continue

        tmp = 0
        for road in A[j]:
            if (now > H[road]):
                tmp += 1

        if tmp == len(A[j]):
            ans += 1

    print(ans)


resolve()

### FIXED CODE ###

def resolve():
    n, m = map(int, input().split())
    hhh = list(map(int, input().split()))
    nice = [1] * n

    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        ha = hhh[a]
        hb = hhh[b]
        if ha <= hb:
            nice[a] = False
        if ha >= hb:
            nice[b] = False

    print(sum(nice))


resolve()
### BUGGY CODE ###

import sys
from operator import itemgetter

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()

co = []
for i in range(n):
    co.append(na())

co.sort(key=itemgetter(1))
for i in range(n):
    co[i][1] = i

# print(co)
ft = [0] * (n + 5)

co.sort(key=itemgetter(0), reverse=True)

ups = [0] * n
downs = [0] * n

def addfenwick(ft, i, v):
    if v == 0 or i < 0: return
    i += 1
    while i < len(ft):
        ft[i] += v
        i += i&-i

def sumfenwick(ft, i):
    s = 0
    i += 1
    while i > 0:
        s += ft[i]
        i -= i&-i
    return s

for i in range(n):
    c = co[i]
    downs[n-1-i] = sumfenwick(ft, c[1])
    ups[n-1-i] = i - downs[n-1-i]
    addfenwick(ft, c[1], 1)

ft = [0] * (n+5)
co = co[::-1]

ans = 0
mod = 998244353
for i in range(n):
    c = co[i]
    d = sumfenwick(ft, c[1])
    u = i - d

    # print(d, u, ups[i], downs[i])
    ans += (pow(2, d, mod)-1) * (pow(2, ups[i], mod)-1) * pow(2, u+downs[i], mod)
    ans += (pow(2, u, mod)-1) * (pow(2, downs[i], mod)-1) * pow(2, d+ups[i], mod)
    ans -= (pow(2, d, mod)-1) * (pow(2, ups[i], mod)-1) * (pow(2, downs[i], mod)-1) * (pow(2, u, mod)-1)
    ans += pow(2, n-1, mod)
    addfenwick(ft, c[1], 1)

ans %= mod
if ans < 0:
    ans += mod
print(ans)



### FIXED CODE ###

import sys
from operator import itemgetter

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()

co = []
for i in range(n):
    co.append(na())

co.sort(key=itemgetter(1))
for i in range(n):
    co[i][1] = i

# print(co)
ft = [0] * (n + 5)

co.sort(key=itemgetter(0), reverse=True)

ups = [0] * n
downs = [0] * n

def addfenwick(ft, i, v):
    if v == 0 or i < 0: return
    i += 1
    while i < len(ft):
        ft[i] += v
        i += i&-i

def sumfenwick(ft, i):
    s = 0
    i += 1
    while i > 0:
        s += ft[i]
        i -= i&-i
    return s

for i in range(n):
    c = co[i]
    downs[n-1-i] = sumfenwick(ft, c[1])
    ups[n-1-i] = i - downs[n-1-i]
    addfenwick(ft, c[1], 1)

ft = [0] * (n+5)
co = co[::-1]

mod = 998244353
ps = [0] * (n+5)
ps[0] = 1
for i in range(1, n+4):
    ps[i] = ps[i-1] * 2 % mod

ans = 0
for i in range(n):
    c = co[i]
    d = sumfenwick(ft, c[1])
    u = i - d

    # print(d, u, ups[i], downs[i])
    ans += (ps[d]-1) * (ps[ups[i]]-1) * ps[u+downs[i]]
    ans += (ps[u]-1) * (ps[downs[i]]-1) * ps[d+ups[i]]
    ans -= (ps[d]-1) * (ps[ups[i]]-1) * (ps[downs[i]]-1) * (ps[u]-1)
    ans += ps[n-1]
    addfenwick(ft, c[1], 1)

ans %= mod
if ans < 0:
    ans += mod
print(ans)
### BUGGY CODE ###

_ = input()
a = list(map(int, input().split()))
cnt = 0
while all(i % 2 == 0 for i in a):
    for j in a:
        j /= 2
    cnt += 1
print(cnt)

### FIXED CODE ###

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

N = int(input())-1

dic={}
ans=[]
#N=1
dic['a']=1
ans.append('a')

alp = ['a','b','c','d','e','f','g','h','i','j','k']


for i in range(N):
    ans_temp = ans
    dic_temp = dic
    #init for N
    ans = []
    dic={}
    #left a
    for j in ans_temp:
        new_j = 'a'+ j
        ans.append(new_j)
        dic[new_j]=dic_temp[j]
    # right append
    for l in ans_temp:
        num_alp = dic_temp[l]
        for m in range(num_alp+1):
            new_l = l+alp[m]

            if new_l not in ans:
                ans.append(new_l)
                if m==num_alp:
                    dic[new_l]=dic_temp[l]+1
                else:
                    dic[new_l]=dic_temp[l]

        
    
        
        

for i in ans:
    print(i)

### FIXED CODE ###

N = int(input())-1

dic={}
ans=[]
#N=1
dic['a']=1
ans.append('a')

alp = ['a','b','c','d','e','f','g','h','i','j','k']


for i in range(N):
    ans_temp = ans
    dic_temp = dic
    #init for N
    ans = []
    dic={}
    dic_count={}
    #left a
    for j in ans_temp:
        new_j = 'a'+ j
        ans.append(new_j)
        dic[new_j]=dic_temp[j]
        dic_count[new_j]=1
    # right append
    for l in ans_temp:
        num_alp = dic_temp[l]
        for m in range(num_alp+1):
            new_l = l+alp[m]

            if dic_count.get(new_l) is None:
                ans.append(new_l)
                dic_count[new_j]=1
                if m==num_alp:
                    dic[new_l]=dic_temp[l]+1
                else:
                    dic[new_l]=dic_temp[l]

        
    
        
        

for i in ans:
    print(i)
### BUGGY CODE ###

N, W = map(int, input().split())
WV = (map(int, input().split()) for _ in range(N))

DP = [0] * (W+1)

for w, v in WV:
  for j in range(W, w-1, -1):
    dp = DP[j-w] + v 
    if DP[j] < dp:
      DP[j] = dp
print(DP[W])

### FIXED CODE ###

def dp():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))

  DP = [0] * (W+1)
  for w, v in WV:
    for j in range(W, w-1, -1):
      dp = DP[j-w] + v 
      if DP[j] < dp:
        DP[j] = dp
  return max(DP)
print(dp())
### BUGGY CODE ###

N = int(input())
S = input()

black = 0
black_counts = []
white = 0
white_counts = []
for i in range(N):
    if S[i] == '#':
        black += 1
    black_counts.append(black)

    if S[-1-i] == '.':
        white += 1
    white_counts.insert(0, white)

min_count = min(black_counts[N-1], white_counts[0])
for i in range(N-1):
    min_count = min(min_count, black_counts[i] + white_counts[i+1])
print(min_count)

### FIXED CODE ###

N = int(input())
S = input()

black = 0
black_counts = [0]*N
white = 0
white_counts = [0]*N
for i in range(N):
    if S[i] == '#':
        black += 1
    black_counts[i] = black

    if S[-1-i] == '.':
        white += 1
    white_counts[N-1-i] = white

min_count = min(black_counts[N-1], white_counts[0])
for i in range(N-1):
    min_count = min(min_count, black_counts[i] + white_counts[i+1])
print(min_count)