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

from fractions import gcd
A,B=map(int,input().split())
gcd_ab=gcd(A,B)
ans=1
for i in range(2,gcd_ab+1):
  if gcd_ab == 1:
    break
  elif (gcd_ab/i)%1 == 0:
    ans+=1
    while (gcd_ab/i)%1 == 0:
      gcd_ab = gcd_ab/i
print(ans)

### FIXED CODE ###

import fractions
import math
A,B=map(int,input().split())

x=fractions.gcd(A,B)

l=[]
for i in range(2, math.floor(math.sqrt(x))+1):
  count=0
  while x%i==0:
    count+=1
    x/=i
  if count>=1:
    l.append([i,count])
if x>math.floor(math.sqrt(x)):
  l.append([x, 1])
print(len(l)+1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

from itertools import accumulate

def solve():
    N, M = map(int, input().split())
    S = map(int, input().split())
    *T, = map(int, input().split())
    dp = [0]*(M+1)
    for s in S:
        is_s = s.__eq__
        acc = [0]*(M+1)
        for i, t in enumerate(T):
            acc[i+1] = acc[i]+(dp[i] + 1 if is_s(t) else 0)
        *dp, = map(int.__add__, dp, acc)
    res = (dp[-1]+1)%(10**9+7)
    return str(res)

if __name__ == '__main__':
    print(solve())


### FIXED CODE ###

# -*- coding: utf-8 -*-
def solve():
    N, M = map(int, input().split())
    S = map(int, input().split())
    *T, = map(int, input().split())
    dp = [1]*(M+1)
    for s in S:
        is_s = s.__eq__
        dp_ = dp[:]
        acc = 0
        for i, t in enumerate(T):
            if is_s(t):
                acc += dp_[i]
            dp[i+1] = dp_[i+1] + acc
    res = (dp[-1])%(10**9+7)
    return str(res)

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

import numpy as np

n = int(input())
a = list(map(int, input().split()))
x = list(sorted(set(a)))
a = np.array(a, dtype="i8")
Li = -1
Ri = len(x) - 1
while Li + 1 < Ri:
    i = (Li + Ri) // 2
    xi = x[i]
    s = 0
    lr = np.cumsum((a > xi) * 2 - 1, dtype="i8")
    M = np.sum((lr >= 0) * 2 - 1)
    for l in range(1, n):
        lr[l:] -= lr[l - 1]
        M += np.sum((lr[l:] >= 0) * 2 - 1)
    if M >= 0:
        Li = i
    else:
        Ri = i
print(x[Ri])


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
x = list(sorted(set(a)))
n_sub = n * (n + 1) // 2
Li = 0
Ri = len(x)
while Ri > Li + 1:
    i = (Li + Ri) // 2
    xi = x[i]
    UorD = [1 if ak >= xi else -1 for ak in a]
    cnt_sum = [0] * (2 * n + 1)
    cumsum = 0
    cnt_sum[cumsum + n] = 1
    judge = 0
    s = 0
    for uk in UorD:
        cumsum += uk
        if uk == 1:
            s += cnt_sum[cumsum + n] + 1
        else:
            s -= cnt_sum[cumsum + n + 1] - 1
        cnt_sum[cumsum + n] += 1
        judge += s
        if judge >= n_sub // 2:
            Li = i
            break
    else:
        Ri = i
print(x[Li])
### BUGGY CODE ###

n = int(input())
nums = [int(e) for e in input().split()]
ans = 1
for i in range(n):
    ans *= nums[i]
print(ans if ans <= 10 ** 18 else -1)

### FIXED CODE ###

N = int(input())
num = sorted([int(e) for e in input().split(" ")])
lim = 10 ** 18
i = -1
ans = 1
for a in num:
    ans *= a
    if(ans > lim):
        print(-1)
        break
    elif(ans == 0):
        print(0)
        break
else:
    print(ans)
### BUGGY CODE ###

N = int(input())
a = [int(i) for i in input().split()]
b = []
for i in range(N):
    if i % 2 == 0:
        b.append(a[i])
    else:
        b.insert(0, a[i])
if N % 2 == 1:
    [print(b[i], end=' ') for i in reversed(range(len(b)))]
else:
    [print(b[i], end=' ') for i in range(len(b))]


### FIXED CODE ###

from collections import deque
N = int(input())
a = [int(i) for i in input().split()]
b = deque()
for i in range(N):
    if i % 2 == 0:
        b.append(a[i])
    else:
        b.appendleft(a[i])
if N % 2 == 1:
    [print(b[i], end=' ') for i in reversed(range(len(b)))]
else:
    [print(b[i], end=' ') for i in range(len(b))]
### BUGGY CODE ###

N,x = map(int, input().split())
alist = list(map(int,input().split()))
ans = 0

for al in range(1,N):
    while (alist[al-1]+alist[al]) > x:
        alist[al] -= 1
        ans += 1

print(ans)

### FIXED CODE ###

N,x = map(int, input().split())
alist = list(map(int,input().split()))
ans = 0

if alist[0] > x:
    ans += (alist[0] - x)
    alist[0] -= (alist[0] - x)

for al in range(1,N):
    if (alist[al-1]+alist[al]) > x:
        ans += (alist[al-1]+alist[al]) - x
        alist[al] -= (alist[al-1]+alist[al]) - x

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

n, k = map(int, input().split())
Ps = list(map(int, input().split()))
Ps.insert(0,0)
Cs = list(map(int, input().split()))
Cs.insert(0,0)
Ls = [0] * (n + 1)  # 周期
As = [] # 回答候補

# 周期を見つける
for i in range(1,n + 1):
  count = 1
  temp = Ps[i]
  while temp != i:
    temp = Ps[temp]
    count += 1
  Ls[i] = count

# それぞれの最大値を見つける
for i in range(1, n + 1):
  ans = 0
  p = []  #途中経過集
  tempIndex = i
  tempSum = 0
  for j in range(Ls[i]):
    tempIndex = Ps[tempIndex]
    tempSum += Cs[tempIndex]
    p.append(tempSum)
  # print(f'p:{p}')
  # ansを求める
  if p[-1] <= 0:
    ans = max(p[:min(k,Ls[i])])
  else:
    q, r = divmod(k, Ls[i])
    # print(f'q,r,k,Ls[i]:{q}{r}{k}{Ls[i]}')
    start = q * p[-1]
    anss = [start]
    tempIndex = i
    tempSum = start
    for z in range(r):
      tempIndex = Ps[tempIndex]
      tempSum += Cs[tempIndex]
      anss.append(tempSum)
    ans = max(anss)
  As.append(ans)
print(max(As))

### FIXED CODE ###

n, k = map(int, input().split())
Ps = list(map(int, input().split()))
Ps.insert(0,0)
Cs = list(map(int, input().split()))
Cs.insert(0,0)
Ls = [0] * (n + 1)  # 周期
As = [0] * (n) # 回答候補

# 周期を見つける
for i in range(1,n + 1):
  count = 1
  temp = Ps[i]
  while temp != i:
    temp = Ps[temp]
    count += 1
  Ls[i] = count

# それぞれの最大値を見つける
for i in range(1, n + 1):
  ans = 0
  p = [0] * Ls[i]  #途中経過集
  tempIndex = i
  tempSum = 0
  for j in range(Ls[i]):
    tempIndex = Ps[tempIndex]
    tempSum += Cs[tempIndex]
    p[j] = tempSum
  # print(f'p:{p}')
  # ansを求める
  if p[-1] <= 0:
    ans = max(p[:min(k,Ls[i])])
  else:
    q, r = divmod(k, Ls[i])
    # print(f'q,r,k,Ls[i]:{q}{r}{k}{Ls[i]}')
    start = (q - 1) * p[-1]
    anss = [0] * (r + Ls[i])
    anss.insert(0, start)
    tempIndex = i
    tempSum = start
    for z in range(r + Ls[i]): #rは高々Ls[i]、つまりn、つまり5 * (10**3)
      tempIndex = Ps[tempIndex]
      tempSum += Cs[tempIndex]
      anss[z + 1] = tempSum
    ans = max(anss)
  As[i-1] = ans
print(max(As))
### BUGGY CODE ###

s=input()
a=input()
a=a.split()


c=1
for x in a:
  c=c*int(x)
  
if c <= 10**18:
  print(c)
else:  
  print("-1") 


### FIXED CODE ###

a=int(input())
A=list(map(int,input().split()))
ans=1
if A.count(0)==0:
    for x in A:
      ans*=x
      if ans>10**18:
        break


    if ans>10**18:
      print(-1)
    else:
      print(ans)
else:
  print(0)
### BUGGY CODE ###

n, k = map(int, input().split())
k = min(k, n - 1)
p = 10 ** 9 + 7
size = n * 2
f_list = [1] * size
for i in range(1, size):
    f_list[i] = (f_list[i - 1] * i) % p

def cmb(n, r):
    return f_list[n] * pow(f_list[r], p-2, p) * pow(f_list[n - r], p-2, p) % p

# 初期値は0人の部屋が0個の場合
ans = 1
for i in range(1, k + 1):
    ans += cmb(n, i) * cmb(n - 1, i)
    ans = ans % p
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
k = min(k, n - 1)
p = 10 ** 9 + 7
size = n + 100
f_list = [1] * size
if_list = [1] * size
for i in range(1, size):
    f_list[i] = (f_list[i - 1] * i) % p
    if_list[i] = pow(f_list[i], p-2, p)

def cmb(n, r):
    return f_list[n] * if_list[r] * if_list[n-r] % p

# 初期値は0人の部屋が0個の場合
ans = 1
for i in range(1, k + 1):
    ans += cmb(n, i) * cmb(n - 1, i)
    ans = ans % p
print(ans)
### BUGGY CODE ###

K, S = list(map(int, input().split()))
ans = 0
for x in range(K+1):
	for y in range(K+1):
		for z in range(K+1):
			if x+y+z == S:
				ans+=1
print(ans)

### FIXED CODE ###

K, S = list(map(int, input().split()))
ans = 0
for x in range(K+1):
	for y in range(K+1):
		if x+y<=S:
			if S-x-y<=K:
				ans+=1
print(ans)
### BUGGY CODE ###

S = input()
mod = 10**9 + 7
dic = {'': 1, 'A': 0, 'B': 0, 'C': 0}
for s in S:
    if s == 'A':
        dic[s] += dic['']

    elif s == 'B':
        dic[s] += dic['A']

    elif s == 'C':
        dic[s] += dic['B']

    elif s == '?':
        dic['C'] = dic['C'] * 3 + dic['B']
        dic['B'] = dic['B'] * 3 + dic['A']
        dic['A'] = dic['A'] * 3 + dic['']
        dic[''] *= 3

print(dic['C']%mod)


### FIXED CODE ###

S = input()
mod = 10**9 + 7
dic = {'': 1, 'A': 0, 'B': 0, 'C': 0}
for s in S:
    if s == 'A':
        dic[s] += dic['']

    elif s == 'B':
        dic[s] += dic['A']

    elif s == 'C':
        dic[s] += dic['B']

    elif s == '?':
        dic['C'] = dic['C'] * 3 + dic['B']
        dic['B'] = dic['B'] * 3 + dic['A']
        dic['A'] = dic['A'] * 3 + dic['']
        dic[''] *= 3

    dic[''] %= mod
    dic['A'] %= mod
    dic['B'] %= mod
    dic['C'] %= mod

print(dic['C']%mod)
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline

N, K, Q = list(map(int, readline().split()))
A = []
for a in range(Q):
    A.append(int(readline()))


points = [K] * N

for i in range(Q):

    for j in range(N):
        if A[i] - 1 != j:
            points[j] -= 1

for p in points:
    print("Yes" if p > 0 else "No")

### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline

N, K, Q = list(map(int, readline().split()))
A = []
for a in range(Q):
    A.append(int(readline()))

points = [0] * N

for i in range(Q):
    points[A[i] - 1] += 1

for p in points:
    score = K - Q + p
    print("Yes" if score > 0 else "No")
### BUGGY CODE ###

n = int(input())
word = []
for i in range(n):#文字列毎
  inp = input()
  for j in range(len(word)):#word配列の長さ毎
    if inp in word[j]:#word[j]に含まれる場合
      if j + 1 == len(word):
        word.append([inp])
        break
    else:
      word[j].append(inp)
      break
  if i == 0:
    word.append([inp])
tmp1 = word[len(word)-1]
tmp2 = []
for i in tmp1:
  if i not in tmp2:
    tmp2.append(i)
tmp2.sort()
for i in tmp2:
  print(i)

### FIXED CODE ###

d = {}
r = []
max = 0

n = int(input())

for i in range(n):
  k = input()
  if k in d:
    d[k] += 1
    if max < d[k]:
      max = d[k]
  else:
    d[k] = 1
    if max == 0:
      max += 1

for i in d:
  if d[i] == max:
    r.append(i)

r.sort()

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

N=int(input())
S=list(map(int,input().split()))
lenS=len(S)
T=[]
for i in range(1,N+1):
    T.append(abs(i-(N+1-i)))

T.sort()
S.sort()



for i in range(N):
    if T!=S:
        print(0)
        exit()


ans=1
nagasa=lenS//2
for i in range(nagasa):
    
    ans=(ans*2)%(10**9+7)

print(ans)


    

### FIXED CODE ###

N=int(input())
S=list(map(int,input().split()))
lenS=len(S)
T=[]
for i in range(1,N+1):
    T.append(abs(i-(N+1-i)))

T.sort()
S.sort()



for i in range(N):
    if T[i]!=S[i]:
        print(0)
        exit()


ans=1
nagasa=lenS//2
for i in range(nagasa):
    
    ans=(ans*2)%(10**9+7)

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

R, G, B, N = map(int,input().split())

cnt = 0
for r in range(0,N//R+1):
    for g in range(0,N//G+1):
        if (N - (R*r + G*g)) % B == 0 and N - (R*r + G*g) >= 0:
            #print(r,g,(N-r-g))
            cnt += 1

print(cnt)

### FIXED CODE ###

R, G, B, N = map(int,input().split())

cnt = 0
for r in range(0,N//R+1):
    for g in range(0,(N-R*r)//G+1):
        if (N - R*r - G*g) % B == 0 :
            #print(r,g,(N-r-g))
            cnt += 1

print(cnt)
### BUGGY CODE ###

import sys
import copy
n=int(input())
maxmatch=n*(n-1)
a=[]
for i in range(n):
  b=list(map(int,input().split()))
  a.append(list(reversed(b)))
day=0
 
match=[0]*(n+1)
jyunban=[i for i in range(n)]
jyunban_n=[]
 
while match[n]<maxmatch:
  jyunban_n.clear()
  day+=1
  check=[True]*(n+1)
  for i in jyunban:
    if match[i]==n-1 or check[i]==False:
      continue
    else:
      vs=a[i][-1]-1
      if check[i] and check[vs]:
        if  a[i][-1]-1==vs and a[vs][-1]-1==i:
          a[i].pop(-1)
          a[vs].pop(-1)
          match[i]+=1
          match[vs]+=1
          match[n]+=2
          check[i]=False
          check[vs]=False
          check[n]=False
          jyunban_n.append(i)
          jyunban_n.append(vs)
      
    if i==jyunban[-1]:
      if check[n]:
        print(-1)
        sys.exit()
  jyunban=copy.copy(jyunban_n)
        
print(day)

### FIXED CODE ###

import sys
MAX_INT = int(10e9)
MIN_NUM = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()
 
N = I()
a = [IL()[::-1] for i in range(N)]
 
used = [-1]*N
updatelist = [i for i in range(N)]
total = N*(N-1)//2
cnt = 0
days = 0
ul = []
while updatelist:
  ul = []
  for i in updatelist:
    #print(a)
    #print(i+1)
    if len(a[i]) > 0 and used[i] != days:
      numIND = a[i][-1] -1
      #print(numIND+1)
      if a[numIND][-1] == i+1 and used[numIND] != days:
        a[i].pop(-1)
        a[numIND].pop(-1)
        used[i] = days
        used[numIND] = days
        ul.append(i)
        ul.append(numIND)
        cnt += 1
  else:
    updatelist = ul[:]
    if len(ul) != 0:
      days += 1
#print(a)
#print(cnt)
if cnt == total:
  print(days)
else:
  print(-1)
### BUGGY CODE ###

x,y,z,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
sum_list = []
for a_i in range(x):
    for b_i in range(y):
        for c_i in range(z):
            if a_i*b_i*c_i > k:
                continue
            sum_list.append(a[a_i]+b[b_i]+c[c_i])
sum_list.sort(reverse=True)
for i in range(k):
    print(sum_list[i])

### FIXED CODE ###

x,y,z,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
sum_list = []
for a_i in range(x):
    for b_i in range(y):
        if a_i*b_i > k:
            break
        for c_i in range(z):
            if a_i*b_i*c_i > k:
                break
            sum_list.append(a[a_i]+b[b_i]+c[c_i])
sum_list.sort(reverse=True)
for i in range(k):
    print(sum_list[i])
### BUGGY CODE ###

N = input()
N = int(N)

l = input().split(" ")
l = [int(n0) for n0 in l]

# print(l)

l.append(10**10)

ans = 0

for xi in range(N-1):
    step = l[xi]
    count = 0
    while l[xi+count] >= l[xi+count+1] :
        # step = l[xi+count+1]
        count = count +1
    if ans < count:
        ans = count

print(ans)


### FIXED CODE ###

n = int(input())
h = [int(xi) for xi in input().split()]

step = 0
mstep = 0
for xi in range(n-1):
    if h[xi] >= h[xi+1]:
        step += 1
    else:
        if mstep<step:
            mstep = step
        step = 0

if mstep<step:
    mstep = step

print(mstep)
### BUGGY CODE ###

import queue
n,m = map(int,input().split())
graph = [[0 for i in range(n)]for j in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    graph[a-1][b-1] = 1
    graph[b-1][a-1] = 1
ans = [0]* n
flag = [0]*n
q = queue.deque()
q.append(1)
while q:
    tmp = q.popleft()
    flag[tmp-1] = 1
    for i in range(len(graph[tmp-1])):
        if graph[tmp-1][i] == 1:
            if flag[i] == 0:
                q.append(i+1)
                if ans[i] == 0:
                    ans[i] = tmp
if sum(flag) == n:
    print('Yes')
    for i in range(1,n):
        print(ans[i])
        
else:
    print('No')

### FIXED CODE ###

import queue
n,m = map(int,input().split())
graph = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    graph[a-1].append(b)
    graph[b-1].append(a)
ans = [0]* n
q = queue.deque()
q.append(1)
while q:
    tmp = q.popleft()
    for i in graph[tmp-1]:
        if ans[i-1] == 0:
            q.append(i)
            ans[i-1] = tmp
                
if 0 in ans:
    print('No')
        
else:
    print('Yes')
    for i in range(1,n):
        print(ans[i])
### BUGGY CODE ###

from itertools import permutations 
inf=10**10
n, m, r = map(int, input().split())
r=list(map(int, input().split()))
abc=[list(map(int, input().split())) for _ in range(m)]
d=[[inf]*n for i in range(n)]
for i in range(n):
    d[i][i]=0
for ai, bi, ci in abc:
    d[ai-1][bi-1]=ci
    d[bi-1][ai-1]=ci
for k in range(n):
    for i in range(n):
        for j in range(i, n):
            d[i][j]=min(d[i][j], d[i][k]+d[k][j])
            d[j][i]=d[i][j]
p=list(permutations(r))
print(min(sum(d[pi[i]-1][pi[i+1]-1] for i in range(len(r)-1)) for pi in p))

### FIXED CODE ###

from itertools import permutations
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
E = [list(map(int, input().split())) for _ in range(M)]
INF = 10 ** 9
d = [[INF for j in range(N)] for i in range(N)]
for i, j, c in E:
    d[i - 1][j - 1] = c
    d[j - 1][i - 1] = c
for k in range(N):
    for i in range(N - 1):
        for j in range(i, N):
            dk = d[i][k] + d[k][j]
            if d[i][j] > dk:
                d[i][j] = dk
                d[j][i] = dk
ans = 10 ** 9
for ri in permutations(r):
    x = 0
    for i in range(R - 1):
        x += d[ri[i] - 1][ri[i + 1] - 1]
    if ans > x:
        ans = x
print(ans)
### BUGGY CODE ###

import sys
from itertools import combinations
input = sys.stdin.readline
n = int(input())
a = [int(x) for x in input().strip().split()]
b = [int(x) for x in input().strip().split()]

all_cards = []
for i, (aa, bb) in enumerate(zip(a, b)):
    all_cards.append((aa, bb, i))

def check(cards):
    pre = -1
    for c in cards:
        print(c)
        if c[0] >= pre:
            pre = c[0]
        else:
            return False
    else:
        return True

def cnt(l):
    ret = 0
    for i in range(len(l)-1):
        for j in range(i+1, len(l)):
            if l[i] > l[j]:
                ret += 1
    return ret

def dp(all_cards, l, p):
    i = len(l) + 1
    if len(l) == n:
        return cnt(l)
    ret = float('inf')
    for card in all_cards:
        if card[2] in l:
            continue
        if card[(i-(card[2]+1))%2] >= p:
            ret = min(ret, dp(all_cards, l+[card[2]], card[(i-(card[2]+1))%2]))
    return ret

ans = dp(all_cards, [], -float('inf'))
if ans == float('inf'):
    ans = -1
print(ans)

### FIXED CODE ###

import sys
from itertools import combinations
input = sys.stdin.readline
n = int(input())
a = [int(x) for x in input().strip().split()]
b = [int(x) for x in input().strip().split()]

all_cards = []
for i, (aa, bb) in enumerate(zip(a, b)):
    if i % 2:
        aa, bb = bb, aa
    all_cards.append([aa, bb, i])

def cnt(l):
    ret = 0
    for i in range(len(l)-1):
        for j in range(i+1, len(l)):
            if l[i][1] > l[j][1]:
                ret += 1
    return ret

ans = float('inf')
for cards in combinations(all_cards, (n + 1)// 2):
    acards = []
    for card in cards:
        acards.append([card[0],card[2]])
    bcards = []
    for card in all_cards:
        if [card[0],card[2]] not in acards:
            bcards.append([card[1],card[2]])

    acards.sort()
    bcards.sort()
    abcards = []
    # print(acards, bcards)
    for i in range(len(bcards)):
        abcards.extend([acards[i], bcards[i]])
    else:
        if n % 2:
            abcards.append(acards[-1])
    # print(abcards)
    if abcards != sorted(abcards, key=lambda x: x[0]):
        continue
    ans = min(ans, cnt(abcards))

if ans == float('inf'):
    ans = -1
print(ans)
### BUGGY CODE ###

n=int(input())
l=list(map(int, input().split()))
c=0
def a(n, l):
    result=False
    num=0
    for i in range(n):
        if l[i]%2==0:
            result=True
            num=i
            break
    return result, num
while True:
    b=a(n, l)
    if b[0]:
        c+=1
        l=list(map(lambda x: x*3, l))
        l[b[1]]//=6
    else:
        break
print(c)

### FIXED CODE ###

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

import sys


def input():
    return sys.stdin.readline().strip()

def main():

    # i have too make index as weight and value as value
    size, total_weight = map(int, input().split())
    dp = [0] * (total_weight+1)
    for _ in range(size):
        weight, val = map(int, input().split())
        for i in range(total_weight - weight, -1, -1):
            dp[weight + i] = max(dp[weight + i], dp[i] + val)
    ans = 0
    for i in range(total_weight+1):
        ans = max(ans, dp[i])
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline().strip()

def main():

    # i have too make index as weight and value as value
    import numpy as np
    N, W = map(int, input().split())

    dp = np.zeros(W + 1, int)

    for i in range(N):
        w, v = map(int, input().split())
        np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])
        # print(dp[:-w],dp[w:] )


    print(dp[-1])


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

K, S = map(int, input().split())
counter = 0
for x in range(K+1):
  if x > S:
    break
  for y in range(K+1):
    if x+y > S:
      break
    for z in range(K+1):
      if x+y+z == S:
        counter += 1
      if x+y+z > S:
        break
print(counter)

### FIXED CODE ###

K, S = map(int, input().split())
counter = 0
for x in range(K+1):
  for y in range(K+1):
    z = S - x - y
    if z >= 0 and z <= K:
      counter += 1
print(counter)
### BUGGY CODE ###

import numpy as np
n,w=map(int,input().split())
wv=[]
for _ in range(n):
    wv.append(list(map(int,input().split())))
dp=np.full(n*100**3+1,w+1) # dp[j]:価値総和jをちょうど実現できる最小の重さ総和
dp[0]=0
for i in range(n):# i番目までの商品について全ての重さについて調べる
    w_=wv[i][0]
    v_=wv[i][1]
    dp[v_:]=np.minimum(dp[v_:],dp[:-v_]+w_)

print(np.where(dp<=w)[0][-1])


### FIXED CODE ###

import numpy as np
n,w=map(int,input().split())
wv=[]
for _ in range(n):
      wv.append(list(map(int,input().split())))
# dp[i]:価値の総和をちょうどiにできる最小の重さ総和
# dp[i]=w+1となる価値総和iにはできない。
# 求めるのはdp[i]<=wとなる最大のi
dp=np.full(10**5+1,w+1) # ndarray(1000,1000,...,1000])
dp[0]=0
# 10**5:viの総和の最大
for i in range(n):
      w_=wv[i][0]
      v_=wv[i][1]
      # i番目までの商品を取るか取らないかの全ての組み合わせをためすことができる。
      dp[v_:]=np.minimum(dp[v_:], dp[:-v_]+w_)
print(np.where(dp<=w)[0][-1])
### BUGGY CODE ###

S = input()

ans_count = 0
b_count = 0
for i in range(len(S)):
    s = S[i]
    if s=="B":
        b_count = b_count + 1
    if s=="W":
        cut_str = S[:i]
        ans_count = ans_count + b_count

print(ans_count)


### FIXED CODE ###

S = input()

ans_count = 0
b_count = 0
for s in S:
    if s=="B":
        b_count = b_count + 1
    if s=="W":
        ans_count = ans_count + b_count

print(ans_count)
### BUGGY CODE ###

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

cnt = 0
z = 0
if N == 1:
    print("0")
    exit()
else:
    for i in range(N-1):
        x = S[i]
        y = S[i+1]
        if x == "#":
            if y == ".":
                cnt += 1
                if i != N-1:
                    mae = S[0:i+1]
                    ato = S[i+2:N]
                    S = mae + "#" + ato

print(cnt)


### FIXED CODE ###

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

if N==1:
    print("0")
else:
    cnt_left=0
    cnt_right=S.count(".")
    cnt = cnt_left + cnt_right
    for i in range(N):
        if S[i] == "#":
            cnt_left += 1
        else:
            cnt_right -= 1

        if cnt_left + cnt_right < cnt:
            cnt = cnt_left + cnt_right
    print(cnt)