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

import collections


def dfs(graph, start):
    visited = set()
    stack = [start]
 
    while stack:
        v = stack.pop()
        if v not in visited:
            stack.extend(graph[v])
            visited.add(v)
            yield v

def read_graph(nodes, edges):
    graph = [set() for _ in range(nodes)]
    for _ in range(edges):
        a, b = (int(x) - 1 for x in input().split())
        graph[a].add(b)
        graph[b].add(a)
 
    return graph

N, M, K = map(int, input().split())

friends = read_graph(N, M)
blockings = read_graph(N, K)

candidates = [None for _ in range(N)]
for i in range(N):
    if candidates[i] is not None:
        continue

    s = set()
    for j in dfs(friends, i):
        s.add(j)
        candidates[j] = s
    

print(
    " ".join(
        str(len(candidates[i] - friends[i] - blockings[i]) - 1) for i in range(N)
    )
)


### FIXED CODE ###

def dfs(graph, start):
    visited = set()
    stack = [start]

    while stack:
        v = stack.pop()
        if v not in visited:
            stack.extend(graph[v])
            visited.add(v)
            yield v


def read_graph(nodes, edges):
    graph = [[] for _ in range(nodes)]
    for _ in range(edges):
        a, b = (int(x) - 1 for x in input().split())
        graph[a].append(b)
        graph[b].append(a)

    return graph


def count_candidates(n, counts, groups, block, friend):
    for i in range(n):
        count = counts[groups[i]]
        for v in block[i]:
            if groups[i] == groups[v]:
                count -= 1

        count -= len(friend[i])
        count -= 1
        yield count


def main():
    n, m, k = map(int, input().split())
    friend = read_graph(n, m)
    block = read_graph(n, k)

    groups = [-1 for _ in range(n)]
    counts = []
    i = 0
    group_id = 0
    while i < n:
        if groups[i] != -1:
            i += 1
            continue

        for j, v in enumerate(dfs(friend, i)):
            groups[v] = group_id

        counts.append(j + 1)
        group_id += 1

    print(" ".join(str(i) for i in count_candidates(n, counts, groups, block, friend)))


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

dp=[0]*110000
LINF=10**9

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

dp[0]=0
for i in range(1,n):
  dp[i]=LINF
  for j in range(1,k+1):
    if i-j>=0:
      dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))

print(dp[n-1])

### FIXED CODE ###

N,K=map(int,input().split())
h=[int(i) for i in input().split()]
f_inf=float('inf')
dp=[f_inf]*(N+10)
dp[0]=0
for i in range(1,N):
  for j in range(1,K+1):
    if i-j>=0:
      dp[i]=min(dp[i-j]+abs(h[i]-h[i-j]),dp[i])
print(dp[N-1])
### BUGGY CODE ###

n = int(input())
ans = 0

def gcd(a,b):
    if a>b:
        p = a
        q = b
    else:
        p = b
        q = a
    d = q
    while p % q != 0:
        d = p % q
        p = q
        q = d
    return d


for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            if i==1 or j==1 or k==1:
                ans += 1
            elif abs(i-j)==1 or abs(j-k)==1 or abs(k-i)==1:
                ans += 1
            else:
                ans += gcd(gcd(i,j),k)

print(ans)


### FIXED CODE ###

n = int(input())
ans = 0
 
def max(a,b):
    if a>b:
        return a
    else:
        return b
 
def min(a,b):
    if a<b:
        return a
    else:
        return b
 
def gcd(a,b):
    p = max(a,b)
    q = min(a,b)
    d = q
    while p % q != 0:
        d = p % q
        p = q
        q = d
    return d
 
 
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            ans += gcd(gcd(i,j),k)
 
print(ans)
### BUGGY CODE ###

def mo(v):
    return v % 1000000007


n = int(input())
a = list(map(int, input().split()))
a.insert(0, 0)
s = 0
for i in range(1, n, 1):
    for j in range(i + 1, n + 1, 1):
        s += mo(a[i] * a[j])
print(mo(s))


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
s = [0]
ans = 0
MOD = 1000000007
for i in range(0, n, 1):
    s.append((s[i] + a[i]) % MOD)

for i in range(0, n, 1):
    ans += ((s[n] - s[i + 1]) * a[i]) % MOD

print(ans % MOD)
### BUGGY CODE ###

import math
H, N = map(int, input().split())
dp = [[0 for _ in range(H + 1)] for _ in range(N)]
A, B = map(int, input().split())
for i in range(H + 1):
    cnt = math.ceil(i / A)
    dp[0][i] = B * cnt

for i in range(1, N):
    A, B = map(int, input().split())
    for j in range(H + 1):
        dp[i][j] = min(dp[i - 1][j], dp[i][max(j - A, 0)] + B)
# print(*dp, sep='\n')
print(dp[-1][-1])

### FIXED CODE ###

import math
H, N = map(int, input().split())
dp = [[0 for _ in range(H + 1)] for _ in range(N)]
A, B = map(int, input().split())
for i in range(H + 1):
    cnt = math.ceil(i / A)
    dp[0][i] = B * cnt

for i in range(1, N):
    A, B = map(int, input().split())
    for j in range(H + 1):
        dp[i][j] = min(dp[i - 1][j], dp[i][max(j - A, 0)] + B)
# print(*dp, sep='\n')
print(dp[-1][-1])
### BUGGY CODE ###

n = int(input())
a_list = list(map(int, input().split()))
ans_len = 10**6+10
is_ans = [0]*(ans_len)

for a in a_list:
    if is_ans[a] == 0:
        b = 2*a
        while b < ans_len:
            is_ans[b] += 1
            b += a

ans = 0
for a in a_list:
    if a_list.count(a) == 1:
        ans += (is_ans[a] == 0)
print(ans)


### FIXED CODE ###

n = int(input())
a_list = list(map(int, input().split()))
ans_len = 10**6+10
is_ans = [0]*(ans_len)

for a in a_list:
    is_ans[a] += 1
    if is_ans[a] == 1:
        b = 2*a
        while b < ans_len:
            is_ans[b] += 2
            b += a

ans = 0
for a in a_list:
    # print(a, is_ans[a])
    ans += (is_ans[a] == 1)
print(ans)
### BUGGY CODE ###

# これは間に合うの？

from heapq import heappop,heappush
N,Q=map(int,input().split())
E=[]
for a in range(N):
    s,t,x=map(int,input().split())
    E.append((s-x,1,x))
    E.append((t-x,0,x))

for a in range(Q):
    E.append((int(input()),2,0))
E.sort()
 
S=set()
H=[]
for time_,type_,x in E:
    if type_==1:
        S.add(x)
        heappush(H,x)
    elif type_==0:
        S.remove(x)
    else:
        while H and H[0] not in S:
            heappop(H)
        print(H[0] if H else -1)


### FIXED CODE ###

import sys
from heapq import heappop, heappush

input = sys.stdin.readline
N, Q = map(int, input().split())
event_list = []
for i in range(N):
  s, t, x = map(int, input().split())
  event_list.append([s-x, 1, x])
  event_list.append([t-x, -1, x])

for i in range(Q):
  event_list.append([int(input()), 2, 0])

ans = []
event_list.sort()
x_set = set()
x_list = []
for time, event, x in event_list:
  if event == 1:
    x_set.add(x)
    heappush(x_list, x)
  elif event == -1:
    x_set.remove(x)
  else:
    while x_list and x_list[0] not in x_set:
      heappop(x_list)
    if x_list:
      ans.append(x_list[0])
    else:
      ans.append(-1)

print(*ans, sep='\n')
### BUGGY CODE ###

n = input()
an = list(map(int, input().split()))
b = []

for i in an:
    b.append(i)
    b.reverse()

print(' '.join(map(str, b)))


### FIXED CODE ###

n = int(input())
a = list(input().split())
if n == 1:
    print(a[0])
elif n % 2:
    print(*(a[-1::-2] + a[1::2]))
else:
    print(*(a[-1::-2] + a[0::2]))
### BUGGY CODE ###

n, q = [int(i) for i in input().split()]
g = [[] for i in range(n)]

for i in range(n-1):
    a, b = [int(_) for _ in input().split()]
    g[a-1].append(b)
c = [0 for i in range(n)]
for i in range(q):
    p, x = [int(_) for _ in input().split()]
    c[p-1] += x

q = [[1, c[0]]]
while len(q) != 0:
    p = q.pop(0)
    for i in g[p[0]-1]:
        c[i-1] += p[1]
        q.append([i, c[i-1]])

print(*c)


### FIXED CODE ###

from collections import deque
n, q = [int(i) for i in input().split()]
g = [[] for i in range(n)]

for i in range(n-1):
    a, b = [int(_) for _ in input().split()]
    g[a-1].append(b)
c = [0 for i in range(n)]
for i in range(q):
    p, x = [int(_) for _ in input().split()]
    c[p-1] += x

q = deque([[1, c[0]]])
while len(q) != 0:
    p = q.popleft()
    for i in g[p[0]-1]:
        c[i-1] += p[1]
        q.append([i, c[i-1]])

print(*c)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    A = LI()
    F = LI()

    # 時間tで感触できるか
    def can_complete(t):
        # 食べ物のtに間に合う要求コストを越えてる人のみ修行
        return sum([max(i-j, 0) for i, j in zip(sorted(A), sorted([t//i for i in F]))]) <= K

    # for j in range(20):
    #     print(can_complete(j))

    ng = -1
    ok = max(A)*max(F)
    while abs(ok-ng)>1:
        m = (ng+ok)//2
        if can_complete(m):
            ok = m
        else:
            ng = m
    print(ok)

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    A = LI()
    F = LI()

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

    # 時間tで感触できるか
    def can_complete(t):
        return sum([max(i-t//j, 0) for i, j in zip(A, F)]) <= K

    # for j in range(20):
    #     print(can_complete(j))

    ng = -1
    ok = max(A)*max(F)
    while abs(ok-ng)>1:
        m = (ng+ok)//2
        if can_complete(m):
            ok = m
        else:
            ng = m
    print(ok)

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

n = int(input())
a = [int(each) for each in input().split()]

result = 0
for i in range(len(a)):
    result += a[i] * sum(a[i+1:]) % 1000000007

print(result % 1000000007)

### FIXED CODE ###

n = int(input())
a = [int(each) for each in input().split()]

result = 0
s = sum(a)
for i in range(len(a)):
    s = (s-a[i])
    result += s % 1000000007 * a[i]
print(result % 1000000007)
### BUGGY CODE ###

import sys
from collections import Counter

input = sys.stdin.readline


def main():
    S = input().rstrip()

    n = len(S)
    T = [0] * (n+1)
    for i in reversed(range(n)):
        T[i] = (10**(n-1-i) * int(S[i]) + T[i+1]) % 2019

    c = Counter(T)
    ans = 0
    for v in c.values():
        ans += v*(v-1)//2  # vC2
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline

P = 2019

def main():
    S = input().rstrip()

    n = len(S)
    counts = [0] * P
    counts[0] += 1
    T = 0
    d = 1
    for s in reversed(S):
        T = (T + (d * int(s)) % P) % P
        d = (d * 10) % P
        counts[T] += 1

    ans = 0
    for c in counts:
        ans += c*(c-1)//2  # cC2
    print(ans)


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

N, D, A = map(int, input().split())
S = [list(map(int, input().split())) for _ in range(N)]

S.sort()
cnt = 0

for i in range(N):
    if S[i][1] <= 0:
        continue
    if S[i][1] % A == 0:
        dmg = S[i][1]
        cnt += S[i][1] // A
    else:
        dmg = A * (S[i][1]//A + 1)
        cnt += S[i][1]//A + 1
    max_X = S[i][0] + D*2
    j = i + 1
    while j < N:
        if S[j][0] > max_X:
            break
        S[j][1] -= dmg
        j += 1

print(cnt)


### FIXED CODE ###

from collections import deque
import math

import sys
input = sys.stdin.readline

N, D, A = map(int, input().split())
S = [0]*N
atack = deque()
for i in range(N):
    x, h = map(int, input().split())
    S[i] = [x, h]

S.sort()
cnt = 0
dmg = 0
for i in range(N):
    while atack:
        if atack[0][0] < S[i][0]:
            x, d = atack.popleft()
            dmg -= d
        else:
            break

    if S[i][1] <= dmg:
        continue
    bomb = math.ceil((S[i][1]-dmg)/A)
    atack.append([S[i][0]+2*D, A*bomb])
    cnt += bomb
    dmg += A*bomb

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

def bfs(start, count):
    global visited, color
    temp = []
    for hh, ww in start:
        if (hh in range(h)) & (ww in range(w)):
            color[hh][ww] = min(count, color[hh][ww])
            visited.add(str(hh) + "_" + str(ww))
            h_w_list = [[hh + 1, ww], [hh, ww + 1], [hh - 1, ww], [hh, ww - 1]]
            for h_, w_ in h_w_list:
                if (str(h_) + "_" + str(w_)) not in visited:
                    if (h_ in range(h)) & (w_ in range(w)):
                        temp.append([h_, w_])
    if len(temp) > 0:
        bfs(temp, count + 1)

inf = 10 ** 9
h, w = map(int, input().split())
a = []
for _ in range(h):
    a.append(list(input()))
color = [[inf for _ in range(w)] for _ in range(h)]
start = []
visited = set([])
for hh in range(h):
    for ww in range(w):
        if a[hh][ww] == "#":
            start.append([hh, ww])
            color[hh][ww] = 0
bfs(start, 0)
colored = []
for c in color:
    colored.extend(c)
print(max(colored))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

moves = [(0,1),(0,-1),(1,0),(-1,0)] #全方向調べる

ans = -1
while q:
  qq = []
  ans += 1
  for x,y in q:
    if not visited[x-1][y]:
      visited[x-1][y] = True
      qq.append((x-1,y))
    if not visited[x+1][y]:
      visited[x+1][y] = True
      qq.append((x+1,y))
    if not visited[x][y-1]:
      visited[x][y-1] = True
      qq.append((x,y-1))
    if not visited[x][y+1]:
      visited[x][y+1] = True
      qq.append((x,y+1))
  q = qq
  
print(ans)
### BUGGY CODE ###

def main():
    import sys
    input=sys.stdin.readline
    h,n=map(int,input().split())
    a=[[int(i) for i in input().split()]for i in range(n)]
    
    dp=[float('inf')]*(h+1) #0-9
    dp[h]=0
    mini=float('inf')
    for i in reversed(range(0,h+1)):
        if dp[i]==float('inf'):
            continue
        for ata,mp in a:
            if i-ata<=0:
                tmp=dp[i]+mp
                mini=min(mini,tmp)
                continue
            dp[i-ata]=min(dp[i-ata],dp[i]+mp)
    print(mini)

if __name__=='__main__':
    main()

### FIXED CODE ###


h,n=map(int,input().split())
a=[[int(i) for i in input().split()]for i in range(n)]
inf=10**9
dp=[inf]*(h+1) #0-9
dp[0]=0
mini=inf
for i in range(h+1):
    if dp[i]==inf:
        continue
    for ata,mp in a:
        if i+ata>=h:
            tmp=dp[i]+mp
            mini=min(mini,tmp)
            continue
        dp[i+ata]=min(dp[i+ata],dp[i]+mp)
print(mini)
### BUGGY CODE ###

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

point = [K] * N
for _ in range(Q):
    winnner = int(input())
    for idx in range(N):
        point[idx] -= 1
    point[winnner-1] += 1

for p in point:
    if(p>0):
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

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

point = [0] * N
for _ in range(Q):
    winnner = int(input())
    point[winnner-1] += 1

for p in point:
    if(p>Q-K):
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n = int(input(''))
adl = input('')

a = list(map(int,adl.split(' ')))

number = 0

mod = 7+1000000000

amari = 0



for i in range(n):
    aa = 0
    for e in range(n-i-1):
        j = i+e+1
        aa = aa + a[j]
    number = number + (a[i] * aa)
amari = number % mod
print(amari)


### FIXED CODE ###

n = int(input(''))
adl = input('')

a = list(map(int,adl.split(' ')))

number = 0

mod = 1000000007

amari = 0

all_a = 0

for i in range(n):
    all_a = all_a + a[i]

for i in range(n):
    all_a = all_a - a[i]
    number = number + (a[i] * all_a)
    number = number % mod
amari = number % mod
print(amari)
### BUGGY CODE ###


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

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


ans = 10**100

for k in range(1,N+1):
    cur = (N+k) * X
    dp = []
    dpnum = []

    for i in range(1,N+1,k):
        sum = 0
        num = 0
        for j in range(i,min(i+k,N+1)):
            sum += a[N-j]
            num += 1
        dp.append(sum)
        dpnum.append(num)


    count = 0
    for i in range(len(dp)):
        if i == 0:
            cur += dp[i] * 5
        else:
            cur += dp[i] * (2*(i+1) + 1)

    """
    for i in range(1,N+1,k):

        num = min(i+k-1,N) - i + 1

        if count == 0:
            cur += dp[count] * 5 * num
        else:
            cur += dp[count] * (2*(count+1) + 1) * num

        
        count += 1
    """
        
    ### print(dp, dpnum, cur)
    ans = min(ans, cur)

print(ans)



### FIXED CODE ###


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

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

a = a[::-1]

dp = [0 for i in range(N+1)]
for i in range(1,N+1):
    dp[i] = a[i-1] + dp[i-1]

ans = 10**100

for k in range(1,N+1):
    cur = (N+k) * X


    count = 1
    i = k
    while 1:
        first = i - k
        last = min(N,i)
        flag = False
        if i > N:
            flag = True

        if count == 1:
            cur += dp[last] * 5
        else:
            cur += (dp[last] - dp[first]) * (2*count + 1)

        count += 1
        i += k
        
        if flag:
            break


        
    ### print(dp, cur)
    ans = min(ans, cur)

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

#coding: utf-8
N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [float("inf") for _ in range(N)]
dp[0] = 0
for i in range(1, N):
    M = i if i <= K else K
    for k in range(1, M+1):
        dp[i] = min(dp[i], dp[i-k] + abs(h[i] - h[i-k]))
print(dp[N-1])

### FIXED CODE ###

#coding: utf-8
import sys
input = sys.stdin.readline
def main(N, K, h):
    dp = [float("inf")] * N
    dp[0] = 0
    for i in range(1, N):
        dp[i] = min(dp[i], min([dp[i-k] + abs(h[i] - h[i-k]) for k in range(1, min(i, K)+1)]))
    print(dp[N-1])
if __name__ == "__main__":
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    main(N, K, h)
### BUGGY CODE ###

import math
x,y = map(int,input().split())
mod = 10**9+7

if (2*x-y)%3 != 0 or (-x+2*y)%3 != 0:
  print(0)
  exit()
  
a = ((2*x-y)//3)%mod
b = ((-x+2*y)//3)%mod


def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

print(cmb(a+b,a)%mod)


### FIXED CODE ###

import math
x,y = map(int,input().split())
mod = 10**9+7

if (2*x-y)%3 != 0 or (-x+2*y)%3 != 0 or y>2*x or x>2*y:
  print(0)
  exit()
  
a = ((2*x-y)//3)%mod
b = ((-x+2*y)//3)%mod


def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

print(cmb(a+b,a)%mod)
### BUGGY CODE ###

MOD = 10**9+7
s = input()
n = len(s)
dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1

for i in range(n):
    digit = n-1-i
    x = s[digit]
    X = []
    if x != '?':
        X.append(int(x)*pow(10, i, 13) % 13)
    else:
        for num in range(10):
            X.append(num*pow(10, i, 13) % 13)
    for j in range(13):
        for x in X:
            dp[i+1][(j+x) % 13] += dp[i][j]
            dp[i+1][(j+x) % 13] %= MOD

print(dp[-1][5])


### FIXED CODE ###

MOD = 10**9+7
s = input()
n = len(s)
dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1

for i in range(n):
    digit = n-1-i
    x = s[digit]
    X = []
    if x != '?':
        X.append(int(x)*pow(10, i, 13) % 13)
    else:
        for num in range(10):
            X.append(num*pow(10, i, 13) % 13)
    for j in range(13):
        for x in X:
            dp[i+1][(j+x) % 13] += dp[i][j]
            dp[i+1][(j+x) % 13] %= MOD

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

import heapq

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

A = [int(i)*(-1) for i in input().split()]



# print(A)
# for i in range(M):
# 	max_index = A.index(max(A))
# 	A[max_index] = int(A[max_index]/2)

# print(sum(A))


for i in range(M):
	heapq.heapify(A)

	min = heapq.heappop(A)
	# 最小値を削除と値を渡す
	# print(A)
	# print(min)

	heapq.heappush(A,int(min/2))
	# print(A)


print(sum(A)*(-1))

### FIXED CODE ###

import heapq
import sys
input = sys.stdin.readline

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

A = [int(i)*(-1) for i in input().split()]



# print(A)
# for i in range(M):
# 	max_index = A.index(max(A))
# 	A[max_index] = int(A[max_index]/2)

# print(sum(A))
heapq.heapify(A)

for i in range(M):
	

	min = heapq.heappop(A)
	# 最小値を削除と値を渡す
	# print(A)
	# print(min)

	heapq.heappush(A,int(min/2))
	# print(A)


print(sum(A)*(-1))
### BUGGY CODE ###

N = int(input())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

L = len(make_divisors(N))

ans = 0
for i in range(L):
    t = N
    while t%(make_divisors(N)[i]) == 0:
        t = t//make_divisors(N)[i]
    if t%(make_divisors(N)[i]) == 1:
        ans = ans + 1
        
print(ans + len(make_divisors(N-1)) -1)

### FIXED CODE ###

N = int(input())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

L = len(make_divisors(N))

A = make_divisors(N)

ans = 0
for i in range(1,L):
    t = N
    while t%(A[i]) == 0:
        t = t//A[i]
    if t%A[i] == 1:
        ans = ans + 1
        
print(ans + len(make_divisors(N-1)) -1)
### BUGGY CODE ###

from collections import Counter
S = input()
S = S + '0'
mod = 2019
p = [0] * mod
r = 0
d = 1
for s in reversed(S):
  t = int(s)%mod
  r += t*d
  r %= mod
  d *= 10%mod
  p[r] += 1

#p.append(0)
#ans = 0
#c = Counter(p)
#for k,n in c.most_common():
#  if n > 1:
#    ans += 1
#  else:break
  
print(sum([i*(i-1)//2 for i in p]))

### FIXED CODE ###

S = input()
S = S + '0'
mod = 2019
p = [0] * mod
r = 0
d = 1
for s in reversed(S):
  t = int(s)%mod
  r += t*d
  r %= mod
  d = d*10%mod
  p[r] += 1

print(sum([i*(i-1)//2 for i in p]))
### BUGGY CODE ###

N, M = map(int, input().split(" "))
A = list(map(int, input().split(" ")))
R = [0] * (N+1)

ans = 0
temp = 0

for i in range(N):
    R[i+1] = temp + A[i]
    temp = R[i+1]

for j in range(1,N+1):
    for d in range(1,N+1):
        if j - d >= 0:
            if (R[j] - R[j-d]) % M == 0:
                ans += 1
print(ans)

### FIXED CODE ###

# coding: utf-8
# Your code here!
N, M = map(int, input().split(" "))
A = list(map(int, input().split(" ")))
R = [0] * (N+1)
S = [0] * (N+1)
S_dict = {}

ans = 0
temp = 0

for i in range(N):
    R[i+1] = temp + A[i]
    S[i+1] = R[i+1] % M
    temp = R[i+1]

for s in S:
    if s in S_dict:
        S_dict[s] += 1
    else:
        S_dict[s] = 1

for v in S_dict.values():
    ans += int(v*(v-1)/2)

print(ans)