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

n = int(input())
l = list(map(int,input().split()))
import bisect
l.sort()
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        x = bisect.bisect_left(l[j+1:],l[i]+l[j])
        ans += x
print(ans)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()
 
from bisect import bisect_left
ans = 0
for i in range(n):
  for j in range(i+1, n):
    t = l[i]+l[j]
    idx = bisect_left(l, t)
    ans += max(0, idx-j-1)
print(ans)
### BUGGY CODE ###

import numpy as np
N,K,Q = map(int, input().split())

points = np.array([K] * N)

for i in range(Q):
  ans = int(input())
  points -= 1
  points[ans-1] += 1

for i in range(N):
  if points[i] > 0:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

import numpy as np
N,K,Q = map(int, input().split())

points = np.array([K-Q] * N)
getpoints = np.array([0] * N)

for i in range(Q):
  ans = int(input())
  getpoints[ans-1] +=1

points += getpoints

for i in range(N):
  if points[i] > 0:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

import sys
max_int = 1000000001  # 10^9+1
min_int = -max_int

n = int(input())
a = map(int, sys.stdin.readline().split())

prod = 1
for one in a:
    if not one:
        print(0)
        break
    prod *= one
else:
    if prod > 10**18:
        print(-1)
    else:
        print(prod)




### FIXED CODE ###

import sys
n = int(input())
a = list(map(int, sys.stdin.readline().split()))

a.sort(reverse=True)

if a[-1] == 0:
    print(0)
else:
    limit = 10**18
    prod = 1
    for one in a:
        prod *= one
        if prod > limit:
            print(-1)
            break
    else:
        print(prod)
### BUGGY CODE ###

n=int(input())
D=[int(i) for i in input().split()]
if n>=24:
  print(0)
else:
  ans=0
  for i in range(2**(n-1)):
    C=[0]*25
    C[0]=1
    C[24]=1
    C[D[0]]+=1
    for j in range(n-1):
      if i&(1<<j):
        C[24-D[j+1]]+=1
      else:
        C[D[j+1]]+=1
    cur=24
    if max(C)==1:
      t=0
      for j in range(1,25):
        if C[j]==1:
          cur=min(cur,t+1)
          t=0
        else:
          t+=1
    else:
      cur=0
    ans=max(ans,cur)
  print(ans)

### FIXED CODE ###

n=int(input())
D=[int(i) for i in input().split()]
C=[1]+[0]*12

for d in D:
  C[min(d,24-d)]+=1
if max(C)>2 or C[0]>1 or C[12]>1:
  print(0)
else:
  ans=0
  
  for i in range(2**(11)):
    CC=[1]+[0]*23+[1]
    for j in range(1,12):
      if C[j]==2:
        CC[j]=1
        CC[24-j]=1
      elif C[j]==1:
        if i&(1<<(j-1)):
          CC[j]=1
        else:
          CC[24-j]=1
    if C[12]==1:
      CC[12]=1
    cur=24
    t=0
    for j in range(1,25):
      if CC[j]==1:
        cur=min(cur,t+1)
        t=0
      else:
        t+=1
    ans=max(ans,cur)
  print(ans)
### BUGGY CODE ###

import collections

def main():
    s = input()
    t = input()

    ns, nt = len(s), len(t)
    cs, ct = set(list(s)), set(list(t))
    for c in ct:
        if c not in cs: return -1

    d = collections.defaultdict(list)
    for i in range(ns):
        if s[i] in ct: d[s[i]].append(i)

    i = 0
    for c in t:
        while d[c][0] < i:
            d[c].append(d[c].pop(0)+ns)
        i = d[c][0]+1
    return i


if __name__ == '__main__':
    print(main())

### FIXED CODE ###

import collections
import bisect

def main():
    s = input()
    t = input()

    ns, nt = len(s), len(t)
    cs, ct = set(list(s)), set(list(t))
    for c in ct:
        if c not in cs: return -1

    # def unittest(s, t):
    #     i = 0
    #     for c in t:
    #         while s[i % ns] != c:
    #             i += 1
    #         i += 1
    #     return i

    d = collections.defaultdict(list)
    for i in range(ns):
        if s[i] in ct: d[s[i]].append(i)
    # print(s, t)
    i = 0
    for c in t:
        # binary search
        j = i % ns
        k = bisect.bisect_left(d[c], j)
        if k == len(d[c]):
            i = (i // ns + 1)*ns + d[c][0]
        else:
            if j <= d[c][k]:
                i = (i // ns)*ns + d[c][k]
            else:
                i = (i // ns + 1)*ns + d[c][k]
        # print(i)
        i += 1
    return i
    # return i, unittest(s, t)


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

import sys
n = int(input())
s = list(map(int, input().split()))
tmp = []
for i in s:
    if i in tmp:
        print('NO')
        sys.exit()
    tmp.append(i)
print('YES')

### FIXED CODE ###

import sys
n = int(input())
s = list(map(int, input().split()))
s.sort()
k = 0
for i in s:
    if i == k:
        print('NO')
        sys.exit()
    k = i
print('YES')
### BUGGY CODE ###

H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]

dp = [0] * (H + 1)
for h in range(1, H + 1):
    dp[h] = min([dp[max(h - a, 0)] + b for a, b in AB])

print(dp[-1])


### FIXED CODE ###

H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
AB.sort(key=lambda x: x[1])

dp = [0] * (H + 1)
for h in range(1, H + 1):
    dp[h] = min([dp[max(h - a, 0)] + b for a, b in AB])

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

from collections import deque
import sys
import copy

def main():
  input = sys.stdin.readline
  n = int(input())
  a = [None]*n
  for i in range(n):
    a[i] = [int(x)-1 for x in input().split()]
  
  count = 0
  ans = 0
  bef_checked = [int(x) for x in range(n)]
  index = [0]*n
  while True:
    ans += 1
    check = copy.deepcopy(bef_checked)
    bef_checked = []
    already = [False]*n
    flag = True
    for v in check:
      if already[v]:
        continue
      flag = False
      v2 = a[v][index[v]]
      if already[v2]:
        continue
      if v != a[v2][index[v2]]:
        continue
      already[v] = True
      already[v2] = True
      index[v] += 1
      index[v2] += 1
      if index[v] == n-1:
        count += 1
      else:
        bef_checked.append(v)
      if index[v2] == n-1:
        count += 1
      else:
        bef_checked.append(v2)
        
    if flag:
      print(-1)
      sys.exit()
    if count == n:
      break
  
  print(ans)
  

if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
from copy import deepcopy as copy

def main():
    input = sys.stdin.readline
    n = int(input())
    a = [None]*n
    for i in range(n):
        a[i] = [int(x)-1 for x in input().split()]
    
    index = [0]*n
    search = [int(x) for x in range(n)]
    ans = 0
    while True:
        already = set()
        judge = True
        sub = []
        for key in search:
            if index[key] == n-1:
                continue
            key2 = a[key][index[key]]
            if index[key2] == n-1:
                continue
            if key != a[key2][index[key2]]:
                continue
            if key in already or key2 in already:
                continue
            already.add(key)
            already.add(key2)
            index[key] += 1
            index[key2] += 1
            sub.append(key)
            sub.append(key2)
            judge = False
        if judge:
            break
        ans += 1
        search = copy(sub)
        
    for value in index:
        if value != n-1:
            print(-1)
            sys.exit()
    print(ans)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

S = input()
ans = 0
while "BW" in S:
    S = S.replace("BW", "WB", 1)
    ans += 1

print(ans)


### FIXED CODE ###

S = input()
b_cnt = 0
ans = 0
for c in S:
    if c == "B":
        b_cnt += 1
    else:
        ans += b_cnt

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

import sys

N = int(input())

S = [''] * N


def query(i):
    print(i)
    s = input()
    if s == 'Vacant':
        print(i)
        sys.exit()
    S[i] = s
    return s


query(0)
query(N - 1)
l = 0
r = N - 1
while r - l >= 2:
    m = (l + r) // 2
    if r - l == 2 and S[l] != S[r]:
        break
    query(m)
    if (m - l) % 2 == 0 and S[l] != S[m]:
        r = m
    else:
        l = m

for i in range(l, r + 1):
    if S[i] == '':
        print(i)
        break


### FIXED CODE ###

import sys

N = int(input())

S = [''] * N


def query(i):
    print(i)
    s = input()
    if s == 'Vacant':
        print(i)
        sys.exit()
    S[i] = s
    return s


query(0)
query(N - 1)
l = 0
r = N - 1
while r - l >= 2:
    m = (l + r) // 2
    if r - l == 2 and S[l] != S[r]:
        break
    query(m)
    if (m - l) % 2 == 0 and S[l] != S[m] or (m - l) % 2 == 1 and S[l] == S[m]:
        r = m
    else:
        l = m

for i in range(l, r + 1):
    if S[i] == '':
        print(i)
        break
### BUGGY CODE ###

import sys
input = sys.stdin.readline
mod = 2019
s = input().rstrip()
n = len(s)
mod_list = [0]
for i in range(n - 1, -1, -1):
    mod_list.append((mod_list[-1] + int(s[i]) * 10**(n - 1 - i) ) % mod)
from collections import Counter
c = Counter(mod_list)
ans = 0
for i in c.keys():
    ans += c[i] * (c[i] - 1) // 2
print(ans)





### FIXED CODE ###

import sys
input = sys.stdin.readline

mod = 2019

s = input().rstrip()
n = len(s)

t = [int(s[n - 1])]

mul = 10
for i in range(n - 2, -1, -1):
    t.append((t[-1] + int(s[i])*mul) % mod)
    mul *= 10
    mul %= mod
t.append(0)

from collections import Counter

c = Counter(t)
ans = 0

for i in c.keys():
    ans += c[i]*(c[i] - 1) // 2

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

from fractions import Fraction
n,k = map(int, input().split())
ttl = 0
res = []
for i in range(1,n+1):
  ttl = i
  cnt = 0
  while True:
    if ttl >= k:
      break
    ttl = ttl*2
    cnt+=1
  res.append(cnt)
ans = sum([Fraction(1,n)*Fraction(1,2)**e for e in res])
print(float(ans))

### FIXED CODE ###

n,k = map(int, input().split())
ttl = 0
res = []
for i in range(1,n+1):
  ttl = i
  cnt = 0
  while True:
    if ttl >= k:
      break
    ttl = ttl*2
    cnt+=1
  p = 0.5**cnt
  res.append(p)
ans = sum(res)/n
print(float(ans))
### BUGGY CODE ###

n,w=map(int,input().split())
dp=[0 for j in range(w+1)]
c,p=map(int,input().split())
dp[c]=p
for i in range(1,n):
  c,p=map(int,input().split())
  for j in range(w,c,-1):
    if dp[j-c] != 0 and dp[j]<dp[j-c]+p:
      dp[j]=dp[j-c]+p
  if dp[c] < p:
    dp[c]=p
print(max(dp))

### FIXED CODE ###

import sys
input=sys.stdin.readline
 
n,w=map(int,input().split())
dp=[0]*(w+1)
 
def ans(n,w):
  for _ in range(n):
    c,p=map(int,input().split())
    for j in range(w,c-1,-1):
      tmp=dp[j-c]+p
      if dp[j]<tmp:
        dp[j]=tmp
  return max(dp)
print(ans(n,w))
### BUGGY CODE ###

# coding: utf-8

# 標準入力 <int>
N = int(input())

# 標準入力<str>
S = input()

ans = 0

for i in range(N - 2):
  for j in range(N - i - 2):
    for k in range(N - i - j - 2):

      if S[i] != S[i + j + 1] and S[i + j + 1] != S[i + j + k + 2] and S[i + j + k + 2] != S[i] and j != k:
        ans += 1

print(ans)


### FIXED CODE ###

# coding: utf-8

# 標準入力 <int>
N = int(input())

# 標準入力<str>
S = input()

R = S.count("R")
G = S.count("G")
B = S.count("B")

cnt = 0

for i in range(N - 2):
  for j in range(i + 1, N - 1):
    k = i + ((j - i) * 2)
    if k < N:
      if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
        cnt += 1

print(R * G * B - cnt)
### BUGGY CODE ###

f=lambda:map(int,input().split())
n,k=f()
l=sorted(f())
INF=10**18+1
from bisect import *
tl=bisect_left(l,0)
tr=bisect(l,0)
tm,tz,tp=tl,tr-tl,n-tr
cm=tm*tp
cz=tz*(n*2-tz-1)//2
cp=(tm*(tm-1)+tp*(tp-1))//2
lm=l[:tl]
lma=list(map(lambda x:-x,lm))[::-1]
lp=l[tr:]
def bs(a,l,r):
  while r-l>1:
    c=(l+r)//2
    if i*a[c]<m: l=c
    else: r=c
  return r
if 0<k-cm<=cz:
  print(0)
elif k<=cm:
  l,r=-INF,0
  while r-l>1:
    m=(l+r)//2
    s=0
    for i in lp:
      s+=bs(lm,-1,tm)
    if s<k: l=m
    else: r=m
  print(l)
else:
  l,r=0,INF
  while r-l>1:
    m=(l+r)//2
    s=0
    for i in lma:
      s+=bs(lma,-1,tm)
      if i*i<m: s-=1
    for i in lp:
      s+=bs(lp,-1,tp)
      if i*i<m: s-=1
    if cm+cz+s//2<k: l=m
    else: r=m
  print(l)

### FIXED CODE ###

f=lambda:map(int,input().split())
n,k=f()
lm,lp=[],[]
for i in f():
  if i<0: lm.append(-i)
  else: lp.append(i)
lm.sort()
lp.sort()
cm=len(lm)
cp=len(lp)
def cnt(x):
  c=0
  if x<0:
    r=cp
    for i in lm:
      while r and i*lp[r-1]>=-x: r-=1
      c+=cp-r
    return c
  r=cm
  for i in lm:
    while r and i*lm[r-1]>x: r-=1
    c+=r
    if i*i<=x: c-=1
  r=cp
  for i in lp:
    while r and i*lp[r-1]>x: r-=1
    c+=r
    if i*i<=x: c-=1
  return cm*cp+c//2
INF=10**18+1
l,r=-INF,INF
while r-l>1:
  m=l+r>>1
  if cnt(m)<k: l=m
  else: r=m
print(r)
### BUGGY CODE ###

import sys
s=input()
t=input()

def c(a,b,s):
    t=s.replace(a,"A")
    u=t.replace(b,a)
    v=u.replace("A",b)
    
    return v
    
l=[]

for i in range(len(t)):
    if s[i]!=t[i]:
        for j in l:
            if s[i]==j:
                print("No")
                sys.exit()
        l.append(t[i])
        s=c(s[i],t[i],s)
    
        

if s==t:
    print("Yes")
else:
    print("No")
        
    

### FIXED CODE ###

s=input()
t=input()


def f(s):
    l=[]
    a="abcdefghijklmnopqrstuvwxyz"
    r=""
    for i in range(len(s)):
        if s[i] in l:
            for j in range(len(l)):
                if s[i]==l[j]:
                    r+=a[j]
        else:
            r+=a[len(l)]
            l.append(s[i])
    return r

if f(s)==f(t):
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

n = int(input())

def calc(n):
    if n < 6:
        return 0
    ans = 0
    for x in range(1, int(n**0.5)):
        for y in range(1, int(n**0.5)):
            for z in range(1, int(n**0.5)):
                if x**2 + y**2 + z**2 + x*y + y*z + z*x == n:
                    ans += 1

    return ans

for i in range(1, n+1):
    print(calc(i))


### FIXED CODE ###

n = int(input())
ans = [0 for _ in range(n+1)]
def calc(n):
    for x in range(1, int(n**0.5)+1):
        for y in range(1, int(n**0.5)+1):
            for z in range(1, int(n**0.5)+1):
                v = x**2 + y**2 + z**2 + x*y + y*z + z*x
                if v < n+1:
                    ans[v] += 1

calc(n)
for i in range(n):
    print(ans[i+1])
### BUGGY CODE ###

N, W = map(int, input().split())
ws = [0] * N
vs = [0] * N

for i in range(N):
  ws[i], vs[i] = map(int, input().split())

import numpy as np
dp_table = [[0]*(W+1) for _ in range(N+1)]

for i in range(1,N+1):
  for w_now in range(1,W+1):
    if w_now - ws[i-1] >= 0:
      dp_table[i][w_now] = max( dp_table[i-1][w_now], dp_table[ i-1][w_now-ws[i-1] ] + vs[i-1] )
    else:
      dp_table[i][w_now] = dp_table[i-1][w_now]
print(int(dp_table[-1][-1]))

### FIXED CODE ###

N, W = map(int, input().split())
ws = [0] * N
vs = [0] * N

for i in range(N):
  ws[i], vs[i] = map(int, input().split())

dp_table = [[0]*(W+1) for _ in range(N+1)]

for i in range(1,N+1):
  for w_now in range(1,W+1):
    if w_now - ws[i-1] >= 0:
      dp_table[i][w_now] = max( dp_table[i-1][w_now], dp_table[ i-1][w_now-ws[i-1] ] + vs[i-1] )
    else:
      dp_table[i][w_now] = dp_table[i-1][w_now]
print(int(dp_table[-1][-1]))
### BUGGY CODE ###

import sys

h,w,m = map(int, sys.stdin.readline().split())
num_in_h = [0] * h
num_in_w = [0] * w
targets = set()
for _ in range(m):
    t_h, t_w = map(lambda x: int(x)-1, sys.stdin.readline().split())
    num_in_h[t_h] += 1
    num_in_w[t_w] += 1
    targets.add((t_h, t_w))

max_h_set = set([i for i, v in enumerate(num_in_h) if v == max(num_in_h)])
max_w_set = set([i for i, v in enumerate(num_in_w) if v == max(num_in_w)])
ans = max(num_in_h) + max(num_in_w) -1

flag = False
for i in max_h_set:
    for j in max_w_set:
        if (i, j) not in targets:
            flag = True
            break
    if flag: break

print(ans+1 if flag else ans)


### FIXED CODE ###

import sys

h,w,m = map(int, sys.stdin.readline().split())
num_in_h = [0] * h
num_in_w = [0] * w
targets = set()
for _ in range(m):
    t_h, t_w = map(lambda x: int(x)-1, sys.stdin.readline().split())
    num_in_h[t_h] += 1
    num_in_w[t_w] += 1
    targets.add((t_h, t_w))

max_h = max(num_in_h)
max_w = max(num_in_w)
max_h_set = set([i for i, v in enumerate(num_in_h) if v == max_h])
max_w_set = set([i for i, v in enumerate(num_in_w) if v == max_w])
ans = max_h + max_w - 1

flag = False
for i in max_h_set:
    for j in max_w_set:
        if (i, j) not in targets:
            flag = True
            break
    if flag: break

print(ans+1 if flag else ans)
### BUGGY CODE ###

import sys
import math
import copy
sys.setrecursionlimit(1000000000)
 
def solve(robots):
    total = len(robots)
    prev = None
    local_robots = copy.deepcopy(robots)
    for i, current in enumerate(robots):
        if count_collisions(current, local_robots) > 0:
            local_robots.remove(current)
            total -= 1
        else:
            prev = current
            
    return total
    
def count_collisions(current, robots):
    count = 0
    for robot in robots:
        if robot[0] < current[0] and robot[0] + robot[1] > current[0] - current[1]:
            count += 1
        if current[0] < robot[0] and current[0] + current[1] > robot[0] - robot[1]:
            count += 1
    return count

N, = map(int, input().split())
ROBOTS = [list(map(int, input().split())) for _ in range(N)]
ROBOTS = list(reversed(sorted(ROBOTS, key=lambda x: count_collisions(x, ROBOTS))))
print(solve(ROBOTS))

### FIXED CODE ###

import sys
import math
sys.setrecursionlimit(1000000000)
 
def solve(robots):
    total = len(robots)
    prev = None
    for current in robots:
        if prev and prev[0] + prev[1] > current[0] - current[1]:
            total -= 1
        else:
            prev = current
            
    return total
 
N, = map(int, input().split())
ROBOTS = [list(map(int, input().split())) for _ in range(N)]
ROBOTS = sorted(ROBOTS, key=lambda x: x[0] + x[1])
print(solve(ROBOTS))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N = int(readline())
S = readline()
count = 0
for i in range(0,1000):
    c = [i//100,(i//10)%10,i%10]
    f = 0
    for j in range(0,N):
        if int(S[j]) == int(c[f]):
            f += 1
        if f == 3:
            break
    if f == 3:
        count += 1
            
print(count)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N = int(readline())
S = readline()
count = 0
for i in range(10):
    a = S.find(str(i))
    if a == -1: 
        continue
    for j in range(10):
        b = S.find(str(j),a+1)
        if b == -1: 
            continue
        for k in range(10):
            c = S.find(str(k),b+1)
            if c != -1: count +=1
print(count)
### BUGGY CODE ###

import sys
from collections import deque

input = sys.stdin.readline


def bfs(H, W, dist):
    queue = deque()
    for h in range(H):
        for w in range(W):
            if dist[h][w] == 0:
                queue.append((h, w))
    while queue:
        h, w = queue.popleft()
        for y, x in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
            hh, ww = h + y, w + x
            if not (0 <= hh < H and 0 <= ww < W):
                continue
            if dist[hh][ww] == -1:
                dist[hh][ww] = dist[h][w] + 1
                queue.append((hh, ww))


def main():
    H, W = map(int, input().split())
    A = [None] * H
    for i in range(H):
        A[i] = input().rstrip()

    distance = [[0 if A[h][w] == "#" else -1
        for w in range(W)] for h in range(H)]

    bfs(H, W, distance)

    ans = max(max(d) for d in distance)
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import deque

input = sys.stdin.readline


def bfs(H, W, A, dist):
    queue = deque([])
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#":
                dist[h][w] = 0
                queue.append((h, w))
    while queue:
        h, w = queue.popleft()
        for y, x in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            next_h, next_w = h + y, w + x
            if dist[next_h][next_w] == -1:
                dist[next_h][next_w] = dist[h][w] + 1
                queue.append((next_h, next_w))


def main():
    H, W = map(int, input().split())
    A = [None] * (H + 2)
    A[0] = A[-1] = "." * (W + 2)
    for i in range(1, H + 1):
        A[i] = "".join([".", input().rstrip(), "."])

    dist = [[0] + [-1] * W + [0] for _ in range(H + 2)]
    dist[0] = dist[-1] = [0] * (W + 2)
    bfs(H + 2, W + 2, A, dist)

    ans = max(map(max, dist))
    print(ans)


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


from copy import copy
N=int(input())
G=[[] for _ in range(N)]
di=[-1]*N
for i in range(N-1):
    u,v,w=map(int,input().split())
    G[u-1].append([v-1,w])
    G[v-1].append([u-1,w])

di[0]=0
for g,w in G[0]:
    di[g]=w

for i in range(1,N):
    if di[i]!=-1:continue
    seen=[0]*N
    stack=copy(G[0])
    seen[0]=1
    dis=0
    while stack:
        y,d=stack.pop()
        if seen[y]==1:continue
        seen[y]=1
        if y==i:
            di[i]=dis+d
            break
        else:
            for z,dist in G[y]:
                if seen[z]==0:
                    di[z]=dis+d+dist
                    stack.append([z,dis+d+dist])

for i in range(N):
    if di[i]%2==0:
        print(0)
    else:
        print(1)

### FIXED CODE ###


from copy import copy
N=int(input())
G=[[] for _ in range(N)]
di=[-1]*N
for i in range(N-1):
    u,v,w=map(int,input().split())
    G[u-1].append([v-1,w])
    G[v-1].append([u-1,w])

di[0]=0
for g,w in G[0]:
    di[g]=w

for i in range(1,N):
    if di[i]!=-1:continue
    seen=[0]*N
    stack=copy(G[0])
    seen[0]=1
    dis=0
    while stack:
        y,d=stack.pop()
        if seen[y]==1:continue
        seen[y]=1
        if y==i:
            di[i]=dis+d
            break
        else:
            for z,dist in G[y]:
                if seen[z]==0:
                    di[z]=dis+d+dist
                    stack.append([z,dis+d+dist])

for i in range(N):
    if di[i]%2==0:
        print(0)
    else:
        print(1)
### BUGGY CODE ###

R, G, B, N = map(int,input().split())
cnt = 0
for r in range(N+1):
    for g in range(N+1):
        if N - R*r - G*g >= 0 and (N-R*r-G*g)%B == 0:
            cnt += 1
print(cnt)

### FIXED CODE ###

*j, N = map(int,input().split())
j.sort()
a,b,c = j
cnt = 0
for r in range(N//b+1):
    for g in range((N-b*r)//c+1):
        v = b*r+c*g
        if (N-v)%a == 0:
            cnt += 1
print(cnt)
### BUGGY CODE ###

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

A.sort()

for m in range(M):
    if len(A) == 1:
        A[0] //= 2
        continue

    *A, a = A

    a //= 2

    for i, x in reversed(list(enumerate(A))):
        if x < a:
            A.insert(i+1, a)
            break
    else:
        A = [a] + A

print(sum(A))


### FIXED CODE ###

import sys
import heapq

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

if len(A) == 1:
    A[0] //= (2 ** M)
    print(sum(A))
    sys.exit()

h = [(1/a, a) for a in A]
heapq.heapify(h)

for m in range(M):
    x = heapq.heappop(h)
    _, a = x

    a //= 2

    heapq.heappush(h, (1/a if a > 0 else float('inf'), a))

print(sum([a for _, a in h]))
### BUGGY CODE ###

n, x, y = map(int, input().split())
for k in range(1, n):
    count = 0
    for start in range(1, n+1):
        for end in range(start+1, n+1):
            if min(end - start, abs(x-start) + abs(y-end) + 1) == k:
                count += 1
    print(count)

### FIXED CODE ###

n, x, y = map(int, input().split())
lengths = [0 for i in range(n)]
for start in range(1, n+1):
    for end in range(start+1, n+1):
        lengths[min(end - start, abs(x-start) + abs(y-end) + 1)] += 1
print("\n".join(map(str, lengths[1:])))
### BUGGY CODE ###

import heapq
N, M = map(int, input().split())
A = list(map(lambda x: int(x), input().split()))
heapq.heapify(A)

for i in range(M):
  b, c = map(int, input().split())
  for j in range(b):
    d = heapq.heappushpop(A, c)
    if c == d:
      break
      
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
exc = []

for i in range(M):
  exc.append(list(map(int, input().split())))
exc.sort(key=lambda x: x[1], reverse=True)
e = []
count = 0
for i in range(M):
  e += [exc[i][1]] * exc[i][0]
  count += exc[i][0]
  if count >= N:
    break
cards = sorted(A+e, reverse=True)
print(sum(cards[:N]))