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

n, p = map(int, input().split())
s = input()

p_cnt = 0
for i in range(n):
    for j in range(i+1, n+1):
        if int(s[i:j]) % p == 0:
            p_cnt += 1

print(p_cnt)

### FIXED CODE ###

n, p = map(int, input().split())
s = [int(i) for i in input()]
p_cnt = 0

if p == 2 or p == 5:
    for i in range(n):
        if s[i] % p == 0:
            p_cnt += i+1
        
else:
    s = s[::-1]
    div_dic = dict(zip(range(p), [0] * p))
    tmp = 0

    for i in range(n):
        tmp += s[i] * pow(10, i, p)
        tmp %= p
        div_dic[tmp] += 1

    for v in div_dic.values():
        p_cnt += v * (v - 1)
    p_cnt //= 2
    p_cnt += div_dic.get(0)

print(p_cnt)
### BUGGY CODE ###

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

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
temp = 1
if 0 in a:
  print(0)
else:
  for i in a:
    temp *= i
    if temp > 10**18:
      temp = -1
      break
  print(temp)
### BUGGY CODE ###

mod = int(1e9 + 7)
N = int(input())
A = [format(i, '060b') for i in map(int, input().split())]
S = 0
for k in range(60):
  s = [A[i][59-k] for i in range(N)]
  v = s.count('0')*s.count('1')
  S += (v<<k)
S %= mod
print(S)


### FIXED CODE ###

mod = int(1e9 + 7)
N = int(input())
A = [format(i, '060b') for i in map(int, input().split())]
S = 0
for k in range(60):
  s = [b[59-k] for b in A]
  v = s.count('0')*s.count('1')
  S += (v<<k)
S %= mod
print(S)
### BUGGY CODE ###

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

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

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

### FIXED CODE ###

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

length = len(a)
total = sum(a)

ans = 0
for i in range(0,length):
    total -= a[i]
    ans += (a[i] * total)


print(ans % (10**9 + 7))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(2*10**5)

n, q = map(int, input().split())
graph = {i: [] for i in range(n)}
for _ in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    graph[a].append(b)
    graph[b].append(a)
ans = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    ans[p-1] += x

def dfs(now, parent, add):
    if parent != -1:
        ans[now] += add
    for i in graph[now]:
        if i != parent:
            dfs(i, now, ans[now])

dfs(0, -1, 0)
print(' '.join(map(str, ans)))


### FIXED CODE ###

import sys

sys.setrecursionlimit(10**7)
input = sys.stdin.readline

n, q = map(int, input().split())
graph = {i: [] for i in range(n)}
for a, b in [[int(i)-1 for i in input().split()] for _ in range(n-1)]:
    graph[a].append(b)
    graph[b].append(a)
ans = [0] * n
for p, x in [[int(i) for i in input().split()] for _ in range(q)]:
    ans[p-1] += x

def dfs(now, parent):
    if parent != -1:
        ans[now] += ans[parent]
    for i in graph[now]:
        if i == parent:
            continue
        dfs(i, now)

dfs(0, -1)
print(' '.join(map(str, ans)))
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n = INT()
p = LIST()
ans = 0
arr = [0 for _ in range(n)]
for i in range(n):
    arr[p[i] - 1] = 1
    ans += 1 if sum(arr[p[i] - 1:]) == i + 1 else 0
print(ans)

### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n = INT()
p = LIST()
ans = 0
arr = [inf for _ in range(n)]
arr[0] = p[0]
for i in range(1, n):
    arr[i] = min(p[i], arr[i-1])
#print(arr)
for i in range(n):
    ans += 1 if arr[i] == p[i] else 0
    #print(i+1, arr, sum(arr[p[i] - 1:]), sum(arr[p[i] - 1:]) == i + 1)
print(ans)
### BUGGY CODE ###

n = int(input())

a_list = [int(i) for i in input().split()]
q = int(input())

BC_list = []

for _ in range(q):
    tmp = [int(i) for i in input().split()]
    BC_list.append(tmp)

# print(BC_list)

ary = [0 for _ in range((10 ** 5)+1)]

for i in a_list:
    ary[i] += i


for i in BC_list:
    b = i[0]
    c = i[1]
    ary[c] += (ary[b]/b)*c
    ary[b] = 0
    ans = int(sum(ary))
    print(ans)


### FIXED CODE ###

n = int(input())

a_list = [int(i) for i in input().split()]
q = int(input())

ary = [0 for _ in range((10**5) + 1)]

for i in a_list:
    ary[i] += 1

ans = []

f_ans = sum(a_list)
for _ in range(q):
    b, c = map(int, input().split())
    f_ans += (c-b)*ary[b]
    ary[c] += ary[b]
    ary[b] = 0

    ans.append(f_ans)

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

n = int(input())
s = list(map(int, input().rstrip()))
ans = [0] * 1000

for i in range(1000):
    if i < 10:
        x, y, z = 0, 0, i
    elif i < 100:
        x, y, z = 0, i // 10, i % 10
    else:
        x = i // 100
        y = (i - x * 100) // 10
        z = i % 10
    for a in range(len(s) - 2):
        if x != s[a]:
            continue
        else:
            for b in range(a + 1, len(s) - 1):
                if y != s[b]:
                    continue
                else:
                    for c in range(b + 1, len(s)):
                        if z != s[c]:
                            continue
                        else:
                            ans[x * 100 + y * 10 + z] = 1

print(sum(ans))

### FIXED CODE ###

n = int(input())
s = list(map(int, input().rstrip()))

ans = 0
for i in range(10):
    if i in s[:n - 2]:
        x = s.index(i)

        for j in range(10):
            if j in s[x + 1:n - 1]:
                y = x + s[x + 1:n - 1].index(j) + 1

                for k in range(10):
                    if k in s[y + 1:]:
                        ans += 1

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

# import numpy as np
# from decimal import Decimal

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

# A = np.array(A).astype(np.int64)

# ans = int(np.prod(A))


import functools
import operator
prod = functools.partial(functools.reduce, operator.mul)

ans = prod(A)

if ans > 10**18:
  print(-1)
else:
  print(ans)


### FIXED CODE ###

import sys

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

ans = 1

if 0 in A:
  print(0)
  sys.exit()

for i in range(N):
  ans *= A[i]
  if ans > 1e18:
    print(-1)
    sys.exit()
print(ans)
### BUGGY CODE ###

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

#整数値入力 1文字の入力
def input_one_number():
    return int(input())

#整数値龍力　複数の入力
def input_multiple_number():
    return map(int, input().split())

#整数値龍力　複数の入力(配列)
def input_multiple_number_as_list():
    return list(map(int, input().split()))



#複数の最小公倍数
def calc_lcm_list(l):
    lcm = l[0]
    for i in l:
        lcm = lcm * i // fractions.gcd(lcm, i)
    return lcm


import fractions
N = input_one_number()
lstA = input_multiple_number_as_list()

lcm = calc_lcm_list(lstA)

ans = 0

pow = 10**9 +7

print(sum(lcm//a for a in lstA)%pow)


### FIXED CODE ###

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

#整数値入力 1文字の入力
def input_one_number():
    return int(input())

#整数値龍力　複数の入力
def input_multiple_number():
    return map(int, input().split())

#整数値龍力　複数の入力(配列)
def input_multiple_number_as_list():
    return list(map(int, input().split()))

def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a
def lcm(a,b):
    return a*b//gcd(a,b)

def calc_gcd_list(l):
    gcd = l[0]
    for i in range(1, N):
        gcd = gcd(gcd, l[i])
    return gcd

def calc_lcm_list(l):
    lcm = 1
    for i in l:
        lcm = lcm * i // gcd(lcm, i)
    return lcm


N = input_one_number()
lstA = input_multiple_number_as_list()
lcm = calc_lcm_list(lstA)
pow = 10**9 +7
print(sum(lcm//a for a in lstA)%pow)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32

def solve(N: int):
    from functools import lru_cache
    # abc154を参考にメモ化で出すとTLE
    @lru_cache(None)
    def f(n: int):
        if 0 <= n <=5:
            return n
        elif 6 <= n < 10:
            return 10-n+1

        q, r = divmod(n, 10)
        # print(q, r)
        return min(
            f(q)+r,
            f(q+1)+10-r
        )
    # print(f(N))

    # N=36を考える
    l = list(map(int, list(str(N))))
    dp = 0,1
    for i in l:
        # a = f(3), f(36)
        a = min(dp[0]+i, dp[1]+10-i)
        # b = f(4), f(40)
        b = min(dp[0]+i+1, dp[1]+10-(i+1))
        dp = a, b

    print(dp[0])
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
# sys.setrecursionlimit(10000000)
# INF = 1<<32

def solve(N: "List[int]"):
    # N=36を考える
    # l = list(map(int, list(str(N))))
    dp = 0,1
    for i in N:
        # a = f(3), f(36)
        a = min(dp[0]+i, dp[1]+10-i)
        # b = f(4), f(40)
        b = min(dp[0]+i+1, dp[1]+10-(i+1))
        dp = a, b

    print(dp[0])
    return



def main():
    stdin = open(0)
    N = [int(x) for x in stdin.read().rstrip()]
    solve(N)

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

import functools
import operator
 
N = int(input())
mylist = list(map(int,input().split()))
Π = functools.partial(functools.reduce, operator.mul)
ans = (Π(mylist))
if ans <= 10**18:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

import math
import sys
N = int(input())
mylist = list(map(int, input().split()))
mylist.sort(reverse = True)
#print(mylist)
if mylist[-1] == 0:
    print(0)
    sys.exit()
else:
    myans = 1
    for m in mylist:
        myans *= m
        if myans > 10**18:
            print(-1)
            sys.exit()
    print(myans)
### BUGGY CODE ###

n=int(input())
a= list((map(int, input().split()))) 
b=[0]
c=[]
if 1 not in a:
  print(-1)
else:  
  for i in range(n):
    if a[0]-b[-1]==1:
      b.append(a.pop(0))
    else:
      c.append(a.pop(0))
  print(n-len(b)+1)

### FIXED CODE ###

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

count=1
for i in range(n):
  if a[i]==count:
    count+=1
if count==1:
  print(-1)
else:
  print(n-count+1)
### BUGGY CODE ###

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
N, M = lr()
S = [0] + lr()
T = [0] + lr()
dp = [[0] * (M+1) for _ in range(N+1)]
dp_cum = [[0] * (M+1) for _ in range(N+1)]
dp[0][0] = 1; dp_cum[0][0] = 1
for i in range(N+1):
    dp_cum[i][0] = 1
for j in range(M+1):
    dp_cum[0][j] = 1

for i in range(1, N+1):
    for j in range(1, M+1):
        if S[i] == T[j]:
            dp[i][j] = dp_cum[i-1][j-1]
        else:
            dp[i][j] = 0
        dp_cum[i][j] = dp_cum[i-1][j] + dp_cum[i][j-1] - dp_cum[i-1][j-1] + dp[i][j]

answer = dp_cum[N][M] % MOD
print(answer)
# 02

### FIXED CODE ###

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
N, M = lr()
S = [0] + lr()
T = [0] + lr()
dp = [[0] * (M+1) for _ in range(N+1)]
dp_cum = [[0] * (M+1) for _ in range(N+1)]
dp[0][0] = 1; dp_cum[0][0] = 1
for i in range(N+1):
    dp_cum[i][0] = 1
for j in range(M+1):
    dp_cum[0][j] = 1

for i in range(1, N+1):
    for j in range(1, M+1):
        if S[i] == T[j]:
            dp[i][j] = dp_cum[i-1][j-1]
        else:
            dp[i][j] = 0
        dp_cum[i][j] = (dp_cum[i-1][j] + dp_cum[i][j-1] - dp_cum[i-1][j-1] + dp[i][j]) % MOD

answer = dp_cum[N][M]
print(answer)
# 02
### BUGGY CODE ###

import os
import sys
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


@lru_cache(maxsize=None)
def solve(n):
    if n == 0:
        return 0
    if n < 0:
        return INF
    d = 0
    ret = INF
    while 6 ** d <= n:
        if n - 6 ** d >= 0:
            ret = min(ret, solve(n - 6 ** d) + 1)
        if n - 9 ** d >= 0:
            ret = min(ret, solve(n - 9 ** d) + 1)
        d += 1
    return ret


n = int(sys.stdin.buffer.readline())
ans = solve(n)
print(ans)


### FIXED CODE ###

import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

# MOD = 998244353


N = int(sys.stdin.buffer.readline())

s = {0}
ans = 0
while True:
    ns = set()
    for n in s:
        d = 0
        while n + 6 ** d <= N:
            ns.add(n + 6 ** d)
            d += 1
        d = 0
        while n + 9 ** d <= N:
            ns.add(n + 9 ** d)
            d += 1
    ans += 1
    if N in ns:
        break
    s = ns
print(ans)
### BUGGY CODE ###

from sys import stdin,stdout
LI=lambda:list(map(int,input().split()))
MAP=lambda:map(int,input().split())
IN=lambda:int(input())
S=lambda:input()
import math
from collections import Counter,defaultdict

d=defaultdict(int)
m=10**6+1
sieve=[-1]*m
n=IN()
a=sorted(LI())
for i in a:
    d[i]+=1
    for j in range(2*i,m,i):
        sieve[j]=1
ans=0
for i in a:
    if sieve[i]==-1 and d[i]==1:
        ans+=1
print(ans)

### FIXED CODE ###

from sys import stdin,stdout
LI=lambda:list(map(int,input().split()))
MAP=lambda:map(int,input().split())
IN=lambda:int(input())
S=lambda:input()
import math
from collections import Counter,defaultdict

d=defaultdict(int)
m=10**6+1
sieve=[-1]*m
n=IN()
a=sorted(LI())
for i in a:
    if d[i]==0:
        d[i]+=1
        for j in range(2*i,m,i):
            sieve[j]=1
    else:
        sieve[i]=1
ans=0
for i in a:
    if sieve[i]==-1:
        ans+=1
print(ans)
### BUGGY CODE ###

mod = 998244353
n = int(input())
d = list(map(int, input().split()))
if d[0] != 0:
    print(0)
    exit()
lis = []
for i in range(n):
    lis.append(d.count(i))
if lis[0] != 1:
    print(0)
    exit()
ans = 1
for i in range(1, n):
    ans *= pow(lis[i-1], lis[i], mod)
    ans %= mod
print(ans)

### FIXED CODE ###

mod = 998244353
n = int(input())
d = list(map(int, input().split()))
if d[0] != 0:
    print(0)
    exit()
lis = [0] * n
for i in d:
    lis[i] += 1
if lis[0] != 1:
    print(0)
    exit()
ans = 1
for i in range(1, n):
    ans *= pow(lis[i-1], lis[i], mod)
    ans %= mod
print(ans)
### BUGGY CODE ###

import math
def f(N, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n,a,b=map(int,input().split())
mod=1000000007
s=(2**n)%mod
A=f(n,a)%mod
B=f(n,b)%mod
print(s-A-B-1)

### FIXED CODE ###

def power(x, a):
    if a == 0:
        return 1
    elif a == 1:
        return x
    elif a % 2 == 0:
        return power(x, a//2) **2 % mod
    else:
        return power(x, a//2) **2 * x % mod

def modinv(x):
    return power(x, mod-2)

def binomial_coefficients(n, k):
    numera = 1  
    denomi = 1  

    for i in range(k):
        numera *= n-i
        numera %= mod
        denomi *= i+1
        denomi %= mod
    return numera * modinv(denomi) % mod

n,a,b=map(int,input().split())
mod=1000000007
print((pow(2,n,mod)-1-binomial_coefficients(n, a)-binomial_coefficients(n, b))%mod)
### BUGGY CODE ###

import collections

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

c = collections.Counter(A)
n = len(c)

cnt = 0
if n - K > 0:
    for i in range(n - K):
        cnt += c.most_common()[::-1][i][1]
print(cnt)

### FIXED CODE ###

import collections

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

c = collections.Counter(A)
n = len(c)
c_sorted = sorted(c.values())
cnt = 0
for i in range(max(0, n - K)):
    cnt += c_sorted[i]
print(cnt)
### BUGGY CODE ###

from numpy import*;B=searchsorted;a,b=loadtxt(open(0),skiprows=1);c=0;l=2**29
while l:h=l;l//=2;b%=h;a%=h;y=sort(hstack((b-h,b)));c+=sum(B(y,h-a)-B(y,l-a))%2*l
print(c)

### FIXED CODE ###

from numpy import*;B,I=searchsorted,lambda:int32(input().split());input();a,b=I(),I();c=0
for k in range(29):l=2**k;h=l*2;x,y=a%h,sort(b%h);y=hstack((y-h,y));c+=sum(B(y,h-x)-B(y,l-x))%2*l
print(c)
### BUGGY CODE ###

h,w=map(int,input().split())
maplis=[input() for i in range(h)]

que=[[0,0,1]]
used=[[0,0]]
bcount =0
for i in maplis:
    bcount+=i.count("#")


def check(x,y,c):
    f=(x<0 or x>w-1 or y<0 or y>h-1)
    f=(f or maplis[y][x]=="#")
    f=(f or [x,y] in used)
    if not f:
        que.append([x,y,c+1])

f=-1
while que:
    x,y,c=que.pop(0)
    if x==w-1 and y==h-1:
        f=c
        break
    used.append([x,y])
    check(x-1,y,c)
    check(x+1,y,c)
    check(x,y-1,c)
    check(x,y+1,c)
print(f if f==-1 else(h*w-f-bcount))


### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
maplis=[input() for i in range(h)]

que=deque([(0,0,1)])
used={(0,0)}
bcount =sum(s.count("#") for s in maplis)


def check(x,y,c):
    if x<0 or x>w-1 or y<0 or y>h-1:
        return
    if maplis[y][x]=="#":
        return
    if  (x,y) in used:
        return
    que.append((x,y,c+1))
    used.add((x,y))

f=-1
while que:
    x,y,c=que.popleft()
    if x==w-1 and y==h-1:
        f=c
        break
    check(x-1,y,c)
    check(x+1,y,c)
    check(x,y-1,c)
    check(x,y+1,c)
print(f if f==-1 else(h*w-f-bcount))
### BUGGY CODE ###

import itertools
S = input()[::-1]
mod = 10**9 + 7
A = [0] * 13
N = 0
for i, v in enumerate(S):
    p = pow(10, i, 13)
    if v == '?':
        A[p] += 1
    else:
        N += int(v) * p
        N %= 13
dp = [0] * 13
dp[N] = 1
for i, v in enumerate(A):
    for _ in range(v):
        dp_old = dp[:]
        for j, k in itertools.product(range(1, 10), range(13)):
            x = (j * i + k) % 13
            dp[x] += dp_old[k]
            dp[x] %= mod
print(dp[5])


### FIXED CODE ###

import itertools
S = input()[::-1]
mod = 10**9 + 7
A = [0] * 13
N = 0
for i, v in enumerate(S):
    p = pow(10, i, 13)
    if v == '?':
        A[p] += 1
    else:
        N += int(v) * p
        N %= 13
dp = [0] * 13
dp[N] = 1
for i, v in enumerate(A):
    for _ in range(v):
        dp_old = dp[:]
        for j, k in itertools.product(range(1, 10), range(13)):
            x = (j * i + k) % 13
            dp[x] += dp_old[k]
            dp[x] %= mod
print(dp[5])
### BUGGY CODE ###

n, m, p = map(int, input().split())
edge = []

for _ in range(m):
    a, b, c = map(int, input().split())
    edge.append([a-1, b-1, -c])

d = [float("inf") for _ in range(n)]
d[0] = 0

check = [0 for _ in range(n)]

for i in range(n):
    for now, next, weight in edge:
        if d[next] > min(d[now] + weight + p, d[next]):
            d[next] = min(d[now] + weight + p, d[next])
            # n+1回目で更新された場合はループしているのでチェックを入れる
            if i == n-1:
                check[next] = 1
        if i == n-1:
            if check[now]:
                check[next] = 1
        # print(d)

# print(check)
if check[-1]:
    print("-1")
else:
    print(max(-d[-1], 0))

### FIXED CODE ###

n, m, p = map(int, input().split())
edge = []

for _ in range(m):
    a, b, c = map(int, input().split())
    edge.append([a-1, b-1, -c])

d = [float("inf") for _ in range(n)]
d[0] = 0

# check = [0 for _ in range(n)]

for i in range(n*2):
    for now, next, weight in edge:
        if d[next] > d[now] + weight + p:
            d[next] = d[now] + weight + p
            # n+1回目で更新された場合はループしているのでチェックを入れる
            if i > n-1:
                d[next] = -float("inf")
                # check[next] = 1
        if i == n-1:
            prev = d[-1]
            # if check[now]:
            #     check[next] = 1
        # print(d)

# print(check)
# if check[-1]:
if prev != d[-1]:
    print("-1")
else:
    print(max(-prev, 0))
    # print(prev)
### BUGGY CODE ###

n, m = [int(i) for i in input().split()]
prices = sorted([int(i) for i in input().split()], reverse=True)
for i in range(m):
	prices[0] = prices[0] // 2
	prices = sorted(prices, reverse=True)
print (sum(prices))

### FIXED CODE ###

n, m = [int(i) for i in input().split()]
prices = sorted([int(i) for i in input().split()], reverse=True)
d = 1
while(True):
	d *= 2
	if d * 2 > 10 ** 9:
		break
while(d > 0):
	for i, price in enumerate(prices):
		if price >= d:
			prices[i] = prices[i] // 2
			m -= 1
			if m == 0:
				d = 0
				break
	prices = sorted(prices, reverse=True)
	d /= 2
print (sum(prices))
### BUGGY CODE ###

def get_sum_arr(arr):
    sum_arr = [0]
    N = len(arr)
    for i in range(1,N+1):
        sum_arr.append(sum_arr[i-1] + arr[i-1])
    return sum_arr
def get_max_book_num(A,B,K):
    A_sum_arr,B_sum_arr = get_sum_arr(A),get_sum_arr(B)
    count,i,j = 0,0,0
    for i in range(0,len(A_sum_arr)):
        if K < A_sum_arr[i]:
            break
        else:
            j = 0
            while B_sum_arr[j] <= (K - A_sum_arr[i]):
                j += 1
                if j >= len(B_sum_arr):
                    break
            j -= 1
        count = max(count,(i+j))
    return count

if __name__ == "__main__":
    N,M,K = list(map(int,input().split()))
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))
    print(get_max_book_num(A,B,K))
    


### FIXED CODE ###

def get_sum_arr(arr):
    sum_arr = [0]
    N = len(arr)
    for i in range(1,N+1):
        sum_arr.append(sum_arr[i-1] + arr[i-1])
    return sum_arr

def get_max_b(left_time,j,B_sum_arr):
    # [0,1,2,3,4,5]
    while B_sum_arr[j] > left_time and j > 0:
        j -= 1
    return j
def get_max_book_num(A,B,K):
    A_sum_arr,B_sum_arr = get_sum_arr(A),get_sum_arr(B)
    count,i,j = 0,0,len(B_sum_arr)-1
    for i in range(0,len(A_sum_arr)):
        if K < A_sum_arr[i]:
            break
        else:
            left_time = K - A_sum_arr[i]
            j = get_max_b(left_time,j,B_sum_arr)
        count = max(count,(i+j))
    return count
if __name__ == "__main__":
    N,M,K = list(map(int,input().split()))
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))
    print(get_max_book_num(A,B,K))
### BUGGY CODE ###

H,N = [int(zz) for zz in input().split()]
li = [[int(zz) for zz in input().split()] for _ in range(N)]

dp = [[0]*(H+1) for _ in range(N)]

for j in range(1,H+1):
    if j <= li[0][0]:
        dp[0][j] = li[0][1]
    else:
        dp[0][j] = dp[0][j-li[0][0]]+li[0][1]

for i in range(1,N):
    for j in range(1,H+1):
        if j <= li[i][0]:
            dp[i][j] = min(li[i][1],dp[i-1][j])
        else:
            dp[i][j] = min(dp[i][j-li[i][0]]+li[i][1],dp[i-1][j])

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


### FIXED CODE ###

H,N = [int(zz) for zz in input().split()]
li = [[int(zz) for zz in input().split()] for _ in range(N)]

dp = [[0]*(H+1) for _ in range(N)]

for j in range(1,H+1):
    if j <= li[0][0]:
        dp[0][j] = li[0][1]
    else:
        dp[0][j] = dp[0][j-li[0][0]]+li[0][1]

for i in range(1,N):
    for j in range(1,H+1):
        if j <= li[i][0]:
            dp[i][j] = min(li[i][1],dp[i-1][j])
        else:
            dp[i][j] = min(dp[i][j-li[i][0]]+li[i][1],dp[i-1][j])

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