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

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

s = [int(i) for i in STR()]
l = len(s)
arr = [-1 for _ in range(l)]
tmp = 0
for i in range(l):
    tmp += s[i] * (10 ** (l - i))
    arr[i] = tmp % 2019
a = list(set(arr))
b = Counter(arr)
ans = 0
for i in a:
    tmp2 = b[i]
    if i == 0:
        ans += (tmp2 + 1) * tmp2 // 2
    else:
        ans += tmp2 * (tmp2 - 1) // 2
print(ans)


### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

s = [int(i) for i in STR()]
l = len(s)
arr = [-1 for _ in range(l)]
tmp = 0
for i in range(l):
    tmp += s[i] * pow(10, l - i, 2019)
    tmp %= 2019
    arr[i] = tmp
arr.sort()
tmp = arr[0]
cnt = 1
ans = 0
for i in range(1, l):
    if tmp == arr[i]:
        cnt += 1
    else:
        ans += cnt * (cnt - 1) // 2
        if tmp == 0:
            ans += cnt
        cnt = 1
        tmp = arr[i]
ans += cnt * (cnt - 1) // 2
if tmp == 0:
    ans += cnt
print(ans)
### BUGGY CODE ###

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

A.sort()
A.reverse()

list = []
ans = 0
for i in range(len(A)):
    if i == 0:
        list.append(A[i])
    elif list:
        ans += list[0]
        list.pop(0)
        list.append(A[i])
        list.append(A[i])

print(ans)

### FIXED CODE ###

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

A.sort()
A.reverse()

list = []
ans = 0
list.append(A[0])
for i in range(1, len(A)):
        ans += list[i - 1]
        list.append(A[i])
        list.append(A[i])

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

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

#まだ左端を選択していない状態(状態 0)。この時は和が0の時1通りでそれ以外は0。
#左端は選択済みだけど右端は選択していない状態(状態 1)
#右端も選択済みの状態(状態 2)

dp = [[[0 for _ in range(3)] for _ in range(S+1)] for _ in range(N+1)]
dp[0][0][0] = 1
#i個目までで和がjとなる場合の数
ans = 0

for i in range(N):
  for j in range(S+1):
    #from 0
    #if j == 0: #j==0の時以外は基本0なのであってもなくても良い。
    dp[i+1][j][0] += dp[i][j][0]
    if j+A[i] <= S:# and j == 0: #j==0の時以外は基本0なのであってもなくても良い。
      dp[i+1][j+A[i]][1] += dp[i][j][0] * (i+1)
      dp[i+1][j+A[i]][2] += dp[i][j][0] * (i+1) * (N-i)
    #from 1
    dp[i+1][j][1] += dp[i][j][1]
    if j+A[i] <= S:
      dp[i+1][j+A[i]][1] += dp[i][j][1]
      dp[i+1][j+A[i]][2] += dp[i][j][1] * (N-i)
    #from 2
    dp[i+1][j][2] += dp[i][j][2]
#print(dp)MODDD
print(dp[N][S][2]%MOD)
      

### FIXED CODE ###

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

Q = [0 for _ in range(S+1)]
ans = 0
for i in range(N):
  Q[0] += 1
  Q2 = [0 for _ in range(S+1)]
  for j in range(S+1):
    Q2[j] += Q[j]%MOD
    if j+A[i] <= S: #(1+x^A[i])をかけてもx^sを超えないときに限り。
      Q2[j+A[i]] += Q[j]%MOD
  Q = Q2
  ans += Q[S]%MOD
ans = ans %MOD
print(ans)
### BUGGY CODE ###

#coding:utf-8
n = int(input())
a = list(map(int, input().split()))
a_sort = sorted(a)
ans = []

for i in range(0, n):
    for j in range(0, n):
        if a_sort[i] == a[j]:
            ans.append(j+1)

print(*ans)

### FIXED CODE ###

#coding:utf-8
import bisect
n = int(input())
a = list(map(int, input().split()))
num = list(range(1, n+1))
dic = {key: val for key, val in zip(num, a)}
#print(dic)

result = sorted(dic.items(), key=lambda x:x[1])

ans = [i[0] for i in result] 
print(*ans)
### BUGGY CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))

# 期待値のリスト生成
ex_list = list()
for i in range(len(p)):
	ex_list.append(sum(range(1,p[i]+1))/p[i])

ans = 0
for i in range(N-K+1):
	ex = sum(ex_list[i:i+K])
	if ans < ex:
		ans = ex

print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))

# 期待値の累積和リストを生成
ex_list = list() 
for i in range(len(p)):
	if i != 0:
		ex_list.append(((1+p[i])/2)+ex_list[-1])
	else:
		ex_list.append((1+p[i])/2)

ans = ex_list[K-1]
for i in range(N-K):
	# print(i,ex_list[i],ex_list[i+K])
	ex = abs(ex_list[i] - ex_list[i+K])
	if ans < ex:
		ans = ex
print(ans)
### BUGGY CODE ###

s=list(input().split())
N=int(s[0])
M=int(s[1])
count=0
total=0
a = list(map(int,input().split()))	
while(count<M):
  a[a.index(max(a))]=a[a.index(max(a))]//2
  count+=1

for i in range(N):
  total=total+a[i]
  
print(total)

### FIXED CODE ###

from sys import stdin
import heapq

s=stdin.readline().rstrip().split()
N=int(s[0])
M=int(s[1])

a=stdin.readline().rstrip().split()
for i in range(N):
  a[i]=int(a[i])*(-1)
  
heapq.heapify(a)
for i in range(M):
  t=-(-heapq.heappop(a)//2)
  heapq.heappush(a,t)
print(sum(a)*(-1))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from itertools import chain
def resolve():
    n,a,b=map(int,input().split())

    if(a+b>n+1):
        print(-1)
        return
    if(a*b<n):
        print(-1)
        return

    # a*b=n のとき
    A=[]
    for i in range(a):
        A.append(list(range((i+1)*b,i*b,-1)))

    d=a*b-n
    for arr in A[1:]:
        k=min(b-1,d)
        d-=k
        for _ in range(k): arr.pop()

    # A を座圧する
    S=sorted(list(chain.from_iterable(A)))
    D={a:i for i,a in enumerate(S,1)}
    ans=[None]*n
    for i,a in enumerate(chain.from_iterable(A)):
        ans[i]=D[a]

    print(*ans)
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,a,b=map(int,input().split())
    if(a+b>n+1):
        print(-1)
        return
    if(a*b<n):
        print(-1)
        return

    ans=list(range(b,0,-1))
    now=b
    d=a*b-n
    for _ in range(a-1):
        k=min(d,b-1)
        d-=k
        next=now+(b-k)
        for i in range(next,now,-1):
            ans.append(i)
        now=next

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

import sys
sys.setrecursionlimit(10**6)

n, q = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(n-1):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  g[a].append(b)
  #g[b].append(a)

ans = [0]*n  
for j in range(q):
  p, x = map(int, input().split())
  p -= 1
  ans[p] += x

def dfs(v):
  for v_ in g[v]:
    ans[v_] += ans[v]
    dfs(v_)

dfs(0)
print(' '.join(map(str, ans)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

n, q = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(n-1):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  g[a].append(b)
  #g[b].append(a)

ans = [0]*n  
for j in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x
  
from collections import deque
s = deque()
s.append(0)

while s:
  v = s.pop()
  for v_ in g[v]:
    ans[v_] += ans[v]
    s.append(v_)

print(' '.join(map(str, ans)))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10**6)

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

path = [[] for _ in range(n + 1)]
for i in range(n - 1):
  a, b = map(int, input().split())
  path[a].append(b)
  path[b].append(a)

# global counter
tree = [0] + [None] * n

def count_tree(num, tree, path, parent):
  l = [num] # self

  for i in path[num]:
    if i == parent:
      continue

    l += count_tree(i, tree, path, num)

  tree[num] = l
  return l

count_tree(1, tree, path, 0)

result = [0] * n

sum = 0
for _ in range(q):
  p, x = map(int, input().split())
  for i in tree[p]:
    result[i - 1] += x

print(" ".join([str(i) for i in result]))


### FIXED CODE ###

import sys

sys.setrecursionlimit(10**6)

n, q = map(int, sys.stdin.readline().strip().split())

path = [[] for _ in range(n + 1)]
for i in range(n - 1):
  a, b = map(int, input().split())
  path[a].append(b)
  path[b].append(a)

plus = [0] * (n + 1)

for _ in range(q):
  p, x = map(int, sys.stdin.readline().strip().split())
  plus[p] += x

def calc(num, path, plus, parent):
  for i in path[num]:
    if i == parent:
      continue

    plus[i] += plus[num]
    calc(i, path, plus, num)

calc(1, path, plus, 0)

print(" ".join([str(i) for i in plus[1:]]))
### BUGGY CODE ###

A, B, N = map(int,input().split())
max = 0

for x in range(N+1):
  f = int(A*x/B) - A*int(x/B)
  if(max <= f):
    max = f
  if(max != 0 and f == 0):
    break
print(max)

### FIXED CODE ###

A,B,N = map(int,input().split())
def f(x):
  f = int((A*x)/B)-A*int(x/B)
  return f
if(B-1 < N):
  print(f(B-1))
else:
  print(f(N))
### BUGGY CODE ###

direction = input()

def next(direction, current):
	output = [0] * len(current)

	for i in range(len(direction)):
		if direction[i] == 'R':
			output[i+1] += current[i]
		if direction[i] == 'L':
			output[i-1] += current[i]

	return output


def solve(direction, start, end, output):
	original = [1] * (end-start)

	sub_direction = direction[start:end]

	prev2 = next(sub_direction, original)
	prev1 = next(sub_direction, prev2)

	count = 2
	while True:
		next_state = next(sub_direction, prev1)
		count += 1
		if next_state == prev2:
			if count % 2 == 0:
				output.append(prev2)
				# print(' '.join(map(str, prev2)))
				return
			else:
				output.append(prev1)
				# print(' '.join(map(str, prev1)))
				return
		prev2 = prev1
		prev1 = next_state

parts = []
prev = 0
for i in range(len(direction)-1):
	if direction[i] == 'L' and direction[i+1] == 'R':
		parts.append((prev,i+1))
		prev = i+1

parts.append((prev,len(direction)))

# print(parts)
output = []
for start,end in parts:
	solve(direction, start, end, output)

# print(output)
final = [x for  y in output for x in y]
print(' '.join(map(str, final)))


# print(solve('RRLRL'))
# print(solve('RRLLLLRLRRLL'))

### FIXED CODE ###

direction = input()

def next(direction, current):
	output = [0] * len(current)

	for i in range(len(direction)):
		if direction[i] == 'R':
			output[i+1] += current[i]
		if direction[i] == 'L':
			output[i-1] += current[i]

	return output

def s(inp):
	r = len([x for x in inp if x == 'R'])
	l = len([x for x in inp if x == 'L'])

	R = L = 0
	for i in range(0, r, 2):
		R += 1
	for i in range(1, r, 2):
		L += 1
	for i in range(0, l, 2):
		L += 1
	for i in range(1, l, 2):
		R += 1
	
	output = [0 for _ in range(len(inp))]
	output[r-1] = R
	output[r] = L
	return output

def solve(inp):
	r = len([x for x in inp if x == 'R'])
	l = len([x for x in inp if x == 'L'])

	output = [0] * len(inp)
	if r == l:
		output[r-1] = output[r] = r
	else:
		m = max(l-1, r-1)
		if m % 2 == 1:
			output[r-1] = r
			output[r] = l
		else:
			output[r-1] = l
			output[r] = r
		


def solve(direction, start, end, output):
	original = [1] * (end-start)

	sub_direction = direction[start:end]

	prev2 = next(sub_direction, original)
	prev1 = next(sub_direction, prev2)

	count = 2

	output.append(s(direction[start:end]))

	# while True:
	# 	next_state = next(sub_direction, prev1)
	# 	count += 1
	# 	if next_state == prev2:
	# 		if count % 2 == 0:
	# 			output.append(prev2)
	# 			# print(' '.join(map(str, prev2)))
	# 			return
	# 		else:
	# 			output.append(prev1)
	# 			# print(' '.join(map(str, prev1)))
	# 			return
	# 	prev2 = prev1
	# 	prev1 = next_state

# direction = 'RRRLLRLLRRRLLLLL'
parts = []
prev = 0
for i in range(len(direction)-1):
	if direction[i] == 'L' and direction[i+1] == 'R':
		parts.append((prev,i+1))
		prev = i+1

parts.append((prev,len(direction)))

# print(parts)
output = []
for start,end in parts:
	solve(direction, start, end, output)

# print(output)
final = [x for  y in output for x in y]
print(' '.join(map(str, final)))


# print(solve('RRLRL'))
# print(solve('RRLLLLRLRRLL'))
### BUGGY CODE ###

numbers =input().rstrip().split(" ")
N =int(numbers[0])
a =int(numbers[1])
b =int(numbers[2])
import math 

def comb(n,k):
    return math.factorial(n)/(math.factorial(k)*math.factorial(n-k))

c =int(2**N-comb(N,a)-comb(N,b)-1)
d =c%(1000000000+7)
print(d)


### FIXED CODE ###

def cmod(n, r, p):
    x,y  = 1, 1
    for i in range(r):
        x = x * (n - i) % p
        y = y * (r - i) % p
    return (x * pow(y, p - 2, p)) % p


n, a, b = map(int, (input().split()))
p = 10 ** 9 + 7
print((pow(2, n, p) - 1 - cmod(n, a, p) - cmod(n, b, p)) % p)
### BUGGY CODE ###

import collections
# s = [[]]
n, m = map(int,input().split())
s = [list(map(int,input().split())) for i in range(m)]

# n, m = 4, 2
# s = [[1,3], [2,4]]

if m == 1:
    print(s[0][-1] - s[0][0] + 1)
else:
    new = [[] for i in range(m)]
    for i in range(m):
        for j in range(s[i][0],s[i][1]+1):
            new[i].append(j)
    tmp = [flatten for inner in new for flatten in inner]
    c = collections.Counter(tmp)
    count = 0
    for i, num in c.most_common():
        if num == m:
            count += 1
        else:
            break
    print(count)

### FIXED CODE ###

import collections
# s = [[]]
n, m = map(int,input().split())
s = [list(map(int,input().split())) for i in range(m)]

# n, m = 4, 2
# s = [[1,3], [2,4]]

if m == 1:
    print(s[0][-1] - s[0][0] + 1)
else:
    l = s[0][0]
    r = s[0][1]
    for i in range(1,m):
        l = max(l,s[i][0])
        r = min(r,s[i][1])
    print(max(r-l+1,0))
### BUGGY CODE ###

# coding: utf-8
# Your code here!

def solve(n, m, q, arrays):
    from itertools import combinations_with_replacement
    pattern = list(combinations_with_replacement(range(1, m+1), n))

    maxp = 0
    for x in pattern:
        get = 0
        for array in arrays:
            if x[array[1]-1] - x[array[0]-1] == array[2]:
                get += array[3]

        maxp = max(maxp, get)

    print(maxp)

n, m, q, *aa = map(int, open(0).read().split())

from numpy import array_split
arrays = list(array_split(aa, q))

solve(n, m, q, arrays)


### FIXED CODE ###

# coding: utf-8
# Your code here!

def solve(n, m, q, arrays):
    from itertools import combinations_with_replacement
    pattern = list(combinations_with_replacement(range(1, m+1), n))

    maxp = 0
    for x in pattern:
        get = 0
        for array in arrays:
            if x[array[1]-1] - x[array[0]-1] == array[2]:
                get += array[3]

        maxp = max(maxp, get)

    print(maxp)

n, m, q, *aa = map(int, open(0).read().split())

arrays = []
loop = 0
array = []
for x in aa:
    array.append(x)
    loop += 1
    if loop % 4 == 0:
        arrays.append(array)
        array = []

solve(n, m, q, arrays)
### BUGGY CODE ###

from heapq import heappush, heappop

N, M = map(int, input().split())
list = []
for _ in range(N):
	a, b = map(int, input().split())
	if a <= M:
		list.append([a, b])

list.sort()

ans = 0
heap = []
for day in range(1,M+1):
	for i in list:		
		if i[0] == day:
			heappush(heap, -i[1])
		elif i[0] > day:
			break
    
	if len(heap) != 0:
		ans += -heappop(heap)

print(ans)

### FIXED CODE ###

from heapq import heappop, heappush
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
X = sorted([list(map(int, input().split())) for _ in range(N)], key = lambda x: x[0])

hq = []
ans, j = 0, 0

for i in range(1, M + 1):  # M - i 日後にするバイトを考える
    while (j < N) and (X[j][0] <= i):
        heappush(hq, -X[j][1])  # 候補の追加
        j += 1
    if len(hq):
        ans += -heappop(hq)  # 候補があるとき、候補から最大値を取り出す

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


MOD = 1000000007

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

def lcm(a, b):
    return a//gcd(a,b)*b

n = int(input())
a = list(map(int,input().split()))
all_lcm = 1
for i in range(n):
    all_lcm = lcm(all_lcm, a[i])
ans = 0
for i in range(n):
    ans += all_lcm//a[i]
print(ans%MOD)

### FIXED CODE ###


MOD = 1000000007

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

def lcm(a, b):
    return a//gcd(a,b)*b

n = int(input())
a = list(map(int,input().split()))
all_lcm = 1
for i in range(n):
    all_lcm = lcm(all_lcm, a[i])
ans = 0
for i in range(n):
    ans += all_lcm//a[i]
print(ans%MOD)
### BUGGY CODE ###

N = int(input())
dlist = list(map(int, input().split()))
dlist.sort(reverse=True)
sum = 0

count_b = 0
count_c = 0
for a in range(N):
    count_b += 1
    count_c = count_b
    for b in range(count_b, N):
        count_c += 1 
        for c in range(count_c, N):
            if dlist[a] < dlist[b] + dlist[c]:
                sum += 1
            else:
                break
print(sum)

### FIXED CODE ###

import bisect
N=int(input())
L=sorted(list(map(int,input().split())))

ans=0
for i in range(N-2):
  for j in range(i+1,N-1):
    ans+=bisect.bisect_left(L,L[i]+L[j])-j-1 # Code 1 
    # ans+=bisect.bisect_left(L,L[i]+L[j],j)-j-1 # Code 2 
print(ans)
### BUGGY CODE ###


def resolve():
    R, C, K = map(int, input().split())
    G = [[0] * (C) for _ in range(R)]
    for _ in range(K):
        r, c, v = map(int, input().split())
        G[r - 1][c - 1] = v

    dp = [[[0] * 4 for _ in range(C+1)] for _ in range(R+1)]

    for i in range(R):
        for j in range(C):
            for k in range(2, -1, -1):
                dp[i][j][k + 1] = max(dp[i][j][k + 1], dp[i][j][k] + G[i][j])
            for k in range(4):
                dp[i + 1][j][0] = max(dp[i + 1][j][0], dp[i][j][k])
                dp[i][j + 1][k] = max(dp[i][j + 1][k], dp[i][j][k])
                
    ans = 0
    for k in range(4):
        ans = max(ans, dp[R-1][C-1][k])
    print(ans)


if __name__ == "__main__":
    resolve()

### FIXED CODE ###


def resolve():
    R, C, K = map(int, input().split())
    G = [[0] * (C+1) for _ in range(R+1)]
    for _ in range(K):
        r, c, v = map(int, input().split())
        G[r][c] = v

    DP1 = [0 for _ in range(C + 1)]  # c列目までとったとき、最新の行で1個以下とったという条件のもとの最大
    DP2 = [0 for _ in range(C + 1)]  # c列目までとったとき、最新の行で2個以下とったという条件のもとの最大
    DP3 = [0 for _ in range(C + 1)]  # c列目までとったとき、最新の行で3個以下とったという条件のもとの最大

    for r in range(1, R+1):
        for c in range(1, C+1):
            # 更新の順番に注意
            # mid = max(DP1[c], DP2[c], DP3[c]) + I[r][c]
            mid = DP3[c] + G[r][c]
            DP3[c] = max(DP3[c - 1], mid, DP2[c - 1] + G[r][c])  # 3個
            DP2[c] = max(DP2[c - 1], mid, DP1[c - 1] + G[r][c])  # 2個
            DP1[c] = max(DP1[c - 1], mid)  # 1個

    print(DP3[C])

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

N,M = [int(x) for x in input().split()]

A = [int(x) for x in input().split()]
A.sort()
max = 0
BC = []
for i in range(M):
    b,c = [int(x) for x in input().split()]
    max += b
    BC.append([c,b])

BC.sort(reverse = True)
str =[]
for c,b in BC:
    str+=[c]*b
    # print(str)

now = 0
for i in range(len(A)):
    if(now >= max):
        break
    if(A[i] < str[now]):
        A[i] = str[now]
        now+=1

# print(A)
print(sum(A))


### FIXED CODE ###

N,M = [int(x) for x in input().split()]

A = [int(x) for x in input().split()]
A.sort()
max = 0
BC = []
for i in range(M):
    b,c = [int(x) for x in input().split()]
    max += b
    BC.append([c,b])

BC.sort(reverse = True)
str =[]
for c,b in BC:
    str+=[c]*b
    # print(str)
    if(len(str) > N):
        break

now = 0
for i in range(len(A)):
    if(now >= max or str[now] < A[i]):
        break
    if(A[i] < str[now]):
        A[i] = str[now]
        now+=1

# print(A)
print(sum(A))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7

from collections import Counter
def factorize(n):
    d = Counter()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
        m += 1
    if n > 1:
        d[n] += 1
    return d

factors = [None] * N

lcms = Counter()
for i,a in enumerate(A):
    factors[i] = factorize(a)
    for k,v in factors[i].items():
        if k in lcms:
            lcms[k] = max(lcms[k], v)
        else:
            lcms[k] = v

ans = 0
for fs in factors:
    a = 1
    for k,v in lcms.items():
        a *= k**(v - fs[k])
        a %= MOD
    ans += a
    ans %= MOD
print(ans)

### FIXED CODE ###

from fractions import gcd
N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7

lcm = 1
for a in A:
    lcm = lcm // gcd(lcm,a) * a

ans = 0
for a in A:
    ans += lcm // a
ans %= MOD
print(ans)
### BUGGY CODE ###

N=int(input())

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

result=1
for i in X:
  result*=i
  if result>10**18:
    result=-1
  
for i in X:
  if i==0:result=0

print(result)


### FIXED CODE ###

N=int(input())

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

result=1
for i in X:
  result*=i
  if result>10**18:
    result=-1
    break
for i in X:
  if i==0:result=0

print(result)
### BUGGY CODE ###

N = int(input())
S = str(input())

ans = 0
for i in range(1000):
  z = str(i).zfill(3)
  right = -1
  center = -1
  for r in range(1, N-1):
    if S[N-r] == z[2]:
      right = N-r
      break
  if right == -1:
    continue
  for c in range(1, right):
    if S[right-c] == z[1]:
      center = right-c
      break
  if center == -1:
    continue
  if z[0] in S[:center]:
    ans += 1
print(ans)


### FIXED CODE ###

N = int(input())
S = str(input())
R = S[::-1]

ans = 0
for i in range(1000):
  z = str(i).zfill(3)
  right = -1
  left = -1
  if z[2] in R:
    r = R.index(z[2]) + 1
    right = N-r
  else:
    continue
  if z[0] in S:
    left = S.index(z[0]) + 1
  else:
    continue
  if z[1] in S[left:right]:
    ans += 1
print(ans)
### BUGGY CODE ###

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

a = [(i, ai) for i, ai in enumerate(A)]
a.sort(key=lambda x: x[1], reverse=True)

# import numpy as np
# dp = np.zeros((N+1, N+1), np.int8)

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

dp[0][0] = 0
for i, ai in enumerate(a):
    for l in range(i+1):
        r = i - l
        dp[i+1][l] = max(dp[i+1][l], dp[i][l] + ai[1] * ((N-1-r) - ai[0]))
        dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l] + ai[1] * (ai[0] - l))

print(max(dp[N]))

### FIXED CODE ###

def solve(N, A):
    a = [(i, ai) for i, ai in enumerate(A)]
    a.sort(key=lambda x: x[1], reverse=True)

    # import numpy as np
    # dp = np.zeros((N+1, N+1), np.int8)

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

    dp[0][0] = 0
    for i, ai in enumerate(a):
        for l in range(i+1):
            r = i - l
            dp[i+1][l] = max(dp[i+1][l], dp[i][l] + ai[1] * ((N-1-r) - ai[0]))
            dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l] + ai[1] * (ai[0] - l))

    print(max(dp[N]))

N = int(input())
A = list(map(int, input().split()))
solve(N,A)
### BUGGY CODE ###

k,s = map(int,input().split())
x = list(range(k+1))
y = list(range(k+1))
z = list(range(k+1))
count = 0
for i in range(k+1):
    for j in range(k+1):
        if (s - (x[i] + y[j])) in z:
            count += 1
print(count)

### FIXED CODE ###

k,s = map(int,input().split())
count = 0
for i in range(k+1):
    for j in range(k+1):
        if s - (i + j) >= 0 and s - (i + j) <= k:
            count += 1
print(count)