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

from functools import lru_cache
N = int(input())
A = list(map(int, input().split()))
INF = 1.0e+100

@lru_cache(maxsize=None)
def f(l, r):
  if r - l == 1:
    return (A[l], 0)
  ret = (INF, INF)
  for i in range(l+1, r):
    (lr, lc) = f(l, i)
    (rr, rc) = f(i, r)
    if lr+rr+lc+rc < ret[1]:
      ret = (lr+rr, lr+rr+lc+rc)
  return ret

print(f(0, N)[1])


### FIXED CODE ###

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

INF = 1.0e+100


dp = [[[None, INF] for _ in range(N+1)] for _ in range(N+1)]
for i in range(N):
    dp[i][i+1] = [A[i], 0]

for g in range(2, N+1):
    for l in range(N-g+1):
        r = l + g
        for i in range(l+1, r):
            lv, lc = dp[l][i]
            rv, rc = dp[i][r]
            nc = lv + rv + lc + rc
            if dp[l][r][1] > nc:
                dp[l][r][0] = lv + rv
                dp[l][r][1] = nc

print(dp[0][N][1])
### BUGGY CODE ###

X = int(input())

ans = 1

for i in range(1, X+1):
    for j in range(2, X+1):
        bp = i**j
        if bp <= X and bp > ans:
            ans = bp

print(ans)


### FIXED CODE ###

X = int(input())

ans = 1

for i in range(1, X+1):
    for j in range(2, X+1):
        bp = i**j
        if bp <= X and bp > ans:
            ans = bp
        if X < bp:
            break

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

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6+5)

class Node:
    def __init__(self):
        self.child = {}
        self.counts = defaultdict(int)

    def add(self, s, bucket, idx_s):
        c = s[idx_s]
        if c not in self.child:
            self.child[c] = Node()
        for i, cnt in enumerate(bucket):
            if cnt:
                self.counts[i] += 1
        bucket[c] -= 1
        if idx_s >= 1:
            self.child[c].add(s, bucket, idx_s-1)

    def get(self, s, idx_s):
        c = s[idx_s]
        if idx_s > 0:
            return self.child[c].get(s, idx_s-1)
        else:
            return self.counts[c]

trie = Node()
N = int(input())
S = [[ord(c)-97 for c in input()] for _ in range(N)]
for s in S:
    b = [0] * 26
    for c in s:
        b[c] += 1
    trie.add(s, b, len(s)-1)
ans = -N
for s in S:
    ans += trie.get(s, len(s)-1)
print(ans)


### FIXED CODE ###

class Node:
    def __init__(self):
        self.child = [None] * 26
        self.counts = [0] * 26

    # def add(self, s, bucket, idx_s):
    #     c = s[idx_s]
    #     if self.child[c] is None:
    #         self.child[c] = Node()
    #     for i, cnt in enumerate(bucket):
    #         if cnt:
    #             self.counts[i] += 1
    #     bucket[c] -= 1
    #     if idx_s >= 1:
    #         self.child[c].add(s, bucket, idx_s - 1)
    #     else:
    #         Leaves.append(self.counts)

    def add(self, s, bucket):
        node = self
        for idx_s, c in zip(range(len(s)-1, -1, -1), s[::-1]):
            if node.child[c] is None:
                node.child[c] = Node()
            for i, cnt in enumerate(bucket):
                if cnt:
                    node.counts[i] += 1
            bucket[c] -= 1
            if idx_s > 0:
                node = node.child[c]
        Leaves.append(node.counts)

    # def get(self, s, idx_s):
    #     c = s[idx_s]
    #     if idx_s > 0:
    #         return self.child[c].get(s, idx_s-1)
    #     else:
    #         return self.counts[c]

Leaves = []
trie = Node()
N = int(input())
S = [[ord(c)-97 for c in input()] for _ in range(N)]
for s in S:
    b = [0] * 26
    for c in s:
        b[c] += 1
    trie.add(s, b)
ans = -N
# for s in S:
#     ans += trie.get(s, len(s)-1)
for s, l in zip(S, Leaves):
    ans += l[s[0]]
print(ans)
### BUGGY CODE ###


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


from collections import Counter

M = 10**9 + 7
cur = {0: 1}
for B in A:
    nxt = Counter()
    C = [1 << i for i, v in enumerate(B) if v == 1]
    for s, v in cur.items():
        v %= M
        for b in C:
            if (s & b) != 0:
                continue
            m = s | b
            nxt[m] += v
    cur = nxt
print(cur[(1<<N) - 1] % M)


### FIXED CODE ###


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

from collections import Counter

M = 10**9 + 7
cur = [0] * (1<<N)
cur[0] = 1
for B in A:
    nxt = [0] * (1 << N)
    C = [1 << i for i, v in enumerate(B) if v == 1]
    for s, v in enumerate(cur):
        if v == 0:
            continue
        v %= M
        for b in C:
            if (s & b) != 0:
                continue
            nxt[s | b] += v
    cur = nxt
print(cur[(1<<N) - 1] % M)
### BUGGY CODE ###

def main():
    from collections import deque
    H, W = list(map(int, input().split()))
    maps =[list(input()) for _ in range(H)]
    mv = {(1, 0), (-1, 0), (0, 1), (0, -1)}

    ans = 0
    for i in range(H):
        for j in range(W):
            if maps[i][j] == '#':
                continue
            stk = deque([[i,j,0]])
            seen = [[False]*W for _ in range(H)]
            while len(stk) > 0:
                l = stk.pop()
                i = l[0]
                j = l[1]
                ct = l[2]
                seen[i][j] = True
                for k in mv:
                    x = i+k[0]
                    y = j+k[1]
                    if 0 <= x < H and 0 <= y < W and \
                        maps[x][y] == '.' and seen[x][y] == False:
                            stk.appendleft([x, y, ct+1])
            ans = max(ans, ct)
    print(ans)

if __name__=='__main__':
    main()

### FIXED CODE ###

H, W = list(map(int, input().split()))
S =[list(input()) for _ in range(H)]
N=H*W
INF=float('inf')
L=[[INF]*N for _ in range(N)]
for i in range(N):
    h=i//W
    w=i%W
    # print(i,h,w)
    if S[h][w]=='.':
        L[i][i]=0
    if w>0 and S[h][w-1]=='.':
        L[i][i-1]=1
    if w<W-1 and S[h][w+1]=='.':
        L[i][i+1]=1
    if h>0 and S[h-1][w]=='.':
        L[i][i-W]=1
    if h<H-1 and S[h+1][w]=='.':
        L[i][i+W]=1
# print(L)

for i in range(N):
    via=L[i]
    if via[i]==INF:
        continue
    for j in range(N):
        st=L[j]
        if st[j]==INF:
            continue
        for k in range(N):
            L[j][k]=min(st[i]+via[k], st[k])
# print(L)
ans=0
for i in range(N):
    for j in range(N):
        if L[i][j]!=INF:
            ans=max(ans,L[i][j])
print(ans)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

count = 0
for i in range(N // R + 1):
    for j in range(N // G + 1):
        tmp = N - i * R - j * G
        if tmp < 0:
            continue
        if tmp % B == 0:
            count += 1

print(count)

### FIXED CODE ###

R, G, B, N = map(int, input().split())

count = 0
tmp1 = N + R
for i in range(N // R + 1):
    tmp1 -= R
    tmp2 = tmp1 + G
    for j in range(N // G + 1):
        tmp2 -= G
        if tmp2 < 0:
            continue
        if tmp2 % B == 0:
            count += 1

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

N,Q=map(int,input().split())
S=input()
lst=[]
for i in range(Q):
  l,r=map(int,input().split())
  x=S[l-1:r]
  lst.append(x.count('AC'))
for i in lst:
  print(i)

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
lst=[0]*(N-1)
x=0
for i in range(len(S)-1):
  if S[i:i+2]=='AC':
    x+=1
  lst[i]=x
lst=[0]+lst
lst2=[]
for i in range(Q):
  l,r=map(int,input().split())
  lst2.append(lst[r-1]-lst[l-1])
for i in lst2:
  print(i)
### BUGGY CODE ###

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

def rec(l, r, xl, xr) :
    if l + 1 == r :
        return 0
        
    ret = float('inf')
    for m in range(l + 1, r) :
        ret = min(ret, rec(l, m, xl, xl+xr) + rec(m, r, xl+xr, xr) + A[m] * (xl+xr))
    return ret
    
print(A[0] + rec(0, N-1, 1, 1) + A[N-1])

### FIXED CODE ###

# ikatakosさんの提出を見てlru_cacheなるものを知った。
# まだまだ知らないことがたくさんありますね。

from functools import lru_cache

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

@lru_cache(maxsize=None)
def rec(l, r, xl, xr) :
    if l + 1 == r :
        return 0
    
    return min(rec(l, m, xl, xl+xr)+rec(m, r, xl+xr, xr)+A[m]*(xl+xr) for m in range(l+1, r))
    
print(A[0] + rec(0, N-1, 1, 1) + A[N-1])
### BUGGY CODE ###

N,M=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
mod=10**9+7
sm=[[ 0 for i in range(M)] for j in range(N)]
s1=0
s2=0
if N>M:
  for i in range(N):
    if t[0]==s[i]:
      a=1
    else:
      a=0
    s1=s1+a
    sm[i][0]=s1
    if i<M:
      if s[0]==t[i]:
        a=1
      else:
        a=0
      s2=s2+a
      sm[0][i]=s2
else:
  for i in range(M):
    if s[0]==t[i]:
      a=1
    else:
      a=0
    s2=s2+a
    sm[0][i]=s2
    if i<N:
      if t[0]==s[i]:
        a=1
      else:
        a=0
      s1=s1+a
      sm[i][0]=s1
for i in range(1,N):
  for j in range(1,M):
    if s[i] != t[j]:
      sm[i][j]=sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1]
    else:
      sm[i][j]=sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1]+sm[i-1][j-1]+1
ans=(sm[N-1][M-1]+1)%mod
print(ans)

### FIXED CODE ###

N,M=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
mod=10**9+7
sm=[[ 0 for i in range(M)] for j in range(N)]
s1=0
s2=0
if N>M:
  for i in range(N):
    if t[0]==s[i]:
      a=1
    else:
      a=0
    s1=s1+a
    sm[i][0]=s1
    if i<M:
      if s[0]==t[i]:
        a=1
      else:
        a=0
      s2=s2+a
      sm[0][i]=s2
else:
  for i in range(M):
    if s[0]==t[i]:
      a=1
    else:
      a=0
    s2=s2+a
    sm[0][i]=s2
    if i<N:
      if t[0]==s[i]:
        a=1
      else:
        a=0
      s1=s1+a
      sm[i][0]=s1
for i in range(1,N):
  for j in range(1,M):
    if s[i] != t[j]:
      sm[i][j]=(sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1])%mod
    else:
      sm[i][j]=(sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1]+sm[i-1][j-1]+1)%mod
ans=(sm[N-1][M-1]+1)%mod
print(ans)
### BUGGY CODE ###

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

mod = 10 ** 9 + 7

N = int(input())
vec = [[] for _ in range(N)]
for _ in range(N - 1) :
  A, B = map(int, input().split())
  vec[A-1].append(B-1)
  vec[B-1].append(A-1)

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

def dfs(cur, pre) :
  s = 0
  for nex in vec[cur] :
    if nex == pre :
      continue
    t = dfs(nex, cur)
    s += t
    sub_size[cur].append(t)
  if s != N - 1 :
    sub_size[cur].append(N - 1 - s)

  return s + 1

dfs(0, -1)

fac = [1]
inv = [1]
for _ in range(N) :
  fac.append(fac[-1] * 2 % mod)
  inv.append(pow(fac[-1], mod - 2, mod))

ret = 0
for i in range(N) :
  if len(sub_size[i]) < 2 :
    continue
  
  a, b = 1, 1
  for ss in sub_size[i] :
    a *= inv[ss]
    b += fac[ss] - 1
    a %= mod
    b %= mod
  ret += (1 - a * b) % mod
  ret %= mod

ret = ret * inv[1] % mod

print(ret)

### FIXED CODE ###

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

mod = 10 ** 9 + 7

N = int(input())
vec = [[] for _ in range(N)]
for _ in range(N - 1) :
  A, B = map(int, input().split())
  vec[A-1].append(B-1)
  vec[B-1].append(A-1)

own_size = [0] * N
sub_size = [[] for _ in range(N)]

# pythonのdfs重すぎて自分でstack書かないと通らない。
# く〜〜つらいとこね、これ！！！！
stack = [(0, -1)]
for i in range(N) :
  cur, pre = stack[i]
  for nex in vec[cur] :
    if nex != pre :
      stack.append((nex, cur))

while stack :
  cur, pre = stack.pop()
  if pre != -1 :
    sub_size[pre].append(own_size[cur] + 1)
    own_size[pre] += own_size[cur] + 1
  if own_size[cur] != N - 1 :
    sub_size[cur].append(N - 1 - own_size[cur])

fac = [1]
inv = [1]
div = pow(2, mod - 2, mod)
for _ in range(N) :
  fac.append(fac[-1] * 2 % mod)
  inv.append(inv[-1] * div % mod)

ret = 0
for i in range(N) :
  if len(sub_size[i]) < 2 :
    continue

  a, b = 1, 1
  for ss in sub_size[i] :
    a *= inv[ss]
    b += fac[ss] - 1
    a %= mod
    b %= mod
  ret += (1 - a * b) % mod
  ret %= mod

ret = ret * div % mod

print(ret)
### BUGGY CODE ###

import itertools

h, w, m = map(int,input().split(' '))
x = [0] * 300001
y = [0] * 300001
z = []
mx, my = 0, 0
for i in range(m):
    a, b = map(int,input().split(' '))
    x[a] += 1
    y[b] += 1
    mx = max(mx, x[a])
    my = max(my, y[b])
    z.append((a, b))
x1 = [i for i in range(300001) if x[i] == mx]
y1 = [i for i in range(300001) if y[i] == my]
z1 = list(itertools.product(x1, y1))
if set(z) >= set(z1): print(mx + my - 1)
else: print(mx + my)

### FIXED CODE ###

import itertools

h, w, m = map(int,input().split(' '))
x = [0] * 300001
y = [0] * 300001
z = []
mx, my = 0, 0
for i in range(m):
    a, b = map(int,input().split(' '))
    x[a] += 1
    y[b] += 1
    mx = max(mx, x[a])
    my = max(my, y[b])
    z.append((a, b))
x1 = x.count(mx)
y1 = y.count(my)
z1 = x1 * y1
for i, j in z:
    if x[i] == mx and y[j] == my:
        z1 -= 1
if z1: print (mx + my)
else: print (mx + my - 1)
### BUGGY CODE ###

a,b,c,n = tuple(int(x) for x in raw_input().split(' '))

ans = 0
for i in xrange(0, n/a+1):
  for j in xrange(0, n/b+1):
    k = (n - i*a - j*b)/c
    #print i,j,k,i*a+j*b+k*c
    if i*a+j*b+k*c == n and k >= 0:
      ans += 1
print ans

### FIXED CODE ###

a,b,c,n = tuple(int(x) for x in raw_input().split(' '))

ans = 0
for i in xrange(0, n/a+1):
  for j in xrange(0, n/b+1):
    k = (n - i*a - j*b)/c
    #print i,j,k,i*a+j*b+k*c
    if i*a+j*b+k*c == n and k >= 0:
      ans += 1
print ans
### BUGGY CODE ###

from collections import defaultdict
from heapq import heapify, heappop
import heapq
n,m,s,t =list(map(int,input().split()))

MAX_VAL = 10**20
uvab =  [list(map(int,input().split())) for _ in range(m)]
jpy_cost = defaultdict(lambda :defaultdict(lambda :MAX_VAL))
snuke_cost = defaultdict(lambda :defaultdict(lambda :MAX_VAL))


for u,v,a,b in uvab:
    u=u-1
    v=v-1
    jpy_cost[u][v] = a
    jpy_cost[v][u] =a
    snuke_cost[u][v]=b
    snuke_cost[v][u]=b


# Dijktra's shortest path algorithm. Prints the path from source to target.


def dijkstra(adj, source):
    INF = MAX_VAL
    dist = [INF for x in range(n)]
    dist[source] = 0
    PQ = []
    heapq.heappush(PQ, [dist[source], source])

    while (PQ):
        u = heapq.heappop(PQ)  # u is a tuple [u_dist, u_id]
        u_dist = u[0]
        u_id = u[1]
        if u_dist == dist[u_id]:
            # if u_id == target:
            #    break
            for v in adj[u_id]:
                v_id = v
                w_uv = adj[u_id][v]
                if dist[u_id] + w_uv < dist[v_id]:
                    dist[v_id] = dist[u_id] + w_uv
                    heapq.heappush(PQ, [dist[v_id], v_id])

    return dist


jpy_dijk =  dijkstra(jpy_cost,s-1)
snuke_dijk = dijkstra(snuke_cost,t-1)
#
# print(s,t)
# print(jpy_dijk)
# print(snuke_dijk)
# print([jpy_dijk[i]+snuke_dijk[i] for i in range(n)])

#ord n
res = []
min_val = MAX_VAL
for i in reversed(range(n)):
    #都市  i で両替
    val = jpy_dijk[i]+ snuke_dijk[i]
    assert val < MAX_VAL
    min_val=min(min_val,val)
    res.append(min_val)
#ord n
for x in reversed(res):
    print(10**15-  x)


### FIXED CODE ###

from collections import defaultdict
from heapq import heapify, heappop
import heapq
n,m,s,t =list(map(int,input().split()))

MAX_VAL = 10**20
uvab =  [list(map(int,input().split())) for _ in range(m)]
jpy_cost = defaultdict(dict)
snuke_cost = defaultdict(dict)


for u,v,a,b in uvab:
    u=u-1
    v=v-1
    jpy_cost[u][v] = a
    jpy_cost[v][u] =a
    snuke_cost[u][v]=b
    snuke_cost[v][u]=b


# Dijktra's shortest path algorithm. Prints the path from source to target.


def dijkstra(adj, source):
    INF = MAX_VAL
    dist = [INF for x in range(n)]
    dist[source] = 0
    PQ = []
    heapq.heappush(PQ, [dist[source], source])

    while (PQ):
        u_dist,u_id = heapq.heappop(PQ)  # u is a tuple [u_dist, u_id]
        if u_dist == dist[u_id]:
            for v in adj[u_id]:
                w_uv = adj[u_id][v]
                if dist[u_id] + w_uv < dist[v]:
                    dist[v] = dist[u_id] + w_uv
                    heapq.heappush(PQ, [dist[v], v])
    return dist


jpy_dijk =  dijkstra(jpy_cost,s-1)
snuke_dijk = dijkstra(snuke_cost,t-1)
#
# print(s,t)
# print(jpy_dijk)
# print(snuke_dijk)
# print([jpy_dijk[i]+snuke_dijk[i] for i in range(n)])

#ord n
res = []
min_val = MAX_VAL
for i in reversed(range(n)):
    #都市  i で両替
    val = jpy_dijk[i]+ snuke_dijk[i]
    assert val < MAX_VAL
    min_val=min(min_val,val)
    res.append(min_val)
#ord n
for x in reversed(res):
    print(10**15-  x)
### BUGGY CODE ###


def main():
    N = int(input())
    X = int(input(), 2)

    def popcount(num):
        return bin(num).count("1")

    def f(x):
        temp = x
        count = 0
        while temp > 0:
            temp = temp % popcount(temp)
            count += 1
        return count
    ans = [0]*N
    for i in range(0, N):
        xi = X ^ (1 << i)
        ans[N-i-1] = f(xi)
    for a in ans:
        print(a)
main()

### FIXED CODE ###

N=int(input())
X=input()
num_X = int(X, base=2)
pop_x = X.count("1")
if pop_x <= 1:
    mod0 = pop_x + 1
    res0 = num_X % mod0
else:
    mod1 = pop_x - 1
    mod0 = pop_x + 1
    res1 = num_X % (mod1)
    res0 = num_X % (mod0)

# pops = [0]*(N+20)
for i in range(N):
    tmp = 0
    if X[i] == "0":
        # +
        tmp = (res0 + pow(2, N-i-1, mod0))%mod0
    else:
        if pop_x == 1:
            print(0)
            continue
        tmp = (res1 - pow(2, N-i-1, mod1))%mod1
    
    if tmp == 0:
        print(1)
        continue
    cnt = 1
    while tmp != 0:
        pop = bin(tmp).count("1")
        tmp %= pop
        cnt += 1
    print(cnt)
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m = inpl()
a = inpl()
a.sort()
for i in range(m):
    a[-1] /= 2
    a.sort()
for i in range(n):
    a[i] = math.floor(a[i])
print(sum(a))

### FIXED CODE ###

from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m = inpl()
a = inpl()
hq = []
heapq.heapify(hq)
ans = 0
for i in range(n):
    tt = a[i]
    heapq.heappush(hq,-tt)
for i in range(m):
    tmp = heapq.heappop(hq)
    tmp /= 2
    heapq.heappush(hq,tmp)
    # print(hq)
for i in range(n):
    tttt = heapq.heappop(hq)
    ans -= math.ceil(tttt)
print(ans)
### BUGGY CODE ###

def INT():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(map(int, input().split()))

N = INT()
A = LI()
mod = 10**9 + 7
ans = 0

for i in range(N):
    for j in range(i + 1, N):
        ans += (A[i] % mod) * (A[j] % mod)
        ans %= mod
        
print(ans)

### FIXED CODE ###

def INT():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(map(int, input().split()))

N = INT()
A = LI()
mod = 10**9 + 7
sm = sum(A) - A[0]
ans = 0

for i in range(N - 1):
    ans += A[i] * sm
    ans %= mod
    sm -= A[i + 1]
    
print(ans)
### BUGGY CODE ###

n = int(input())

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

q = int(input())

for i in range(q):
    
    b,c = map(int, input().split())
    
    if b in a:
        index = [i for i, x in enumerate(a) if x == b]
        for i in index:
            a[i] = c

    print(sum(a))

### FIXED CODE ###

n = int(input())

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

q = int(input())

#初期化

a_dic ={}
ans = 0

for i in a:
    if i not in a_dic:
        a_dic[i] = 1
    else:
        a_dic[i] += 1
    
    ans += i

#print(ans)
#a_sorted = sorted(a)
for i in range(q):
    #ans = 0
    b,c = map(int, input().split())
    #print(a_dic)
    
    if b in a_dic:
        if c not in a_dic:
            a_dic[c] = a_dic[b]

        else:
            tmp_c = a_dic[c]
            tmp_c += a_dic[b]
            a_dic[c] = tmp_c
        tmp_a = (c-b) * a_dic[b]
        a_dic.pop(b)
        ans += tmp_a
    print(ans)
### BUGGY CODE ###


from operator import itemgetter
 
n,m=map(int, input().split())
A=[]
a=0
b=0
for i in range(m):
  a,b=map(int, input().split())
  A.append([a,b])

A.sort(key=itemgetter(1))
bri=[1 for i in range(n)] #bri[0]は1,2番目の島をつなぐ

count=0

#print(A)
for i in range(m):
  #print(i)
  a=A[i][0]
  b=A[i][1]
  #print(bri[a-1:b-1])

  zero=0
  for j in range(a-1,b-1):
    if bri[j]==0:
      zero=1
      
  if zero==0:


    #print(bri[a-1:b-1])
    bri[b-2]=0
    #print(bri)
    #print(A[i])
    #print(A)
    #print(bri)
    count+=1

print(count)


### FIXED CODE ###


from operator import itemgetter
 
n,m=map(int, input().split())
A=[]
B=[]
a=0
b=0
for i in range(m):
  a,b=map(int, input().split())
  A.append([a,b])

A.sort(key=itemgetter(1))
bri=0 #取った橋のうち番号最大の島のもの。bri=5なら4,5番目の島の橋

count=0

for i in range(m):
  a=A[i][0]
  b=A[i][1]
  
  if a>=bri:
    bri=b
    count+=1

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

inp = input().split()

i = 1

while i <= pow(10,18):
	if i % int(inp[0])  == 0 and i % int(inp[1]) != 0:
		print(i)
		break
	i *= int(inp[0])


if i >= pow(10,18):
	print(-1)

### FIXED CODE ###

inp = input().split()

i = 1
x = 0

while i <= pow(10,18):
	if inp[0] == "1" and inp[1] == "1":
		print(-1)
		x = 1
		break
	if i % int(inp[0])  == 0 and i % int(inp[1]) != 0:
		print(i)
		x = 1
		break
	i *= int(inp[0])

if x == 0:
	print(-1)
### BUGGY CODE ###

s =  ['Z'] + list(input())

ret = 0
i = 0

while i < len(s) :
    if s[i:i+3] == ['A', 'B', 'C'] :
        s[i:i+3] = ['B', 'C', 'A']
        ret += 1
        i -= 1
    else :
        i += 1

print(ret)

### FIXED CODE ###

s =  list(input())

ret = 0
i = 0
a = 0
bc = 0

while True :
    while i < len(s) and s[i] == 'A' :
        a += 1
        i += 1

    while i < len(s) - 1 and s[i:i+2] == ['B', 'C']  :
        bc += 1
        i += 2

    ret += a * bc

    bc = 0

    if i < len(s) and s[i] != 'A' :
        a = 0
        
    while i < len(s) and s[i] != 'A' :
        i += 1

    if i >= len(s) - 1 :
        break
    

print(ret)
### BUGGY CODE ###

x, y, z, k = map(int, input().split())

a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
c.sort(reverse=True)

e = [a_i + b_j for b_j in b for a_i in a]
e.sort(reverse=True)

ans = [e_i + c_j for c_j in c[:k] for e_i in e[:k]]
ans.sort(reverse=True)

for idx in range(k):
    print(ans[idx])

### FIXED CODE ###

x, y, z, k = map(int, input().split())

a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
c.sort(reverse=True)

e = [a_i + b_j for b_j in b for a_i in a]
e.sort(reverse=True)

ans = [e_i + c_j for c_j in c[:k] for e_i in e[:k]]
ans.sort(reverse=True)

for i in ans[:k]:
    print(i)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
B = []
for a in A:
    if a in B:
        B.remove(a)
    else:
        B.append(a)

print(len(B))


### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()
A.append(10**9+1)

now = 0
cnt = 0
ans = 0
for a in A:
    if a == now:
        cnt += 1
    else:
        now = a
        ans += cnt % 2
        cnt = 1

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

N = int(input())
a = list(map(int,input().split()))
ans = [a[0]]
for i,j in enumerate(a[1:]):
    if(N%2==0):
        if(i%2==0):
            ans.insert(0,j)
        else:
            ans.append(j)
    else:
        if(i%2==1):
            ans.insert(0,j)
        else:
            ans.append(j)
print(" ".join(map(str,ans)))

### FIXED CODE ###

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

ans = [a[0]]
check = N%2==0
for i,j in enumerate(a[1:]):
    if(check):
        if(i%2==0):
            ans.insert(0,j)
        else:
            ans.append(j)
    else:
        if(i%2==1):
            ans.insert(0,j)
        else:
            ans.append(j)
print(" ".join(map(str,ans)))