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

n = int(input())
a = list(map(int,input().split()))
mu = 1
for i in range(n):
    mu = mu*a[i]
if mu>10**18: print(-1)
else:
    print(mu)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
mu = 1
if 0 in a:
    print(0)
else:
    fl=0
    for i in range(n):
        mu = mu*a[i]
        if mu>10**18:
            print(-1)
            fl=1
            break
    # print(mu)
    if fl==0:
        print(mu)
### BUGGY CODE ###

h,w,d=map(int,input().split())
ind={}
for i in range(h):
    l=list(map(int,input().split()))

    for j in range(w):
        ind[l[j]]=(i,j)
table=[0]*((((h*w)//d).bit_length())*h*w)
now=1
for i in range(1,h*w-d+1):
    a,s=ind[i]
    de,f=ind[i+d]
    table[i-1+d]=abs(a-de)+abs(s-f)
step=2
for i in range(1,((h*w)//d).bit_length()):
    for j in range(1,h*w-step*d+1):
        table[j-1+step*d+i*h*w]=table[j-1+d*step//2+(i-1)*h*w]+table[j-1+d*step+(i-1)*h*w]
    step*=2
#print(*[table[k*h*w:k*w*h+h*w]for k in range(((h*w)//d).bit_length())],sep="\n")
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    times=(r-l)//d
    cost=0
    now=1
    kata=0
    while times:
        if times%2:
            l+=d*now
            cost+=table[l-1+kata*h*w]

        times//=2
        now*=2
        kata+=1
    print(cost)

### FIXED CODE ###

h,w,d=map(int,input().split())
ind={}
for i in range(h):
    l=list(map(int,input().split()))

    for j in range(w):
        ind[l[j]]=(i,j)
table=[0]*((((h*w)//d).bit_length())*h*w)
now=1
for i in range(1,h*w-d+1):
    a,s=ind[i]
    de,f=ind[i+d]
    table[i-1+d]=abs(a-de)+abs(s-f)
step=2
for i in range(1,((h*w)//d).bit_length()):
    for j in range(1,h*w-step*d+1):
        table[j-1+step*d+i*h*w]=table[j-1+d*step//2+(i-1)*h*w]+table[j-1+d*step+(i-1)*h*w]
    step*=2
#print(*[table[k*h*w:k*w*h+h*w]for k in range(((h*w)//d).bit_length())],sep="\n")
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    times=(r-l)//d
    cost=0
    now=1
    kata=0
    while times:
        if times%2:
            l+=d*now
            cost+=table[l-1+kata*h*w]

        times//=2
        now*=2
        kata+=1
    print(cost)
### BUGGY CODE ###

def main():
  n, p = map(int, input().strip().split())
  s = input().strip()
  ans = 0
  if 10 % p == 0:
    for r in range(n):
      if int(s[r]) % p == 0:
        ans += r+1
    print(ans)
    return

  remains = [0] * (n+1)
  counts = [0] * p
  counts[0] += 1
  x = 1
  for r in range(n):
    remain = (int(s[-(r+1)]) * x) % p
    remains[-(r+1)] = (remains[-r] + remain) % p
    counts[remains[-(r+1)]] += 1
    x = (x * 10)
  for count in counts:
    ans += (count * (count - 1)) // 2
  print(ans)
 

if __name__=='__main__':
  main()


### FIXED CODE ###

n, p = map(int, input().split())
s = list(map(int, list(input())))[::-1]

sum = 0
cnt = [0] * p
cnt[0] = 1

ans = 0
if p in [2, 5]:
    if p == 2:
        ok_list = [0, 2, 4, 6, 8]
    if p == 5:
        ok_list = [0, 5]

    for i in range(n):
        d = s[i]
        if d in ok_list:
            ans += n - i

else:
    for i in range(n):
        d = s[i] * pow(10, i, p)
        sum = (sum + d) % p
        cnt[sum] += 1
    for i in range(p):
        ans += cnt[i] * (cnt[i]-1) // 2
print(ans)
### BUGGY CODE ###

import heapq
def SME():
    A = [[x,i] for i,x in enumerate(Whole)]
    A.sort()
    C = set([i for i in range(N)])
    D = set([])
    parameter = 0.997
    count = 0
    ANS = [None] * N
    for j in range(N) :
        a = A[j]
        for i,x in enumerate(ANS[a[1]:a[1]+L]):
            if x : continue
            else :
                ANS[a[1]+i] = a[0]
                D.add(a[1]+i)
                count += 1
        if count > N * parameter : break
    for i in C.difference(D):
        if i < L : ANS[i] = min(Whole[:i+1])
        else : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
ANS = SME()
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

N, P = map(int, input().split())
S = input()
from collections import Counter
ans = 0
if P == 2 or P == 5:
    for i in range(N-1, -1, -1):
        t = S[i]
        if not int(t) % P:
            ans += i + 1
else:
    c = Counter()
    c[0] += 1
    t = ""
    for i in range(N-1, -1, -1):
        t = S[i] + t
        r = int(t) % P
        c[r] += 1

    for a in c.values():
        ans += (a * (a-1)) // 2
print(ans)

### FIXED CODE ###

N, P = map(int, input().split())
S = input()
from collections import Counter
ans = 0
if P == 2 or P == 5:
    for i in range(N-1, -1, -1):
        t = S[i]
        if not int(t) % P:
            ans += i + 1
else:
    c = Counter()
    c[0] += 1
    p = 1
    t = int(S[N-1])
    c[t%P] += 1
    for i in range(N-2, -1, -1):
        p *= 10
        t = int(S[i]) * p + t
        c[t % P] += 1
        p %= P
    for a in c.values():
        ans += (a * (a-1)) // 2
print(ans)
### BUGGY CODE ###

# coding: utf-8
# Your code here!

MOD = 1000000007
S = input()

def add(a,b):
    a += b
    if a >= MOD:
        a -= MOD
    return a

dp = [[0 for i in range(5)] for j in range(2000000)]

dp[0][0] = 1

for i in range(len(S)):
    for j in range(4):
        if S[i] == '?':
            dp[i+1][j] = add(dp[i+1][j], dp[i][j] * 3 % MOD)
        else:
            dp[i+1][j] = add(dp[i+1][j], dp[i][j])
    if S[i] == 'A' or S[i] == '?':
        dp[i+1][1] = add(dp[i+1][1], dp[i][0])
    if S[i] == 'B' or S[i] == '?':
        dp[i+1][2] = add(dp[i+1][2], dp[i][1])
    if S[i] == 'C' or S[i] == '?':
        dp[i+1][3] = add(dp[i+1][3], dp[i][2])

print(dp[len(S)][3])

### FIXED CODE ###

# coding: utf-8
# Your code here!

MOD = 1000000007
S = input()

def add(a,b):
    a += b
    if a >= MOD:
        a -= MOD
    return a

dp = [[0 for i in range(5)] for j in range(200000)]

dp[0][0] = 1

for i in range(len(S)):
    for j in range(4):
        if S[i] == '?':
            dp[i+1][j] = add(dp[i+1][j], dp[i][j] * 3 % MOD)
        else:
            dp[i+1][j] = add(dp[i+1][j], dp[i][j])
    if S[i] == 'A' or S[i] == '?':
        dp[i+1][1] = add(dp[i+1][1], dp[i][0])
    if S[i] == 'B' or S[i] == '?':
        dp[i+1][2] = add(dp[i+1][2], dp[i][1])
    if S[i] == 'C' or S[i] == '?':
        dp[i+1][3] = add(dp[i+1][3], dp[i][2])

print(dp[len(S)][3])
### BUGGY CODE ###

import collections

def calc(one,two,three):
  if dp[one][two][three]!=-1:
    return dp[one][two][three]
  zero=n-one-two-three
  ret=0
  if zero!=n:
    ret=1/(1-zero/n)
  if one!=0:
    ret+=(calc(one-1,two,three)*one/n)/(1-zero/n)
  if two!=0:
    ret+=(calc(one+1,two-1,three)*two/n)/(1-zero/n)
  if three!=0:
    ret+=(calc(one,two+1,three-1)*three/n)/(1-zero/n)
  dp[one][two][three]=ret
  return ret

n=int(input())
arr=list(map(int,input().split()))
dp=[[[-1]*301 for _ in range(301)] for _ in range(301)]
cnt=[0,0,0,0]
for val in arr:
  cnt[val]+=1
calc(cnt[1],cnt[2],cnt[3])
print(dp[cnt[1]][cnt[2]][cnt[3]])

### FIXED CODE ###

import collections

n=int(input())
arr=list(map(int,input().split()))
dp=[[[0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]
cnt=collections.Counter(arr)
for total in range(1,n+1):
  for three in range(total+1):
    for two in range(total-three+1):
      one=total-two-three
      dp[one][two][three]+=n/total
      if one!=0:
        dp[one][two][three]+=dp[one-1][two][three]*one/total
      if two!=0:
        dp[one][two][three]+=dp[one+1][two-1][three]*two/total
      if three!=0:
        dp[one][two][three]+=dp[one][two+1][three-1]*three/total
print(dp[cnt[1]][cnt[2]][cnt[3]])
### BUGGY CODE ###

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

A.sort(reverse=True)

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

print(sum(A))

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = list(map(lambda x: int(x)*(-1), input().split()))

heapq.heapify(A)

for _ in range(M):
    mn = heapq.heappop(A)
    heapq.heappush(A, -mn//2*(-1))

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

s = list(input())
 
s_split = []
tmp = []
idx_all = []
l = -1
for i in range(len(s) - 1):
    tmp.append(s[i])
    if s[i] == 'R' and s[i + 1] == 'L':
        idx_all.append(i - l - 1)
    if s[i] == 'L' and s[i + 1] == 'R':
        s_split.append(tmp)
        tmp = []
        l = i
tmp.append(s[-1])
s_split.append(tmp)
 
out = ''
for a in range(len(s_split)):
    idx = idx_all[a]
    _split = s_split[a]
 
    if len(_split) % 2 == 0:
        r_int = len(_split) // 2
        l_int = len(_split) // 2
 
    else:
        if idx % 2 == 1:
            r_int = (len(_split) - 1) // 2
            l_int = (len(_split) + 1) // 2
 
        else:
            l_int = (len(_split) - 1) // 2
            r_int = (len(_split) + 1) // 2
 
    out += ' 0' * idx
    out += ' ' + str(r_int)
    out += ' ' + str(l_int)
    out += ' 0' * (len(_split) - idx - 2)
 
print(out[1:])

### FIXED CODE ###

s = list(input())

s_split = []
tmp = []
idx_all = []
l = -1
for i in range(len(s) - 1):
    tmp.append(s[i])
    if s[i] == 'R' and s[i + 1] == 'L':
        idx_all.append(i - l - 1)
    if s[i] == 'L' and s[i + 1] == 'R':
        s_split.append(tmp)
        tmp = []
        l = i
tmp.append(s[-1])
s_split.append(tmp)

out = ''
for a in range(len(s_split)):
    idx = idx_all[a]
    _split = s_split[a]

    if len(_split) % 2 == 0:
        r_int = len(_split) // 2
        l_int = len(_split) // 2

    else:
        if idx % 2 == 1:
            r_int = (len(_split) - 1) // 2
            l_int = (len(_split) + 1) // 2

        else:
            l_int = (len(_split) - 1) // 2
            r_int = (len(_split) + 1) // 2

    out += ' 0' * idx
    out += ' ' + str(r_int)
    out += ' ' + str(l_int)
    out += ' 0' * (len(_split) - idx - 2)

print(out[1:])
### BUGGY CODE ###

s=list(map(int,input().split()))
t=list(map(int,input().split()))
u=[list(map(int,input().split())) for i in range(s[1])]
t.sort()
a=0
for i in range(s[1]):
  for j in range(u[i][0]):
    if t[j]<u[i][1]:
      t[j]=u[i][1]
  t.sort()

for pq in range(s[0]):
  a=a+t[pq]
print(a)

### FIXED CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
B=[list(map(int,input().split())) for _ in range(M)]
B.sort(key=lambda x:-x[1])
i,j=0,0
while i<=N-1:
  for l in range(B[j][0]):
    if A[i]>=B[j][1]:
      print(sum(A))
      exit()
    A[i]=B[j][1]
    i+=1
    if i==N:
      print(sum(A))
      exit()
  j+=1
  if j==M:
    print(sum(A))
    exit()
print(sum(A))
### BUGGY CODE ###

h,w = map(int,input().split(" "))
s = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    tmp = list(input())
    for j in range(w):
        s[i][j] = tmp[j]

dp1 = [[-1 for i in range(w)] for j in range(h)]
dp2 = [[-1 for i in range(w)] for j in range(h)]
dp3 = [[-1 for i in range(w)] for j in range(h)]
dp4 = [[-1 for i in range(w)] for j in range(h)]





for i in range(w):
    for j in range(h):
        if s[j][i] == "#":
            dp3[j][i] = 0
        elif j == 0:
            dp3[j][i] = 1
        else:
            dp3[j][i] = 1 + dp3[j-1][i]

        if s[h-j-1][i] == "#":
            dp4[h-j-1][i] = 0
        elif h-j-1 == h-1:
            dp4[h-j-1][i] = 1
        else:
            dp4[h-j-1][i] = 1 + dp4[h-j][i]


a = 1
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            dp1[i][j] = 0
        elif j == 0:
            dp1[i][j] = 1
        else:
            dp1[i][j] = 1 + dp1[i][j-1]

        if s[i][w-j-1] == "#":
            dp2[i][w-j-1] = 0
        elif w-j-1 == w-1:
            dp2[i][w-j-1] = 1
        else:
            dp2[i][w-j-1] = 1 + dp2[i][w-j]
a = 1
for i in range(h):
    for j in range(w):
        a = max(a,dp1[i][j]+dp2[i][j]+dp3[i][j]+dp4[i][j]-3)


print(a)

### FIXED CODE ###

h,w = map(int,input().split(" "))
s = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    tmp = list(input())
    for j in range(w):
        s[i][j] = tmp[j]

dp1= []
dp2= [[-1 for i in range(w)] for j in range(h)]
dp3=[]
dp4=[[-1 for i in range(w)] for j in range(h)]


for i in range(h):
    dp1.append([])
    dp3.append([])
    for j in range(w):
        dp1[i].append(-1)
        dp3[i].append(-1)

        if s[i][j] == "#":
            dp1[i][j] = 0
        elif j == 0:
            dp1[i][j] = 1
        else:
            dp1[i][j] = 1 + dp1[i][j-1]

        if s[i][w-j-1] == "#":
            dp2[i][w-j-1] = 0
        elif w-j-1 == w-1:
            dp2[i][w-j-1] = 1
        else:
            dp2[i][w-j-1] = 1 + dp2[i][w-j]

        if s[i][j] == "#":
            dp3[i][j] = 0
        elif i == 0:
            dp3[i][j] = 1
        else:
            dp3[i][j] = 1 + dp3[i-1][j]

        if s[h-i-1][j] == "#":
            dp4[h-i-1][j] = 0
        elif h-i-1 == h-1:
            dp4[h-i-1][j] = 1
        else:
            dp4[h-i-1][j] = 1 + dp4[h-i][j]



        

a = 1
for i in range(h):
    for j in range(w):
        a = max(a,dp1[i][j]+dp2[i][j]+dp3[i][j]+dp4[i][j]-3)


print(a)
### BUGGY CODE ###

L,R= map(int,input().split())
#境界条件
bool = True
for i in range(L,R):
    for j in range(i+1,R+1):
        temp = (i * j) % 2019
        if bool:
            min = temp
            ans = min
            bool = False
        elif min > temp:
            min = temp
            ans = min
        if min == 0:
            break
print(ans)

### FIXED CODE ###

L,R= map(int,input().split())
#境界条件
bool = True
flag = False
for i in range(L,R):
    for j in range(i+1,R+1):
        temp = (i * j) % 2019
        if bool:
            min = temp
            ans = min
            bool = False
        elif min > temp:
            min = temp
            ans = min
        if min == 0:
            flag = True
            break
    if flag:
        break
print(ans)
### BUGGY CODE ###

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

count = 0

for r in range(N//R + 1):
    for g in range(N//G + 1):
        if 0 <= (N - R * r - G * g) and (N - R * r - G * g) % B == 0:
            count += 1

print(count)

### FIXED CODE ###

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

count = 0

for r in range(N//R + 1):
    for g in range(N//G + 1):
        if 0 <= (N - R * r - G * g) and (N - R * r - G * g) % B == 0:
            count += 1

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

n, m = input().split()
N = int(n)
M = int(m)

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

for _ in range(M):
    a = max(enumerate(A), key=lambda x: x[1])

    A[a[0]] = a[1] // 2

print(sum(A))


### FIXED CODE ###

N, M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
it = 0
for i in range(M):
    A[it]=A[it]//2
    if it<N-1:
        if A[it]<A[it+1] and A[0]<A[it+1]:
            it+=1
        else:
            A.sort(reverse = True)
            it = 0
    if it == N-1:
        A.sort(reverse = True)
        it = 0
print(sum(A))
### BUGGY CODE ###

def yakusu(n):
    max_yakusu = int(n**0.5)
    arr = [1]
    tmp = 2

    while n > 1:
        for i in range(tmp,max(n+1,max_yakusu+1)):
            if n % i == 0:
                while n % i == 0:
                    arr.append(i)
                    n = int(n/i)
                    tmp = i + 1
                break
    return arr

def gcd(x,y):
    if y == 0:
       return x
    else:
       return gcd(y, x % y)

A,B = [int(x) for x in input().split()]
koyaku = gcd(A,B)

koyaku_insu = set(yakusu(koyaku))


print(len(koyaku_insu))

### FIXED CODE ###

def prime_factorize(n):
    a = [1]
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
  
def gcd(x,y):
    if y == 0:
       return x
    else:
       return gcd(y, x % y)
 
A,B = [int(x) for x in input().split()]
koyaku = gcd(A,B)
 
koyaku_insu = list(set(prime_factorize(koyaku)))
 
 
print(len(koyaku_insu))
### BUGGY CODE ###

K=int(input())
if K%2 == 0 or K%5 == 0:
  print(-1)
else:
  base = ''
  count = 1
  while(1):
    base += '7'
    if int(base)%K == 0:
      print(count)
      break
    else:
      count += 1
    if count > K:
      print(-1)
      break
  


### FIXED CODE ###

K = int(input())
base = 0

for count in range(1, K+1):
  num = base*10 + 7
  if (num%K == 0):
    print(count)
    exit()
  else:
    base = num%K
print(-1)
### BUGGY CODE ###

import itertools
from functools import lru_cache

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

XY = [[int(x) for x in input().split()] for _ in range(N)]
X,Y = zip(*XY)

@lru_cache(None)
def cnt(x,y):
  c = 0
  for x1,y1 in XY:
    if x1 <= x and y1 <= y:
      c += 1
  return c

min_area = 5*10**18

for x1,x2 in itertools.combinations(X,2):
  for y1,y2 in itertools.combinations(Y,2):
    if x1 > x2:
      x1,x2 = x2,x1
    if y1 > y2:
      y1,y2 = y2,y1

    area = (x2-x1) * (y2-y1)
    if area > min_area:
      continue
    
    c = cnt(x2,y2) - cnt(x2,y1-1) - cnt(x1-1,y2) + cnt(x1-1,y1-1)
    if c < K:
      continue
      
    min_area = area
    
print(min_area)

### FIXED CODE ###

import itertools

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

X = []
Y = []

for _ in range(N):
  x,y = map(int, input().split())
  X.append(x)
  Y.append(y)

# 全部数えても間に合う

min_area = 5*10**18

for x1,x2 in itertools.combinations(X,2):
  for y1,y2 in itertools.combinations(Y,2):
    if x1 > x2:
      x1,x2 = x2,x1
    if y1 > y2:
      y1,y2 = y2,y1

    area = (x2-x1) * (y2-y1)
    if area > min_area:
      continue
      
    cnt = 0
    for x,y in zip(X,Y):
      if x1 <= x <= x2 and y1 <= y <= y2:
        cnt += 1
    if cnt < K:
      continue
      
    min_area = area
    
print(min_area)
### BUGGY CODE ###

import math

n = int(input())

start = math.ceil(n**0.5)

for i in range(start ,n+1):
    if n % i == 0:
        a = i
        b = n // i
        break

print(a + b -2)

### FIXED CODE ###

import math

n = int(input())

start = int(math.sqrt(n)+0.5)
l =[]
for i in range(1,start+1):
    if n % i == 0:
        a = i
        b = n // i
        l.append(a+b-2)

print(min(l))
### BUGGY CODE ###

import math
k = int(input())
ans = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            res = math.gcd(math.gcd(a,b), c)
            ans += res
print(ans)

### FIXED CODE ###

import math
k = int(input())
ans = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        res = math.gcd(a,b)
        for c in range(1,k+1):
            ans += math.gcd(res, c)

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

n,m=map(int,input().split())
ass=[tuple(map(int,input().split())) for i in range(m)]

ass.sort(key = lambda x:x[1])
count = 0

while ass != []:
    count = count+1
    ref = ass[0]
    #print('ref',ref)
    ass.sort(key = lambda x:x[0])
    #print('sortedass',ass)
    index = next((i for i,x in enumerate(ass) if x[0]>=ref[1]),len(ass) )
    ass = ass[index::]
    ass.sort(key = lambda x:x[1])
    #print(index)
    #print(ass)

print(count)



### FIXED CODE ###

n,m=map(int,input().split())
ass=[tuple(map(int,input().split())) for i in range(m)]
ass.sort(key=lambda x:x[1])

acum = []

def ifsatisfied(ab):
    for x in acum:
        if ab[0]<x <=ab[1]:
            return(True)
    return(False)

for ab in ass:
    if not ifsatisfied(ab):
        acum.append(ab[1])

print(len(acum))
### BUGGY CODE ###

N,K = map(int,input().split())
A = sorted([list(map(int,input().split())) for _ in range(N)],key=lambda x:x[1],reverse=True)
C = {}
tot1 = 0
for i in range(K):
    t,d = A[i]
    if t not in C:
        C[t] = 0
    C[t] += 1
    tot1 += d
tot2 = len(C)
tot = tot1+tot2**2
cur = K
for i in range(K-1,-1,-1):
    t,d = A[i]
    if C[t]>1:
        tot1 -= d
        C[t] -= 1
        j = cur
        while j<N:
            t1,d1 = A[j]
            if t1 not in C:
                C[t1]=1
                tot1 += d1
                tot2 += 1
                if tot1+tot2**2>tot:
                    tot = tot1+tot2**2
                    cur = j+1
                break
            else:
                j += 1
print(tot)

### FIXED CODE ###

N,K = map(int,input().split())
A = sorted([list(map(int,input().split())) for _ in range(N)],key=lambda x:x[1],reverse=True)
C = {}
tot1 = 0
for i in range(K):
    t,d = A[i]
    if t not in C:
        C[t] = 0
    C[t] += 1
    tot1 += d
tot2 = len(C)
tot = tot1+tot2**2
cur = K
for i in range(K-1,-1,-1):
    t,d = A[i]
    if C[t]>1:
        tot1 -= d
        C[t] -= 1
        j = cur
        while j<N:
            t1,d1 = A[j]
            if t1 not in C:
                C[t1]=1
                tot1 += d1
                tot2 += 1
                if tot1+tot2**2>tot:
                    tot = tot1+tot2**2
                cur = j+1
                break
            else:
                j += 1
                cur = j
print(tot)
### BUGGY CODE ###

n = int(input())
P = list(map(int, input().split()))
cnt = 0
for i, p in enumerate(P):
    if p == min(P[:i + 1]):
        cnt += 1
print(cnt)


### FIXED CODE ###

n = int(input())
P = list(map(int, input().split()))
cnt = 0
m = P[0]
for p in P:
    if m >= p:
        cnt += 1
        m = p
print(cnt)
### BUGGY CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
 
n,m = na()
a = na()
for i in range(m):
    b,c = na()
    a += [c]*b

aa = list(reversed(sorted(a)))

print(sum(aa[:n]))

### FIXED CODE ###

import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,m = na()
a = na()

bc = [na() for i in range(m)]
bc.sort(key=lambda x:x[1])

for b,c in bc[::-1]:
  a.extend([c]*b)
  if len(a)>2*n:
    break

a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
import numpy as np
a0 = np.array(a)
b0 = np.array(b)
c0 = np.array(c)
count = 0
for i in range(n):
    L_A = 0
    L_C = 0
    A = a0[a0<b[i]]
    L_A = len(A)
    C = c0[c0>b[i]]
    L_C = len(C)
    count += L_A*L_C
print(count)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
a = sorted(a)
b = sorted(b)
c = sorted(c)
count = 0
import bisect
for i in range(n):
    A = bisect.bisect_right(a,b[i]-1)
    C = bisect.bisect_left(c,b[i]+1)
    count += A*(n-C)
print(count)