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

import heapq as hq
def main():
    n,m=list(map(int,input().split(' ')))
    card = list(map(int,input().split(' ')))
    hq.heapify(card)
    for i in range(m):
        b,c=list(map(int,input().split(' ')))
        for i in range(b):
            hq.heappushpop(card,c)
    print(sum(card))
if __name__ =='__main__':
    main()

### FIXED CODE ###

import heapq as hq

def get_num():
    return list(map(int,input().split(' ')))

def main():
    n,m = get_num()
    card = get_num()
    card_sum=sum(card)
    hq.heapify(card)
    d_set=[]
    d=[]
    for i in range(m):
        b,c=get_num()
        hq.heappush(d_set,(-c,b))
    for i in range(m):
        if len(d) ==n:
            break
        cnt = hq.heappop(d_set)
        for i in range(cnt[1]):
            d.append(-cnt[0])
            if len(d)==n:
                break
    for i in range(len(d)):
        c_min=hq.heappop(card)
        d_max=d[i]
        if c_min>=d_max:
            break
        else:
            card_sum += (d_max-c_min)
    print(card_sum)
main()
### BUGGY CODE ###

n = int(input())
ss = [sorted(input()) for i in range(n)]
cnt = 0
for i in range(n):
  for j in range(i):
    if ss[i]==ss[j]:
      cnt+=1
print(cnt)

### FIXED CODE ###

from collections import Counter
n=int(input())
string_list=["".join(sorted(list(input()))) for i in range(n)]
counter=Counter(string_list)
cnt=0
for k, v in counter.items():
  cnt+=int(v*(v-1)/2)
print(cnt)
### BUGGY CODE ###

l = input()

ans = 0
a = 0
for i in range(len(l)):
    if l[i]=='1':
        ans += ((3**(len(l)-i-1))*(2**a))
        a+=1
    if i==len(l)-1:
        ans += (2**a)
    ans %= 10**9+7

print(ans)


### FIXED CODE ###

l = input()

a3 = [1]
a2 = [1]

for i in range(len(l)+5):
    a3.append((a3[-1]*3)%(10**9+7))
    a2.append((a2[-1]*2)%(10**9+7))

ans = 0
a = 0
for i in range(len(l)):
    if l[i]=='1':
        ans += (a3[len(l)-i-1]*a2[a])
        a+=1
    if i==len(l)-1:
        ans += a2[a]
    ans %= 10**9+7

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

n = int(input())
s = input()
a = 0
pw, pw1, pw2 = [0] * n, [0] * n, [0] * n
pw[0], pw1[0], pw2[0] = 1, 1, 1
v = 0
for i in range(n):
    if s[i] == '1':
        v += 1
for i in range(1, n):
    pw[i] = int(pw[i - 1] * 2)
    pw1[i] = int(pw1[i - 1] * 2) % (v + 1)
    if v >= 2:
        pw2[i] = int(pw2[i - 1] * 2) % (v - 1)
for i in range(n):
    if s[i] == '1':
        a += pw[n - i - 1]        
mod1 = a % (v + 1)
mod2 = 0
if v >= 2:
    mod2 = a % (v - 1)
for i in range(n):
    copy = 0
    x = v
    cnt = 1
    if s[i] == '0':
        x += 1
        copy = (mod1 + pw1[n - i - 1]) % x
    else:
        x -= 1
        if x >= 1:
            copy = (mod2 - pw2[n - i - 1]) % x
        else:
            copy = -1
    if copy == -1:
        print(0)
    else:
        x = bin(copy).count('1')
        while copy > 0:
            copy %= x
            x = bin(copy).count('1')
            cnt += 1
        print(cnt)


### FIXED CODE ###

n = int(input())
s = input()
pw, pw1, pw2 = [0] * n, [0] * n, [0] * n
pw[0], pw1[0], pw2[0] = 1, 1, 1
v, mod1, mod2 = 0, 0, 0
for i in range(n):
    if s[i] == '1':
        v += 1
for i in range(1, n):
    pw1[i] = int(pw1[i - 1] * 2) % (v + 1)
    if v >= 2:
        pw2[i] = int(pw2[i - 1] * 2) % (v - 1)
for i in range(n):
    if s[i] == '1':
        mod1 = (mod1 + pw1[n - i - 1]) % (v + 1)
        if v >= 2:
            mod2 = (mod2 + pw2[n - i - 1]) % (v - 1)    
for i in range(n):
    copy, x, cnt = 0, v, 1
    
    if s[i] == '0':
        x += 1
        copy = (mod1 + pw1[n - i - 1]) % x
    else:
        x -= 1
        if x >= 1:
            copy = (mod2 - pw2[n - i - 1]) % x
        else:
            copy = -1
    if copy == -1:
        print(0)
    else:
        x = bin(copy).count('1')
        while copy > 0:
            copy %= x
            x = bin(copy).count('1')
            cnt += 1
        print(cnt)
### BUGGY CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = map(int, input().split())
g = [ list(map(lambda x: int(x)-1, input().split())) for _ in range(M) ]

from collections import Counter, defaultdict
childs  = Counter( x[1] for x in g)
childs_list  = defaultdict(list)

for x,y in g:
    childs_list[x].append(y)
roots = []
for i in range(N):
    if childs[i] == 0:
        roots.append(i)

l = [ i for i in roots]
costs = [ 0 for _ in range(N)]

while l: 
    p = l.pop()

    
    # costs[p] = max(costs[v_idx], cnt)
    # costs[p] = max(costs[p], costs[ 

    cnt = costs[p]

    for c in childs_list[p]:
        if cnt+1 > costs[c]:
            # l.append(  (c, childs_list[c], cnt+1) ) 
            costs[c] = cnt+1
            l.append( c ) 
            # nex_stack.append( c ) 


print(max(costs))
        
        



### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = map(int, input().split())
g = [ list(map(lambda x: int(x)-1, input().split())) for _ in range(M) ]

from collections import Counter, defaultdict
childs  = Counter( x[1] for x in g)
childs_list  = defaultdict(list)

for x,y in g:
    childs_list[x].append(y)
roots = []
for i in range(N):
    if childs[i] == 0:
        roots.append(i)

l = [ i for i in roots]
costs = [ 0 for _ in range(N)]

while l: 

    nex_stack = []
    # p = l.pop()
    for p in l:
        # cnt = costs[p]
        for c in childs_list[p]:
            costs[c] = max(costs[p]+1, costs[c])
            childs[c] -= 1
            if childs[c] == 0:
                nex_stack.append(c)
    
    l = nex_stack


print(max(costs))
### BUGGY CODE ###

N,W=list(map(int,input().split()))
v=[[],[],[],[]]
kosu=[0,0,0,0]
kr=list(map(int,input().split()))
v[0].append(kr[1])
w0=kr[0]
for i in range(1,N):
    kr=list(map(int,input().split()))
    v[kr[0]-w0].append(kr[1])
for i in range(4):
    v[i].sort()
    v[i].reverse()
kos=[len(v[0]),len(v[1]),len(v[2]),len(v[3])]
def toru(a,b,c,d,nw):
    max=0
    if a<kos[0] and W>=nw+w0 and max<toru(a+1,b,c,d,nw+w0)+v[0][a]:
        max=toru(a+1,b,c,d,nw+w0)+v[0][a]
    if b<kos[1] and W>=nw+w0+1 and max<toru(a,b+1,c,d,nw+w0+1)+v[1][b]:
        max=toru(a,b+1,c,d,nw+w0+1)+v[1][b]
    if c<kos[2] and W>=nw+w0+2 and max<toru(a,b,c+1,d,nw+w0+2)+v[2][c]:
        max=toru(a,b,c+1,d,nw+w0+2)+v[2][c]
    if d<kos[3] and W>=nw+w0+3 and max<toru(a,b,c,d+1,nw+w0+3)+v[3][d]:
        max=toru(a+1,b,c,d+1,nw+w0+3)+v[3][d]
    return max


maxv=toru(0,0,0,0,0)

print(maxv)


### FIXED CODE ###

N,W=list(map(int,input().split()))
v=[[],[],[],[]]
kosu=[0,0,0,0]
kr=list(map(int,input().split()))
v[0].append(kr[1])
w0=kr[0]
for i in range(1,N):
    kr=list(map(int,input().split()))
    v[kr[0]-w0].append(kr[1])
for i in range(4):
    v[i].sort()
    v[i].reverse()
kos=[len(v[0]),len(v[1]),len(v[2]),len(v[3])]
kk=[-1]*((kos[0]+1)*(kos[1]+1)*(kos[2]+1)*(kos[3]+1))
def toru(a,b,c,d,nw):
    global kk
    if kk[a+(kos[0]+1)*(b+((kos[1]+1)*(c+(kos[2]+1)*d)))]!=-1:
        return kk[a+(kos[0]+1)*(b+((kos[1]+1)*(c+(kos[2]+1)*d)))]
    max=0
    if a<kos[0] and W>=nw+w0 and max<toru(a+1,b,c,d,nw+w0)+v[0][a]:
        max=toru(a+1,b,c,d,nw+w0)+v[0][a]
    if b<kos[1] and W>=nw+w0+1 and max<toru(a,b+1,c,d,nw+w0+1)+v[1][b]:
        max=toru(a,b+1,c,d,nw+w0+1)+v[1][b]
    if c<kos[2] and W>=nw+w0+2 and max<toru(a,b,c+1,d,nw+w0+2)+v[2][c]:
        max=toru(a,b,c+1,d,nw+w0+2)+v[2][c]
    if d<kos[3] and W>=nw+w0+3 and max<toru(a,b,c,d+1,nw+w0+3)+v[3][d]:
        max=toru(a,b,c,d+1,nw+w0+3)+v[3][d]
    kk[a+(kos[0]+1)*(b+((kos[1]+1)*(c+(kos[2]+1)*d)))]=max
    return max
 
 
maxv=toru(0,0,0,0,0)
 
print(maxv)
### BUGGY CODE ###

I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = I[2:2 + N]
LR = I[2 + N:]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)

arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted((lr[1], lr[0], i) for i, lr in enumerate(zip(LR[::2], LR[1::2])))
ans = [None] * Q
j = 0
for r, l, i in RLI:
    while j < r:
        BIT.add(arr[C[j]], -1)
        arr[C[j]] = j + 1
        BIT.add(j + 1, 1)
        j += 1
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print(*ans, sep='\n')


### FIXED CODE ###

I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = [0] + I[2:2 + N]
LR = I[2 + N:]
L, R = LR[::2], LR[1::2]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)

arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted(r * (2 ** 40) + l * (2 ** 20) + i for r, l, i in zip(R, L, range(Q)))
ans = [None] * Q
j = 0
for rli in RLI:
    r, li = divmod(rli, 2 ** 40)
    l, i = divmod(li, 2 ** 20)
    for j in range(j + 1, r + 1):
        BIT.add(arr[C[j]], -1)
        arr[C[j]] = j
        BIT.add(j, 1)
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print('\n'.join(map(str, ans)))
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, *a = map(int, read().split())
mod = 10 ** 9 + 7
ans = 0
x = 1
for bit in range(60):
    b = 0
    for i, aa in enumerate(a):
        if aa % 2:
            b += 1
        a[i] //= 2
    ans += (x * b * (n - b)) % mod
    ans %= mod
    x *= 2
    x %= mod
print(ans)


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np

n = int(readline())
a = np.array(read().split(), np.int64)
ans = 0
mod = 10 ** 9 + 7
for i in range(63):
    b = (a >> i) & 1
    x = np.count_nonzero(b)
    y = n - x
    x *= y
    for j in range(i):
        x *= 2
        x %= mod
    ans += x
print(ans % mod)
### BUGGY CODE ###

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

ablist=[]
for i in range(N):
  a,b=map(int,input().split())
  ablist.append((a,b))
  
dp=[]
for i in range(N+1):
  dp.append([10**9]*(H+1))
  
for i in range(N+1):
  dp[i][0]=0
  
#print(dp)  
for i in range(1,N+1):
  ai,bi=ablist[i-1]
  for j in range(1,H+1):
    if j-ai<0:
      dp[i][j]=min(dp[i-1][j],bi)
    else:
      dp[i][j]=min(dp[i-1][j],dp[i][j-ai]+bi)
      
#print(dp)
print(dp[N][H])

### FIXED CODE ###

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

ablist=[]
for i in range(N):
  a,b=map(int,input().split())
  ablist.append((a,b))
  
dp=[]
for i in range(N+1):
  dp.append([10**9]*(H+1))
  
for i in range(N+1):
  dp[i][0]=0
  
#print(dp)  
for i in range(1,N+1):
  ai,bi=ablist[i-1]
  for j in range(1,H+1):
    if j-ai<0:
      dp[i][j]=min(dp[i-1][j],bi)
    else:
      dp[i][j]=min(dp[i-1][j],dp[i][j-ai]+bi)
      
#print(dp)
print(dp[N][H])
### BUGGY CODE ###

H,W=map(int,input().split())
S=[input()for _ in range(H)]

w1=[[]for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j]=='#':
            w1[i].append(j)
    w1[i].append(W)

w2=[[0]*W for _ in range(H)]
for i in range(H):
    k=0
    L=-1
    R=w1[i][k]
    for j in range(W):
        if S[i][j]=='#':
            L=w1[i][k]
            k+=1
            R=w1[i][k]
            continue
        w2[i][j]=R-L-1

h1=[[]for _ in range(W)]
for j in range(W):
    for i in range(H):
        if S[i][j]=='#':
            h1[j].append(i)
    h1[j].append(H)

h2=[[0]*W for _ in range(H)]
for j in range(W):
    k=0
    L=-1
    R=h1[j][k]
    for i in range(H):
        if S[i][j]=='#':
            L=h1[j][k]
            k+=1
            R=h1[j][k]
            continue
        h2[i][j]=R-L-1

print(max(w2[i][j]+h2[i][j]-1 for i in range(H)for j in range(W)))

### FIXED CODE ###

H,W=map(int,input().split())
S=[input()for _ in range(H)]

w1=[[]for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j]=='#':
            w1[i].append(j)
    w1[i].append(W)

w2=[[0]*W for _ in range(H)]
for i in range(H):
    k=0
    L=-1
    R=w1[i][k]
    for j in range(W):
        if S[i][j]=='#':
            L=w1[i][k]
            k+=1
            R=w1[i][k]
            continue
        w2[i][j]=R-L-1

h1=[[]for _ in range(W)]
for j in range(W):
    for i in range(H):
        if S[i][j]=='#':
            h1[j].append(i)
    h1[j].append(H)

h2=[[0]*W for _ in range(H)]
for j in range(W):
    k=0
    L=-1
    R=h1[j][k]
    for i in range(H):
        if S[i][j]=='#':
            L=h1[j][k]
            k+=1
            R=h1[j][k]
            continue
        h2[i][j]=R-L-1

print(max(w2[i][j]+h2[i][j]-1 for i in range(H)for j in range(W)))
### BUGGY CODE ###

S = list(input())
Q = int(input())
Qry = [input().split() for i in range(Q)]
for q in Qry:
    if q[0] == '1':
        S.reverse()
    else:
        if q[1] == '1':
            S = [q[2]] + S
        else:
            S += [q[2]]
print(*S, sep='')


### FIXED CODE ###

S = input()
Q = int(input())
qry = [input().split() for _ in range(Q)]
A = ''
B = ''
oq = 0
even = True
for q in qry:
    if q[0] == '1':
        even = not even
        if oq == '1':
            continue
    else:
        if even:
            if q[1] == '1':
                A = q[2] + A
            else:
                B += q[2]
        else:
            if q[1] == '1':
                B += q[2]
            else:
                A = q[2] + A
    oq = q

if even:
    print(A+S+B)
else:
    print(B[::-1]+S[::-1]+A[::-1])
### BUGGY CODE ###

#import sys
#input = sys.stdin.readline
n=int(input())
a=[int(i) for i in input().split()]
b=a
b+=[a[i]-1 for i in range(n)]
b+=[a[i]+1 for i in range(n)]
#print(a)

ans=0
maxa=max(a)
for i in range(1,max(a)+1):
    cnt=b.count(i)
    if ans <= cnt:
      ans = cnt

print(ans)



### FIXED CODE ###

from collections import Counter

#tmp_list = [1, 1, 1, 1, 0, 1, 1]


n=int(input())
a=[int(i) for i in input().split()]
b=[i-1 for i in a]
c=[i+1 for i in a]
d=a+b+c

counter = Counter(d)

print(counter.most_common()[0][1])
### BUGGY CODE ###

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

base=fractions.gcd(A,B)
count=1

i=2
while base>1:
    if base%i==0:
        count+=1
        while base%i==0:
            base//=i
        
    i+=1
print(count)

### FIXED CODE ###

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

base=fractions.gcd(A,B)
count=1


for i in range(2,int(pow(base,1/2)+1)):
    if base==1:
        break
    else:
        if base%i==0:
            count+=1
            while base%i==0:
                base//=i
if base!=1:
    count+=1
print(count)
### BUGGY CODE ###

n = int(input())
ans = 0
for i in range(1,n+1):
    i = list(str(i))
    if set(i) == {"3","5","7"}:
        ans += 1
print(ans)

### FIXED CODE ###

import itertools
ans = 0
n = int(input())

for k in range(1,10):
    s = itertools.product(["3","5","7"], repeat=k)
    for seq in s:
        x = set()
        for i in seq:
            x.add(i)
        if len(x) != 3:
            continue
        t = "".join(seq)
        if 1 <= int(t) <= n:
            ans += 1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

H, N = map(int, input().split(" "))
dp = [[float('inf') for i in range(H + 1)] for j in range(N + 1)]
for i in range(N + 1):
    dp[i][0] = 0

for i in range(N):
    A, B = map(int, input().split(" "))
    for j in range(H + 1):
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        dp[i][min(j + A, H)] = min(dp[i][min(j + A, H)], dp[i][j] + B)
print(dp[N][H])

### FIXED CODE ###

import sys
input = sys.stdin.readline

H, N = map(int, input().split(" "))
dp = [1e10 for i in range(H + 1)]
dp[0] = 0

for i in range(N):
    A, B = map(int, input().split(" "))
    for j in range(H + 1):
        if dp[j] != 1e10:
            dp[min(j + A, H)] = min(dp[min(j + A, H)], dp[j] + B)
print(dp[H])
### BUGGY CODE ###

input_str = input().split()
N = int(input_str[0])
Y = int(input_str[1])

x_quo = Y//10000

flag = False
for x in range(min([x_quo,N]),-1,-1):
  Y_x = Y - 10000*x
  N_x = N - x
  y_quo = Y_x // 5000
  for y in range(min([y_quo,N_x]),-1,-1):
    Y_xy = Y_x - 5000*y
    N_xy = N_x - y
    z_quo = Y_xy // 1000
    for z in range(min([z_quo,N_xy]),-1,-1):
      if 10000*x + 5000*y + 1000*z == Y and x+y+z == N:
        flag = True;
        break;
    else:
      continue
    break
  else:
    continue
  break

if flag == True:
  print(str(x) + " " + str(y) + " " + str(z))
else:
  print("-1 -1 -1")

### FIXED CODE ###

input_str = input().split()
N = int(input_str[0])
Y = int(input_str[1])

x_quo = Y//10000

flag = False
for x in range(min([x_quo,N]),-1,-1):
  Y_x = Y - 10000*x
  N_x = N - x
  y_quo = Y_x // 5000
  for y in range(min([y_quo,N_x]),-1,-1):
    z = N-x-y
    if 10000*x + 5000*y + 1000*z == Y and x+y+z == N:
      flag = True;
      break;
  else:
    continue
  break

if flag == True:
  print(str(x) + " " + str(y) + " " + str(z))
else:
  print("-1 -1 -1")
### BUGGY CODE ###

from collections import deque

n, q = map(int, input().split())
neighbor = [[] for _ in range(n)]
pl = []

for i in range(n-1):
    a, b = map(int, input().split())
    neighbor[a-1].append(b-1)
    neighbor[b-1].append(a-1)

for i in range(q):
    pl.append(list(map(int, input().split())))

parent = [-1 for _ in range(n)]
child = [[] for _ in range(n)]
parent[0] = 0
point = [0] * n
que = deque([])


def makeTree():
    global parent, neighbor, child
    queue = deque([[0, 0]])
    while len(queue) > 0:
        now = queue.popleft()
        que.append(now[0])
        for neiv in neighbor[now[0]]:
            if parent[neiv] == -1:
                parent[neiv] = now[0]
                queue.append([neiv, now[1]])
                child[now[0]].append(neiv)


def calcPoint():
    global pl, parent, point, que
    for p in pl:
        point[p[0] - 1] += p[1]
    que.popleft()
    while len(que) > 0:
        now = que.popleft()
        point[now] += point[parent[now]]


makeTree()

calcPoint()

print(*point)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n, q = map(int, input().split())
neighbor = [[] for _ in range(n)]
point = [0]*n

for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    neighbor[a].append(b)
    neighbor[b].append(a)

for i in range(q):
    p, x = map(int, input().split())
    point[p-1] += x


def dfs(now, past):
    for nv in neighbor[now]:
        if nv == past:
            continue
        point[nv] += point[now]
        dfs(nv, now)


dfs(0, -1)


print(*point)
### BUGGY CODE ###

s = input()
n = int(input())
for i in range(n):
	com = input().split()
	if len(com) == 1:
		s = s[::-1]
	else:
		s = com[2]*(com[1]=='1') + s + com[2]*(com[1]=='2')
print(s)

### FIXED CODE ###

from collections import deque

s = deque(input())
n = int(input())
status = True

for i in range(n):
	com = input().split()
	if com[0] == '1':
		status = not status
	elif int(com[1])+status == 2:
		s.appendleft(com[2])
	else:
		s.append(com[2])
        
if not status:
	s.reverse()
print("".join(s))
### BUGGY CODE ###

k = int(input())
val = 7
count = 1
if(k % 2 == 0 or k % 5 == 0):
	print(-1)
	exit()
while(True):
	if(val % k == 0):
		break
	if(count >= 100000):
		print(-1)
		exit()
	count += 1
	val = val * 10 + 7
print(count)	

### FIXED CODE ###

k = int(input())
val = 7
val %= k
for i in range(k+1):
	if(val ==0):
		print(i+1)
		break
	val = (val * 10 + 7) % k
else:
	print(-1)
### BUGGY CODE ###

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

L,R = [],[]
ans = [0]*(N+1)
for i in range(M):
    a,b = map(int,input().split())
    
    for j in range(a,b+1):
        ans[j] += 1

count = 0
for i in ans:
    if i == M:
        count += 1

print(count)





### FIXED CODE ###

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

L,R = 0,100100
ans = [0]*(N+1)
for i in range(M):
    a,b = map(int,input().split())
    L = max(L,a)
    R = min(R,b)
if R - L >= 0:
    print(R-L+1)
else:
    print(0)
### BUGGY CODE ###

N = int(input())
ans = 0
for i in range(1,N+1):
    count = 0
    for j in range(1,i+1):
        if i%j == 0:
            count += 1
    ans += i*count
print(ans)

### FIXED CODE ###

N = int(input())
ans = 0
for i in range(1,N+1):
    val = N // i
    ans += val*(val+1)*i//2
print(ans)
### BUGGY CODE ###

numx,numy,numz,k=list(map(int,input().split()))
X=list(map(int,input().split()))
Y=list(map(int,input().split()))
Z=list(map(int,input().split()))

XY=[ x + y for x in X for y in Y]
XY.sort(reverse=True)
XY=XY[:k]
XYZ=[xy + z for xy in XY for z in Z]
XYZ.sort(reverse=True)

for i in range(k):
  print(XYZ[i])

### FIXED CODE ###

numx,numy,numz,k=list(map(int,input().split()))
X=list(map(int,input().split()))
Y=list(map(int,input().split()))
Z=list(map(int,input().split()))

XY=[ x + y for x in X for y in Y]
XY.sort(reverse=True)
XY=XY[:k]
XYZ=[xy + z for xy in XY for z in Z]
XYZ.sort(reverse=True)

for i in range(k):
  print(XYZ[i])
### BUGGY CODE ###

n=int(input())
a=sorted(map(int,input().split()),reverse=True)
t=[0]*1000001
for i in a:
    t[i]+=1
    for j in range(i*2,1000001,i):
        t[j]+=2
print(t.count(1))

### FIXED CODE ###


n=int(input())
a=sorted(map(int,input().split()))
m=max(a)+1
t=[0]*m
cnt=0
for i in a:
    if t[i]==0:
        cnt+=1
    elif t[i]==1:
        cnt-=1
    if t[i]<2:
        t[i]+=1
        for j in range(i*2,m,i):
            t[j]=2
print(cnt)
### BUGGY CODE ###

import numpy as np
import sys
input = sys.stdin.readline


def main():
    n, s = map(int, input().split())
    a = np.array([int(i) for i in input().split()], dtype="int16")
    MOD = 998244353

    dp = np.zeros(s + 1, dtype="int64")
    dp[0] = 1

    for i in a:
        p = np.zeros(s + 1, dtype="int64")
        dp, p = p, dp
        dp += p * 2
        dp %= MOD
        for j in range(s + 1):
            # print(f"{i = }, {j = }, {dp = }, {p = }")
            if (ji := j + i) <= s:
                dp[ji] = (dp[ji] + p[j]) % MOD

    print(dp[s])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.readline


def main():
    n, s = map(int, input().split())
    A = [int(i) for i in input().split()]

    MOD = 998244353

    dp = np.zeros(s + 1, dtype="int32")
    dp[0] = 1

    for a in A:
        p = (dp * 2) % MOD
        p %= MOD
        p[a:] += dp[:-a]
        dp = p % MOD

    print(dp[s])


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

N = int(input())
S = input()
 
lis = [0 for _ in range(1000)]
 
usiro_lis = [[0 for _ in range(10)] for _ in range(N)]
for i in range(N)[::-1]:
  for j in range(0, i):
    usiro_lis[j][int(S[i])] = 1

for i in range(N-2):
  for j in range(i+1, N-1):
    for k in range(10):
      if usiro_lis[j][k] == 1:
      	lis[100*int(S[i])+10*int(S[j])+k] = 1
      
print(sum(lis))

### FIXED CODE ###

N = int(input())
S = input()
numbers=[str(i).zfill(3) for i in range(1000)]
 
count=0
for num in numbers:
  j=0
  for i in range(N):
    if num[j]==S[i]:
      j+=1
      if j==3:
        count+=1
        break
print(count)