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

import copy
h,w,k=map(int,input().split())
S=[]
for i in range(h):
    s=int(input(),2)
    S.append(s)
ans=100000
for i in range(2**(h-1)):
    now=0
    S1=copy.copy(S)
    cnt=0
    T=[]
    y=0
    for j in range(h-1):
        if (i>>j)&1:
            y+=1
    C=[0]*(y+1)
    for x in range(w):
        T=[]
        for j in range(h):        
            cnt+=S1[j]&1
            S1[j]=S1[j]>>1
            if (i>>j)&1: #横の区切り判定
                T.append(cnt)
                cnt=0
            if j==h-1:
                T.append(cnt)
                cnt=0
        for j in range(len(C)):
            if C[j]+T[j]>k:
                now+=1
                C=T
                break
            else:
                C[j]+=T[j]
    ans=min(ans,now+y)
print(ans)

### FIXED CODE ###

h,w,k=map(int,input().split())
S=[]
for i in range(h):
    s=int(input(),2)
    S.append(s)
ans=h+w-2
for i in range(2**(h-1)):
    flag=False
    now=0 #区切った数
    cnt=0 #1の数
    y=0
    for j in range(h-1):
        if (i>>j)&1:
            y+=1
    C=[0]*(y+1) #1の数保存配列
    for x in range(w):
        T=[] #現在の列での1の数保存配列
        for j in range(h):      
            cnt+=(S[j]>>x)&1
            if cnt>k:
                flag=True
                break
            if (i>>j)&1: #横の区切り判定
                T.append(cnt)
                cnt=0
            if j==h-1: #最後の列
                T.append(cnt)
                cnt=0
        if flag:
            break
        for j in range(len(C)): #それぞれのブロックに対して
            if C[j]+T[j]>k:
                now+=1
                C=T
                break
            else:
                C[j]+=T[j]
    if flag:
        continue
    ans=min(ans,now+y)
print(ans)
### BUGGY CODE ###

a, b, k = map(int, input().split())
for i in range(k):
  if a >= 1:
    a -= 1
  elif b >= 1:
    for j in range(k-i):
      b -= 1
      if b < 1:
        break
    break
  else:
    break
print("{} {}".format(a, b))

### FIXED CODE ###

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

if k != 0:
    diva = a / k
    if diva >= 1:
        a -= k
    else:
        k -= a
        a = 0
        b -= k
        if b < 0:
            b = 0
print("{} {}".format(a, b))
### BUGGY CODE ###

string=str(input())
Q=int(input())
def func1(s):
    s=s[::-1]
    return s
def func2(s,F,C):
    if F=="1":
        s=C+s
        return s
    if F=="2":
        s=s+C
        return s

            
for i in range(Q):
    Input=list(map(str,input().split()))
    if Input[0]=='1':
        string=func1(string)
        
    elif Input[0]=='2':
        string=func2(string,Input[1],Input[2])

print(string)            
        
        

### FIXED CODE ###

S = str(input())
Q = int(input())
 
hanten = 0
front = ""
end = ""
 
for i in range(Q):
    query=list(map(str,input().split()))
    if query[0]=="1":
        hanten+=1
        hanten=hanten%2
    else:
        if query[1]=="1":
            if hanten==0:
                front=query[2]+front
            else:
                end=end+query[2]
        else:
            if hanten==0:
                end=end+query[2]
            else:
                front=query[2]+front
ans=front+S+end
if hanten==1:
    ans=ans[::-1]
print(ans)
### BUGGY CODE ###

import math
n=int(input())
lim=math.ceil(math.sqrt(n))

for i in range(lim, n+1):
  if n%i==0:
    print(len(str(i)))
    exit()

### FIXED CODE ###

n=int(input())
l=int((n**0.5))+1
ans=n
for i in range(1, l+1):
  if n%i==0:
    ans=min(ans, len(str(n//i)))
print(ans)
### BUGGY CODE ###

import sys


sys.setrecursionlimit(10000)


def my_search(l, low, high, t):
    n = (low+high)//2
    if t > l[n]:
        low = n
    else:
        high = n
    if high == low + 1:
        return low
    else:
        return my_search(l, low, high, t)

a,b,q = [int(_) for _ in input().split()]
s_l = [-float('inf')]
t_l = [-float('inf')]
x_l = []
for i in range(a):
    s_l.append(int(input()))
s_l.append(float('inf'))
for i in range(b):
    t_l.append(int(input()))
t_l.append(float('inf'))
for i in range(q):
    x_l.append(int(input()))
for i in range(q):
    x = x_l[i]
    s1_id = my_search(s_l, 0, len(s_l)-1, x)
    s2_id = s1_id + 1
    s1 = s_l[s1_id]
    s2 = s_l[s2_id]
    t1_id = my_search(t_l, 0, len(t_l)-1, x)
    t2_id = t1_id + 1
    t1 = t_l[t1_id]
    t2 = t_l[t2_id]
    res = float('inf')
    for s in [s1,s2]:
        for t in [t1,t2]:
            d1, d2 = abs(s-x) + abs(t-s), abs(t-x) + abs(s-t)
            res = min(res, d1, d2)
    print(res)


### FIXED CODE ###

import bisect


a,b,q = [int(_) for _ in input().split()]
s_l = [-float('inf')]
t_l = [-float('inf')]
x_l = []
for i in range(a):
    s_l.append(int(input()))
s_l.append(float('inf'))
for i in range(b):
    t_l.append(int(input()))
t_l.append(float('inf'))
for i in range(q):
    x_l.append(int(input()))
for i in range(q):
    x = x_l[i]
    s1_id = bisect.bisect_left(s_l, x) - 1 
    s2_id = s1_id + 1
    s1 = s_l[s1_id]
    s2 = s_l[s2_id]
    t1_id = bisect.bisect_left(t_l, x) - 1 
    t2_id = t1_id + 1
    t1 = t_l[t1_id]
    t2 = t_l[t2_id]
    res = float('inf')
    for s in [s1,s2]:
        for t in [t1,t2]:
            d1, d2 = abs(s-x) + abs(t-s), abs(t-x) + abs(s-t)
            res = min(res, d1, d2)
    print(res)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[[0]*(k+1) for _ in range(n+1)]
mod=1000000007
#i人目までに0個配る方法は1通り
for i in range(n+1):
  dp[i][0]=1

def main():
  for i in range(1,n+1):
    for j in range(1,k+1):
      tmp=dp[i - 1][j] + dp[i][j - 1]
      if tmp>=mod:
        tmp%=mod
      dp[i][j]=tmp
      if j-a[i-1]-1>=0:
        tmp=dp[i][j]-dp[i-1][j-a[i-1]-1]
        if tmp>=mod:
          tmp%=mod
        dp[i][j]=tmp
    #print(dp)   
  print(dp[n][k]%mod)
main()

### FIXED CODE ###

import sys
from itertools import accumulate

def main():
  input=sys.stdin.readline
  n,k=map(int,input().split())
  A=list(map(int,input().split()))
  mod=10**9+7
  dp=[0]*(k+1)
  dp[0]=1
  for a in A:
    dp=list(accumulate(dp))
    #print("accumulated",dp)
    for j,d in enumerate(dp[:k-a],start=a+1):
      dp[j]-=d
    dp=[dpi%mod for dpi in dp]
    #print(dp)
  print(dp[k])
"""
def main():
  dp=[[0]*(k+1) for _ in range(n+1)]
  mod=1000000007
  #i人目までに0個配る方法は1通り
  #for i in range(n+1):
  #  dp[i][0]=1
  for i in range(0,n+1):
    for j in range(0,k+1):
      if i==0 and j==0:
        dp[i][j]=1
        break
      if j==0:
        dp[i][j]=1
        continue
      tmp=dp[i - 1][j] + dp[i][j - 1]
      if tmp>=mod:
        tmp%=mod
      dp[i][j]=tmp
      if j-a[i-1]-1>=0:
        tmp=dp[i][j]-dp[i-1][j-a[i-1]-1]
        if tmp>=mod:
          tmp%=mod
        dp[i][j]=tmp
    #print(dp)   
  print(dp[n][k])"""
main()
### BUGGY CODE ###

import math
import numpy as np

S = list(input())
N = len(S)+1
if N%2==0:
    D = np.zeros(N)
else:
    D = np.zeros(N-1)
   
nc = 1
cur = S[0]
curi = 0
for i in range(1,N-1):
    if S[i]==cur:
        nc += 1
    else:
        D[curi] = nc
        cur = S[i]
        curi += 1
        nc = 1
D[curi] = nc
D=D.reshape([-1,2])
Asum = 0
for d in D:
    if d.all == 0:
        break
    else:
        a1 = max(np.absolute(d))
        a2 = min(np.absolute(d))
        Asum += int(np.sum(np.arange(0,a1+1)) + np.sum(np.arange(0,a2)))

print(Asum)

### FIXED CODE ###

import math
import numpy as np

# N,K = map(int,input().split())
# A = np.sort(list(map(int,input().split())))
# F = np.sort(list(map(int,input().split())))[::-1]
#         if np.sum(AF[AF>0]) > K: 

S = list(input())
if S[0]=='>':
    S = ['<']+S
if S[-1]=='<':
    S = S+['>']

N=len(S)
D=np.zeros(N)
nc = 1
cur = S[0]
curi = 0
for i in range(1,N):
    if S[i]==cur:
        nc += 1
    else:
        D[curi] = nc
        cur = S[i]
        curi += 1
        nc = 1
D[curi] = nc
D = D[D>0]
D=D.reshape([-1,2])
Asum = 0
for d in D:
    a1 = max(d)
    a2 = min(d)
    Asum += int((a1+1)*a1/2 + a2*(a2-1)/2)

print(Asum)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = [0]*N

if N ==1:
    ans[0] = 1
else:
    for X in range(N):
        for i in range(N):
            if abs(X-A[i])<=1:
                ans[X]+=1

print(max(ans))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = [0]*(10**5+3)

for i in range(N):
    ans[A[i]-1] +=1
    ans[A[i]] +=1
    ans[A[i]+1] +=1

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

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

base_2_cnt = [0]*60 
for a in al:
    for i in range(60):
        if ((a >> i) & 1): base_2_cnt[i] += 1

ans = 0
for i in range(60):
    base_01_comb = base_2_cnt[i] * (n-base_2_cnt[i])
    ans += base_01_comb * (2**i)

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

### FIXED CODE ###

def main():
    MOD = 10**9+7
    n = int(input())
    al = list(map(int, input().split()))

    base_2_cnt = [0]*60 
    for a in al:
        for i in range(60):
            if ((a >> i) & 1): base_2_cnt[i] += 1

    ans = 0
    curr_2 = 1
    for i in range(60):
        base_01_comb = base_2_cnt[i] * (n-base_2_cnt[i])
        ans += base_01_comb * curr_2
        ans %= MOD
        curr_2*=2
        curr_2%=MOD

    print(ans%MOD)

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

from functools import lru_cache
N,W=map(int,input().split())

@lru_cache(None)
def knapsack_recursive(capacity, currentIndex):
    if capacity <= 0 or currentIndex >= len(profits): return 0

    profit = 0
    if weights[currentIndex] <= capacity:
        profit = profits[currentIndex] + knapsack_recursive(capacity - weights[currentIndex], currentIndex + 1)
    tmp = knapsack_recursive(capacity, currentIndex + 1)
    if tmp > profit:
        profit = tmp  
    return profit
  
def main():

    res = knapsack_recursive(W, 0)

    print(res)
if __name__ == "__main__":
    weights,profits = [0]*N, [0]*N
    for i in range(N):
        weights[i],profits[i] = map(int,input().split())
    main()

### FIXED CODE ###

def main():
  n, w = [int(e) for e in input().split()]
  t = [-1 for i in range(w + 1)]
  t[w] = 0
  for _ in range(n):
    nw, nv = [int(e) for e in input().split()]
    for i in range(nw, w + 1):
      if t[i] == -1:
        continue
      if t[i - nw] < t[i] + nv:
        t[i - nw] = t[i] + nv
  print(max(t))
main()
### BUGGY CODE ###

import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)

@lru_cache(maxsize=1000)
def dfs(v,p,d):
    for i, j in tree[v]:
        if i != p:
            depth[i] = d + j
            dfs(i,v,d+j)

N = int(input())

tree = [[] for _ in range(N)]

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

Q, K = map(int, input().split())

depth = [0 for i in range(N)]
depth[K-1] = 0

dfs(K-1,-1,0)

for _ in range(Q):
    x, y = map(int, input().split())
    print(depth[x-1] + depth[y-1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
def dfs(v,p,d):
    for i, j in tree[v]:
        if i != p:
            depth[i] = d + j
            dfs(i,v,d+j)

N = int(input())

tree = [[] for _ in range(N)]

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

Q, K = map(int, input().split())

depth = [0 for i in range(N)]
depth[K-1] = 0

dfs(K-1,-1,0)

for _ in range(Q):
    x, y = map(int, input().split())
    print(depth[x-1] + depth[y-1])
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
cnt = 0
ans = []

for i in range(n):
    cnt += 1
    ind = a.index(cnt)
    ans.append(str(ind + 1))

print(" ".join(ans))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
cnt = 0
ans = [0] * n

for i in a:
    cnt += 1
    ans[i-1] = str(cnt)

print(" ".join(ans))
### BUGGY CODE ###

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

ans=[]

for i in range(n):
    ans.append(a.index(i+1)+1)
print(*ans)




### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
ll=[]
for i in range(n):
    ll.append([l[i],i+1])
    
ll=sorted(ll)
ans=[]
for j in range(n):
    ans.append(ll[j][1])

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

N,K,Q=map(int,input().split())
ls1 = [int(input()) for i in range(Q)]
ls_ = [K]*N
for i in ls1:
  ls_ = list(map(lambda x: x-1,ls_))
  ls_[i-1]+=1
for i in ls_:
  if i <=0:
    print("No")
  else:
    print("Yes")

### FIXED CODE ###

N,K,Q=map(int,input().split())
ls_ = [K]*N
for i in range(Q):
  ls_[int(input())-1]+=1
ls__ = ["No" if i <= Q else "Yes" for i in ls_]
string = "\n".join(ls__)
print(string)
### BUGGY CODE ###

import bisect
N=int(input())
ue=list(map(int,input().split()))
naka=list(map(int,input().split()))
sita=list(map(int,input().split()))
ue.sort(),sita.sort(),naka.sort()
count=0
stop=[0]*N
for i in range(N):
    k=naka[i]
    stop_index=bisect.bisect_right(sita,k)
    if stop_index!=N:
        stop[i]=N-stop_index
for i in range(N):
    k=ue[i]
    a=bisect.bisect_right(naka,k)
    if a!=N:
        count+=sum(stop[a:N])
print(count)


### FIXED CODE ###

import bisect
N=int(input())
ue=list(map(int,input().split()))
naka=list(map(int,input().split()))
sita=list(map(int,input().split()))
sita.sort(),naka.sort(),ue.sort()
count2=[0]*N
count1=[0]*N
for i in range(N):
    m = naka[i]
    k=naka[i]
    small=bisect.bisect_left(ue,k)
    count1[i]=small
    big = bisect.bisect_right(sita, m)
    count2[i]=N-big
ans=0
for i in range(N):
    ans+=count1[i]*count2[i]
print(ans)
### BUGGY CODE ###

import sys
from collections import deque

n,m = map(int, input().split())
adj_list = [[] for i in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    adj_list[l-1].append((r-1, d))
    adj_list[r-1].append((l-1, -d))
def search(start, dist_all):
    q = deque([[start]])
    q_d = deque([0])
    while(len(q) > 0):
        path = q.popleft()
        dist = q_d.popleft()
        w = path[len(path) - 1]
        for x in adj_list[w]:
            if x[0] not in path:
                new_path = path[:]
                new_path.append(x[0])
                if dist_all[x[0]] is None:
                    dist_all[x[0]] = dist + x[1]
                elif dist_all[x[0]] != dist + x[1]:
                    return False
                q.append(new_path)
                q_d.append(dist + x[1])
    return True
dist_all = [None for i in range(n)]
for i in range(n):
    if dist_all[i] is None:
        if not search(i, dist_all):
            print('No')
            exit(0)
print('Yes')

### FIXED CODE ###

import sys
from collections import deque

n,m = map(int, input().split())
adj_list = [[] for i in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    adj_list[l-1].append((r-1, d))
    adj_list[r-1].append((l-1, -d))
def search(start, dist_all):
    q = deque([start])
    dist_all[i] = 0
    while(len(q) > 0):
        w = q.popleft()
        for x in adj_list[w]:
            if dist_all[x[0]] is None:
                dist_all[x[0]] = dist_all[w] + x[1]
                q.append(x[0])
            elif dist_all[x[0]] != dist_all[w] + x[1]:
                return False
    return True
dist_all = [None for i in range(n)]
for i in range(n):
    if dist_all[i] is None:
        if not search(i, dist_all):
            print('No')
            exit(0)
print('Yes')
### BUGGY CODE ###

from collections import deque

N,M = map(int, input().split())
N = 2 * M + 1

lis = [i for i in range(1,N+1)]
if M % 2 == 0:
    lis1 = lis[:N//2+1]
    lis2 = lis[N//2+1:]
    for i in range(M//2):
        a = lis1.pop(0)
        b = lis1.pop()
        print(a,b)
    for i in range(M//2):
        a = lis2.pop(0)
        b = lis2.pop()
        print(a,b)
else:
    lis1 = lis[:N//2+1]
    lis2 = lis[N//2+1:]
    for i in range(M//2+1):
        a = lis1.pop(0)
        b = lis1.pop()
        print(a,b)
    for i in range(M//2):
        a = lis2.pop(0)
        b = lis2.pop()
        print(a, b)



### FIXED CODE ###

from collections import deque

N,M = map(int, input().split())
N = 2 * M + 1

lis = [i for i in range(1,N+1)]
lis1 = deque(lis[:N//2+1])
lis2 = deque(lis[N//2+1:])
if M % 2 == 0:
    
    for i in range(M//2):
        a = lis1.popleft()
        b = lis1.pop()
        print(a,b)
    for i in range(M//2):
        a = lis2.popleft()
        b = lis2.pop()
        print(a,b)
else:
    for i in range(M//2+1):
        a = lis1.popleft()
        b = lis1.pop()
        print(a,b)
    for i in range(M//2):
        a = lis2.popleft()
        b = lis2.pop()
        print(a, b)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
import copy
def knapsack(N,W,weight,value):
  inf=float("inf")
  dp=[[-inf for i in range(W+1)] for j in range(N+1)]
  dp2=[[[] for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1): dp[0][i]=0

  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w:
        if dp[i][w-weight[i]]+value[i]>dp[i][w]:
          dp[i+1][w]=dp[i][w-weight[i]]+value[i]
          x=copy.copy(dp2[i][w-weight[i]])
          x.append(i)
          dp2[i+1][w]=x
        else:
          dp[i+1][w]=dp[i][w]
          dp2[i+1][w]=dp2[i][w]
        
      else:
        dp[i+1][w]=dp[i][w]
        dp2[i+1][w]=dp2[i][w]
  return [dp[N][W],dp2[N][W]]

n,t=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
a=[];b=[]
for i in range(n):
  a.append(l[i][0])
  b.append(l[i][1])
z=knapsack(n,t-1,a,b)
x=z[0];y=z[1]
L=[0 for i in range(n)]
for i in range(len(y)):
  L[y[i]]=1
M=[]
for i in range(n):
  if L[i]==0:
    M.append(b[i])
if len(M)==0:
  print(x)
else:
  print(x+max(M))

### FIXED CODE ###

import sys
input=sys.stdin.readline
import copy
def knapsack(N,W,weight,value):
  dp=[[999999999999 for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1): dp[0][i]=0
 
  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w:
        if dp[i][w-weight[i]]+value[i]>dp[i][w]:
          dp[i+1][w]=dp[i][w-weight[i]]+value[i]
        else:
          dp[i+1][w]=dp[i][w]
      else:
        dp[i+1][w]=dp[i][w]
  return dp
 
n,t=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
l.sort()
a=[];b=[]
for i in range(n):
  a.append(l[i][0])
  b.append(l[i][1])
dp=knapsack(n,t-1,a,b)
ans=[]
for i in range(n):
  if i!=n:
    ans.append(dp[i][t-1]+b[i])
  else:
    ans.append(dp[n][t-i])
print(max(ans))
### BUGGY CODE ###

from fractions import gcd
def lcm(a):
    len_a = len(a)
    ret = a[0]
    for i in range(1, len_a):
        ret = (ret * a[i]) // gcd(ret, a[i])
    return ret
n = int(input())
a = [int(i) for i in input().split()]

def f(m):
    sum = 0
    for i in range(n):
        sum += m % a[i]
    return sum

print(max(f(i) for i in range(lcm(a))))

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
print(sum(a) - n)
### BUGGY CODE ###

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

a.sort()

cnt = 0
flags = [True] * n
for i in range(n):
    if not flags[i]:
        continue

    if i == n - 1 or a[i] != a[i + 1]:
        cnt += 1

    for j in range(i + 1, n):
        if flags[j] and a[j] % a[i] == 0:
            flags[j] = False

print(cnt)


### FIXED CODE ###

from collections import Counter


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

flags = [True] * (a[-1] + 1)

for e in a:
    for mul in range(2, a[-1] // e + 1):
        flags[e * mul] = False

print(sum([flags[a[i]] and c[a[i]] == 1 for i in range(n)]))
### BUGGY CODE ###

import math
from functools import reduce
import fractions
import numpy as np
def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

N = int(input())
A = list(map(int, input().split()))
ans=0
for i in range(N):
    a = A[0]
    del A[0]
    
    b = gcd_list(A)
    if ans < b:
        ans = b
    A.append(a)

print(ans)
        

### FIXED CODE ###

def gcd(x,y):
  if y==0:
    return x
  else:
    return gcd(y, x%y)

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

left_gcd = [A[0]]
a = A[0]
for i in range(1,N-1):
  a = gcd(a, A[i])
  left_gcd.append(a)

right_gcd = [A[N-1]]
b = A[N-1]
for k in range(N-2, 0, -1):
  b = gcd(b, A[k])
  right_gcd.append(b)

ans_gcd = [right_gcd[N-2], left_gcd[N-2]]

for p in range(N-2):
  ans_gcd.append(gcd(left_gcd[p], right_gcd[N-p-3]))

print(max(ans_gcd))
### BUGGY CODE ###

import heapq

n, m = map(int, input().split())
queue = []
for a in map(int, input().split()):
  heapq.heappush(queue, a)
for _ in range(m):
  b, c = map(int, input().split())
  for _ in range(b):
    if queue[0] < c:
      heapq.heapreplace(queue, c)
    else:
      break
print(sum(queue))

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
cb = [list(map(int, input().split()[::-1])) for _ in range(m)]
a.sort()
cb.sort()
summation = 0
a_tmp = a.pop()
cb_tmp = cb.pop()
for i in range(n):
  if a_tmp >= cb_tmp[0]:
    summation += a_tmp
    if a:
      a_tmp = a.pop()
  else:
    summation += cb_tmp[0]
    cb_tmp[1] -= 1
    if cb_tmp[1] == 0:
      if cb:
        cb_tmp = cb.pop()
      else:
        cb_tmp = [0, n]
print(summation)
### BUGGY CODE ###

n, k = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]

if n <= k:
    k = n-1

dp=[0]*(n)
for i in range(k+1):
    dp[i] = abs(h[0]-h[i])

#dp2=[0]*(k)
m = 100000000000

for i in range(k+1,n):
    m = 100000000000
    for j in range(1,k+1):
        if abs(h[i] - h[i - j]) +dp[i-j] < m:
            m = abs(h[i] - h[i - j]) +dp[i-j]
        #dp2[j-1]=abs(h[i] - h[i - j]) +dp[i-j]

    #dp[i]=min(dp2)
    dp[i]=m

print(dp[n-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
 
DP = [0]
for i in range(N-1):
    act = float("inf")
    for k in range(K):
        if i-k < 0 : continue
        act = min(DP[-1-k] + abs(h[i-k]-h[i+1]) , act)
    DP += [act]
 
print(DP[-1])
### BUGGY CODE ###

H,W=map(int, input().split())
Ch,Cw=map(int, input().split())
Dh,Dw=map(int, input().split())
A=[]
for i in range(H):
  d=list(input())
  A.append(d)
D=[[10**8]*W for i in range(H)]
dy=[-1,1,0,0,2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
dx=[0,0,1,-1,0,1,2,-1,-2,1,2,-1,-2,2,-2,1,2,-1,-2,0,1,2,-1,-2]
from collections import deque
import sys
sys.setrecursionlimit(10**8) 
def bfs(y,x):
  q=deque()
  q.append((y,x))
  while len(q):
    y,x=q.popleft()
    for i in range(24):
      ny=y+dy[i]
      nx=x+dx[i]
      if 0<=ny<H and 0<=nx<W:
        if abs(ny-y)+abs(nx-x)==1:
          if A[ny][nx]=='.' and D[y][x]<D[ny][nx]:
            q.append((ny,nx))
            D[ny][nx]=D[y][x]
        else:
          if A[ny][nx]=='.':
            if D[ny][nx]==10**8:
              q.append((ny,nx))
              D[ny][nx]=D[y][x]+1
            elif D[ny][nx]>D[y][x]+1:
              q.append((ny,nx))
              D[ny][nx]=D[y][x]+1
D[Ch-1][Cw-1]=0
bfs(Ch-1,Cw-1)
if D[Dh-1][Dw-1]==10**8:
  print(-1)
else:
  print(D[Dh-1][Dw-1])

### FIXED CODE ###

H,W=map(int, input().split())
Ch,Cw=map(int, input().split())
Dh,Dw=map(int, input().split())
A=[]
for i in range(H):
  d=list(input())
  A.append(d)
D=[[10**8]*W for i in range(H)]
DD=[[-1]*W for i in range(H)]
dy=[-1,1,0,0]
dx=[0,0,1,-1,]
ey=[2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
ex=[0,1,2,-1,-2,1,2,-1,-2,2,-2,1,2,-1,-2,0,1,2,-1,-2]
for h in range(H):
  for w in range(W):
    if A[h][w]=='#':
      D[h][w]=10**5
from collections import deque
import sys
sys.setrecursionlimit(10**7) 
def bfs(y,x):
  q=deque()
  q.append((y,x))
  
  while len(q):
    y,x=q.popleft()
    cnt=0
    for i in range(4):
      ny=y+dy[i]
      nx=x+dx[i]
      if 0<=ny<H and 0<=nx<W:
        if A[ny][nx]=='.' and D[y][x]<D[ny][nx]:
          q.appendleft((ny,nx))
          D[ny][nx]=D[y][x]
          DD[ny][nx]=1

    for i in range(20):
      my=y+ey[i]
      mx=x+ex[i]
      if 0<=my<H and 0<=mx<W:
        if A[my][mx]=='.' and D[my][mx]==10**8 and DD[my][mx]==-1:
          q.append((my,mx))
          D[my][mx]=D[y][x]+1
            
D[Ch-1][Cw-1]=0
bfs(Ch-1,Cw-1)
if D[Dh-1][Dw-1]==10**8:
  print(-1)
else:
  print(D[Dh-1][Dw-1])