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

N, M = map(int, input().split())
A_list = list(map(int, input().split()))
A_list.sort()
while M > 0:
    A_list[-1] = A_list[-1] // 2
    A_list.sort()
    M -= 1
print(sum(A_list))


### FIXED CODE ###

# 優先度付きキューの考え方が必須
import heapq

N, M = map(int, input().split())
# 読み込み時に * -1 を乗算している
A_list = list(map(lambda x: int(x)*(-1), input().split()))
# A_listを優先度付きキューにする
heapq.heapify(A_list)

while M > 0:
    temp_max = heapq.heappop(A_list)
    # //2 で余りは切り捨てのため -1 を 2回 乗算している
    heapq.heappush(A_list, (-1)*((-1*temp_max)//2))
    M -= 1
print(-1*sum(A_list))
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]


def bfs(x, y):
    queue = deque([(x, y, 0)])
    visited = [[False]*W for _ in range(H)]

    max_cost = 0
    while queue:
        px, py, cost = queue.popleft()
        max_cost = max(max_cost, cost)

        candidate = ((px + 1, py), (px - 1, py), (px, py + 1), (px, py - 1))
        visited[py][px] = True
        for cx, cy in candidate:
            if 0 <= cx < W and 0 <= cy < H and not visited[cy][cx] and maze[cy][cx] == ".":
                queue.append((cx, cy, cost + 1))
    return max_cost


ans = 0
for y in range(H):
    for x in range(W):
        if maze[y][x] == ".":
            ans = max(ans, bfs(x, y))

print(ans)


### FIXED CODE ###

H, W = map(int, input().split())
m = [list(input()) for _ in range(H)]
inf = 10**3

V = H*W
maze = [[inf]*V for _ in range(V)]

for i in range(V):
    maze[i][i] = 0

for py in range(H):
    for px in range(W):
        if m[py][px] == "#":
            continue
        candidate = [(px+1, py), (px-1, py), (px, py+1), (px, py-1)]
        for x, y in candidate:
            if not (0<=x<W and 0<=y<H):continue
            if m[y][x] == "#":
                continue
            maze[W*py+px][W*y+x] = 1

for k in range(V):
    for i in range(V):
        for j in range(V):
            maze[i][j] = min(maze[i][j], maze[i][k]+maze[k][j])

print(max([j for i in maze for j in i if j!=inf]))
### BUGGY CODE ###

n=int(input());
num_list=[];
for i in range(n):
    num_list.append(int(input()));
for j in range(n):
    m=num_list[j];
    num_list[j]=0;
    print(max(num_list));
    num_list[j]=m;


### FIXED CODE ###

n=int(input())
num_list=[]
top1=0
top2=0
for i in range(n):
    num_list.append(int(input()))
    if top1<num_list[i]:
        top1=num_list[i]
    elif top2<num_list[i]:
        top2=num_list[i]
for j in range(n):
    if num_list[j]==top1:
        print(top2)
    else:
        print(top1)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

N, M = map(int, input().split())
# 0段目からN段目まである
N += 1
broken_stairs = [int(input()) for _ in range(M)]

# dp[i] = i段目に辿り着くまでの経路本数
dp = [0 for _ in range(N)]

# 初期化する
if 0 not in broken_stairs:
    dp[0] = 1
if 1 not in broken_stairs:
    dp[1] = 1

# MOD用
MOD = 10 ** 9 + 7

for i in range(2, N):
    """TLEだったやつ
    # 1段上が範囲内で使用可能なら現在の段の経路数を足す
    if i + 1 < N and i + 1 not in broken_stairs:
        # MODを取って更新
        dp[i + 1] += dp[i] % MOD
    # 2段上が範囲内で使用可能なら現在の段の経路数を足す
    if i + 2 < N and i + 2 not in broken_stairs:
        # MODを取って更新
        dp[i + 2] += dp[i] % MOD
    """
    # i段目が使用可能なら1段前と2段前の経路数を足した値を入れる
    if i not in broken_stairs:
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD


print(dp[-1])


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

N, M = map(int, input().split())
# 0段目からN段目まである
N += 1
broken_stairs = [int(input()) for _ in range(M)]

# dp[i] = i段目に辿り着くまでの経路本数
dp = [1 for _ in range(N)]

# 初期化する
for b in broken_stairs:
    dp[b] = 0

# MOD用
MOD = 10 ** 9 + 7

for i in range(2, N):
    """TLEだったやつ
    # 1段上が範囲内で使用可能なら現在の段の経路数を足す
    if i + 1 < N and i + 1 not in broken_stairs:
        # MODを取って更新
        dp[i + 1] += dp[i] % MOD
    # 2段上が範囲内で使用可能なら現在の段の経路数を足す
    if i + 2 < N and i + 2 not in broken_stairs:
        # MODを取って更新
        dp[i + 2] += dp[i] % MOD
    """
    # i段目が使用可能なら1段前と2段前の経路数を足した値を入れる
    if dp[i]:
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD


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

N,M = map(int,input().split())
array = []
c = 0
for i in range(M):
    a = int(input())
    if a-1 not in array:
        array.append(a)
    else:
        c = 1
        break
if c == 1:
    print(0)
else:
    dp = [0 for i in range(N+1)]
    dp[0] = 1
    for i in range(N-1):
        if i+1 not in array:
            dp[i+1] += dp[i]%(10**9+7)
        if i+2 not in array:
            dp[i+2] += dp[i]%(10**9+7)
    if N-1 not in array:
        dp[N] += dp[N-1]%(10**9+7)
    print(dp[-1]%(10**9+7))

### FIXED CODE ###

N,M = map(int,input().split())
array = [0 for i in range(N+1)]
c = 0
for i in range(M):
    a = int(input())
    if array[a-1] == 0:
        array[a] = 1
    else:
        c = 1
        break
if c == 1:
    print(0)
else:
    dp = [0 for i in range(N+1)]
    dp[0] = 1
    for i in range(N-1):
        if array[i+1] == 0:
            dp[i+1] += dp[i]%(10**9+7)
        if array[i+2] == 0:
            dp[i+2] += dp[i]%(10**9+7)
    if array[N-1] == 0:
        dp[N] += dp[N-1]%(10**9+7)
    print(dp[-1]%(10**9+7))
### BUGGY CODE ###

x,y=map(int,input().split())
ans=False
for i in range(1,10**18):
    if(i % x) == 0 and (i % y) != 0:
        ans=True
        break
    else:
        continue
if ans: print(i)
else: print(-1)

### FIXED CODE ###

x,y=map(int,input().split())
if x%y==0:
    print('-1')
else:
    print(x)
### BUGGY CODE ###

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def LCS(S, T, f=False):

    L1 = len(S)
    L2 = len(T)
    dp = [[0] * (L2 + 1) for i in range(L1 + 1)]

    for i in range(L1 - 1, -1, -1):
        for j in range(L2 - 1, -1, -1):
            r = max(dp[i + 1][j], dp[i][j + 1])
            if S[i] == T[j]:
                r = max(r, dp[i + 1][j + 1] + 1)
            dp[i][j] = r

    if not f:
        return dp[0][0]

    res = []
    i = 0
    j = 0
    while i < L1 and j < L2:
        if S[i] == T[j]:
            res.append(S[i])
            i += 1
            j += 1
        elif dp[i][j] == dp[i + 1][j]:
            i += 1
        elif dp[i][j] == dp[i][j + 1]:
            j += 1

    return (dp[0][0], ''.join(res))


def main():
    N = in_n()
    S = in_s()

    ans = 0
    for i in range(1, N):
        ans = max(ans, LCS(S[:i], S[i:]))

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def z_algo(S):
    N = len(S)
    A = [0] * N
    i = 1
    j = 0
    A[0] = l = len(S)
    while i < l:
        while i + j < l and S[j] == S[i + j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l - i > k < j - A[k]:
            A[i + k] = A[k]
            k += 1
        i += k
        j -= k

    ret = 0
    for i in range(1, N):
        ret = max(ret, min(A[i], i))

    return ret


def main():

    N = in_n()
    S = in_s()

    ans = 0
    for i in range(N):
        ans = max(ans, z_algo(S[i:]))

    print(ans)


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

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

ok = True
for i in range(n - 1):
    for j in range(i + 1, n):
        if hs[i] - hs[j] > 1:
            ok = False
            break
    if not ok:
        break
if ok:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

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

ok = True
threshold = hs[0] - 1
for i in range(1, n):
    if hs[i] < threshold:
        ok = False
        break
    threshold = max(threshold, hs[i] - 1)
if ok:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

a, b, x = map(int, input().split())
count1 = 0
count2 = 0
for i in range(0, a, x):
    count1 += 1

for i in range(0, b + 1, x):
    count2 += 1

print(count2 - count1)

### FIXED CODE ###

a, b, x = map(int, input().split())
def func(n):
  if n >= 0:
    return n // x + 1
  elif n == -1:
    return 0
print(func(b) - func(a-1))
### BUGGY CODE ###

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

remain = []
T = 0
flag = True
while flag:
    B = remain + A
    num_list = []
    for i in range(len(B)):
        if(not B[i] in num_list):
            num_list.append(B[i])
        else:
            index = num_list.index(B[i])
            num_list = num_list[:index]
    remain = num_list
    T += 1
    if(remain == []):
        break

M = K % T

remain = []
for i in range(M):
    B = remain + A
    num_list = []
    for i in range(len(B)):
        if(not B[i] in num_list):
            num_list.append(B[i])
        else:
            index = num_list.index(B[i])
            num_list = num_list[:index]
    remain = num_list

ans = ''
for i in range(len(remain)):
    ans += str(remain[i]) + ' '
print(ans)


### FIXED CODE ###

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

if n == 1:
    if k % 2:
        print(*arr)
    else:
        print(*[])
    exit()

table = {}
original_table = {}
move = {}

for i, a in enumerate(arr):
    if a not in table:
        table[a] = i
        original_table[a] = i
    else:
        move[table[a]], move[i] = i + 1, original_table[a] + 1
        table[a] = i

res = {}
idx = 0

for i in range(1, k + 1):
    while idx in move and move[idx] > idx:
        idx = move[idx]

    res[i] = idx
    if idx == len(arr):
        k %= len(res)
        if not k:
            k = len(res)
        break

    if idx in move:
        idx = move[idx]
    else:
        idx += 1

idx = res[k]
response = []

while idx < len(arr):
    while idx in move and move[idx] > idx:
        idx = move[idx]
    if idx < len(arr):
        response.append(arr[idx])
    idx += 1

print(*response)
### BUGGY CODE ###

def main():
    from sys import stdin
    input = stdin.readline
    import numpy as np
    import scipy.sparse as sp

    n, m, s, t = map(int, input().split())
    uvab = np.array([list(map(int, input().split())) for _ in [0]*m])

    data = np.append(uvab[:, 2], uvab[:, 2])
    row = np.append(uvab[:, 0], uvab[:, 1]) - 1
    col = np.append(uvab[:, 1], uvab[:, 0]) - 1

    matrix = sp.csr_matrix(
        (data, (row, col)), shape=(n, n), dtype=np.int32)
    yen = sp.csgraph.dijkstra(matrix, indices=s-1)

    data = np.append(uvab[:, 3], uvab[:, 3])
    matrix = sp.csr_matrix(
        (data, (row, col)), shape=(n, n), dtype=np.int32)
    snk = sp.csgraph.dijkstra(matrix, indices=t-1)

    cost = yen+snk
    m = cost[-1]
    for i in range(n-1, -1, -1):
        m = min(cost[i], m)
        cost[i] = m

    cost = 10**15-cost

    for i in cost:
        print(int(i))


main()


### FIXED CODE ###

n,m,s,t=map(int,input().split())
uvab=[list(map(int,input().split())) for _ in [0]*m]
g_yen=[[] for _ in [0]*n]
[g_yen[u-1].append([v-1,a]) for u,v,a,b in uvab]
[g_yen[v-1].append([u-1,a]) for u,v,a,b in uvab]

g_snk=[[] for _ in [0]*n]
[g_snk[u-1].append([v-1,b]) for u,v,a,b in uvab]
[g_snk[v-1].append([u-1,b]) for u,v,a,b in uvab]

import heapq
def dijkstra(g,start):
    inf=10**15
    dist=[inf for _ in [0]*n]
    h=[(0,start)]
    heapq.heapify(h)
    while h:
        d,i=heapq.heappop(h)
        if dist[i]==inf:
            dist[i]=d
            for x,y in g[i]:
                heapq.heappush(h,(d+y,x))
    return dist

yen=dijkstra(g_yen,s-1)
snk=dijkstra(g_snk,t-1)

cost=[yen[i]+snk[i] for i in range(n)]
m=cost[-1]
for i in range(n-1,-1,-1):
    m=min(m,cost[i])
    cost[i]=m
    
for i in cost:
    print(10**15-i)
### BUGGY CODE ###

#coding: utf-8
import math
import heapq

MOD = 10**9+7

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

ans = 0
for a in range(N-2):
    for b in range(a+1,N-1):
        for c in range(b+1,N):
            if(L[c]<L[a]+L[b]):
                ans+=1
            else:
                break

print(ans)

### FIXED CODE ###

#coding: utf-8
import math
import heapq
import bisect

MOD = 10**9+7

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

ans = 0
for a in range(N-2):
    for b in range(a+1,N-1):
        c = bisect.bisect_left(L,L[a]+L[b])
        ans += c-b-1
            
print(ans)
### BUGGY CODE ###

mod = 998244353
N, S = map(int, input().split())
A = list(map(int, input().split()))
dp = [[0]*(S+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(1,N+1):
    dp[i][0] = dp[i-1][0]*2%mod

for i in range(1,N+1):
    for j in range(1,S+1):
        dp[i][j] = dp[i-1][j]*2%mod
        if j>=A[i-1]:
            dp[i][j] += dp[i-1][j-A[i-1]]

ans = dp[-1][-1]%mod
print(ans)


### FIXED CODE ###

mod = 998244353
N, S = map(int, input().split())
A = list(map(int, input().split()))
dp = [[0]*(S+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(1,N+1):
    dp[i][0] = dp[i-1][0]*2%mod

for i in range(1,N+1):
    for j in range(1,S+1):
        dp[i][j] = dp[i-1][j]*2%mod
        if j>=A[i-1]:
            dp[i][j] += dp[i-1][j-A[i-1]]

ans = dp[-1][-1]%mod
print(ans)
### BUGGY CODE ###

import heapq

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

def calc_score(b):
    score = 0
    for i, a in enumerate(A):
        score += abs(a - (b + i + 1))
    return score


def decide_direction():
    score_b0 = calc_score(0)
    score_b1 = calc_score(1)
    
    if score_b0 > score_b1:
        return 1
    else:
        return -1


pre_score = calc_score(0)
b = 0
direction = decide_direction()

while True:
    b += direction
    score = calc_score(b)
    if score > pre_score:
        print(pre_score)
        break
    else:
        pre_score = score

### FIXED CODE ###

from statistics import median

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

A_star = [a - (i + 1) for i, a in enumerate(A)]

def calc_score(b):
    score = 0
    for a in A_star:
        score += abs(a - b)
    return score

def decide_direction(b):
    score0 = calc_score(b)
    score1 = calc_score(b + 1)
    if score0 > score1:
        return 1
    else:
        return -1

b = int(median(A_star))
direction = decide_direction(b)
pre_score = calc_score(b)

while True:
    b += direction
    score = calc_score(b)
    if score >= pre_score:
        print(pre_score)
        break
    else:
        pre_score = score
### BUGGY CODE ###

n, m = map(int, input().split())
for i in range(m//n, 0, -1):
    rem = m-i*n
    if rem%i==0:
        print(i)
        break

### FIXED CODE ###

n, m = map(int, input().split())
for i in range(m//n, 0, -1):
    rem = m-i*n
    if rem%i==0:
        print(i)
        break
### BUGGY CODE ###

l, r = map(int, input().split())
mod = 2019
ans = l*r%mod
for i in range(l, r):
    for j in range(i+1, r+1):
        tmp = i*j%mod
        if ans > tmp:
            ans = tmp
print(ans)

### FIXED CODE ###

L,R=map(int,input().split())
c=2019
z=0
for i in range(L,R+1):
    for j in range(i+1,R+1):
        a=i*j
        b=a%2019
        if c>b:
            c=b
        if c==0:
            z=1
            break
    if z==1:
        break
print(c)
### BUGGY CODE ###

n = int(input())
V = list(map(int,input().split()))
Vodd = list()
Veven = list()
nodd = 0
neven = 0
for x in range(0,n,2):
    Vodd.append(V[x])
    Veven.append(V[x+1]) 
oddcounts = {x:Vodd.count(x) for x in set(Vodd)}
evencounts = {x:Veven.count(x) for x in set(Veven)}

y = sorted(oddcounts.items(),key=lambda x:x[1],reverse=True)
z = sorted(evencounts.items(),key=lambda x:x[1],reverse=True)

number = len(Vodd) - y[0][1] + len(Veven) - z[0][1]

if y[0][0] == z[0][0]:
    if len(y) == 1:
        y.append((0,0))
    if len(z) == 1:
        z.append((0,0))
    number = min(len(Vodd)-y[1][1]+len(Veven)-z[0][1],len(Vodd)-y[0][1]+len(Veven)-z[1][1])

print(number)

### FIXED CODE ###

from collections import Counter
n = int(input())
V = list(map(int,input().split()))
Vodd = list()
Veven = list()
for x in range(0,n//2):
    Vodd.append(V[2*x])
    Veven.append(V[2*x+1]) 

oddcounts = Counter(Vodd).most_common(2)
evencounts = Counter(Veven).most_common(2)

number = n - oddcounts[0][1] - evencounts[0][1]

if oddcounts[0][0] == evencounts[0][0]:
    if len(oddcounts) == 1:
        a = 0
    else:
        a = oddcounts[1][1]
    if len(evencounts) == 1:
        b = 0
    else:
        b = evencounts[1][1]
    number = min(n - a - evencounts[0][1],n - oddcounts[0][1] - b)

print(number)
### BUGGY CODE ###

n, m = map(int, input().split())
mod = 10**9 + 7
def fact(n):
  i = n
  ret = 1
  while i > 1:
    ret *= i
    i -= 1
  return ret
if n == m:
  print(fact(n) ** 2 * 2 % mod)
# elif n+1 == m or n-1 == m:
#   print(fact(n) * fact(m))
elif n == m+1:
  n_f = fact(n)
  print(n_f * (n_f//n) % mod)
elif n == m-1:
  m_f = fact(m)
  print(m_f * (m_f//m) % mod)
else:
  print(0)

### FIXED CODE ###

n, m = map(int, input().split())
mod = 10**9 + 7
def fact(x):
  ret = 1
  for i in range(1, x+1):
    ret = ret * i % mod
  return ret
if n == m:
  print(fact(n)**2 * 2 % mod)
elif n+1 == m or n-1 == m:
  print(fact(n) * fact(m) % mod)
else:
  print(0)
### BUGGY CODE ###

import math
from functools import reduce
K = int(input())
CNT= 0
def gcd(*numbers):
    return reduce(math.gcd, numbers)
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            CNT += gcd(i,j,k)
print(CNT)

### FIXED CODE ###

import math
from functools import reduce
K = int(input())
CNT= 0
def gcd(*numbers):
    return reduce(math.gcd, numbers)
for i in range(1,K+1):
    for j in range(1,K+1):
        GCD = gcd(i,j)
        if GCD == 1:
            CNT += K
        else:
            for k in range(1, K+1):
                if gcd(GCD,k) != 1:
                    CNT += gcd(GCD,k)
                else:
                    CNT += 1
print(CNT)
### BUGGY CODE ###

flag = True
n = int(input())

a = input().split()

if n != len(a):
    print("error")

start = 0
for i in a:
    start += 1
    for j in a[start:]:
        if i == j:
            flag = False
            break
    
            
if flag:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

flag = True
n = int(input())

a = input().split()

a.sort()
start = 0
for i in a:
    for j in a[start-1:start+1:2]:
        if i == j:
            flag = False
            break
    start += 1
    
if flag:
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

n, ma, mb = map(int, raw_input().split())
N = 403
memo = [[10**18]*(N+20) for i in xrange(N+20)]
memo[0][0] = 0
for t in xrange(n):
    a, b, c = map(int, raw_input().split())
    for i in xrange(N, -1, -1):
        for j in xrange(N, -1, -1):
            memo[i+a][j+b] = min(memo[i+a][j+b], memo[i][j] + c)
ans = 10**18
a = ma; b = mb
while a < N and b < N:
    ans = min(ans, memo[a][b])
    a += ma; b += mb
print -1 if ans > 50000 else ans

### FIXED CODE ###

from heapq import heappush, heappop
n, ma, mb = map(int, raw_input().split())
dp = {(0, 0): 0}
INF = 10**18
for i in xrange(n):
    a, b, c = map(int, raw_input().split())
    for x, y in sorted(dp.keys())[::-1]:
        dp[x+a, y+b] = min(dp.get((x+a, y+b), INF), dp[x, y] + c)
ans = INF
for x, y in dp:
    if x*mb == y*ma > 0:
        ans = min(ans, dp[x, y])
print -1 if ans==INF else ans
### BUGGY CODE ###

import sys
input = sys.stdin.readline
Q = int(input())
l = []
r = []
for i in range(Q) :
    p, q = map(int,input().split())
    l.append(p)
    r.append(q)

def get_primenumber(number):
    prime_list = []
    search_list = list(range(2,number+1))
    while True:
      if search_list[0]**2 > number:
        prime_list.extend(search_list)
        break
      else:
        head_num = search_list[0]
        prime_list.append(head_num)
        search_list.pop(0)
        search_list = [num for num in search_list if num % head_num != 0]
    return prime_list

primes = get_primenumber(10**5+1)

for i in range(Q) :
    ans = 0
    for j in range(l[i],r[i]+1) :
        if j%2 == 0 :
            continue
        if j in primes and (j+1)//2 in primes :
            ans += 1
    print(ans)


### FIXED CODE ###

import sys
import itertools
input = sys.stdin.readline
Q = int(input())
l = []
r = []
for i in range(Q) :
    p, q = map(int,input().split())
    l.append(p)
    r.append(q)

def get_primenumber(number):
    prime_list = []
    search_list = list(range(2,number+1))
    while True:
      if search_list[0]**2 > number:
        prime_list.extend(search_list)
        break
      else:
        head_num = search_list[0]
        prime_list.append(head_num)
        search_list.pop(0)
        search_list = [num for num in search_list if num % head_num != 0]
    return prime_list

primes = get_primenumber(10**5+1)
like2017 = [0 for _ in range(10**5+1)]

for p in primes :
    if (p+1)//2 in primes :
        like2017[p] = 1

like2017s = list(itertools.accumulate(like2017))

for i in range(Q) :
    print(like2017s[r[i]] - like2017s[l[i]-1])
### BUGGY CODE ###

#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())

k = I()
a = 7
if k%2 == 0:
    print(-1)
    exit()
for i in range(10**5):
    if a%k == 0:
        print(i+1)
        exit()
    a = a*10 + 7
print(-1)


### FIXED CODE ###

#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())

k = I()
a = 7
if k%2 == 0:
    print(-1)
    exit()
for i in range(10**6):
    if a%k == 0:
        print(i+1)
        exit()
    a = (a*10 + 7)%k

print(-1)
### BUGGY CODE ###

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

N = int(input())
A = list(map(int, input().split()))
A = sorted([(a, p) for p, a in enumerate(A)], reverse=True)


# dp[i][j] := i番目の幼児まで見て、左に詰める選択をj回行った場合のうれしさの最大値
dp = [[0] * (N + 1) for _ in range(N + 1)]
for i, (a, p) in enumerate(A):
    for j in range(i + 1):
        # 左に詰める場合
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + (p - j) * a)

        # 右に詰める場合
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + ((N - (i - j) - 1) - p) * a)
#print(dp)
print(max(dp[-1]))


### FIXED CODE ###

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

N = int(input())
A = list(map(int, input().split()))
A = sorted([(a, p) for p, a in enumerate(A)], reverse=True)


# dp[i][j] := i番目の幼児まで見て、左に詰める選択をj回行った場合のうれしさの最大値
dp = [[0] * (N + 1) for _ in range(N + 1)]
for i, (a, p) in enumerate(A):
    for j in range(i + 1):
        # 左に詰める場合
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + (p - j) * a)

        # 右に詰める場合
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + ((N - (i - j) - 1) - p) * a)
#print(dp)
print(max(dp[-1]))