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

N, W = map(int, input().split())
WV = [list(map(int, input().split())) for i in range(N)]

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if j < WV[i][0]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - WV[i][0]] + WV[i][1])


print(dp[-1][-1])


### FIXED CODE ###

N, W = map(int, input().split())
WV = [list(map(int, input().split())) for i in range(N)]

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if j < WV[i][0]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - WV[i][0]] + WV[i][1])


print(dp[-1][-1])
### BUGGY CODE ###

import math
k = int(input())
ans = 0
for a in range(1,k+1):
  for b in range(1,k+1):
    for c in range(1,k+1):
      ans += math.gcd(math.gcd(a,b),c)
print(ans)


### FIXED CODE ###

import math
k = int(input())
ans = 0
for a in range(1,k+1):
  for b in range(1,k+1):
    n = math.gcd(a,b)
    for c in range(1,k+1):
      ans += math.gcd(n,c)
print(ans)
### BUGGY CODE ###

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

a = [int(input()) for i in range(M)]


for i in range(M - 1):
    if a[i] + 1 == a[i+1]:
        print(0)
        exit()

dp = [0] * (N + 1)

if N == 1 and M != 1:
    print(1)
    exit()
elif N == 1 and M == 1:
    print(0)
    exit()

if 1 in a and 2 in a:
    print(0)
    exit()

if 1 in a:
    dp[1] = 0
    dp[2] = 1
elif 2 in a:
    dp[1] = 1
    dp[2] = 0
else:
    dp[1] = 1
    dp[2] = 2

for i in range(3,N+1):
    if i in a:
        dp[i] = 0
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007

print(dp[N])

### FIXED CODE ###

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

a = [int(input()) for i in range(M)]


for i in range(M - 1):
    if a[i] + 1 == a[i+1]:
        print(0)
        exit()

dp = [0] * (N + 1)
flag_a = [0] * (N + 1)

for i in range(M):
    flag_a[a[i]] = -1


if N == 1 and M != 1:
    print(1)
    exit()
elif N == 1 and M == 1:
    print(0)
    exit()

if 1 in a and 2 in a:
    print(0)
    exit()

if 1 in a:
    dp[1] = 0
    dp[2] = 1
elif 2 in a:
    dp[1] = 1
    dp[2] = 0
else:
    dp[1] = 1
    dp[2] = 2

for i in range(3,N+1):
    if flag_a[i] == -1:
        dp[i] = 0
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007

print(dp[N])
### BUGGY CODE ###

from functools import lru_cache
n, a = map(int, input().split(' '))
x = list(map(int, input().split(' ')))
t = 0
@lru_cache(maxsize=1024)
def dfs(i,sum,v):
    if i == n:
        v = max(1,v)
        if sum/v == a:
            return 1
        else:
            return 0
    return dfs(i+1,sum,v)+dfs(i+1,sum+x[i],v+1)

print(dfs(0,0,0))


### FIXED CODE ###

n,a = map(int, input().split(' '))
x = list(map(int, input().split(' ')))
y = [i - a for i in x]
X = max(a,max(x))

dp = []
for i in range(n+1):
    dp.append([0]*(2*n*X+1))
for j in range(n,-1,-1):
    for t in range(2*n*X+1):
        if j == n and t ==n*X:
            dp[j][t] = 1
        elif j == n:
            dp[j][t] = 0
        elif 0 <= t-y[j] <= 2*n*X:
            dp[j][t] = dp[j+1][t] + dp[j+1][t-y[j]]
        else:
            dp[j][t] = dp[j+1][t]
def main():
    print(dp[0][n*X]-1)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N=int(input())
A=list(map(int, input().split()))
a=set(A)
for i in range(1,N+1):
    if i in a:
        print(A.count(i))
    else:
        print(0)

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
b=[0]*N
for i in A:
    b[i-1]+=1
for j in b:
    print(j)
### BUGGY CODE ###

def main():
    from sys import stdin
    input=stdin.readline
    n, m, r = map(int, input().split())
    root = list(map(int, input().split()))
    abc = [list(map(int, input().split())) for _ in [0]*m]
    inf = 10**10
    dist = [[inf for _ in [0]*n] for _ in [0]*n]
    for i in range(n):
        dist[i][i] = 0
    for a, b, c in abc:
        dist[a-1][b-1] = c
        dist[b-1][a-1] = c
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], (dist[i][k]+dist[k][j]))

    from itertools import permutations

    p = list(permutations(root))

    D = 10**10
    for i in p:
        d = 0
        for j in range(len(i)-1):
            d += dist[i[j]-1][i[j+1]-1]
        D = min(D, d)
    print(D)


main()

### FIXED CODE ###

n,m,r=map(int,input().split())
root=list(map(int,input().split()))
abc=[list(map(int,input().split())) for _ in [0]*m]
inf=10**10
dist=[[inf for _ in [0]*n] for _ in [0]*n]
for i in range(n):dist[i][i]=0
for a,b,c in abc:
    dist[a-1][b-1]=c
    dist[b-1][a-1]=c
for k in range(n):
    for i in range(n):
        for j in range(n):dist[i][j]=min(dist[i][j],(dist[i][k]+dist[k][j]))

from itertools import permutations

p=list(permutations(root))

D=10**10
for i in p:
    d=0
    for j in range(len(i)-1):
        d+=dist[i[j]-1][i[j+1]-1]
    D=min(D,d)
print(D)
### BUGGY CODE ###

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

print(' '.join(list(str(A.index(i+1)+1) for i in range(n))))
    


### FIXED CODE ###

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

L = [0]*n
for i in range(n):
    L[A[i]-1] = i+1
print(*L)
### BUGGY CODE ###

n = int(input())

s = [input() for _ in range(n)]

for i in range(n):
    s[i] = sorted(s[i])
    s[i] = "".join(s[i])

s = sorted(s)

c = []
for j in range(n):
    if j == 0 :
        c.append(s.count(s[0]))
    else :
        c.append(s.count(s[j]))
        if s[j] == s[j-1] :
            c[j] = 0

ans = 0
for k in range(n):
    ans += c[k]*(c[k]-1)//2

print(ans)


### FIXED CODE ###

n = int(input())

s = [input() for _ in range(n)]

for i in range(n):
    s[i] = sorted(s[i])
    s[i] = "".join(s[i])

t = {}
for i in range(n):
    if s[i] in t :
        t[s[i]] += 1
    else :
        t[s[i]] = 1

print(sum(t[k]*(t[k]-1)//2 for k in t))
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
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()))

h, w = LI()
ch, cw = LI()
dh, dw = LI()
s = [input() for _ in range(h)]

dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]
d = [[10**10] * w for _ in range(h)]
d[ch-1][cw-1] = 0
H = []
heappush(H, (0, cw-1, ch-1))
while H:
    D, x, y = heappop(H)
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < w and 0 <= ny < h:
            if s[ny][nx] == '.' and d[ny][nx] > D:
                d[ny][nx] = D
                heappush(H, (D, nx, ny))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nx, ny = x + i, y + j
            if 0 <= nx < w and 0 <= ny < h:
                if s[ny][nx] == '.' and d[ny][nx] > D + 1:
                    d[ny][nx] = D + 1
                    heappush(H, (D + 1, nx, ny))
if d[dh-1][dw-1] == 10**10:
    print(-1)
else:
    print(d[dh-1][dw-1])

### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
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()))

h, w = LI()
ch, cw = LI()
dh, dw = LI()
s = [input() for _ in range(h)]

dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]
que = deque([(cw-1, ch-1)])
d = [[10**10] * w for _ in range(h)]
d[ch-1][cw-1] = 0
while que:
    x, y = que.popleft()
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < w and 0 <= ny < h:
            if s[ny][nx] == '.' and d[ny][nx] > d[y][x]:
                d[ny][nx] = d[y][x]
                que.appendleft((nx, ny))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nx, ny = x + i, y + j
            if 0 <= nx < w and 0 <= ny < h:
                if s[ny][nx] == '.' and d[ny][nx] > d[y][x] + 1:
                    d[ny][nx] = d[y][x] + 1
                    que.append((nx, ny))
if d[dh-1][dw-1] == 10**10:
    print(-1)
else:
    print(d[dh-1][dw-1])
### BUGGY CODE ###

S=[i for i in input()]
m=0
while True:
  f=0
  for i in range(len(S)-1):
    if (S[i]=='1' and S[i+1]=='0') or (S[i]=='0' and S[i+1]=='1'):
      S.pop(i+1)
      S.pop(i)
      m+=2
      f=1
      break
  if f==0:
    break
print(m)

### FIXED CODE ###

S=[i for i in input()]
m=0
for i in range(len(S)):
  if S[i]=='1':
    m+=1
  else:
    m-=1
print(len(S)-abs(m))
### BUGGY CODE ###

from sys import stdin

def main():
    import numpy as np
    input = stdin.readline

    n = int(input())
    a = [[] for _ in range(n)]
    for i in range(n - 1):
        a[i] = [0] * i + [1, 1] + [0] * (n - i - 2)
    a[n - 1] = [1] + [0] * (n - 2) + [1]
    A = np.array(a)
    b = np.array(list(map(int, input().split())))
    x = np.linalg.solve(A, b) * 2
    print(' '.join(map(str, map(int, x))))
main()

### FIXED CODE ###

from sys import stdin

def main():
    input = stdin.readline

    n = int(input())
    a = list(map(int, input().split()))
    ans = [0] * n
    for i in range(n):
        if i % 2 == 0:
            ans[0] += a[i]
        else:
            ans[0] -= a[i]
    for i in range(1, n):
        ans[i] = 2 * a[i - 1] - ans[i - 1]
    print(' '.join(map(str, ans)))
main()
### BUGGY CODE ###

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

# Function of Combination mod M
# set n >= max p expected
M = 10**9+7


if k >= n-1:
    fac = [1]+[0]*(2*n-1)
    for i in range(1,2*n): fac[i] = fac[i-1]*i %M
    comb = lambda p,q:(fac[p]*pow(fac[q],M-2,M)*pow(fac[p-q],M-2,M))%M
    y = comb(2*n-1,n-1)
    
else:
    fac = [1]+[0]*n
    for i in range(1,n+1): fac[i] = fac[i-1]*i %M
    comb = lambda p,q:(fac[p]*pow(fac[q],M-2,M)*pow(fac[p-q],M-2,M))%M
    y = 1
    for i in range(1,k+1):
        y += (comb(n,i)*comb(n-1,n-1-i))%M
print(y%M)

### FIXED CODE ###

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

# Function of Combination mod M
# set n >= max p expected
M = 10**9+7


if k >= n-1:
    fac = [1]+[0]*(2*n-1)
    for i in range(1,2*n): fac[i] = fac[i-1]*i %M
    comb = lambda p,q:(fac[p]*pow(fac[q],M-2,M)*pow(fac[p-q],M-2,M))%M
    y = comb(2*n-1,n-1)
    
else:
    y = 1
    c1,c2=1,1
    for i in range(1,k+1):
        p = pow(i,M-2,M)
        c1 = c1*(n+1-i)*p%M
        c2 = c2*(n-i)*p%M
        y += c1*c2%M
        # y = (y+c1*c2)%M
print(y%M)
### BUGGY CODE ###

import math
n = int(input())

ans = 0
for i in range(1,n+1):
  for j in range(1,n+1):
    for k in range(1,n+1):
      ans += math.gcd(math.gcd(i,j),k)
print(ans)

### FIXED CODE ###

import math
n = int(input())

ans = 0
for i in range(1,n+1):
  for j in range(1,n+1):
    temp = math.gcd(i,j)
    for k in range(1,n+1):
      ans += math.gcd(temp,k)
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = set()
d = 0
for i in range(N):
  f = True
  for j in ans:
    if A[i] % j == 0:
      f = False
      break
  if f:
    ans.add(A[i])
    if i < N - 1 and A[i] == A[i+1]:
      d += 1
print(len(ans) - d)

### FIXED CODE ###

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

F = [0 for i in range(A[-1]+1)]
for i in A:
  F[i] = 1

c_set = set()
for i in A:
  if F[i] == 0:
    continue
  c_set.add(i)
  for j in range(i, A[-1]+1, i):
    F[j] = 0

ans = len(c_set)
d = 0
d_set = set()
for i in range(N):
  if i == 0 and N > 1:
    if A[i] == A[i+1]:
      d_set.add(A[i])
  elif i < N - 1 and A[i-1] != A[i] and A[i] == A[i+1]:
    d_set.add(A[i])

print( len(c_set - d_set) )
### BUGGY CODE ###

n = int(input())
t = [0] * (n + 1)
for x in range(1,n + 1):
    for y in range(1,n - x):
        for z in range(1,n - x - y):
            k = x * x + y * y + z * z + x * y + y * z + x * z
            if k <= n:
                t[k] += 1

for i in range(n):
    print(t[i + 1])

### FIXED CODE ###

import math
n = int(input())
t = [0] * (n + 1)
m = math.floor(math.sqrt(n))

for i in range(1,m):
    for j in range(1,m):
        for k in range(1,m):
            p = i*i+j*j+k*k+i*j+j*k+i*k
            if p <= n:
                t[p] += 1

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

from queue import Queue

#入力
H, W = map(int, input().split())

#lst = [['a']*W for _ in range(H)]
count = 0 #白色のマスの総数
lst = []
row = []
for i in range(H):
    row = list(input())
    count += row.count('.')
    lst += [row]
 
#for i in range(H):
#    for j in range(W):
#        if lst[i][j] == '.':
#            count += 1

sx, sy = 1, 1 #スタート位置
gx, gy = H, W #ゴール位置

move = [[-1, 0], [1,0], [0, -1], [0, 1]]

def bfs(x, y):
    q = Queue()
    INF = 10 ** 9
    d = [[INF]* W for _ in range(H)]
    q.put(x)
    q.put(y)
    d[x][y] = 0

    while True:
        px = q.get()
        py = q.get()
        if px == gx-1 and py == gy-1:
            break
        else:
            for dx, dy in move:
                nx = px + dx
                ny = py + dy

                if 0 <= nx and nx < H and 0 <= ny and ny < W and lst[nx][ny] == '.' and d[nx][ny] == INF:
                    q.put(nx)
                    q.put(ny)
                    d[nx][ny] = d[px][py] + 1
    return d[gx-1][gy-1]

a = bfs(sx-1, sy-1)

if a == 10 **9:
    print (-1)
else:
    print (count - a - 1)

### FIXED CODE ###

from queue import Queue

#入力
H, W = map(int, input().split())

#lst = [['a']*W for _ in range(H)]
count = 0 #白色のマスの総数
lst = []
row = []
for i in range(H):
    row = list(input())
    count += row.count('.')
    lst += [row]
 
#for i in range(H):
#    for j in range(W):
#        if lst[i][j] == '.':
#            count += 1

#sx, sy = 1, 1 #スタート位置
#gx, gy = H, W #ゴール位置

move = [[-1, 0], [1,0], [0, -1], [0, 1]]

def bfs():
    q = Queue()
    INF = 10 ** 9
    d = [[INF]* W for _ in range(H)]
    q.put(0)
    q.put(0)
    d[0][0] = 0

    while True:
        if q.empty():
            break
        else:
            px = q.get()
            py = q.get()
            if px == H-1 and py == W-1:
                break
            else:
                for dx, dy in move:
                    nx = px + dx
                    ny = py + dy

                    if 0 <= nx and nx < H and 0 <= ny and ny < W and lst[nx][ny] == '.' and d[nx][ny] == INF:
                        q.put(nx)
                        q.put(ny)
                        d[nx][ny] = d[px][py] + 1
    return d[H-1][W-1]

a = bfs()

if a == 10 **9:
    print (-1)
else:
    print (count - a - 1)
### BUGGY CODE ###

n, k, l = map(int, input().split())
load = list(range(n + 1))
train = list(range(n + 1))

def find(x, u):
    if u[x] == x :
        return x
    else:
        return find(u[x],u)

for i in range(k):
    p, q = map(int, input().split())
    rp = find(p, load)
    rq = find(q, load)
    if rp != rq:
        root = min(rp, rq)
        load[q] = root
        load[p] = root
        load[rp] = root
        load[rq] = root
load = [find(x,load) for x in load]

for i in range(l):
    r, s = map(int, input().split())
    rr = find(r, train)
    rs = find(s, train)
    if rr != rs:
        root = min(rr, rs)
        train[s] = root
        train[r] = root
        train[rr] = root
        train[rs] = root
train = [find(x,train) for x in train]


ans = []
for x, y in zip(load, train):
    if x == -1 or y == -1:
        ans.append(1)
    else:
        ans.append(sum([(x == X and y == Y) for X, Y in zip(load,train)]))

print(*ans[1:])

### FIXED CODE ###

n, k, l = map(int, input().split())
load = [-1] * (n + 1)
train = [-1] * (n + 1)

def find_load(x, u = load):
    if u[x] < 0 :
        return x
    else:
        u[x] = find_load(u[x])
        return u[x]

def find_train(x, u = train):
    if u[x] < 0 :
        return x
    else:
        u[x] = find_train(u[x])
        return u[x]

for i in range(k):

    p, q = map(int, input().split())
    p, q = map(find_load, [p, q])
    p, q = sorted((p, q))
    if p != q:
        load[q] = p

load = [i if x < 0 else x for i, x in enumerate(load)]

for i in range(l):
    r, s = map(int, input().split())
    r, s = map(find_train, [r, s])
    r, s = sorted((r, s))
    if r != s:
        train[s] = r
train = [i if x < 0 else x for i, x in enumerate(train)]

keys = []
dic  = {}

for node in range(n):
    key = (find_load(load[node + 1]), find_train(train[node + 1]))
    keys.append(key)
    if key in dic:
        dic[key] += 1
    else:
        dic[key] = 1

ans = [str(dic[key]) for key in keys]
print(" ".join(ans))
### BUGGY CODE ###

N=int(input());A=sorted((int(x),i)for i,x in enumerate(input().split()));t=[0]*N**2
for w in range(N):
 a,j=A[w]
 for l in range(N-w):r=l+w;p=a*abs(j-l);t[l*N+r]=max(p+t[(l+1)*N+r],a*abs(j-r)+t[l*N+r-1])if w else p
print(t[N-1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
N = int(input())
A = list(map(int, input().split()))
acts = [(x, i) for i, x in enumerate(A)]
acts.sort()
dp = [[-1]*N for _ in range(N)]

def solve(l, r):
    if r < l:
        return 0
    if dp[l][r] >= 0:
        return dp[l][r]
    k = r - l
    act, init_pos = acts[k]
    gain_l = act * abs(l - init_pos)
    gain_r = act * abs(r - init_pos)
    res = dp[l][r] = max(gain_l + solve(l+1, r), gain_r + solve(l, r-1))
    return res

print(solve(0, N-1))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(100000000)


def main():
    n = int(input())
    ls = list(map(int, input().split()))
    dic = {}
    for x in ls:
        z = dic.setdefault(x, 0)
        dic[x] = z + 1

    for i in range(n):
        # ls[i]を除く
        a = ls[i]
        dic[a] -= 1
        res = 0
        for k, v in dic.items():
            if v < 2:
                continue
            elif v == 2:
                res += 1
            else:
                res += int(v*(v-1)/2)
        print(res)
        dic[a] += 1


main()


### FIXED CODE ###

def z(z_dic, v: int):
    if v in z_dic:
        return z_dic[v]
    z = 0
    if v == 2:
        z = 1
    elif v > 2:
        z = int(v*(v-1)/2)
    z_dic.setdefault(v, z)
    return z


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

    ar = [0] * (n+1)
    ls = []

    for x in map(int, input().split()):
        ls.append(x)
        ar[x] += 1

    zls = []
    zls2 = []

    z_dic = {}

    for i in range(1, n+1):
        v = ar[i]
        zls.append(z(z_dic, v))
        zls2.append(z(z_dic, v-1))
    ss = sum(zls)

    for i in range(1, n+1):
        aa = ls[i-1]
        print(ss - zls[aa-1] + zls2[aa-1])
    #
    # itr = map(int, input().split())
    # dic = {}
    # for num in itr:
    #     dic.setdefault(num, 0)
    #     dic[num] += 1
    #     ls.append(num)
    #
    # for i in range(n):
    #     # ls[i]を除く
    #     a = ls[i]
    #     dic[a] -= 1
    #     res = 0
    #     for k, v in dic.items():
    #         if v < 2:
    #             continue
    #         elif v == 2:
    #             res += 1
    #         else:
    #             res += int(v*(v-1)/2)
    #     print(res)
    #     dic[a] += 1


main()
### BUGGY CODE ###

N, K = [int(_) for _ in input().split()]
H = [int(_) for _ in input().split()]
dp = [float('inf')] * N
dp[0] = 0
for i in range(N - 1):
    for j in range(1, K + 1):
        if i + j < N:
            dp[i + j] = min(dp[i + j], dp[i] + abs(H[i + j] - H[i]))
print(dp[-1])


### FIXED CODE ###

N, K = [int(_) for _ in input().split()]
H = [int(_) for _ in input().split()]
dp = [float('inf')] * N
dp[0] = 0
for i in range(N - 1):
    for j in range(1, K + 1):
        if i + j < N:
            dp[i + j] = min(dp[i + j], dp[i] + abs(H[i + j] - H[i]))
print(dp[-1])
### BUGGY CODE ###

'''
参考: https://beta.atcoder.jp/contests/agc026/submissions/2849460
'''

if __name__ == '__main__':
    n = int(input())
    s = input()

    s_left = s[:n]
    s_right = s[n:]
    m = dict()

    Bs = [bin(x)[2:].zfill(n) for x in range(2 ** n)]
    intBs = [list(map(int, list(x))) for x in Bs]

    for b in intBs:
        s_red, s_blue = '', ''
        for i in range(n):
            if b[i] == 0:
                s_red += s_left[i]
            else:
                s_blue += s_left[i]
        if (s_red, s_blue) in m:
            m[(s_red, s_blue)] += 1
        else:
            m[(s_red, s_blue)] = 1

    ans = 0
    for b in intBs:
        s_red, s_blue = '', ''
        for i in range(n):
            if b[i] == 0:
                s_red += s_right[i]
            else:
                s_blue += s_right[i]

        s_red = s_red[::-1]
        s_blue = s_blue[::-1]
        
        if (s_red, s_blue) in m:
            ans += m[(s_red, s_blue)]
    print(ans)

### FIXED CODE ###

def main():
    from collections import defaultdict

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

    L, R = S[:N], S[N * 2 - 1:N - 1:-1]

    def make_counter(s: str) -> defaultdict(int):
        ret = defaultdict(int)
        for bit in range(1 << N):
            red, blue = '', ''
            for j in range(N):
                if (bit >> j) & 1:
                    red += s[j]
                else:
                    blue += s[j]

            ret[red + '_' + blue] += 1
        return ret

    ld = make_counter(L)
    rd = make_counter(R)

    print(sum(ld[key] * rd[key] for key in ld))


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

K, S = map(int, input().split())
Y = 0

for i in range(K+1):
  for j in range(K+1):
    for k in range(K+1):
      if i+j+k == S:
        Y = Y+1

print(Y)

### FIXED CODE ###

K, S = map(int, input().split())
Y = 0

for i in range(K+1):
  for j in range(K+1):
    if 0 <= S-i-j and S-i-j <= K:
      Y = Y+1

print(Y)
### BUGGY CODE ###

k = int(input())
a = list(map(str, list(range(1, 10))))
ans = a + []
while len(ans) < k:
    b = []
    for i in a:
        inti = int(i)
        if inti > 323456666:
            break
        il = i[-1]
        intil = int(il)
        if intil == 0:
            ad = [0,1]
        elif intil == 9:
            ad = [8,9]
        else:
            ad = [intil-1, intil, intil+1]
        c = [i + str(j) for j in ad]
        b = b + c
    a = b
    ans = ans + b

print(ans[k-1])

### FIXED CODE ###

k = int(input())
from collections import deque
q = deque()
a = list(map(str, list(range(1, 10))))
ans = a + []
illist = []
for i in range(10):
    if i == 0:
        illist.append(["0","1"])
    elif i == 9:
        illist.append(["8","9"])
    else:
        illist.append([str(i-1),str(i),str(i+1)])
for i in range(1,10):
    q.append(str(i))

node = "0"
while node != "323456667":
    node = q.popleft()
    for j in illist[int(node[-1])]:
        nodej = node+j
        q.append(nodej)
        a.append(nodej)

print(a[k - 1])
### BUGGY CODE ###

n = int(input())
d = []
for i in range(n):
    s = input()
    if not(s in d): d.append(s)

print(len(d))



### FIXED CODE ###

n = int(input())
d = {}
for i in range(n):
    s = input()
    if not(s in d): d[s] = 1

print(len(d))
### BUGGY CODE ###

import numpy as np
n,k = map(int, input().split())
As = list(map(int, input().split()))

def f(x):
    # サイズxで切る
    cnt = 0
    for a in As:
        # 斬らなければイケない本数
        cnt += int(np.ceil(a/x))-1
        if cnt > k:
            return False
    # 斬らなければいけない本数がk本以下
    return cnt <= k

l = 10**-6
r = 10**9
while r-l > 10**-1:
    # print(l,r)
    m = (l+r)/2
    if f(m):
        r = m
    else:
        l = m
print(int(np.ceil(l)))

### FIXED CODE ###

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

def f(x):
    # サイズxで切る
    cnt = 0
    for a in As:
        # 斬らなければイケない本数
        cnt += int((a-0.01)/x)
        if cnt > k:
            return False
    # 斬らなければいけない本数がk本以下
    return cnt <= k

l = 10**-2
r = 10**9
while r-l > 10**-1:
    m = (l*r)**0.5
    if f(m):
        r = m
    else:
        l = m
print(int(l)+1)