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

import sys
sys.setrecursionlimit(10 ** 7)

N = int(input())
X = input()
pc = X.count("1")

if pc == 1:
    if X[-1] == "0":
        for i, s in enumerate(X):
            if i == N - 1:
                print(2)
            elif s == "0":
                print(1)
            else:
                print(0)
    else:
        ans = [2] * (N - 1) + [0]
        print(*ans, sep="\n")
    exit()


m01 = 0
m10 = 0
for i, s in enumerate(X[::-1]):
    if s == "1":
        m01 += pow(2, i, pc + 1)
        m01 %= pc + 1
        m10 += pow(2, i, pc - 1)
        m10 %= pc - 1


def pop_count(T):
    T = (T & 0x55555555) + ((T >> 1) & 0x55555555)
    T = (T & 0x33333333) + ((T >> 2) & 0x33333333)
    T = (T & 0x0F0F0F0F) + ((T >> 4) & 0x0F0F0F0F)
    T = (T & 0x00FF00FF) + ((T >> 8) & 0x00FF00FF)
    T = (T & 0x0000FFFF) + ((T >> 16) & 0x0000FFFF)
    return T


memo = [0] * (N + 10)
for i in range(1, N + 10):
    p = pop_count(i)
    memo[i] = memo[i % p] + 1


ans = [0] * N
for i, s in enumerate(X[::-1]):
    if s == "0":
        m = m01
        m += 1 << i
        m %= pc + 1
    else:
        m = m10
        m -= 1 << i
        m %= pc - 1
    ans[i] = memo[m] + 1

print(*ans[::-1], sep="\n")

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

N = int(input())
X = input()
pc = X.count("1")

if pc == 1:
    if X[-1] == "0":
        for i, s in enumerate(X):
            if i == N - 1:
                print(2)
            elif s == "0":
                print(1)
            else:
                print(0)
    else:
        ans = [2] * (N - 1) + [0]
        print(*ans, sep="\n")
    exit()


m01 = 0
m10 = 0
b01 = 1
b10 = 1
for i, s in enumerate(X[::-1]):
    if s == "1":
        m01 += b01
        m01 %= pc + 1
        m10 += b10
        m10 %= pc - 1
    b01 *= 2
    b01 %= pc + 1
    b10 *= 2
    b10 %= pc - 1


def pop_count(T):
    T = (T & 0x55555555) + ((T >> 1) & 0x55555555)
    T = (T & 0x33333333) + ((T >> 2) & 0x33333333)
    T = (T & 0x0F0F0F0F) + ((T >> 4) & 0x0F0F0F0F)
    T = (T & 0x00FF00FF) + ((T >> 8) & 0x00FF00FF)
    T = (T & 0x0000FFFF) + ((T >> 16) & 0x0000FFFF)
    return T


memo = [0] * (N + 10)
for i in range(1, N + 10):
    p = pop_count(i)
    memo[i] = memo[i % p] + 1


ans = [0] * N
b01 = 1
b10 = 1
for i, s in enumerate(X[::-1]):
    if s == "0":
        m = m01
        m += b01
        m %= pc + 1
    else:
        m = m10
        m -= b10
        m %= pc - 1
    ans[i] = memo[m] + 1
    b01 *= 2
    b01 %= pc + 1
    b10 *= 2
    b10 %= pc - 1

print(*ans[::-1], sep="\n")
### BUGGY CODE ###

import math
S=input()
Q=int(input())
Rev=True
front=""
back=""
for i in range(Q):
    a=input()
    if a=="1":
        Rev=not(Rev)
    else:
        b,c,x=a.split()
        if c == "1":
            if Rev:
                front += x
            else:
                back += x
        else:
            if Rev:
                back += x
            else:
                front += x
if Rev:
    print(front[::-1] + S + back)
else:
    print(back[::-1]+S[::-1]+front)


### FIXED CODE ###

S=input()
Q=int(input())
Rev=True
front=''
back=''
for i in range(Q):
    a=input()
    if a=='1':
        Rev=not(Rev)
    else:
        b,c,x=a.split()
        if c == '1':
            if Rev:
                front += x
            else:
                back += x
        else:
            if Rev:
                back += x
            else:
                front += x
if Rev:
    print(front[::-1] + S + back)
else:
    print(back[::-1]+S[::-1]+front)
### BUGGY CODE ###

n = int(input())

total = 0

for i in range(1, n + 1):
  m = n // i
  total += i * sum(range(1, m + 1))

print(total)

### FIXED CODE ###

n = int(input())

total = 0

for i in range(1, n + 1):
  m = n // i
  total += i * m * (m + 1) // 2

print(total)
### BUGGY CODE ###

N, K = [int(i) for i in input().split()]
h = [int(i)for i in  input().split()]

d=[0]*N
for i in range(1,N):
    from_num=max(0, i-K)
    d[i]=min([abs(h[i]-h[j])+d[j] for j in range(from_num, i)])

print(d[-1])


### FIXED CODE ###

N, K = [int(i) for i in input().split()]
h = [int(i)for i in  input().split()]

d=[1e16]*N
d[0]=0
for i in range(1,N):
    from_num=max(0, i-K)
    for j in range(from_num, i):
        d[i]=min([d[i], abs(h[i]-h[j])+d[j]])

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

N, M = map(int, input().split())
a = list(map(int, input().split()))
for k in range(N):
  a[k] //= 2

foo = 1
while a[0]%2 == 0:
  foo *= 2
  a[0] // 2
for k in range(1, N):
  if a[k] % foo == 0 and a[k]%(2*foo) !=0:
    a[k] //= foo
    continue
  else:
    print(0)
    exit()
ans = 0

import math
lcm = a.pop()
for k in range(1, N):
  b = a.pop()
  lcm = lcm * b // math.gcd(lcm, b)
  if lcm* foo > M:
    print(0)
    exit()
lcm *= foo
ans = int((M / lcm -1)//2 + 1)
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
a = list(map(int, input().split()))
for k in range(N):
  a[k] //= 2

foo = 1
while a[0]%2 == 0:
  foo *= 2
  a[0] //= 2
for k in range(1, N):
  if a[k] % foo == 0 and a[k]%(2*foo) !=0:
    a[k] //= foo
    continue
  else:
    print(0)
    exit()
ans = 0

import math
lcm = a.pop()
for k in range(1, N):
  b = a.pop()
  lcm = lcm * b // math.gcd(lcm, b)
  if lcm* foo > M:
    print(0)
    exit()
lcm *= foo
ans = int((M / lcm -1)//2 + 1)
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
mod=10**9+7
dp=[0]*(n+2)
dp[n]=1
for i in range(n-1,-1,-1):
    if i in a:
        dp[i]=0
    else:
        dp[i]=(dp[i+1]%mod+dp[i+2]%mod)%mod
print(dp[0])


### FIXED CODE ###

n,m=map(int,input().split())
a=set(int(input()) for _ in range(m))
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
    if i in a:
        dp[i]=0
print(dp[n])
### BUGGY CODE ###

def sole():
    import sys
    N, M = map(int, input().split())
    A = [int(a) for a in input().split()]
    B = [int(b) for b in input().split()]

    A.sort(reverse=True)
    B.sort(reverse=True)

    if len(set(A))!=len(A) or len(set(B))!=len(B):
        print(0)
        sys.exit()

    ans = 1
    rows, columna = 0,0
    mod = 10**9+7
    for x in range(N*M, 0, -1):

        if x in A and x in B:
            rows += 1
            columna += 1

        elif x in A and not x in B:
            rows += 1
            ans = ans * (columna)

        elif x in B and not x in A:
            columna += 1
            ans = ans *(rows)

        else:
            ans = ans * (rows * columna -(N*M-x))

        ans %= mod

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



if __name__ == '__main__':
    sole()


### FIXED CODE ###

def solve():
    MOD = 10 ** 9 + 7
    N, M = map(int, input().split())
    A = set(map(int, input().split()))
    B = set(map(int, input().split()))
    
    row, columun = 0, 0
    ans = 1
    for i in range(N * M, 0, -1):
        in_A = i in A
        in_B = i in B
        if in_A and in_B:
            row += 1
            columun += 1
        elif in_A:
            row += 1
            ans *= columun
        elif in_B:
            columun += 1
            ans *= row
        else:
            ans *= row * columun - (N * M - i)
        ans %= MOD
    print(ans)


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

n = int(input())
h = list(map(int, input().split()))
def triangle(n,h):
    x = 0
    for i in range(0,n-2):
        for j in range(i+1,n-1):
            for k in range(j+1, n):
                if h[i] < h[j] + h[k] and h[j] < h[i] + h[k] and h[k] < h[j] + h[i]:
                    x = x + 1
    return x
print(triangle(n,h))

### FIXED CODE ###

import bisect
N = int(input())
#ソートしておく
L = sorted(list(map(int, input().split())))
ans = 0
 
#短い2辺を総当たりで選択
for i in range(N - 2):
  for j in range(i + 1, N - 1):
    #小さい順に並べた時の成立条件
    # l1 + l2 > l3
    l12 = L[i] + L[j]
    #l2の隣から　l12以下のところまで全部が対象、成立しない場合
    #ans += max(bisect.bisect_left(L, l12) - j - 1, 0)
    ans += bisect.bisect_left(L, l12) - j - 1
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
As = list(map(int, input().split()))
M = [[] for i in range(200001)]
for i, a in enumerate(As):
  M[a].append(i)
S = []
for i, a in enumerate(As):
  l = M[a]
  index = l.index(i)
  if index+1 == len(l):
    n = l[0]+N
  else:
    n = l[index+1]
  S.append(n+1-i)
#print(S)
p = 0
while True:
  p = p+S[p%N]
  if p%N == 0:
    break
count = p//N
#print(count)
K = K%count
#print(K)
p = 0
while True:
  q = p+S[p%N]
  if q > N*K:
    break
  p = q
index = p%N
#print(index, As[index:N])
s = []
for a in As[index:N]:
  i = -1
  for j in range(len(s)):
    if s[j] == a:
      i = j
  if i < 0:
    s.append(a)
  else:
    s = s[0:i]
print(" ".join(map(str, s)))


### FIXED CODE ###

N, K = map(int, input().split())
As = list(map(int, input().split()))
M = [[] for i in range(200001)]
for i, a in enumerate(As):
  M[a].append(i)
S = []
for i, a in enumerate(As):
  l = M[a]
  index = l.index(i)
  if index+1 == len(l):
    n = l[0]+N
  else:
    n = l[index+1]
  S.append(n+1-i)
#print(S)
p = 0
while True:
  p = p+S[p%N]
  if p%N == 0:
    break
count = p//N
#print(count)
K = K%count
#print(K)
p = 0
s = []
while p < N*K:
  q = p+S[p%N]
  if q > N*K:
    s.append(As[p%N])
    p = p+1
  else:
    p = q
print(" ".join(map(str, s)))
### BUGGY CODE ###

def solve(a, b):
    pdp = {a[0]:0}
    ndp = {}
    for ai in a[1:] + [0]:
        for k, v in pdp.items():
            for bi in b:
                vb = v + st(k, bi)
                kb = k & (65535 ^ bi) | ai
                try:
                    ndp[kb] = max(ndp[kb], vb)
                except KeyError:
                    ndp[kb] = vb
        pdp, ndp = ndp, {}
        
    return max(pdp.values())

def st(i, j):
    return bin(i).count('1') - bin(i & (65535 ^ j)).count('1')

import sys
f = sys.stdin

while True:
    n, c = map(int, f.readline().split())
    if n == c == 0:
        break
    a = [int(''.join(f.readline().split()), 2) for i in range(n)]
    b = [int(''.join(f.readline().split()), 2) for i in range(c)]
    print(solve(a, b))

### FIXED CODE ###

bitcount = [bin(i).count('1') for i in range(0x10000)]
def solve(a, b):
    global bitcount
    b = [65535 ^ bi for bi in b]
    pdp = {a[0]:0}
    ndp = {}
    for ai in a[1:] + [0]:
        for k, v in pdp.items():
            v += bitcount[k]
            for bi in b:
                bi &= k
                vb = v - bitcount[bi]
                bi |= ai
                try:
                    if ndp[bi] < vb:
                        ndp[bi] = vb
                except KeyError:
                    ndp[bi] = vb
        pdp, ndp = ndp, {}
        
    return max(pdp.values())

import sys
f = sys.stdin


while True:
    n, c = map(int, f.readline().split())
    if n == c == 0:
        break
    a = [int(''.join(f.readline().split()), 2) for i in range(n)]
    b = [int(''.join(f.readline().split()), 2) for i in range(c)]
    print(solve(a, b))
### BUGGY CODE ###

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

bridges = [list(map(int,input().split())) for i in range(M)]

roots = list(range(0,N))
a =int(N*(N-1)/2)
ans = [a]

for i in range(0,M)[::-1]:
    island0, island1 = bridges[i][0],bridges[i][1]

    if roots[island0-1] == roots[island1-1]:
        ans.append(int(a))
        continue

    num_island0 = roots.count(roots[island0-1])
    num_island1 = roots.count(roots[island1-1])
    num_island01 = num_island0 + num_island1
    if roots[island1-1] != island1: # merge
        min_i = min(roots[island0-1],roots[island1-1])
        max_i = max(roots[island0-1],roots[island1-1])
        roots = [min_i if root==max_i else root for root in roots]        
    else: # つなげる
        roots[island1-1] = roots[island0-1]
    
    a -= (num_island01*(num_island01-1) - num_island0*(num_island0-1) - num_island1 *(num_island1-1))/2
    ans.append(int(a))

[print(ans[i]) for i in range(M)[::-1]]


### FIXED CODE ###


class UnionFindTree():
    # Union find tree
    # 2つの効率化　経路圧縮、ランク
    # つなげることはできるか分離することはできないので、木をつなげる方向に利用する
    # 
    def __init__(self, node_size):
        # node_num: 全体のノード数
        # parent: ノードがrootなら-1、親がいれば親の番号を入れる
        # size:
        # rank:  
        self.parent =[-1] * node_size 
        self.size = [1] * node_size
        self.rank = [1] * node_size
    
    def find_root(self,node):
        # node属する木のrootを探す
        # たどった経路に含まれるnodeの親をrootにつなぎ替える
        if self.parent[node] == -1:             # 自身がrootの場合
            root = node
        else:                                   # 自身がrootでない場合
            root = self.find_root(self.parent[node]) # 再帰的にrootを探す
            self.parent[node] = root            # たどった経路に含まれるnodeの親をrootにつなぎ替える(経路圧縮)
        return root

    def unite(self,node0, node1):
        # node0とnode1が含まれる木を結合する
        
        #node0 node1のrootを求める
        root0 = self.find_root(node0) 
        root1 = self.find_root(node1)

        if root0 != root1:
            # rankを比較しrankが小さい方の木を大きい方の木のrootにつなげる
            # rank is sameのときのみrankが増える
            rank0 = self.rank[root0]
            rank1 = self.rank[root1]

            if rank0 == rank1: # rank is same
                self.parent[root1] = root0
                self.size[root0] += self.size[root1]
                self.rank[root0] += 1
            elif rank0 > rank1:
                self.parent[root1] = root0
                self.size[root0] += self.size[root1]
            else:
                self.parent[root0] = root1
                self.size[root1] += self.size[root0]

            


N,M = map(int,input().split())
bridges = [list(map(int,input().split())) for i in range(M)]

UFT = UnionFindTree(N)

a = int(N*(N-1)/2) # 不便さ
ans = [a]

for i in range(1,M)[::-1]:
    island0_num, island1_num = bridges[i][0]-1, bridges[i][1]-1 
    root0 = UFT.find_root(island0_num)
    root1 = UFT.find_root(island1_num)
    if root0 != root1:
        size0 =  UFT.size[root0]
        size1 =  UFT.size[root1]
        UFT.unite(island0_num,island1_num)
        a -= size0 * size1
    ans.append(int(a))

[print(ans[i]) for i in range(M)[::-1]]
### BUGGY CODE ###

#import numpy

N,X,Y=map(int,input().split())

L=[[i+1 for i in range(j+1)][::-1]+[0]*(N-1-j) for j in range(N-1)]
#print(L)

for i in range(len(L)):
    L[i]=[0]+L[i]+[0]
L.append([0]*(N+2))
L.insert(0,[0]*(N+2))
L.insert(0,[0]*(N+2))

#print(L)

H=[i+1 for i in range(N-1)][::-1]
#print(L)
#print(H)

L[Y][X]=1
task=[(Y,X,1)]
while len(task)>0:
    P=task.pop()
    y,x,c=P[0],P[1],P[2]
    if y<0 or x<0 or y>N or x>N:
        continue
    if L[y+1][x]>=c+1:
        L[y+1][x]=c+1
        task.append((y+1,x,c+1))
    if L[y-1][x]>=c+1:
        L[y-1][x]=c+1
        task.append((y-1,x,c+1))
    if L[y][x+1]>=c+1:
        L[y][x+1]=c+1
        task.append((y,x+1,c+1))
    if L[y][x-1]>=c+1:
        L[y][x-1]=c+1
        task.append((y,x-1,c+1))
    #print(y,x,c)
    #print(numpy.array(L))

LL=[]
for i in range(len(L)):
    LL+=L[i]
#LL.sort()
#print(LL)

import collections
D=collections.Counter(LL)
d=list(D.values())
d.pop(0)
d+=[0]*(max(N-len(d)-1,0))

for i in d:
    print(i)



### FIXED CODE ###

N,X,Y=map(int,input().split())
ans=[0]*N
X-=1
Y-=1

for i in range(N-1):
    for j in range(i+1,N):
        ans[min(j-i,abs(j-Y)+abs(i-X)+1)]+=1

ans.pop(0)
for i in ans:
    print(i)
### BUGGY CODE ###

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

while(m>0):
    a[a.index(max(a))] //=2
    m-=1
print(sum(a))

### FIXED CODE ###

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

from heapq import heappush, heappop
hq=[]

for a_val in a:
    # heappopで最も小さい値が取り出されるため、(-1)をかけて入れる
    heappush(hq, -a_val)
for _ in range(m):
    heappush(hq, -(heappop(hq)//(-2)))
print(-sum(hq))
### BUGGY CODE ###

from collections import Counter

n = int(input())
S = [input() for _ in range(n)]
cnt = 0

for i in range(n) : 
    for j in range(i) : 
        if Counter(S[i]) == Counter(S[j]) : 
            cnt += 1

print(cnt)

### FIXED CODE ###

from collections import Counter

n = int(input())
S = [input() for _ in range(n)]
ans = 0

ctr = Counter()

for s in S : 
    a = ''.join(sorted(list(s)))
    if ctr[a] != 0 : 
        ans += ctr[a]
    ctr[a] += 1
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
def gcd(a,b):
    if b==0:return a
    return gcd(b,a%b)

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


g_max = 1
for i in range(n):
    d = a_l.pop(0)

    if n-1==1:
        g = a_l[0]
    else:
        g = gcd(a_l[0], a_l[1])
        if n-1==2:g=g
        else:
            for j in range(2,n-1):
                g=gcd(g,a_l[j])
    # print(g)
    g_max = max(g, g_max)
    # print(d)
    a_l.append(d)

print(g_max)

### FIXED CODE ###

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

# 最大公約数
def gcd(a,b):
    if b==0:return a
    return gcd(b,a%b)

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

# 累積GCD
left = [0]*(n+1)
right = [0]*(n+1)
for i in range(n):
    left[i+1] = gcd(left[i], a[i])
for i in reversed(range(n)):
    right[i] = gcd(right[i+1], a[i])

# print(left)
# print(right)

# 集計
ans = 0
for i in range(n):
    l = left[i]
    r = right[i+1]
    ans = max(ans, gcd(l, r))

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

n, m = map(int, input().split())
ab = []
for i in range(n):
  t = [int(inp) for inp in input().split()]
  if t[0] <= m:
    ab.append(t)

ab.sort(key = lambda x: x[0])
ans = 0
for i in range(1, m+1):
  ma = [0,0]
  for t in ab:
    if t[0] > i:
      break
    if t[1] > ma[1]:
      ma = t
  if ma != [0, 0]:
    ans += ma[1]
    ab.remove(ma)
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
ab = [[] for _ in range(m+1)]
for i in range(n):
  t = [int(inp) for inp in input().split()]
  if t[0] <= m:
    ab[t[0]].append(-t[1])
ans = 0
import heapq
h = ab[1]
heapq.heapify(h)
for i in range(1, m+1):
  if len(h) > 0:
    ans += heapq.heappop(h)
  if i != m:
    for t in ab[i+1]:
      heapq.heappush(h, t)
print(-ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

sum_odd = sum(a[1::2])
sum_eve = sum(a[::2])

count = 0
sum_a  = 0
if sum_odd >= sum_eve:#奇数の和がおおきいので、偶数　0,2,4...を負にする
    for i in range(n):
        
        sum_a = sum_a + a[i]
        #print('sum_a : ' +str(sum_a))
        #print('sum_a *(-1)**(i+1) : '+str(sum_a *(-1)**(i+1)))
        if sum_a *(-1)**(i+1) < 1:
            while sum_a*(-1)**(i+1) <1:
                count += 1
                a[i] += 1*(-1)**(i+1)
                sum_a += 1*(-1)**(i+1)
else:
    for i in range(n):
       
        sum_a = sum_a + a[i]
        if sum_a *(-1)**(i) < 1:
            while sum_a*(-1)**(i) <1:
                count += 1
                a[i] += 1*(-1)**(i)
                sum_a += 1*(-1)**(i)
print(count)


### FIXED CODE ###


import sys
import copy
input = sys.stdin.readline

n = int(input())
a = list(map(int,input().split()))
b = copy.copy(a)
sum_odd = sum(a[1::2])
sum_eve = sum(a[::2])

ans = 0
sum_a  = 0
for i in range(n):
        
    sum_a = sum_a + a[i]
        
    if sum_a *(-1)**(i+1) < 1:
        kari = 1-sum_a *(-1)**(i+1)
        a[i] += 1*(-1)**(i+1) *(kari)
        sum_a += 1*(-1)**(i+1) *(kari)
            
        ans = ans + abs(kari)
            
ans1 = 0
sum_b = 0
             
for i in range(n):
       
    sum_b = sum_b + b[i]
    if sum_b *(-1)**(i) < 1:
        kari = (1-sum_b *(-1)**(i))
        b[i] += 1*(-1)**(i) * kari
        sum_b += 1*(-1)**(i) * kari

        ans1 = ans1 + abs(kari)


print(min(ans,ans1))
### BUGGY CODE ###

R,C,k=map(int,input().split())
rcv = [[0 for _ in range(C+1)] for _ in range(R+1)]
for i in range(k):
  r,c,v = map(int,input().split())
  rcv[r][c] = v
# dp: 各場所までの合計の最大値
dp = [[[0 for _ in range(4)] for _ in range(C+1)] for _ in range(R+1)]
dp[1][1][1] = rcv[1][1]
#print(dp[1][1][1])
for r in range(1,R+1):
  for c in range(1,C+1):
    dp[r][c][1] = max(dp[r][c][1],dp[r][c-1][0]+rcv[r][c],dp[r][c-1][1])
    dp[r][c][2] = max(dp[r][c-1][1]+rcv[r][c],dp[r][c-1][2])
    dp[r][c][3] = max(dp[r][c-1][2]+rcv[r][c],dp[r][c-1][3])
    
    if r < R:
      dp[r+1][c][0] = max(dp[r][c])
      dp[r+1][c][1] = max(dp[r][c])+rcv[r+1][c]
print(max(dp[R][C]))
#print(*dp)

### FIXED CODE ###

R,C,k=map(int,input().split())
rcv = [[0 for _ in range(C+1)] for _ in range(R+1)]
for i in range(k):
  r,c,v = map(int,input().split())
  rcv[r][c] = v
# dp: 各場所までの合計の最大値
dp0=[[0 for _ in range(C+1)] for _ in range(R+1)]
dp1=[[0 for _ in range(C+1)] for _ in range(R+1)]
dp2=[[0 for _ in range(C+1)] for _ in range(R+1)]
dp3=[[0 for _ in range(C+1)] for _ in range(R+1)]
dp1[1][1] = rcv[1][1]
for r in range(1,R+1):
  for c in range(1,C+1):
    dp1[r][c] = max(dp0[r][c]+rcv[r][c],dp0[r][c-1]+rcv[r][c],dp1[r][c-1])
    dp2[r][c] = max(dp1[r][c-1]+rcv[r][c],dp2[r][c-1])
    dp3[r][c] = max(dp2[r][c-1]+rcv[r][c],dp3[r][c-1])
    
    if r < R:
      dp0[r+1][c] = max(dp0[r][c],dp1[r][c],dp2[r][c],dp3[r][c])
print(max(dp0[R][C],dp1[R][C],dp2[R][C],dp3[R][C]))
### BUGGY CODE ###

N, W = map(int, input().split())
wv = []
for _ in range(N):
    wv.append(list(map(int, input().split())))
INF = 10**10
v_max = 10**5
dp = [[INF]*(v_max+1) for _ in range(N+1)]
dp[0][0] = 0
ans = 0
for i in range(N):
    for j in range(v_max+1):
        if j >= wv[i][1]:
            dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]]+wv[i][0])
            #print(i, j, dp[i+1][j], dp[i][j], wv[i][0])
        else:
            dp[i+1][j] = dp[i][j]
        if dp[i+1][j] <= W:
            ans = j
print(ans)

### FIXED CODE ###

N, W = map(int, input().split())
wv = []
for _ in range(N):
    wv.append(list(map(int, input().split())))
INF = 10**10
v_max = 10**5
dp = [[INF]*(v_max+1) for _ in range(N+1)]
dp[0][0] = 0
ans = 0
for i in range(N):
    for j in range(v_max+1):
        if j >= wv[i][1]:
            dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]]+wv[i][0])
            #print(i, j, dp[i+1][j], dp[i][j], wv[i][0])
        else:
            dp[i+1][j] = dp[i][j]
        if i+1 == N and dp[i+1][j] <= W:
            ans = j
print(ans)
### BUGGY CODE ###

import collections
N = int(input())
A = list(map(int,input().split()))
ans = 0
for k in range(N):
    buf = A[k]
    ans = 0
    A[k] = 0
    c = collections.Counter(A)
    for l in c.values():
        ans = ans + l*(l-1)/2
    print(int(ans))
    A[k] = buf


### FIXED CODE ###

import collections
N = int(input())
A = list(map(int,input().split()))
ans = 0
c = collections.Counter(A)
for l in c.values():
    ans = ans + l*(l-1)/2
for k in A:
    print(int(ans-(c[k]-1)))
### BUGGY CODE ###

def psolve(k, Xs, N):
    arr = [[]]
    i = Xs[0]
    for x in Xs:
        if x <= i + k:
            arr[-1].append(x)
        else:
            arr.append([])
            arr[-1].append(x)
            i = x
            if len(arr) > N:
                break

    if len(arr) <= N:
        ans = sum([max(a) - min(a) for a in arr])
        return ans
    else:
        return 10 ** 9


def solve(N, M, Xs):
    Xs = sorted(Xs)
    ans = 10 ** 9
    for k in range(0, (Xs[-1] - Xs[0]) + 1):
        nans = psolve(k, Xs, N)
        ans = min(ans, nans)
    return ans


if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    Xs = list(map(int, input().split(" ")))
    print(solve(N, M, Xs))


### FIXED CODE ###


def solve(N, M, Xs):
    Xs = sorted(Xs)
    diffs = sorted([Xs[i+1] - Xs[i] for i in range(M-1)], reverse=True)
    return Xs[-1] - Xs[0] - sum(diffs[:N-1])


if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    Xs = list(map(int, input().split(" ")))
    print(solve(N, M, Xs))