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

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

a = []
for i in range(n):
    a.append(list(map(int,input().split())))

b = []
for i in range(n):
    b += [100 * (i + 1) for j in range(a[i][0])]

d = []
ans = 1000000000000000
for i in range(2 ** len(b)):
    check = 0
    c = []
    counter = {}
    for j in range(len(b)):
        if (i >> j) & 1:
            if b[j] in counter.keys():
                c.append(b[j])
                counter[b[j]] += 1
            else:
                c.append(b[j])
                counter[b[j]] = 1
    for k in range(n):
        if 100 * (k + 1) in counter.keys():
            if counter[100 * (k + 1)] == a[k][0]:
                check += a[k][1]
    check += sum(c)
    if check >= m and len(c) < ans:
        ans = len(c)
    #print(ans, check, c)
print(ans)

### FIXED CODE ###

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

a = []
for i in range(n):
    a.append(list(map(int,input().split())))

ans = 1000000000000000
for i in range(2 ** n):
    check = 0
    ac = 0
    tmp = 0
    for j in range(n):
        if (i >> j) & 1:
            check += a[j][0] * 100 * (j + 1) + a[j][1]
            tmp += a[j][0]
        
        if check >= m:
            ans = min(ans, tmp)

        else:
            for k in reversed(range(n)):
                if not (i >> k) & 1:
                    ac = -(-(m - check) // ((k + 1) * 100))
                    if ac < a[k][0]:
                        ans = min(ans, ac + tmp)

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

s=list(input())
k=int(input())
n=len(s)
subset=set([])
for i in range(n):
    tmp=[s[i]]
    subset.add(tmp[0])
    for j in range(i+1, n):
        tmp.append(s[j])
        subset.add(''.join(tmp))
subset=sorted(list(subset))
print(subset[k-1])

### FIXED CODE ###

s=list(input())
k=int(input())
n=len(s)
subset=[]
from bisect import bisect_left

for i in range(n):
    tmp=s[i]
    for j in range(i,min(n,i+5)):
        if j==i: pass
        else: tmp+=s[j]
        if tmp not in subset:
            l=bisect_left(subset, tmp)
            if 0<=l<5:
                subset=subset[:l]+[tmp]+subset[l:5]
                subset=subset[:5]
            else:
                break
print(subset[k-1])
### BUGGY CODE ###

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

mx = sum(p[:K])
for i in range(1, N-K+1):
  mx = max(mx, sum(p[i:i+K]))
  
ans = (mx+K) / 2
print(ans)

### FIXED CODE ###

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

mx = sum(p[:K])
cur = mx
for i in range(N-K):
  cur = cur-p[i]+p[i+K]
  mx = max(mx, cur)
  
ans = (mx+K) / 2
print(ans)
### BUGGY CODE ###

_, _, _, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

ab = [x+y for x in a for y in b]
ab.sort(reverse=True)

abc = [x+y for x in ab[:k] for y in c]

abc.sort(reverse=True)
for i in abc[:k]:
  print(i)

### FIXED CODE ###

x, y, z, k = list(map(int, input().split()))
a = sorted(map(int, input().split()))
b = sorted(map(int, input().split()))
c = sorted(map(int, input().split()))

ab = sorted(x+y for x in a for y in b)[:-k-1:-1]
abc = sorted(x+y for x in ab[:k] for y in c)[:-k-1:-1]
print(*abc, sep='\n')
### BUGGY CODE ###

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

dist = []
dist.append(a[1]-a[0])

for num in range(1, len(a)):
  if num == len(a) - 1:
    dist.append(k-a[num]+a[0])
  else:
    dist.append(a[num+1]-a[num])
#print(dist)

min_index = [i for i, v in enumerate(dist) if v == min(dist)]

right = 0
left = 0
result = []
for start_index in min_index:
  for n in range(0, len(dist)-1):
    x = start_index + n
    y = start_index - n
    if x > len(dist)-1:
      x = (len(dist) - n - start_index) * -1
    if y < 0:
      y = len(dist)-n
    right += dist[x]
    left += dist[y]
    if len(result) > 0 and (min(result) < right and min(result) < left):
      break
  result.append(min(right, left))
  
print(min(result))

### FIXED CODE ###

import numpy as np

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

dist = []
dist.append(a[1]-a[0])

for num in range(1, len(a)):
  if num == len(a) - 1:
    dist.append(k-a[num]+a[0])
  else:
    dist.append(a[num+1]-a[num])
#print(dist)
dist = np.array(dist)

#min_index = np.where(dist == dist.min())[0]
s = np.sum(dist)
result = []
for start_index in range(0, len(dist)):
  if start_index == 0:
    result.append(s - dist[len(dist)-1])
    result.append(s - dist[start_index+1])
  elif start_index == len(dist)-1:
    result.append(s - dist[start_index-1])
    result.append(s - dist[0])
  else:
    result.append(s - dist[start_index-1])
    result.append(s - dist[start_index+1])
print(min(result))
### BUGGY CODE ###

l = input()
m = l.split(" ")
n = int(m[0])
k = int(m[1])
while (abs(n-k)<n):
  n = abs(n-k)
  a = abs(n-k)
print(n)


### FIXED CODE ###

NK = input().split(' ')
N = int(NK[0])
K = int(NK[1])

while N>K:
  N = N%K
  
print(min([N,K-N]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n, k = [ int(v) for v in input().split() ]
card_parent = [ i for i in range(n) ]
card_set = [ set([i]) for i in range(n) ]
card_list = [ tuple( int(v)-1 for v in input().split() ) for i in range(k) ]

card_list = set(card_list)
for i in card_list:
    p, q = i[0], i[1]
    if card_parent[p] != card_parent[q]:
        union_parent, vanish_parent = min(card_parent[p], card_parent[q]), max(card_parent[p], card_parent[q])
        for j in card_set[vanish_parent]:
            card_parent[j] = union_parent
        card_set[union_parent] = card_set[union_parent] | card_set[vanish_parent]

print(len(set(card_parent)))


### FIXED CODE ###


import sys
input = sys.stdin.readline
n, k = [ int(v) for v in input().split() ]
card_parent = [ i for i in range(n) ]
card_set = [ set([i]) for i in range(n) ]
card_list = [ tuple( int(v)-1 for v in input().split() ) for i in range(k) ]

def parent(x,a):
    if card_parent[x] == x:
        return x, a
    else:
        return parent(card_parent[x],a+1)


for i in card_list:
    p, q = i[0], i[1]
    card_parent[p], rank_p = parent(p,0)
    card_parent[q], rank_q = parent(q,0)
    if card_parent[p] != card_parent[q]:
        if rank_p > rank_q:
            card_parent[card_parent[q]] = card_parent[p]
        else:
            card_parent[card_parent[p]] = card_parent[q]




card_parent = [ parent(i,0)[0] for i in range(n) ]

print(len(set(card_parent)))
### BUGGY CODE ###

N = int(input())

list = []
for i in range(N):
    list.append(str(input()))
    a = list.count("AC")
    b = list.count("WA")
    c = list.count("TLE")
    d = list.count("RE")

print("AC x",a)
print("WA x" , b)
print("TLE x" , c)
print("RE x" ,d)

### FIXED CODE ###

N = int(input())

list = []
for i in range(N):
    list.append(str(input()))
a = list.count("AC")
b = list.count("WA")
c = list.count("TLE")
d = list.count("RE")

print("AC x",a)
print("WA x" ,b)
print("TLE x" ,c)
print("RE x" ,d)
### BUGGY CODE ###

inp = input()
len_1st = len(inp)

inf = 10 ** 5
for i in range(inf):
  inp = inp.replace('10','')  
  inp = inp.replace('01','')  
  
  if i%100 == 0: 
    cnt_01 = inp.count('01')
    cnt_10 = inp.count('10')
    if (cnt_01 == 0) & (cnt_10 == 0):
      break
  
len_after = len(inp)
print(len_1st - len_after)

### FIXED CODE ###

inp = input()

cnt_0 = inp.count('0')
cnt_1 = inp.count('1')

if (cnt_0 == 0) or (cnt_1 == 0):
  print(0)
else:
  print(min(cnt_0,cnt_1) * 2)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

N, Q = list(map(int, input().split()))
nodes = [[] for i in range(N)]
for i in range(N-1):
  r, e = list(map(int, input().split()))
  r, e = r - 1, e - 1
  nodes[r].append(e)
  nodes[e].append(r)
#print(nodes)

result = [0] * N
for i in range(Q):
  r, s = list(map(int, input().split()))
  result[r-1] += s

def dfs(r, prev=-1):
  for i in nodes[r]:
    if i == prev:
      continue
    result[i] += result[r]
    dfs(i, r)

dfs(0)
print(*result)


### FIXED CODE ###

#人の（ほぼ同じなのにうまくいかないので）
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N, Q = map(int, input().split())
lines = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    lines[a-1].append(b-1)
    lines[b-1].append(a-1)
ans = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    ans[p-1] += x

def dfs(v, parent):
    for u in lines[v]:
        if u != parent:
            ans[u] += ans[v]
            dfs(u, v)

dfs(0, -1)
print (*ans)
### BUGGY CODE ###

n = int(input())
tall = list(map(int, input().split()))
maxhigh = [i for i, x in enumerate(tall) if x == max(tall)]
minhigh = [i for i, x in enumerate(tall) if x == min(tall)]

if(n == 1):
    print("Yes")
elif((max(tall) - min(tall)>= 2)and(min(maxhigh)>max(minhigh))):
    print("Yes")
else:
    print("No")


### FIXED CODE ###

n = int(input())
tall = list(map(int, input().split()))
lar = tall[0]
lno = 0
frag = 0


for i in range(n):
    if(tall[i]>lar):
        lar= tall[i]
    if(lar - tall[i] >= 2):
        frag = 1
        break

if(frag == 1):
    print("No")
else:
    print("Yes")
### BUGGY CODE ###

a,b,k=map(int,input().split())

for i in range(a,b+1):
  if (i<a+k or b-k<i):
    print(i)



### FIXED CODE ###

a,b,k=map(int,input().split())

if (b-a<1000):
  for i in range(a,b+1):
    if (i<a+k or b-k<i):
      print(i)
else:
  for i in range(k):
    print(a+i)
  for i in range(k-1,-1,-1):
    print(b-i)
### BUGGY CODE ###

X,Y,A,B,C = (int(x) for x in input().split())
red = list(map(int, input().strip().split()))
green = list(map(int, input().strip().split()))
clear = list(map(int, input().strip().split()))
red.sort(reverse=True)
green.sort(reverse=True)
clear.sort(reverse=True)
pre_answer = 0
answer = 0
for i in range (max(X+Y,C)):
    for k in range (i+1):
        if(X-k>=0 and Y-(i-k)>=0 ):
            pre_answer = sum(red[0:X-k]) + sum(green[0:Y-(i-k)]) + sum(clear[0:i])
#             print(X-k,Y-(i-k),i,pre_answer)
            if(answer<pre_answer):
                answer = pre_answer
print(answer)

### FIXED CODE ###

X,Y,A,B,C = (int(x) for x in input().split())
red = list(map(int, input().strip().split()))
green = list(map(int, input().strip().split()))
clear = list(map(int, input().strip().split()))
red.sort(reverse=True)
green.sort(reverse=True)
# clear.sort(reverse=True)
apple = red[0:X] + green[0:Y] + clear
apple.sort(reverse=True)
print(sum(apple[0:X+Y]))
### BUGGY CODE ###

def main():
  import bisect
  import sys
  from itertools import accumulate
  input = sys.stdin.readline
  def hsnum(x):
    num = 0
    for i in a:
      y = x-i
      num += n-bisect.bisect_left(a,y)
    return num
  n,m = map(int, input().split())
  a = list(map(int, input().split()))
  a.sort()
  suma = [0]+list(accumulate(a))
  lx = 0
  rx = 2*10**5+2
  error = 0
  while lx < rx:
    mx = (lx+rx)//2
    if hsnum(mx) < m:
      rx = mx
    elif hsnum(mx) > m:
      if hsnum(mx+1) < m:
        error = hsnum(mx)-m
        lx = mx
        break
      lx = mx + 1
    else:
      lx = mx
      break
  ans = 0
  for i in a:
    rema = lx - i
    j = bisect.bisect_left(a,rema)
    ans += (n-j)*i+suma[n]-suma[j]
  print(ans-error*lx)
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
  import bisect
  import sys
  from itertools import accumulate
  input = sys.stdin.readline
  def hsnum(x):
    num = 0
    for i in a:
      y = x-i
      num += n-bisect.bisect_left(a,y)
    return num
  n,m = map(int, input().split())
  a = list(map(int, input().split()))
  a.sort()
  suma = [0]+list(accumulate(a))
  lx = 0
  rx = 2*10**5+2
  error = 0
  while lx+1 < rx:
    mx = (lx+rx)//2
    if hsnum(mx) < m:
      rx = mx
    elif hsnum(mx) > m:
      lx = mx + 1
    else:
      lx = mx
      break
  if hsnum(lx)<m:
    lx -= 1
  error = hsnum(lx)-m
  ans = 0
  for i in a:
    rema = lx - i
    j = bisect.bisect_left(a,rema)
    ans += (n-j)*i-suma[j]
  ans += suma[n]*n
  print(ans-error*lx)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

s = list(map(int, input().split()))
n=s[0]
k=s[1]
s = list(map(int, input().split()))
ep=[]
for i in s:
    ep.append((1+i)/2)
max_ep=0
for i in range(n-k+1):
    sum=0
    for j in range(i,i+k):
        sum+=ep[j]
    if sum>max_ep:
        max_ep=sum
print(max_ep)

### FIXED CODE ###

s = list(map(int, input().split()))
n=s[0]
k=s[1]
s = list(map(int, input().split()))
ep=[]
for i in s:
    ep.append((1+i)/2)
s={}
s[k-1]=0
for i in range(k):
    s[k-1]+=ep[i]
for i in range(k-1,n-1):
    s[i+1]=s[i]+ep[i+1]-ep[i-k+1]
print(max(s.values()))
### BUGGY CODE ###

#from math import gcd
from fractions import gcd
from functools import reduce
import sys


def input():
    return sys.stdin.readline()[:-1]


def lcm(a, b):
	return a * b // gcd(a, b)

def main():
	mod = 10**9 + 7
	N = int(input())
	A = [i for i in map(int, input().split())]
	
	ans = reduce(lcm, A)
	"""
	a = 1
	for i in A:
		a = lcm(a, i)
	"""
	#print(a, ans)
	B = [ans//i for i in A]
	print(sum(B) % mod)

if __name__ == "__main__":
	main()


### FIXED CODE ###

#from math import gcd
from fractions import gcd
from functools import reduce

mod = 10**9 + 7

def lcm(a, b):
	return a * b // gcd(a, b)


N = int(input())
A = [i for i in map(int, input().split())]

ans = reduce(lcm, A)

#print(ans)
B = [ans//i for i in A]

print(sum(B) % mod)
### BUGGY CODE ###

def warshall_floyd(V, E):
    INF = 10 ** 9
    d = [[0 for _ in range(V + 1)]] + [[0] + [INF for j in range(V)] for i in range(V)]
    for i in range(V + 1):
        d[i][i] = 0
    for i, j in E:
        d[i][j] = 1
        d[j][i] = 1
    for k in range(1, V + 1):
        for i in range(1, V):
            for j in range(i, V + 1):
                dk = d[i][k] + d[k][j]
                if d[i][j] > dk:
                    d[i][j] = dk
                    d[j][i] = dk
    return d


h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
n = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            n += 1
            s[i][j] = n
        else:
            s[i][j] = 0


E = []
for i in range(h):
    for j in range(w):
        p = s[i][j]
        if p > 0:
            if j < w - 1:
                p1 = s[i][j + 1]
                if p1 > 0:
                    E.append([p, p1])
            if i < h - 1:
                p2 = s[i + 1][j]
                if p2 > 0:
                    E.append([p, p2])

ans = 0
INF = 10 ** 9
D = warshall_floyd(n, E)
ans = max(list(map(max, D)))
print(ans)


### FIXED CODE ###

def warshall_floyd(V, E):
    INF = 10 ** 9
    d = [[0 for _ in range(V + 1)]] + [[0] + [INF for j in range(V)] for i in range(V)]
    for i in range(V + 1):
        d[i][i] = 0
    for i, j in E:
        d[i][j] = 1
        d[j][i] = 1
    for k in range(1, V + 1):
        for i in range(1, V):
            for j in range(i, V + 1):
                dk = d[i][k] + d[k][j]
                if d[i][j] > dk:
                    d[i][j] = dk
                    d[j][i] = dk
    return d


h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
n = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            n += 1
            s[i][j] = n
        else:
            s[i][j] = 0


E = []
for i in range(h):
    for j in range(w):
        p = s[i][j]
        if p > 0:
            if j < w - 1:
                p1 = s[i][j + 1]
                if p1 > 0:
                    E.append([p, p1])
            if i < h - 1:
                p2 = s[i + 1][j]
                if p2 > 0:
                    E.append([p, p2])

ans = 0
INF = 10 ** 9
D = warshall_floyd(n, E)
ans = max(list(map(max, D)))
print(ans)
### BUGGY CODE ###

import re

NQ = [int(i) for i in input().split()]
N = NQ[0]
Q = NQ[1]
S = input()
index = 0
answer = []
while(Q > 0):
    lr = [int(i) for i in input().split()]
    l = lr[0]
    r = lr[1]
    new_str = S[l-1:r]
    answer.append(len(re.findall("AC",new_str)))
    Q -= 1
    index += 1

for s in answer:
    print(s)

### FIXED CODE ###

import re

NQ = [int(i) for i in input().split()]
N = NQ[0]
Q = NQ[1]
S = input()
LR = [[int(i) for i in input().split()] for j in range(Q)]
check = [0] * N
for i in range(N - 1):
    check[i + 1] = check[i] + (1 if S[i:i + 2] == "AC" else 0)


for j in range(Q):
    print((check[LR[j][1] - 1]) - (check[LR[j][0] - 1]))
### BUGGY CODE ###

n = int(input())
d = list(map(int, input().split()))
m = int(input())
t = list(map(int, input().split()))

for i in t:
  if i in d:
    d.remove(i)
  else:
    print("NO")
    exit()

print("YES")

### FIXED CODE ###

n = int(input())

ht = {}

for i in input().split():
  ht[i] = ht.get(i, 0) + 1

m = int(input())

for i in input().split():
  if i not in ht or ht[i] == 0:
    print("NO")
    exit()
  else:
    ht[i] -= 1

print("YES")
### BUGGY CODE ###

n, q = map(int, input().split())
cnt = [0]*n
root = [[] for i in range(n)]

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

for i in range(q):
    p, x = map(int, input().split())

    tmpi = p-1
    tmparr = [tmpi]
    while tmparr:
        tmpi = tmparr.pop(0)
        cnt[tmpi] += x
        tmparr += root[tmpi]
print(*cnt)

### FIXED CODE ###

from sys import stdin
n, q = map(int, input().split())
cnt = [0]*n
root = [[] for i in range(n)]

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

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

tmparr = [0]
while tmparr:
    tmpi = tmparr.pop()
    for i in root[tmpi]:
        cnt[i] += cnt[tmpi]
    tmparr += root[tmpi]
print(*cnt)
### BUGGY CODE ###

N=int(input())
P = []
for _ in range(N):
    prize = input()
    if not prize in P:
        P.append(prize)
print(len(P))



### FIXED CODE ###

N=int(input())
P = []
# 26進数で表していこう
for _ in range(N):
    prize = input()
    prize_num = 0
    for i,p in enumerate(prize[::-1]):
        prize_num += 26**i * ord(p)
    P.append(prize_num)

P.sort()
now=-1
count = 0
for p in P:
    if not p==now:
        now=p
        count+=1

print(count)
### BUGGY CODE ###

import sys

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

    t = 0
    while True:
        for i in range(N):
            if A[i] % 2 == 1:
                break
            else:
                A[i] = A[i]/2
                
        t += 1

main()

### FIXED CODE ###

import sys

def main():
    N = int(input())
    A = [int(_) for _ in input().split()]

    t = 0
    while True:
        for i in range(N):
            if A[i] % 2 == 0:
                A[i] //= 2
            else:
                print(t)
                sys.exit()
        t += 1

main()
### BUGGY CODE ###

def main():
    S = list(input())
    S.reverse()
    N = len(S)
    mod = 10**9+7
    dp = [[0 for r in range(13)] for n in range(N+1)]
    dp[0][0] = 1
    lookup = [[0 for d in range(10)] for n in range(N)]
    for n in range(N):
        for d in range(10):
            lookup[n][d] = d*pow(10, n, 13) % 13
    for n in range(1, N+1):
        if S[n-1] == '?':
            for d in range(10):
                for r in range(13):
                    dp[n][(r+lookup[n-1][d]) % 13] += dp[n-1][r] % mod
        else:
            for r in range(13):
                dp[n][(r+lookup[n-1][int(S[n-1])]) % 13] += dp[n-1][r] % mod
    print(dp[-1][5] % mod)


main()


### FIXED CODE ###

S = list(input())
S.reverse()
N = len(S)
mod = 10**9+7
dp = [[0 for r in range(13)] for n in range(N+1)]
dp[0][0] = 1
lookup = [[0 for d in range(10)] for n in range(N)]
for n in range(N):
    for d in range(10):
        lookup[n][d] = d*pow(10, n, 13) % 13
for n in range(1, N+1):
    if S[n-1] == '?':
        for d in range(10):
            for r in range(13):
                dp[n][(r+lookup[n-1][d]) % 13] += dp[n-1][r] % mod
    else:
        for r in range(13):
            dp[n][(r+lookup[n-1][int(S[n-1])]) % 13] += dp[n-1][r] % mod
print(dp[-1][5] % mod)
### BUGGY CODE ###

H,N=map(int,input().split())
A=[]
B=[]

for _ in range(N):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)

dp=[0]
for i in range(1,H+max(A)):
    dcand=[]
    for j in range(N):
        dcand.append(B[j]+min(dp[i-A[j]:]))
    dp.append(min(dcand))

print(min(dp[H:]))

### FIXED CODE ###

h, n = map(int, input().split())
magics = [list(map(int, input().split())) for _ in range(n)]
max_a = max(a for a, b in magics)
dp = [0] * (h + max_a)
for i in range(1, h + max_a):
    dp[i] = min(dp[i - a] + b for a, b in magics)
print(dp[h])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

def solve(N: int, A: "List[List[int]]"):
    for i in range(N):
        A[i] = A[i][::-1]
    
    answer = 0
    totalGame = 0
    while True:
        if totalGame == N*(N-1)//2:
            break

        match = set()
        # 既にこのターンでマッチしたインデックスを保持

        for i in range(N):
            if not A[i]:
                continue
            match_index = A[i][-1]-1

            if match_index in match or i in match:
                continue

            if A[match_index][-1]-1 == i:
                A[i].pop()
                A[match_index].pop()
                match.add(i)
                match.add(match_index)
                totalGame += 1
            else:
                continue

        if len(match) == 0:
            print(-1)
            return
        answer += 1

    print(answer)
    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
    A = [[int(next(tokens)) for _ in range(N - 1)] for _ in range(N)]  # type: "List[List[int]]"
    solve(N, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

def solve(N: int, A: "List[List[int]]"):
    for i in range(N):
        A[i] = A[i][::-1]
    
    answer = 0
    totalGame = 0
    MAXGAME = (N*(N-1))//2
    match = set()

    while True:
        if totalGame == 0:
            for i in range(N):
                if not A[i]:
                    continue
                match_index = A[i][-1]-1

                if not A[match_index]:
                    continue

                if match_index in match or i in match:
                    continue

                if A[match_index][-1]-1 == i:
                    A[i].pop()
                    A[match_index].pop()
                    match.add(i)
                    match.add(match_index)
                    totalGame += 1
        else:
            if totalGame == MAXGAME:
                break

            check_needed = list(match)
            # 既にこのターンでマッチしたインデックスを保持
            match = set()

            for i in check_needed:
                if not A[i]:
                    continue
                match_index = A[i][-1]-1

                if not A[match_index]:
                    continue

                if match_index in match or i in match:
                    continue

                if A[match_index][-1]-1 == i:
                    A[i].pop()
                    A[match_index].pop()
                    match.add(i)
                    match.add(match_index)
                    totalGame += 1

        if len(match) == 0:
            print(-1)
            return

        answer += 1

    print(answer)
    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
    A = [[int(next(tokens)) for _ in range(N - 1)] for _ in range(N)]  # type: "List[List[int]]"
    solve(N, A)

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

k, n = map(int, input().split())
a_list = list(map(int, input().split()))
ans = k
for i in a_list:
    seq_list = a_list
    for j in range(n):
        if i == 0 and a_list[j] > k / 2:
            seq_list[j] = a_list[j] - k
        else:
            seq_list[j] = a_list[j] - i
    max_a = max(seq_list)
    min_a = min(seq_list)
    seq_dis = max_a - min_a
    ans = min(seq_dis, ans)
print(ans)

### FIXED CODE ###

k, n = map(int, input().split())
a = list(map(int, input().split()))
a.append(a[0] + k)
dis = [a1 - a0 for a0, a1 in zip(a, a[1:])]
print(k - max(dis))