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

import numpy as np
import math
from numba import njit
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=np.int64)


@njit('i8,i8,i8[::1]', cache=True)
def solve(N, K, A):
    # 一度照らされると二度目以降は確実に照らされるはず。
    for i in range(K):
        # j番目の電球を操作
        B = np.array([0] * N, dtype=np.int64)
        if list(set(A)) == [N]:
            break
        for j in range(N):
            if A[j] == N:
                B[j] = N
                continue
            maxA = j + A[j]
            minA = j - A[j]

            for k in range(max(0, minA), min(N, maxA + 1)):
                B[k] += 1
        A = B.copy()
    return A


A = solve(N, K, A)
for i in range(N):
    if i != (N - 1):
        print(A[i], end=" ")
    else:
        print(A[i])


### FIXED CODE ###

import numpy as np
from numba import njit
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=np.int64)


@njit
def solve(N, K, A):
    # 一度照らされると二度目以降は確実に照らされるはず。
    for i in range(K):
        # j番目の電球を操作
        B = np.zeros(N + 1, dtype=np.int64)
        for j in range(N):
            # 左辺を確認
            B[max(j - A[j], 0)] += 1
            # 右辺を確認(なんで-1?)
            B[min(j + A[j] + 1, N)] -= 1

        A = np.cumsum(B)[:-1]

        if np.all(A == N):
            return A

    else:
        return A


A = solve(N, K, A)
for i in range(N):
    if i != (N - 1):
        print(A[i], end=" ")
    else:
        print(A[i])
### BUGGY CODE ###

#python3

INF = int(1e9)

def main():

    n, k = map(int, input().split()) 
    h = [int(i) for i in input().split()] + [0]* 110


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

    print(dp[n-1])

main() 

### FIXED CODE ###

#python3

INF = int(1e9)

def main():

    n, k = map(int, input().split()) 
    h = [int(i) for i in input().split()] + [0]* 110


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

    print(dp[n-1])

main()
### BUGGY CODE ###

import sys
import bisect
n = int(input())
s = list(input())
alpha = "abcdefghijklmnopqrstuvwxyz"
dict = {i:[] for i in alpha}
for i, _s in enumerate(s):
    dict[_s].append(i)
q = int(input())
for i in range(q):
    type, first, last = [i for i in sys.stdin.readline().split()]
    if type == "2":
        first = int(first)
        last = int(last)
        first -= 1
        last -= 1
        cnt = 0
        for a in alpha:
            ls = dict[a]
            if bisect.bisect_left(ls, first) != bisect.bisect_right(ls, last):
                cnt += 1
        print(cnt)
    else:
        first = int(first)
        first -= 1
        dict[s[first]].remove(first)
        s[first] = last
        bisect.insort_left(dict[last], first)

### FIXED CODE ###

import sys
import bisect
n = int(sys.stdin.readline().strip())
s = list(sys.stdin.readline().strip())
alpha = "abcdefghijklmnopqrstuvwxyz"
dict = {i:[] for i in alpha}
for i, _s in enumerate(s):
    dict[_s].append(i)
q = int(sys.stdin.readline().strip())
for i in range(q):
    type, first, last = [i for i in sys.stdin.readline().split()]
    if type == "2":
        first = int(first)
        last = int(last)
        first -= 1
        last -= 1
        cnt = 0
        for ls in dict.values():
            if bisect.bisect_left(ls, first) != bisect.bisect_right(ls, last):
                cnt += 1
        print(cnt)
    else:
        first = int(first)
        first -= 1
        _s = s[first]
        if _s == last:
            continue
        del dict[_s][(bisect.bisect_left(dict[_s], first))]
        s[first] = last
        bisect.insort_left(dict[last], first)
### BUGGY CODE ###

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

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

for i in range(1, H + 10 ** 4 + 1):
    values = []
    for a, b in ab:
        values.append(dp[i - a] + b)
    dp[i] = min(values)

print(min(dp[H:]))


### FIXED CODE ###

import numpy as np

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

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

ab = np.array(ab)
a_list = ab[:, 0]
b_list = ab[:, 1]
max_a = ab.max()

inf = float('inf')
dp = np.array([inf for _ in range(H + max_a)])
dp[0] = 0

for i in range(1, len(dp)):
    dp[i] = np.amin(dp[np.maximum(i - a_list, 0)] + b_list)

print(int(min(dp[H:])))
### BUGGY CODE ###

X, Y, Z, K = list(map(int, input().split()))
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)
s = []

for i in A:
    for j in B:
        for k in C:
            s.append(i+j+k)

s = sorted(s, reverse=True)

for i in range(K):
    print(s[i])

### FIXED CODE ###

X, Y, Z, K = list(map(int, input().split()))
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)
e = []
s = []

for i in A:
    for j in B:
        e.append(i+j)
e = sorted(e, reverse=True)

if K<len(e):
    e = e[0:K]

for i in e:
    for j in C:
        s.append(i+j)

s = sorted(s, reverse=True)

for i in range(K):
    print(s[i])
### BUGGY CODE ###

import fractions
n=int(input())
a = list(map(int, input().split()))
ans = a[0]
for i in range(1, n):
    ans = ans * a[i] // fractions.gcd(ans, a[i])
mod=10**9+7
kai=0
for i in a:
    kai+=ans//i
    kai%=mod
print(kai)


### FIXED CODE ###

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

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

#factorization(24) 

## [[2, 3], [3, 1]]
z=[0]*(10**6+1)
for i in l:
    if i>=2:
        re=factorization(i)
        for p in re:
            z[p[0]]=max(z[p[0]],p[1])
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m
w=1
mod=10**9+7
for i in range(10**6+1):
    w*=pow(i,z[i],mod)
    w%=mod
kai=0
for i in l:
    kai+=w*mod_inv(i,mod)
    kai%=mod
print(kai)
### BUGGY CODE ###

import numpy as np

n,m,q = map(int,input().split())
li = [[0 for i in range(n+1)]for j in range(n+1)]

for i in range(m):
    l,r = map(int,input().split())
    li[l][r] += 1
    li[r][l] += 1

li = np.array(li)
for i in range(n+1):
    li[i] = np.cumsum(li[i])

for i in range(q):
    l,r = map(int,input().split())
    point = 0
    for j in range(l,r+1):
        point += li[j][r]-li[j][l-1]
    print(point//2)

### FIXED CODE ###

import numpy as np

n,m,q = map(int,input().split())
li = [[0 for i in range(n+1)]for j in range(n+1)]

for i in range(m):
    l,r = map(int,input().split())
    li[l][r] += 1

li = np.array(li)
c = np.cumsum(li,axis=1).cumsum(axis=0).tolist()

for i in range(q):
    l,r = map(int,input().split())
    l -= 1
    point = c[r][r]
    point -= c[r][l]
    point -= c[l][r]
    point += c[l][l]
    print(point)
### BUGGY CODE ###

from collections import deque

S = input()

if len(S) < 5:
    print(0)
    exit()

check_str = deque()
first = 0
end = 4

for i_range in range(5, len(S)):
    start = 0
    while start+i_range <= len(S):
        check_str.append(int(S[start:start+i_range]))
        start += 1

ans = 0
while len(check_str) > 0:
    now_num = check_str.popleft()
    if now_num % 2019 == 0:
        ans += 1

print(ans)

### FIXED CODE ###

S = input()
S_reverse = S[::-1]

dp = [0] * 2019
now_mod = 0
digit = 1

for i_s in S_reverse:
    now_mod = (now_mod + int(i_s)*digit) % 2019
    digit = (digit*10) % 2019
    dp[now_mod] += 1

ans = sum(x*(x-1)//2 for x in dp)
ans += dp[0]

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

from collections import defaultdict
import sys
input = sys.stdin.readline

N = int(input())

if (N == 1):
    print("First")
    quit()

tree = defaultdict(list)
nodes_len = defaultdict(list)
for i in range(N):
    nodes_len[i+1] = [0, 0]

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

queue_set = set()
while len(tree) > 1:
    del_nodes = []
    for from_node, to_nodes in tree.items():
        # dictのサイズが1なら
        if len(to_nodes) == 1:
            to_node = to_nodes[0]

            # queueに次のノードを入れる
            queue_set.add(to_node)

            # そのノードが持つ隣接ノード長を追加する
            nodes_len[to_node].append(nodes_len[from_node][0]+1)

            # 長さが2以上のみ保持する
            nodes_len[to_node].sort(reverse=True)
            nodes_len[to_node] = nodes_len[to_node][:2]

            # treeのto_nodeの部分から削除する
            tree[to_node].remove(from_node)

            del_nodes.append(from_node)

    for node in del_nodes:
        del tree[node]

n = list(tree.keys())[0]
print("Second" if (nodes_len[n][0] + nodes_len[n][1]+1) % 3 == 2 else "First")


### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline


N = int(input())
# 例外処理
if (N == 1):
    print("First")
    quit()

tree = defaultdict(set)
tree_main = defaultdict(set)
for i in range(N-1):
    a, b = tuple(map(int, input().split()))
    tree[a].add(b)
    tree[b].add(a)
    tree_main[a].add(b)
    tree_main[b].add(a)

def longest_path(tree, from_node=1):
    cnt = 1

    nearest_nodes = list(tree[from_node])
    while len(nearest_nodes) > 0:
        for one_step_node in nearest_nodes:
            for two_step_node in tree[one_step_node]:
                if two_step_node != from_node:
                    tree[two_step_node].remove(one_step_node)
                    tree[two_step_node].add(from_node)
                    tree[from_node].add(two_step_node)
            tree[from_node].remove(one_step_node)
        cnt += 1
        nearest_nodes = list(tree[from_node])

    return one_step_node, cnt


far, _ = longest_path(tree)
_, n = longest_path(tree_main, far)
print("Second" if n % 3 == 2 else "First")
### BUGGY CODE ###

import math
from functools import reduce
import itertools

def gcd(*numbers):
    return reduce(math.gcd, numbers)

N = int(input())

i = 0
for a, b, c in itertools.product(range(1,N+1), range(1,N+1),range(1,N+1)):
    i += gcd(a, b, c)

print(i)

### FIXED CODE ###

from math import gcd 
N = int(input())
i = 0
 
for a in range(1, N+1):
    for b in range(1, N+1):
        for c in range(1, N+1):
            i += gcd(gcd(a, b), c)
            
print(i)
### BUGGY CODE ###

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

p = al[0]
for i in range(1, n):
    p = p * al[i] // fractions.gcd(p, al[i])

ans = 0

for a in al:
    ans += p // a
    ans %= 10**9 + 7

print(ans)

### FIXED CODE ###

import fractions
n = int(input())
al = list(map(int,input().split()))
al = sorted(al)
p = al[0]
for i in range(1, n):
    p = p * al[i] // fractions.gcd(p, al[i])

ans = 0

for a in al:
    ans += p // a

print(ans % (10**9 + 7))
### BUGGY CODE ###

H, W = map(int, input().split())
c_set = set()
for i in range(H):
  b = input()
  count_b = b.count('#')
  index = 0
  for x in range(count_b):
    index = b.find('#', x)
    c_set.add((i, index))
ans = 0
for i in range(H+W):
  ll = c_set.copy()
  if len(c_set) >= H*W:
    break;
  else:
    ans += 1
    for c in ll:
      if not c[0]-1 < 0:
        c_set.add((c[0]-1, c[1]))
      if not c[0]+1 > W-1:
        c_set.add((c[0]+1, c[1]))
      if not c[1]-1 < 0:
        c_set.add((c[0], c[1]-1))
      if not c[1]+1 > W-1:
        c_set.add((c[0], c[1]+1))

print(ans)


### FIXED CODE ###

h,w= map(int, input().split())
s_list = []
b_list = []
for i in range(h):
    li = input()
    aa = []
    for j in range(w):
        aa.append(li[j])
        if aa[j] == '#':
            b_list.append((i, j))
    s_list.append(aa)
ans = 0
while True:
    bb_list = []
    for p in b_list:
        pp = [(p[0]-1, p[1]), (p[0]+1, p[1]), (p[0], p[1]-1), (p[0], p[1]+1)]
        for ppp in pp:
            if (0 <= ppp[0] < h) and (0 <= ppp[1] < w):
                if s_list[ppp[0]][ppp[1]] == '.':
                    s_list[ppp[0]][ppp[1]] = '#'
                    bb_list.append((ppp[0], ppp[1]))
    # ここで複数回同じbをやらなくて済むようにしている
    b_list = bb_list
    if len(b_list) == 0:
        break
    ans += 1
    # print(x)
print(ans)
### BUGGY CODE ###

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

def gcd(a, b):
    if b > a:
        a,b = b,a
    a,b = b,a % b
    if b == 0:
        return a
    else:
        return gcd(a,b)
def lcm(a, b):
	return a * b // gcd (a, b)

if s[0] != t[0]:
    print(-1)
    exit()
if gcd(n,m) == 1:
    print(lcm(n,m))
    exit()

ans = lcm(n,m)

for i in range(1,ans):
    if i % (ans//n) != 0 or i%(ans//m) != 0:
        continue
    if s[i // (ans//n)] == t[i // (ans//m)]:
        continue
    else:
        print(-1)
        exit()
print(ans)


### FIXED CODE ###

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

def gcd(a, b):
    if b > a:
        a,b = b,a
    a,b = b,a % b
    if b == 0:
        return a
    else:
        return gcd(a,b)
def lcm(a, b):
	return a * b // gcd (a, b)

if s[0] != t[0]:
    print(-1)
    exit()
if gcd(n,m) == 1:
    print(lcm(n,m))
    exit()

ans = lcm(n,m)
nn = ans//n
mm = ans//m
e = lcm(nn,mm)
for i in range(1,ans,e):
    # print(i // (ans//n),i // (ans//m))
    # print(s[i // (ans//n)],t[i // (ans//m)])
    if s[i // (ans//n)] != t[i // (ans//m)]:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

from collections import deque

n, m = map(int, input().split())
edges = [[] for i in range(n)]
for i in range(m):
    p, q, c = map(int, input().split())
    p, q, c = p-1, q-1, c-1
    edges[p].append((q, c))
    edges[q].append((p, c))

que = deque()
cost = [float("inf")]*n
colr = [-1]*n
# now, prev,prev_color, cost
que.append((0, -1, -1, 0))

while que:
    now, prev, prev_color, cost_now = que.popleft()
    if cost[now] < cost_now or (cost[now] == cost_now and colr[now] == prev_color):
        continue
    cost[now] = cost_now
    colr[now] = prev_color
    for to, color in edges[now]:
        if to == prev:
            continue
        if cost_now+int(color!=prev_color) <= cost[to]:
            que.append((to, now, color, cost_now+int(color!=prev_color)))
if cost[-1] == float("inf"):
    print(-1)
else:
    print(cost[-1])

### FIXED CODE ###

# https://juppy.hatenablog.com/entry/2019/04/10/ARC061_-_E_%E3%81%99%E3%81%AC%E3%81%91%E5%90%9B%E3%81%AE%E5%9C%B0%E4%B8%8B%E9%89%84%E6%97%85%E8%A1%8C_-_Python_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0_Atcoder
# 参考にさせていただきました。

from collections import deque, defaultdict

chg = 10**6
n, m = map(int, input().split())
edges = defaultdict(set)
# m=0のためにdefaultdictにしておくべき
visited = defaultdict(set)
for i in range(m):
    p, q, c = map(int, input().split())
    edges[p+c*chg].add(q+c*chg)
    edges[q+c*chg].add(p+c*chg)
    edges[p].add(p+c*chg)
    edges[q].add(q+c*chg)
    edges[p+c*chg].add(p)
    edges[q+c*chg].add(q)
    visited[p] = False
    visited[q] = False
    visited[p+c*chg] = False
    visited[q+c*chg] = False

ans = float("inf")
que = deque()
# now, dist
que.append((1, 0))
# 今求めるのはendの距離だけなので、dist配列はいらない
# さらに、距離は0/1なのでheapで辺を管理する必要もなく、0なら最短確定なので先に、1ならその時点での最長なので後ろにすれば良い
while que:
    now, dist = que.popleft()
    if visited[now]:
        continue
    visited[now] = True
    if now == n:
        ans = dist
        break
    for to in edges[now]:
        # 駅→ホーム
        if now < chg and to > chg:
            que.append((to, dist+1))
        else:
            que.appendleft((to, dist))
if ans == float("inf"):
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
def grun(A, K):
    if A < K:
        return 0
    if A%K == 0:
        return A//K
    return grun(A - A//K - 1, K)

N = int(input())
X = 0
for _ in range(N):
    A, K = map(int, input().split())
    X ^= grun(A, K)
print('Takahashi' if X else 'Aoki')


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
def grun(A, K):
    if A < K:
        return 0
    a, b = divmod(A, K)
    if b == 0:
        return a
    a += 1
    r = A % a
    return grun((((a-1)*K-r)//a)*a+r, K)
def solve():
    N = int(input())
    X = 0
    for _ in range(N):
        A, K = map(int, input().split())
        X ^= grun(A, K)
    print('Takahashi' if X else 'Aoki')

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

def main():
    n = int(input())
    a = [int(input()) for i in range(n)]

    btn = 1
    hist = []
    while True:
        if btn == 2:
            print(len(hist))
            break

        if btn in hist:
            print(-1)
            break

        hist.append(btn)
        btn = a[btn - 1]


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())
    a = [int(input()) for i in range(n)]

    btn = 1
    hist = set()
    while True:
        if btn == 2:
            print(len(hist))
            break

        if btn in hist:
            print(-1)
            break

        hist.add(btn)
        btn = a[btn - 1]


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

a = input()
b = input()

cnt = 0

i=0

while(i<len(a)):
  if(a[i]!=b[i]):
    cnt+=1
  cnt+=1

print(cnt)

### FIXED CODE ###

a = input()
b = input()

cnt = 0

i=0

while(i<len(a)):
    if(a[i]!=b[i]):
      cnt+=1
    i+=1

print(cnt)
### BUGGY CODE ###

import numpy as np
from numba import njit

N, K = list(map(int, input().strip().split()))
A = np.array(input().strip().split(), dtype=np.int64)

@njit(cache=True)
def calc(a, step):
    b = np.array([0]*N)
    for i in range(N):
        left = int(max(0, i-a[i]))
        right = int(min(N-1, i+a[i]))
        b[left:right+1] += 1
    
    if np.all(a==b) or step>=K:
        return b
    else:
        step += 1
        return calc(b, step)

ans = calc(A, 1)
ans = [str(x) for x in ans]
print(" ".join(ans))

### FIXED CODE ###

import numpy as np
from numba import njit

N, K = list(map(int, input().strip().split()))
A = np.array(input().strip().split(), dtype=np.int64)

@njit(cache=True)
def calc(a, step):
    b = np.array([0]*N)
    for i in range(N):
        left = int(max(0, i-a[i]))
        right = int(min(N-1, i+a[i]))
        b[left] += 1
        if right + 1 < N:
            b[right+1] -= 1
    b = np.cumsum(b)
    
    if np.all(a==b) or step>=K:
        return b
    else:
        step += 1
        return calc(b, step)

ans = calc(A, 1)
ans = [str(x) for x in ans]
print(" ".join(ans))
### BUGGY CODE ###

from collections import deque
H, W = map(int,input().split())

A = [[False for _ in range(W)] for _ in range(H)]

Q = deque()
for y in range(H):
    S = input()
    for x, s in enumerate(S):
        if s == "#":
            Q.append((y, x))
            A[y][x] = True

ans = 0
while Q:
    ans += 1
    NQ = deque()
    for y, x in Q:
        if x > 0 and A[y][x-1] == False:
            A[y][x-1] = True
            NQ.append((y,x-1))
        if x < W-1 and A[y][x+1] == False:
            A[y][x+1] = True
            NQ.append((y,x+1))
        if y > 0 and A[y-1][x] == False:
            A[y-1][x] = True
            NQ.append((y-1, x))
        if y < H-1 and A[y+1][x] == False:
            A[y+1][x] = True
            NQ.append((y+1,x))
    if NQ:
        Q = NQ
    else:
        break

print(ans-1)

### FIXED CODE ###

def main():
    H, W = map(int,input().split())

    A = [[False for _ in range(W)] for _ in range(H)]

    Q = []
    for y in range(H):
        S = input()
        for x, s in enumerate(S):
            if s == "#":
                Q.append((y, x))
                A[y][x] = True

    ans = 0
    while Q:
        ans += 1
        NQ = []
        for y, x in Q:
            if x > 0 and A[y][x-1] == False:
                A[y][x-1] = True
                NQ.append((y,x-1))
            if x < W-1 and A[y][x+1] == False:
                A[y][x+1] = True
                NQ.append((y,x+1))
            if y > 0 and A[y-1][x] == False:
                A[y-1][x] = True
                NQ.append((y-1, x))
            if y < H-1 and A[y+1][x] == False:
                A[y+1][x] = True
                NQ.append((y+1,x))
        if NQ:
            Q = NQ
        else:
            break

    print(ans-1)

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

import numpy as np
n = int(input())
A = [int(i) for i in range(1, n+1)]
dp = [[] for _ in range(A[-1]+1)]
f = np.array([True for _ in range(A[-1]+1)])
A = np.array(A)
prev = 0
ans = 1
for a in A[1:]:
  if f[a]:
    if prev == a:
      f[a] = False
    for i in range(A[-1]//a+1):
      if i >= 1:
        cnt = 1
        tmp = i
        while tmp % a == 0:
          cnt += 1
          tmp = tmp // a
        dp[i*a].append(cnt)
        f[i*a] = False
  prev = a
  t = 1
  for d in dp[a]:
    t = t * (d+1)
  ans += a * t
print(ans)

### FIXED CODE ###

n = int(input())

ans = 0
for i in range(1, n+1):
  y = n//i
  ans += i * y * (y+1) // 2
print(ans)
### BUGGY CODE ###

from math import ceil


def check_p(p):
    global k, ws
    ct, nt = 0, 1
    for w in ws:
        if ct + w <= p:
            ct += w
        else:
            nt += 1
            if nt > k:
                return False
            ct = w
    return True


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

ws = [int(input()) for _ in range(n)]

p = max(ceil(sum(ws) / k), *ws)

while True:
    if check_p(p):
        break
    p += 1

print(p)

### FIXED CODE ###

def check_p(p):
    global k, ws
    lt, nt = 0, 1  # loadage_of_current_truck, num_of_truck
    for w in ws:
        lt += w
        if lt > p:
            nt += 1
            if nt > k:
                return False
            lt = w
    return True


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

ws = [int(input()) for _ in range(n)]
l, r, p = max(ws), sum(ws), 0

while l < r:
    p = (l + r) // 2
    if check_p(p):
        r = p
    else:
        l = p = p + 1

print(p)
### BUGGY CODE ###

#200426C
N = int(input())

X = []
ans = 0
for i in range(N):
    S = str(input())
    if X.count(S)==0:
        X.append(S)
        ans += 1
print(ans)


### FIXED CODE ###

#200426C
import collections
N = int(input())

X = []
ans = 0
for i in range(N):
    S = str(input())
    X.append(S)
Y = collections.Counter(X)
print(len(Y))
### BUGGY CODE ###

s = list(input())
q = int(input())
for i in range(1,q+1):
  queue = list(input().split())
  if len(queue) > 1:
    if queue[1] == '1':
      s.insert(0,queue[2])
    elif queue[1] == '2':
      s.append(queue[2])
  else:
    s.reverse()
print(''.join(s))

### FIXED CODE ###

from collections import deque
S=deque(input())
Q=int(input())
ref=0
for i in range(Q):
    T=input().split()
    if T[0] == '2':
        if (T[1]=='1' and ref%2==0):
            S.appendleft(T[2])
        elif (T[1]=='2' and ref%2==0):
            S.append(T[2])
        elif (T[1]=='1' and ref%2==1):
            S.append(T[2])
        elif (T[1]=='2' and ref%2==1):
            S.appendleft(T[2])
    else:
        ref+=1
for i in range(len(S)):
    if ref%2==0:
        char=S.popleft()
        print(char,end='')
    else:
        char=S.pop()
        print(char,end='')
### BUGGY CODE ###

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

import heapq

heapq.heapify(cards)

for _ in range(m):
    b,c = map(int,input().split())

    for _ in range(b):
        heapq.heappush(cards,c)

for _ in range(len(cards) - n):
    heapq.heappop(cards)

print(sum(cards))

### FIXED CODE ###

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

from collections import Counter

d = dict(Counter(cards))

for _ in range(m):
    b,c = map(int,input().split())

    if c in d:
        d[c]+=b
    else:
        d[c]=b

d= sorted(d.items(),key=lambda x: x[0],reverse=True)

ans = 0
cnt = 0
for j in d:
    cnt +=j[1]
    ans +=j[0] * j[1]



    if cnt>n:
        ans -=j[0]*(cnt-n)
        print(ans)
        exit(0)

print(ans)