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

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

count = 0
for i in range(n):
    l1 = s[i]
    for j in range(i + 1, n):
        if s[j] == l1:
            continue
        else:
            l2 = s[j]
        for k in range(j + 1, n):
            if s[k] == l1 or s[k] == l2 or (j - i) == (k - j):
                continue
            else:
                count += 1
print(count)

### FIXED CODE ###

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

import random
from collections import Counter

res = 1
val = Counter(s).values()
if len(val) < 3:
    print(0)
    exit()

for i in val:
    res *= i

count = 0
for i in range(n):
    j = 1
    while i + 2 * j < n:
        if (s[i] != s[i+j]) and (s[i+j] != s[i+2*j]) and (s[i] != s[i+2*j]):
            count += 1
        j += 1

print(res - count)
### BUGGY CODE ###

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

for i in range(n):
    tmp=0
    ans=0
    for j in range(n):
        if i==j:
            continue
        ans+=abs(tmp-a_input[j])
        tmp=a_input[j]
    if i==n-1:
        ans+=abs(a_input[-2])
    else:
        ans+=abs(a_input[-1])
    print(ans)




### FIXED CODE ###

n = int(input())
a_input = [0]+list(map(int,input().split()))+[0]

cost_li = [0]*(n+1)
cost_li[0]=a_input[1]
cost_li[-1]=abs(a_input[-2])

for i in range(1,n+1):
    cost_li[i-1]=abs(a_input[i]-a_input[i-1])

sum_cost = sum(cost_li)

for i in range(1,n+1):
    ans = sum_cost-cost_li[i-1]-cost_li[i]+abs(a_input[i+1]-a_input[i-1])
    print(ans)
### BUGGY CODE ###

s = int(input())
arr = []

arr.append(s)

while s <= 5:
    if s % 2 == 0:
        s = s // 2
        arr.append(s)
    else:
        s = 3 * s + 1
        arr.append(s)

while s > 4:
    if s % 2 == 0:
        s = s // 2
        arr.append(s)
    else:
        s = 3 * s + 1
        arr.append(s)

print(len(arr) + 3)

### FIXED CODE ###

s = int(input())
arr = []

arr.append(s)

while s > 4:
    if s % 2 == 0:
        s = s // 2
        arr.append(s)
    else:
        s = 3 * s + 1
        arr.append(s)

if s == 3:
    print(9)
else:
    print(len(arr) + 3)
### BUGGY CODE ###

k,s=map(int,input().split())
c=0

for l in range(k+1):
    for m in range(k+1):
        for n in range(k+1):
            if l+m+n==s:
                c+=1
            elif l+m+n>s:
                break
print(c)

### FIXED CODE ###

k,s=map(int,input().split())
c=0

for l in range(k+1):
    for m in range(k+1):
        if 0<=s-l-m and s-l-m<=k:
            c+=1
print(c)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
 
num_cnt = [0]*n
sum_cnt = 0
 
for num in range(n):
    cnt = a.count(num+1)
    if cnt > 0:
        num_cnt[num] = cnt
        sum_cnt += cnt*(cnt-1)//2
res = [0]*n
 
for num in range(n):
    cnt = num_cnt[num]
    res[num] = (sum_cnt - (cnt-1)) if cnt != 0 else 0
 
for a_k in a:
    print(res[a_k-1])

### FIXED CODE ###

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

import collections
cnt = collections.Counter(a)

sum_cnt = 0
for v in cnt.values():
    sum_cnt += v*(v-1)//2

res = []
for value in a:
    res.append(str( sum_cnt - (cnt[value]-1) ))
print('\n'.join(res))
### BUGGY CODE ###

import copy,numpy
n=int(input())
A=[int(input()) for _ in range(n)]
for i,_ in enumerate(A):
    B=copy.copy(A)
    del B[i]
    print(numpy.max(B))

### FIXED CODE ###

n=int(input())
A=[int(input()) for _ in range(n)]
ma=max(A)
ma_i=A.index(ma)
for i in range(n):
    if i==ma_i:
        print(max(A[:i]+A[i+1:]))
    else:
        print(ma)
### BUGGY CODE ###

def solve():
    n, m = map(int, input().split())
    h = list(map(int, input().split()))
    ab = [list(map(int, input().split())) for _ in range(m)]

    cnt = [0]*n
    for i in range(n):
        num = 0
        for j in range(m):
            a, b = ab[j]
            if a == i+1:
                if h[i] <= h[b-1]:
                    cnt[i] -= 1
                num += 1
            elif b == i+1:
                if h[i] <= h[a-1]:
                    cnt[i] -= 1
                num += 1
        if num == 0:
            cnt[i] = 0


    return cnt.count(0)




print(solve())


### FIXED CODE ###

def solve():
    n, m = map(int, input().split())
    h = list(map(int, input().split()))
    ab = [list(map(int, input().split())) for _ in range(m)]

    cnt = [0]*n
    for j in range(m):
        a, b = ab[j]
        if h[a-1] < h[b-1]:
            cnt[a-1] -= 1
        elif h[b-1] < h[a-1]:
            cnt[b-1] -= 1
        elif h[a-1] == h[b-1]:
            cnt[a-1] -= 1
            cnt[b-1] -= 1

    
    return cnt.count(0)




print(solve())
### BUGGY CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10000000)
n,m,q=map(int,input().split())
abcd=[list(map(int,input().split()))for _ in range(q)]
def dfs(li):
  ans=0
  for a,b,c,d in abcd:
    if li[b-1]-li[a-1]==c:ans+=d
  for i in range(n-1):
    if li[i]<li[i+1]:
      li[i]+=1
      ans=max(ans,dfs(li))
      li[i]-=1
  if li[-1]!=m:
    li[-1]+=1
    ans=max(ans,dfs(li))
    li[-1]-=1
  return ans
print(dfs([1]*n))

### FIXED CODE ###

import itertools
n,m,q=map(int,input().split())
abcd=[list(map(int,input().split()))for _ in range(q)]
ans=0
for i in itertools.combinations_with_replacement(range(m),n):
  anss=0
  for a,b,c,d in abcd:
    if i[b-1]-i[a-1]==c:anss+=d
  ans=max(ans,anss)
print(ans)
### BUGGY CODE ###

import functools
import operator

prod = functools.partial(functools.reduce, operator.mul)
count = int(input())
list = list(map(int, input().split()))
sum = prod(list)

if sum > 1000000000000000000:
    sum = -1

print(sum)

### FIXED CODE ###

from functools import reduce
from operator import mul
import sys
input = sys.stdin.readline

count = int(input())
list = list(map(int, input().split()))
sum = list[0]
if 0 in list:
    print(0)
    exit()
else:
    for i in range(count - 1):
        sum = sum * list[i + 1]
        if sum > 1000000000000000000:
            print(-1)
            exit()


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

S = input()
Q = int(input())
pre = []
suf = []
for i in range(Q):
    q = input().split()
    if len(q) == 1:
        pre, suf = suf[::-1], pre[::-1]
        S = S[::-1]
    else:
        if q[1] == '1':
            pre = pre[::-1]
            pre.append(q[2])
            pre = pre[::-1]
        else:
            suf.append(q[2])
print(''.join(pre) + S + ''.join(suf))


### FIXED CODE ###

from collections import deque
S = input()
Q = int(input())
pre = deque()
suf = deque()
rev = False
for i in range(Q):
    q = input().split()
    if len(q) == 1:
        rev = not rev
    else:
        if (not rev and q[1] == '1') or (rev and q[1] == '2'):
            pre.appendleft(q[2])
        else:
            suf.append(q[2])
if rev:
    S = S[::-1]
    p = list(suf)[::-1]
    s = list(pre)[::-1]
else:
    p = list(pre)
    s = list(suf)
print(''.join(p) + S + ''.join(s))
### BUGGY CODE ###

import numpy as np
import copy

def main():
    N, K = map(int, input().split())
    p = list(map(float, input().split()))

    p = np.array(p)
    p_prime = p
    p_1 = p + 1
    p = p * p_1 / 2
    p = p / p_prime
    k = p
    for i in range(K-1):
        k = k + np.roll(p, i+1)

    print(max(k))


    return 0

if __name__ == '__main__':
    main()

### FIXED CODE ###

import math
def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))

    P_e = []
    for p in P:
        P_e.append((1 + p)/2)

    P_sum = [0]
    tmp = 0
    for i in range(N):
        tmp += P_e[i]
        P_sum.append(tmp)

    max = 0
    for i in range(K, N+1):
        tmp = P_sum[i] - P_sum[i-K]
        if tmp > max:
            max = tmp

    print(max)
    return 0
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import numpy as np
n=int(input())
s=[a for a in input()]
s=[a.replace('.','0') for a in s]
s=[a.replace('#','1') for a in s]
s=[int(a) for a in s]
p=[i for i, x in enumerate(s) if x == 1]
s = np.array(s)
cnt = np.sum(s)
for i in p:
    s[-1 * (n-i):] = 1 - s[-1 * (n-i):]
    _cnt = np.sum(s)
    if cnt > _cnt:
        cnt =_cnt
print(cnt)

### FIXED CODE ###

n=int(input())
s=input()
cnt =s.count('#')
l =[cnt]
for i in range(n):
    if s[n-i-1] == '#':
        cnt -= 1
        l.append(cnt)
    else:
        cnt+=1
        l.append(cnt)
print(min(l))
### BUGGY CODE ###

#abc163c
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
 print(a.count(i+1))


### FIXED CODE ###

#abc163c
n=int(input())
a=list(map(int,input().split()))
res=[0]*n
for x in a:
 res[x-1]+=1
for i in res:
 print(i)
### BUGGY CODE ###

# distutils: language=c++
# cython: language_level=3, boundscheck=False, wraparound=False
# cython: cdivision=True

def INT(): return int(input())
def MAPINT(): return map(int, input().split())
def LMAPINT(): return list(map(int, input().split()))
def STR(): return input()
def MAPSTR(): return map(str, input().split())
def LMAPSTR(): return list(map(str, input().split()))

def main():
  n = INT()
  a = sorted(LMAPINT())

  ans = [0] * (max(a) + 1)
  for x in a:
    # 重複
    if ans[x] == 0:
      for j in range(x, max(a)+1, x):
        ans[j] += 1
    else:
      ans[x] = 2
  
  print(len(list(filter(lambda x: ans[x] == 1, a))))


if __name__ == '__main__':
  main()

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
 
xs = [0] * (max(a) + 1)
 
for v in a:
    if xs[v] == 0:
        for j in range(v, len(xs), v):
            xs[j] += 1
    else:
        xs[v] += 1
print(len(list(filter(lambda v: xs[v] == 1, a))))
### BUGGY CODE ###

A, B, C, D, E, F = map(int, input().split())

#memo
list = [0, 0]

#操作1-4
ope1 = 100 * A
ope2 = 100 * B
ope3 = C
ope4 = D
#入れた水、砂糖の総量
w_sum = 0
s_sum = 0
#パーセンテージ
p = 0
#トータル
total = w_sum + s_sum
#砂糖の表示用の変数
s = 0

for i in range(101):
    for j in range(101):
        for k in range(31):
            for l in range(31):
                w_sum = l * ope1 + k * ope2
                s_sum = j * ope3 + i * ope4
                if w_sum != 0 and w_sum + s_sum <= F and s_sum <= E * (l + k) :
                    p_tmp = (s_sum / (w_sum + s_sum)) * 100
                    if p_tmp >= p:
                        p = p_tmp
                        list[0] = w_sum + s_sum
                        list[1] = s_sum

print(list[0], list[1])                        


### FIXED CODE ###

def solve():
    
    A, B, C, D, E, F = map(int, input().split())
    memo = {}
    
    for a in range(31):
        for b in range(31):
            for c in range(101):
                for d in range(101):
                    w = (100*A)*a + (100*B)*b
                    s = C*c + D*d
                    if w ==0:
                        break
                    if w+s > F:
                        break
                    else:
                        if w/100 * E >= s:
                            density = 100*s/(w+s)
                            memo[a,b,c,d] = density
    
    max_v = max(memo.values())
    
    for k, v in memo.items():
        if v == max_v:
            print((100*A)*k[0] + (100*B)*k[1] + C*k[2] + D*k[3], C*k[2] + D*k[3] )
            break
 
if __name__ == '__main__':
    solve()
### BUGGY CODE ###

H, N = map(int, input().split())
magic = [list(map(int, input().split())) for _ in range(N)]

INF = 10**9
dp = [[INF for _ in range(H+10)] for _ in range(N+1)]

for i in range(1, N+1):
    a, b = magic[i-1]
    dp[i][0] = 0
    for j in range(1, H+1):
        dp[i][j] = min(dp[i][max(0, j-a)]+b, dp[i-1][j])

print(dp[N][H])

### FIXED CODE ###

H, N=map(int, input().split())
AB=[list(map(int, input().split())) for _ in range(N)]
AB.sort(key=lambda x: x[1])
dp=[[0 for _ in range(H+1)] for _ in range(N)]
A, B=AB[0]
for j in range(1, H+1):
  dp[0][j]=((j-1)//A+1)*B
for i in range(1, N):
  A, B=AB[i]
  for j in range(H+1):
    if j>=A:
      dp[i][j]=min(dp[i-1][j], dp[i-1][j-A]+B, dp[i][j-A]+B)
    else:
      dp[i][j]=min(dp[i-1][j], B)
print(dp[N-1][H])
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
for lz in range(Q):
  l1,l2=map(int,input().split())
  print(S[l1-1:l2].count('AC'))

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
k = [0] * (N+1)

for i in range(1,N):
  v = 1 if S[i-1]+S[i] == 'AC' else 0
  k[i] = k[i-1] + v
k[-1]=k[-2]
for _ in range(Q):
  f,l = map(int,input().split())
  print(k[l-1] - k[f-1])
### BUGGY CODE ###

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = [[]]
for i in range(N):
    A.append(LIST()[::-1])

cnt = N*(N-1)//2
nxtli = set(range(1, N+1))
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    # 前回変更があった場所のみでループを回す
    curli = nxtli.copy()
    nxtli = set()
    for i in curli:
        if len(A[i]) and not skip[i]:
            a = A[i][-1]
            if len(A[a]) and not skip[a]:
                b = A[a][-1]
                if i == b:
                    A[i].pop()
                    A[a].pop()
                    # 変更があった場所をリストに入れておく
                    if len(A[i]):
                        nxtli.add(i)
                    if len(A[a]):
                        nxtli.add(a)
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    day += 1
print(day)


### FIXED CODE ###

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

import sys
import time
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = [deque()]
for i in range(N):
    A.append(deque(LIST()))

start = time.time()

cnt = N*(N-1)//2
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    for i in range(1, N+1):
        if len(A[i]) and not skip[i]:
            a = A[i][0]
            if len(A[a]) and not skip[a]:
                b = A[a][0]
                if i == b:
                    A[i].popleft()
                    A[a].popleft()
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    day += 1

    elapsed_time = time.time() - start
    if elapsed_time > 1:
        print(N*(N-1)//2)
        exit()
print(day)
### BUGGY CODE ###

N = int(input())
# N = 3

items = []

for i in range(0, N) :
    newItem = str(input())
    # newItem = str("apple")
    # print(newItem)
    
    if newItem not in items :
        items.append(newItem)

print(len(items)) # don't forget print()!

### FIXED CODE ###

N = int(input())
# N = 3

items = set()

for i in range(0, N) :
    items.add(str(input()))
    # items.add(str("apple"))
    # print(newItem)

print(len(items)) # don't forget print()!
### BUGGY CODE ###

from collections import defaultdict
N = int(input())
G = defaultdict(list)
A = list(map(int, input().split()))
A = sorted(A)
for i in range(N):
    for j in range(i + 1, N):
        for k in range(30):
            if i != j and A[i] + A[j] == 2 ** k:
                G[i].append(N + j)
                G[j].append(N + i)
                break
            if A[i] + A[j] < 2 ** k:
                break


used = [False] * 2 * N
match = [-1] * 2 * N


def dfs(v):
    global used
    used[v] = True
    for u in G[v]:
        w = match[u]
        if w < 0 or not used[w] and dfs(w):
            match[v] = u
            match[u] = v
            return True


ma = 0
for i in range(N):
    if match[i] < 0:
        used = [False] * 2 * N
        if dfs(i):
            ma += 1

print(ma // 2)

### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
pow2 = [1]
for i in range(31):
    pow2.append(pow2[-1] * 2)
a = sorted(a, reverse=True)
d = defaultdict(int)
for i in a:
    d[i] += 1


num = 0
for i in range(N):
    if d[a[i]] == 0:
        continue
    for k in range(30, -1, -1):
        inv = pow2[k] - a[i]
        if inv < 0 or inv > a[i]:
            continue
        if inv != a[i]:
            if d[inv] > 0 and d[a[i]] > 0:
                p = min(d[inv], d[a[i]])
                num += p
                d[inv] -= p
                d[a[i]] -= p
                break
        else:
            if d[a[i]] >= 2:
                num += d[a[i]] // 2
                d[a[i]] %= 2
                break
print(num)
### BUGGY CODE ###

# @oj:atcoder
# @id: hitwanyang
# @email: 296866643@qq.com
# @date: 2020-04-20 10:31
# @url:https://atcoder.jp/contests/dp/tasks/dp_b
nk=list(map(int,input().split()))
h=list(map(int,input().split()))
n=nk[0]
k=nk[1]
dp=[10**9]*n
dp[0]=0
dp[1]=abs(h[1]-h[0])
for i in range(2,n):
    for j in range(i-k,i):
        if j>=0:
            dp[i]=min(dp[j]+abs(h[i]-h[j]),dp[i])

print (dp[-1])

### FIXED CODE ###

import sys


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


def main():
    size, jumps = map(int, input().split())
    array = list(map(int, input().split()))
    dp = [999999999] * size
    dp[0]= 0
    dp[1] = abs(array[0]- array[1])
    for i in range(2,size):
        dp[i] = min(abs(array[i] - array[j]) + dp[j] for j in range(max(0, i - jumps), i))
    print(dp[size-1])

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

q = int(input())

for i in range(q):
    x = list(input())
    y = list(input())
    lcs = [[0 for i in range(len(x)+1)] for j in range(len(y)+1)]
    for i in range(1,len(y) + 1):
        for j in range(1,len(x) + 1):
            if x[j-1] != y[i-1]:
                lcs[i][j] = max(lcs[i-1][j-1],lcs[i][j-1],lcs[i-1][j])
            else:
                lcs[i][j] = max(lcs[i-1][j-1] + 1,lcs[i][j-1],lcs[i-1][j])
    print(lcs[i][j])

### FIXED CODE ###

q = int(input())
 
def lcss(x,y):
     
    lcs = [0]*(len(x)+1)
    for i in range(len(y)):
        w1 = y[i]
        lcs_2 = lcs[:]
        for j in range(len(x)):
            if x[j] == w1:
                lcs[j+1] = lcs_2[j] + 1  
            elif lcs[j+1] < lcs[j]:
                lcs[j+1] = lcs[j]
    return lcs[-1]
 
for i in range(q):
    x = input()
    y = input()
    print(lcss(x,y))
### BUGGY CODE ###

def calculate_money(array):
    return [i * j for (i, j) in zip(array, money_list)]


if __name__ == '__main__':
    input_list = input().split()
    N = int(input_list[0])
    Y = int(input_list[1])
    money_list = [10000, 5000, 1000]
    num_list = []

    for x_num in range(0, N + 1):
        for y_num in range(0, N + 1 - x_num):
            num_list.append([x_num, y_num, N - x_num - y_num])

    cal_list = list(map(calculate_money, num_list))

    result = []

    for num, cal in enumerate(cal_list):
        if sum(cal) == Y:
            result = num_list[num]

    if len(result) == 0:
        print("-1 -1 -1")
    else:
        print(" ".join(map(str, result)))


### FIXED CODE ###

def calculate_money():
    input_list = input().split()
    N = int(input_list[0])
    Y = int(input_list[1])

    for x_num in range(0, N + 1):
        for y_num in range(0, N + 1 - x_num):
            z_num = N - x_num - y_num
            if 10000 * x_num + 5000 * y_num + 1000 * z_num == Y:
                print(x_num, " ", y_num, " ", z_num)
                return
    print("-1 -1 -1")


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

from queue import Queue
import sys

inf = float("inf")
N, M = list(map(int, input().split()))
to = [[] for x in range(N+1)]
cost = [[] for x in range(N+1)]
value = [inf for x in range(N+1)]

for i in range(M):
    l, r, d = list(map(int, input().split()))
    to[l].append(r)
    cost[l].append(d)
    to[r].append(l)
    cost[r].append(-d)

for i in range(1, N+1):
    if value[i] != inf: continue
    
    value[i] = 0
    q = Queue()
    q.put(i)
    while not q.empty():
        tmp = q.get()
        for j in range(len(to[tmp])):
            nxt = to[tmp][j]
            nxt_val = value[tmp] + cost[tmp][j]
            if value[nxt] != inf:
                if value[nxt] == nxt_val: continue
                print("No")
                sys.exit()
            value[nxt] = nxt_val
            q.put(nxt)
print("Yes")

### FIXED CODE ###

from queue import Queue
import sys

inf = float("inf")
N, M = list(map(int, input().split()))
dist = [[] for x in range(N+1)]
value = [inf for x in range(N+1)]

for i in range(M):
    l, r, d = list(map(int, input().split()))
    dist[l].append((r, d))
    dist[r].append((l, -d))

for i in range(1, N+1):
    if value[i] != inf: continue
    
    value[i] = 0
    q = Queue()
    q.put(i)
    while not q.empty():
        tmp = q.get()
        for x in dist[tmp]:
            nxt = x[0]
            nxt_val = value[tmp] + x[1]
            if value[nxt] != inf:
                if value[nxt] == nxt_val: continue
                print("No")
                sys.exit()
            value[nxt] = nxt_val
            q.put(nxt)
print("Yes")
### BUGGY CODE ###

import math
import bisect
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
for _ in range(M):
    x=math.floor(A.pop(N-1)/2)
    bisect.insort(A,x)
print(sum(A))


### FIXED CODE ###

import math
import bisect
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
for _ in range(M):
    x=math.floor(A.pop(N-1)/2)
    bisect.insort(A,x)
print(sum(A))
### BUGGY CODE ###

K=int(input())
a=K
while a%2==0:
    a//=2
while a%5==0:
    a//=5
if a==1:
    print(1)
else:
    mod=set([])
    a=1
    while a not in mod:
        mod.add(a)
        a*=10
        a%=K

    mod=list(mod)
    n=len(mod)
    check=1
    table=[0 for i in range(0,n)]
    for i in range(1,46):
        for j in range(0,n):
            table[j]=(check<<mod[j])|check
        ans=0
        for j in range(0,n):
            ans=ans|table[j]
        check=ans
        for j in range(1,46):
            if (check>>j*K)&1==1:
                print(i)
                exit()

### FIXED CODE ###

K=int(input())
a=K
while a%2==0:
    a//=2
while a%5==0:
    a//=5
if a==1:
    print(1)
else:
    mod=set([])
    a=1
    while a not in mod:
        mod.add(a)
        a*=10
        a%=K

    mod=list(mod)
    n=len(mod)
    wei=pow(2,K)-1
    check=1
    ans=0
    for j in range(0,n):
        ans=ans|(check<<mod[j])
    check=ans
    for i in range(1,46):
        if check>>0 &1==1:
            print(i)
            exit()
        ans=check
        for j in range(0,n):
            ans=ans|(check<<mod[j])
        ans1=ans&wei
        ans2=ans>>K
        check=ans1|ans2