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

# -*- coding: utf-8 -*-

# 整数の入力
a = int(input())
# # スペース区切りの整数の入力
nums = list(map(int, input().split()))

vilist = []
for i in range(a):
    vilist.append((nums[i], i))
vilist = sorted(vilist, key=lambda vi: vi[0])

# dp[x][y]をx人を左から活性度順に並べて、y人を右から活性度順に並べた状態のスコア最大値とする
dp = []
for i in range(a):
    dp.append([0]*(a-i))

# dp = [[0] * a for i in range(a)]

cnt = 0
# dp[i][j]を考える
for k in range(a-1):
    vi = vilist.pop()
    v = vi[0]
    p = vi[1]
    vi_z = vilist[0]
    vz = vi_z[0]
    pz = vi_z[1]
    for i in range(k + 2):
        cnt += 1
        j = k - i + 1
        if i == 0 and j == 0:
            continue

        # 最後の値は場所が特定できるのでそのまま計算させる
        if k == a - 2:
            if j == 0:
                dp[i][0] = dp[i-1][0] + v * abs(p - i + 1) + vz * abs(pz - i)
            elif i == 0:
                dp[0][j] = dp[0][j-1] + v * abs(a - j - p) + vz * abs(a - j - 1 - pz)
            else:
                dp[i][j] = max(dp[i-1][j] + v * abs(p - i + 1) + vz * abs(pz - i),
                               dp[i][j-1] + v * abs(a - j - p) + vz * abs(pz - i))
        else:
            if j == 0:
                dp[i][0] = dp[i-1][0] + v * abs(p - i + 1)
            elif i == 0:
                dp[0][j] = dp[0][j-1] + v * abs(a - j - p)
            else:
                dp[i][j] = max(dp[i-1][j] + v * abs(p - i + 1),
                               dp[i][j-1] + v * abs(a - j - p))

# print(cnt)
print(max([max(x) for x in dp]))


### FIXED CODE ###

# -*- coding: utf-8 -*-


def main():

    # 整数の入力
    a = int(input())
    # # スペース区切りの整数の入力
    nums = list(map(int, input().split()))

    vilist = []
    for i in range(a):
        vilist.append((nums[i], i))
    vilist = sorted(vilist, key=lambda vi: vi[0])

    # dp[x][y]をx人を左から活性度順に並べて、y人を右から活性度順に並べた状態のスコア最大値とする
    dp = []
    for i in range(a):
        dp.append([0]*(a-i))

    # dp = [[0] * a for i in range(a)]

    # cnt = 0
    # dp[i][j]を考える
    for k in range(a-1):
        vi = vilist.pop()
        v = vi[0]
        p = vi[1]
        vi_z = vilist[0]
        vz = vi_z[0]
        pz = vi_z[1]

        for i in range(k + 2):
            # cnt += 1
            j = k - i + 1
            # if i == 0 and j == 0:
            #     continue

            # 最後の値は場所が特定できるのでそのまま計算させる
            if k == a - 2:
                if j == 0:
                    dp[i][0] = dp[i-1][0] + v * abs(p - i + 1) + vz * abs(pz - i)
                elif i == 0:
                    dp[0][j] = dp[0][j-1] + v * abs(a - j - p) + vz * abs(a - j - 1 - pz)
                else:
                    dp[i][j] = max(dp[i-1][j] + v * abs(p - i + 1) + vz * abs(pz - i),
                                   dp[i][j-1] + v * abs(a - j - p) + vz * abs(pz - i))
            else:
                if j == 0:
                    dp[i][0] = dp[i-1][0] + v * abs(p - i + 1)
                elif i == 0:
                    dp[0][j] = dp[0][j-1] + v * abs(a - j - p)
                else:
                    dp[i][j] = max(dp[i-1][j] + v * abs(p - i + 1),
                                   dp[i][j-1] + v * abs(a - j - p))

    # print(cnt)
    print(max([max(x) for x in dp]))


main()
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
out = []
for i in range(1, N+1):
    if i not in A:
        print(0)
    else:
        print(A.count(i))


### FIXED CODE ###

import collections

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

c = collections.Counter(A)

for i in range(1, N+1):
    if i not in c:
        print(0)
    else:
        print(c[i])
### BUGGY CODE ###

import itertools

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
B = list(map(int, input().split()))
B.sort(reverse=True)
C = list(map(int, input().split()))
C.sort(reverse=True)

AB = []
for p in itertools.product(A, B):
    AB.append(sum(p))
AB.sort(reverse=True)
AB = AB[:K]

l = []
for p in itertools.product(AB, C):
    l.append(sum(p))
l.sort(reverse=True)
for i in range(K):
    print(l[i])

### FIXED CODE ###

x,y,z,k = map(int,input().split())
lisa = list(map(int,input().split()))
lisb = list(map(int,input().split()))
lisc = list(map(int,input().split()))
lisa.sort(reverse=True)
lisb.sort(reverse=True)
lisc.sort(reverse=True)
an = []
ans = []
for num in lisb:
    for nu in lisa:
        an.append(num+nu)
an.sort(reverse=True)
an = an[:min(3001,x*y*z+1)]
for num in lisc:
    for nu in an:
        ans.append(num+nu)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

H = int(input())

lst = [H]
cnt = 0
while len(lst) > 0:
    cnt += 1
    mon = lst.pop()
    if mon == 1:
        continue
    else:
        new_mon = (mon // 2)
        lst.append(new_mon)
        lst.append(new_mon)
        
print(cnt)

### FIXED CODE ###

H = int(input())

import math
n = int(math.log(H, 2))

ans = 0
for i in range(n + 1):
    ans += pow(2, i)
    
print(ans)
### BUGGY CODE ###

s = input()
n = len(s)
ans = 0
i = 1

while i < n:
    if s[i-1] == "0" and s[i] == "1":
        s = s[:i-1] + s[i+1:]
        n -= 2
        ans += 2
        i = 1
        if n == 0 or n == 1:
            print(ans)
            exit()
        continue
    elif s[i-1] == "1" and s[i] == "0":
        s = s[:i-1] + s[i+1:]
        n -= 2
        ans += 2
        i = 1
        if n == 0 or n == 1:
            print(ans)
            exit()
        continue
    else:
        i += 1
        
print(ans)

### FIXED CODE ###

s = input()
n = len(s)
x = []

for i in s:
    x.append(i)

cnt_0 = x.count("0")
cnt_1 = x.count("1")

if cnt_0 == cnt_1:
    print(n)
else:
    print((2*min(cnt_0, cnt_1)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

from fractions import gcd


MOD = 10**9+7
N = int(input())
F = []
zero_v = 0
inf = 0
zero = 0
for _ in range(N):
  x,y = map(int,input().split())
  if x==0 and y==0:
    zero_v += 1
  elif x==0:
    inf += 1
  elif y==0:
    zero += 1
  else:
    G = gcd(abs(x),abs(y))
    F.append((x//G,y//G))

all_keys = set()

for x,y in F:
  if x*y >0:
    if x>0:
      all_keys.add((x,y))
    else:
      all_keys.add((-x,-y))
  x,y = -y,x
  if x*y >0:
    if x>0:
      all_keys.add((x,y))
    else:
      all_keys.add((-x,-y))

all_dic = {k:[0,0] for k in all_keys}

for x,y in F:
  if x*y > 0:
    if x>0:
      all_dic[(x,y)][0] += 1
    else:
      all_dic[(-x,-y)][0] += 1
  else:
    if x>0:
      all_dic[(-y,x)][1] += 1
    else:
      all_dic[(y,-x)][1] += 1

ans = (pow(2,inf,MOD)) + (pow(2,zero,MOD))-1
ans %= MOD

for k in all_keys:
  P,N = all_dic[k]
  ans *= (pow(2,P,MOD)) + (pow(2,N,MOD))-1
  ans %= MOD


ans += zero_v-1

print(ans%MOD)


### FIXED CODE ###

import sys
input = sys.stdin.readline

def gcd(a, b):
  while b:
    a, b = b, a % b
  return a

MOD = 10**9+7
N = int(input())
F = []
zero_v = 0
inf = 0
zero = 0
for _ in range(N):
  x,y = map(int,input().split())
  if x==0 and y==0:
    zero_v += 1
  elif x==0:
    inf += 1
  elif y==0:
    zero += 1
  else:
    G = gcd(abs(x),abs(y))
    F.append((x//G,y//G))

all_keys = set()

for x,y in F:
  if x*y >0:
    if x>0:
      all_keys.add((x,y))
    else:
      all_keys.add((-x,-y))
  x,y = -y,x
  if x*y >0:
    if x>0:
      all_keys.add((x,y))
    else:
      all_keys.add((-x,-y))

all_dic = {k:[0,0] for k in all_keys}

for x,y in F:
  if x*y > 0:
    if x>0:
      all_dic[(x,y)][0] += 1
    else:
      all_dic[(-x,-y)][0] += 1
  else:
    if x>0:
      all_dic[(-y,x)][1] += 1
    else:
      all_dic[(y,-x)][1] += 1

ans = (pow(2,inf,MOD)) + (pow(2,zero,MOD))-1
ans %= MOD

for k in all_keys:
  P,N = all_dic[k]
  ans *= (pow(2,P,MOD)) + (pow(2,N,MOD))-1
  ans %= MOD


ans += zero_v-1

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

import sys

input = sys.stdin.readline

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

tmp1 = 1
tmp2 = 1
for i in range(k):
    tmp1 *= a[i]

for i in range(k, n):
    tmp2 = (tmp1 // a[i - k]) * a[i]
    print(["No", "Yes"][tmp1 < tmp2])
    tmp1 = tmp2

### FIXED CODE ###

import sys

input = sys.stdin.readline

import sys

input = sys.stdin.readline

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

for i in range(k, n):
    print(["No", "Yes"][a[i - k] < a[i]])
### BUGGY CODE ###

n = int(input())
s = str(input())
ans = 0
rr,gg,bb = [],[],[]
for i in range(0,len(s)):
    if s[i] == "R":
        rr.append(i)
    elif s[i] == "G":
        gg.append(i)
    else:
        bb.append(i)

for i in range(0,len(rr)):
    for j in range(0,len(gg)):
        che = 0
        a = rr[i] + gg[j]
        if a % 2 == 0:
            if s[a//2] == "B":
                che += -1
        b = min(rr[i],gg[j]) - abs(rr[i]-gg[j])
        if b >= 0:
            if s[b] == "B":
                che += -1
        c = max(rr[i],gg[j]) + abs(rr[i]-gg[j])
        if c < n:
            if s[c] == "B":
                che += -1
        ans += len(bb)
        ans += che

print(ans)

### FIXED CODE ###

n = int(input())
s = str(input())
rr,gg = [],[]
for i in range(0,len(s)):
    if s[i] == "R":
        rr.append(i)
    elif s[i] == "G":
        gg.append(i)

bb = len(s) -len(rr) -len(gg)
ans = len(rr) * len(gg) * bb
for i in range(0,len(rr)):
    for j in range(0,len(gg)):
        che = 0
        a = rr[i] + gg[j]
        if a % 2 == 0:
            if s[a//2] == "B":
                che += -1
        b = min(rr[i],gg[j]) - abs(rr[i]-gg[j])
        if b >= 0:
            if s[b] == "B":
                che += -1
        c = a - b
        if c < n:
            if s[c] == "B":
                che += -1
        ans += che

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

MOD = 10**9 + 7

s = input().strip()
ss = s[::-1]
rs = [10**i % 13 for i in range(6)]

n = len(s)
dp = [[0] * 13 for _ in range(n)]
for i, c in enumerate(ss):
    if i == 0:
        if c == '?':
            for j in range(10):
                dp[i][j] = 1
        else:
            dp[i][int(c)] = 1
    else:
        r = rs[i % 6]
        if c == '?':
            for j in range(13):
                for k in range(10):
                    dp[i][(j + r * k) % 13] += dp[i - 1][j]
        else:
            for j in range(13):
                dp[i][(j + r * int(c)) % 13] += dp[i - 1][j]
print(dp[n - 1][5] % MOD)

### FIXED CODE ###

MOD = 10**9 + 7

s = input().strip()
ss = s[::-1]
rs = [10**i % 13 for i in range(6)]

n = len(s)
dp = [[0] * 13 for _ in range(n)]
for i, c in enumerate(ss):
    if i == 0:
        if c == '?':
            for j in range(10):
                dp[i][j] = 1
        else:
            dp[i][int(c)] = 1
    else:
        r = rs[i % 6]
        if c == '?':
            for j in range(13):
                for k in range(10):
                    dp[i][(j + r * k) % 13] += dp[i - 1][j]
        else:
            for j in range(13):
                dp[i][(j + r * int(c)) % 13] += dp[i - 1][j]
        for j in range(13):
            dp[i][j] %= MOD
print(dp[n - 1][5] % MOD)
### BUGGY CODE ###

N,Y=[int(s) for s in input().split()]
##N枚でY円
flag=0
i10=0
while i10*10000<=Y:
  i5=0
  while i10*10000+i5*5000<=Y:
    i1=0
    while i10*10000+i5*5000+i1*1000<=Y:
      if i10*10000+i5*5000+i1*1000==Y and i10+i5+i1==N:
        print(*[i10,i5,i1])
        flag=1
        break
      i1+=1
    if flag==1 : break
    i5+=1
  if flag==1 : break
  i10+=1
else:
  print(*[-1,-1,-1])


### FIXED CODE ###

N,Y=[int(s) for s in input().split()]
##N枚でY円
flag=0
i10=0
while i10*10000<=Y and i10<=N:
  i5=0
  while i10*10000+i5*5000<=Y and i10+i5<=N :
    i1=N-i10-i5
    if i10*10000+i5*5000+i1*1000==Y:
      print(*[i10,i5,i1])
      flag=1
      break
    i5+=1
  if flag==1 : break
  i10+=1
else:
  print(*[-1,-1,-1])
### BUGGY CODE ###

a, b, c, d = (int(x) for x in input().split())
ans = 0
for i in range(a, b+1, 1):
    if i%c != 0 and i%d != 0:
        ans += 1
print(ans)

### FIXED CODE ###

import fractions
 
a, b, c, d = (int(x) for x in input().split())
def kansu(x,y,z):
    sta = x
    end = y
    if sta%z != 0:
        sta = sta+(z-(sta%z))
    if end%z != 0:
        end = end-(end%z)
    ans = ((end-sta)//z) +1
    return ans
a1 = kansu(a,b,c)
a2 = kansu(a,b,d)
lcm = c*d//(fractions.gcd(c,d))
a3 = kansu(a,b,lcm)
print(b-a-a1-a2+a3+1)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a%b)
def list_euclid(int_list):
    ans = int_list[0]
    for i in range(1,len(int_list)):
        ans = euclid(ans, int_list[i])
    return ans
n = int(input())
a = list(map(int, input().split()))
max = 0
if n < 5:
    for i in range(0,n):
        new_list = a[:]
        del new_list[i]
        x = list_euclid(new_list)
        if max < x:
            max = x
else:
    for i in range(0,n):
        new_list = a[:]
        del new_list[i]
        k = n // 2
        y = list_euclid(new_list[0:k])
        z = list_euclid(new_list[k:n-1])
        x = euclid(y, z)
        if max < x:
            max = x
print(max)

### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
import sys
def gcd(a, b): #最大公約数
  while b:
    a, b = b, a % b
  return int(a)
    
n = int(input())
a = list(map(int, input().split()))
if n==2:
  print(max(a))
  sys.exit(0)
elif n==3:
  lis = [gcd(a[0], a[1]), gcd(a[1], a[2]), gcd(a[2], a[0])]
  print(max(lis))
  sys.exit(0)
tmp_unused = gcd(a[0], a[1])
tmp_used = max(a[0], a[1])
#print("used=", tmp_used, "unused=", tmp_unused)
for i in range(2,n):
  #print(a[i])
  tmp_used = max(tmp_unused, gcd(tmp_used, a[i]))
  tmp_unused = gcd(tmp_unused, a[i])
  
  #print("used=", tmp_used, "unused=", tmp_unused)
print(tmp_used)
### BUGGY CODE ###



r=[]
for i in range(128):
    A=i-63
    for j in range(128):
        B=j-63
        r.append((A**5-B**5,A,B))
r.sort()

target=int(input())
lwbd = 0
upbd = len(r)

while lwbd<upbd:
    middle = lwbd+ (upbd-lwbd)//2
    if(r[middle][0]==target):
        break
    elif r[middle][0]>target:
        upbd = middle
    else:
        lwbd = middle
print(r[middle][1],r[middle][2])

### FIXED CODE ###



r=[]
for i in range(230):
    A=i-125
    for j in range(230):
        B=j-125
        r.append((A**5-B**5,A,B))
r.sort()

target=int(input())
lwbd = 0
upbd = len(r)


while lwbd<=upbd:
    middle = lwbd + (upbd-lwbd)//2
    if(r[middle][0]==target):
        break
    elif r[middle][0]>target:
        upbd = middle -1
    else:
        lwbd = middle +1
print(r[middle][1],r[middle][2])
### BUGGY CODE ###

import fileinput


class Cache():
    def __init__(self, n_1, n_2, n_3):
        self._n_1 = n_1 + n_2 + n_3 + 1
        self._n_2 = n_2 + n_3 + 1
        self._n_3 = n_3 + 1

        self._arr = [0.0] * (self._n_1 * self._n_2 * self._n_3)

    def get(self, n_1, n_2, n_3):
        return self._arr[n_1 + n_2 * self._n_1 + n_3 * self._n_1 * self._n_2]

    def add(self, n_1, n_2, n_3, val):
        self._arr[n_1 + n_2 * self._n_1 + n_3 * self._n_1 * self._n_2] = val


def num_turns(total, n_1, n_2, n_3, cache):
    for i_3 in range(n_3 + 1):
        for i_2 in range(n_2 + 1 + n_3 - i_3):
            for i_1 in range(n_1 + 1 + n_2 + n_3 - i_3 - i_2):
                with_sushi = i_1 + i_2 + i_3
                if with_sushi == 0:
                    cache.add(i_1, i_2, i_3, 0)
                    continue
                expectation = total / with_sushi
                if i_1 > 0:
                    p = i_1 / with_sushi
                    expectation += p * cache.get(i_1 - 1, i_2, i_3)

                if i_2 > 0:
                    p = i_2 / with_sushi
                    expectation += p * cache.get(i_1 + 1, i_2 - 1, i_3)

                if i_3 > 0:
                    p = i_3 / with_sushi
                    expectation += p * cache.get(i_1, i_2 + 1, i_3 - 1)
                cache.add(i_1, i_2, i_3, expectation)
    return cache.get(n_1, n_2, n_3)


inp = fileinput.FileInput()
total = int(inp.readline())

n_1 = 0
n_2 = 0
n_3 = 0

for v in inp.readline().split(" "):
    v = int(v)
    if v == 1:
        n_1 += 1
    if v == 2:
        n_2 += 1
    if v == 3:
        n_3 += 1

print(num_turns(total, n_1, n_2, n_3, Cache(n_1, n_2, n_3)))

### FIXED CODE ###

import fileinput


def num_turns(total, n_1, n_2, n_3):
    _n_1 = n_1 + n_2 + n_3 + 1
    _n_2 = n_2 + n_3 + 1
    _n_3 = n_3 + 1

    _arr = [0.0] * (_n_1 * _n_2 * _n_3)

    for i_3 in range(n_3 + 1):
        for i_2 in range(n_2 + 1 + n_3 - i_3):
            for i_1 in range(n_1 + 1 + n_2 + n_3 - i_3 - i_2):
                with_sushi = i_1 + i_2 + i_3
                if with_sushi == 0:
                    continue
                expectation = total / with_sushi
                if i_1 > 0:
                    p = i_1 / with_sushi
                    expectation += p * _arr[(i_1 - 1) + i_2 * _n_1 + i_3 * _n_1 * _n_2]

                if i_2 > 0:
                    p = i_2 / with_sushi
                    expectation += p * _arr[i_1 + 1 + (i_2 - 1) * _n_1 + i_3 * _n_1 * _n_2]

                if i_3 > 0:
                    p = i_3 / with_sushi
                    expectation += p * _arr[i_1 + (i_2 + 1) * _n_1 + (i_3 - 1) * _n_1 * _n_2]
                _arr[i_1 + i_2 * _n_1 + i_3 * _n_1 * _n_2] = expectation

    return _arr[n_1 + n_2 * _n_1 + n_3 * _n_1 * _n_2]


inp = fileinput.FileInput()
total = int(inp.readline())

n_1 = 0
n_2 = 0
n_3 = 0

for v in inp.readline().split(" "):
    v = int(v)
    if v == 1:
        n_1 += 1
    if v == 2:
        n_2 += 1
    if v == 3:
        n_3 += 1

print(num_turns(total, n_1, n_2, n_3))
### BUGGY CODE ###

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

a_list = []
b_list = []
for i in range(n):
    a,b = map(int, input().split())
    a_list.append(a)
    b_list.append(b)

ans = 0
for i in range(m):
    i = i+1
    if min(a_list) <= i:
        # ind = a_list.index(max(b_list[list(map(lambda x : x < i+1,b_list))]))
        max_num = max( map(lambda y: y[0] * (y[1] <=i) ,zip(b_list,a_list)))
        # ind = a_list.index(max(b_list * list(map(lambda x : x <= i,a_list))))
        ind = b_list.index(max_num)
        ans = ans + b_list[ind]
        a_list[ind] = m + 1

print(ans)

# print( list(map(lambda x : x < 3,[1,2,3,4])))
# list(map(lambda x : x < i+1,b_list))

# print( [1,2,3,4] * [True,False,True,False])
# print(1 * False)


### FIXED CODE ###

n,m = map(int,input().split())
db = []

for i in range(n):
    a,b = map(int,input().split())
    if(a<=m):
        db.append([m-a,-1*b])

db.sort(reverse=True)

# ヒープキュー（最小値・最大値の取得）
import heapq
a=[]
heapq.heapify(a)

ans = 0
pnt = 0
day = m-1
while(day>=0):
    if(pnt < len(db)):
        while(db[pnt][0] == day):
            heapq.heappush(a,db[pnt][1])
            pnt += 1
            if(pnt == len(db)):
                break
    day -= 1

    if(len(a) > 0):
        ans -= heapq.heappop(a)

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

from collections import deque

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

pos = a.index(min(a))
na = [a[pos]] + a[pos+1:] + a[:pos]

ans = sum(a)
for k in range(1, N):
    d = deque([], k + 1)
    b = []
    for i in range(N):
        d.append(na[i])
        # print(d)
        b.append(min(d))
    # print(k, b)
    ans = min(ans, k * x + sum(b))
print(ans)


### FIXED CODE ###

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

pos = a.index(min(a))
na = [a[pos]] + a[pos+1:] + a[:pos]

ans = sum(a)
old_b = na[:]
for k in range(1, N):
    b = []
    for i in range(N):
        if i - k >= 0:
            b.append(min(old_b[i], na[i - k]))
        else:
            b.append(old_b[i])
    # print(k, b)
    old_b = b
    ans = min(ans, k * x + sum(b))
print(ans)
### BUGGY CODE ###

from collections import defaultdict

n, k = map(int, input().split())
ans = 0
sushi = defaultdict(list)

for _ in range(n):
    t, d = map(int, input().split())
    sushi[t].append(d)

most_tasty = []
other_sushi = []

for key, value in sushi.items():
    value.sort(reverse=True)
    most_tasty.append(value[0])
    value.pop(0)
    other_sushi += value

most_tasty.sort(reverse=True)
other_sushi.sort(reverse=True)
for i in range(1, k + 1):
    num = min(i, len(most_tasty))
    point = sum(most_tasty[:num])
    point += sum(other_sushi[:(k - num)])
    point += num ** 2
    ans = max(ans, point)

print(ans)


### FIXED CODE ###

from collections import defaultdict

n, k = map(int, input().split())
top = [0] * n
sub = []

for i in range(n):
    t, d = map(int, input().split())
    t -= 1
    if top[t] == 0:
        top[t] = d
    else:
        if d > top[t]:
            sub.append(top[t])
            top[t] = d
        else:
            sub.append(d)

top.sort(reverse=True)
top_sum = [0]
sub.sort(reverse=True)
sub_sum = [0]

for p in top:
    if p == 0:
        top_sum.append(-1)
    else:
        top_sum.append(top_sum[-1] + p)

for p in sub:
    sub_sum.append(sub_sum[-1] + p)

ans = 0

for i in range(1, k + 1):
    if (len(sub_sum) - 1) >= (k - i) and top_sum[i] != -1:
        ans = max(ans, top_sum[i] + sub_sum[k - i] + i ** 2)

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

k,s=map(int,input().split())
l=[x+y+z for z in range(k+1) for y in range(k+1) for x in range(k+1)]
print(l.count(s))

### FIXED CODE ###

k,s=map(int,input().split())
ans=0
for i in range(k+1):
    x=min(s-i,k)-max(0,s-k-i)
    if x>=0:
        ans+=x+1
print(ans)
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
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 input(): return sys.stdin.readline().strip()
def INT(): return int(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()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

max_length = len("{:b}".format(max(A)))

cnt = [defaultdict(int) for _ in range(max_length)]

for i in range(N):
    num = "{:b}".format(A[i]).zfill(max_length)
    for j in range(len(num)):
        # [i桁目][numのj番目の数，(0 or 1)]
        # 0, 1 の数を数える
        cnt[max_length-1-j][num[j]] += 1

ans = 0

for i in range(max_length):
    # 1を左にiシフト(2 ** i 倍)
    # 桁内で0の個数 * 桁内で1の個数 が，XOR = 1になる数 (0 xor 1 = 1)
    ans = ans + (1 << i) * cnt[i]["0"] * cnt[i]["1"]
ans = ans % mod
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
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 input(): return sys.stdin.readline().strip()
def INT(): return int(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()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
N = INT()
A = LIST()
 
max_length = len("{:b}".format(max(A)))
 
cnt = [defaultdict(int) for _ in range(max_length)]
 
for i in range(N):
    num = "{:b}".format(A[i]).zfill(max_length)
    for j in range(len(num)):
        # [i桁目][numのj番目の数，(0 or 1)]
        # 0, 1 の数を数える
        cnt[max_length-1-j][num[j]] += 1
 
ans = 0
 
for i in range(max_length):
    # 1を左にiシフト(2 ** i 倍)
    # 桁内で0の個数 * 桁内で1の個数 が，XOR = 1になる数 (0 xor 1 = 1)
    ans = ans + (1 << i) * cnt[i]["0"] * cnt[i]["1"]
ans = ans % mod
print(ans)