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

import numpy as np

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

def summation(x):
    result = 0
    for i in range(x+1):
        result += i
    return result

expect = {}
for i in range(1, 1001):
    prob = 1 / float(i)
    expect[i] = summation(i) * prob

p_mapped = [expect[i] for i in p]

max = 0
for i in range(len(p_mapped)-K+1):
    answer = np.sum(p_mapped[i:i+K])
    if answer >= max:
        max = answer
print(max)

### FIXED CODE ###

import numpy as np

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

p_mapped = [(i + 1) / 2 for i in p]
p_m_cumsum = np.cumsum(p_mapped)

max = 0
for i in range(len(p_m_cumsum)-K+1):
    if i != 0:
        answer = p_m_cumsum[i+K-1] - p_m_cumsum[i-1]
    else:
        answer = p_m_cumsum[i+K-1]
    if answer >= max:
        max = answer
print(max)
### BUGGY CODE ###

from collections import deque
MAX_VAL = 10 ** 9
H, W = map(int, input().split())



border_row = "#"*(W+2)
field = [border_row]
for i in range(H):
    line = input()
    field.append("#"+line+"#")
field.append(border_row)

cost = [[MAX_VAL]*(W+2) for _ in range(H+2)]

if field[1][1] == ".":
    cost[1][1] = 1
else:
    cost[1][1] = MAX_VAL

visited = [[False]*(W+2) for _ in range(H+2)] 
dxdy = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def bfs():
    q = deque()
    q.append((1, 1))
    while len(q):
        x, y = q.popleft()
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            if field[ny][nx] == ".":
                cost[ny][nx] = min(cost[ny][nx], cost[y][x]+1)
                if not visited[ny][nx]:
                    q.append((nx, ny))
        visited[y][x] = True

bfs()
num_blacks = 0
for line in field[1:H+1]:
    for c in line[1:W+1]:
        if c == "#":
            num_blacks += 1
print(H*W-num_blacks-cost[H][W]) if cost[H][W] < MAX_VAL else print(-1)




### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())


field = []
num_blacks = 0
for i in range(H):
    line = input()
    num_blacks += line.count(".")
    field.append(line)

cost = [[-1]*(W) for _ in range(H)]

cost[0][0] = 1
dxdy = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def bfs():
    q = deque()
    q.append((0, 0))
    while len(q):
        x, y = q.popleft()
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            if nx < 0 or nx >= W or ny < 0 or ny >= H:
                continue

            if field[ny][nx] == "." and cost[ny][nx] < 0:
                cost[ny][nx] = cost[y][x]+1
                q.append((nx, ny))

bfs()
print(num_blacks - cost[H-1][W-1]) if cost[H-1][W-1] > 0 else print(-1)
### BUGGY CODE ###


from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,M = inpl()

if M == N-1: # 一本道
    for _ in range(M):
        s,t = inpl()
    print(M)
else:
    lines = defaultdict(set)
    linesr = defaultdict(set)
    LL = [0]*N
    for _ in range(M):
        s,t = inpl()
        s -= 1; t -= 1
        lines[s].add(t)
        linesr[t].add(s)
        LL[s] += 1


    ans = 10**10
    for s in range(N-1):
        for t in lines[s]:
            if LL[s] == 1:
                continue
            MEMO = [-1]*N
            MEMO[-1] = 0
            lines[s].remove(t)
            linesr[t].remove(s)
            LL[s] -= 1

            MEMO = [0] * N
            for tt in reversed(range(N)):
                if tt != N-1:
                    MEMO[tt] /= LL[tt]
                for ss in linesr[tt]:
                    MEMO[ss] += MEMO[tt] + 1

            ans = min(ans,MEMO[0])

            lines[s].add(t)
            linesr[t].add(s)
            LL[s] += 1

    print(ans)


### FIXED CODE ###


from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,M = inpl()

if M == N-1: # 一本道
    for _ in range(M):
        s,t = inpl()
    print(M)
else:
    lines = defaultdict(set)
    LL = [0]*N
    for _ in range(M):
        s,t = inpl()
        s -= 1; t -= 1
        lines[s].add(t)
        LL[s] += 1

    def dfs(s):
        global MEMO
        if MEMO[s] != -1:
            return MEMO[s]
        else:
            tmp = 0
            for t in lines[s]:
                if MEMO[t] != -1:
                    tmp += MEMO[t] + 1
                else:
                    tmp += dfs(t) + 1
            MEMO[s] = tmp / LL[s]
            return MEMO[s]

    MEMO = [-1]*N
    MEMO[-1] = 0
    dfs(0)
    koho = [-1]*N
    for s in range(N):
        x = -1
        for t in lines[s]:
            if x < MEMO[t]:
                x = MEMO[t]
                koho[s] = t

    ans = 10**10
    for s in range(N-1):
        t = koho[s]
        if LL[s] == 1 or t == -1:
            continue
        MEMO = [-1]*N
        MEMO[-1] = 0
        lines[s].remove(t)
        LL[s] -= 1
        ans = min(ans,dfs(0))
        lines[s].add(t)
        LL[s] += 1
    print(ans)
### BUGGY CODE ###

import copy

N = int(input())
l = []
for i in range(N):
  l.append(int(input()))

mv = max(l)
for i in range(N):
  if l[i] < mv:
    print(mv)
  if l[i] == mv:
    a = copy.copy(l)
    del a[i]
    print(max(a))


### FIXED CODE ###

import copy

N = int(input())
l = []
for i in range(N):
  l.append(int(input()))

mcnt = 0
mv = max(l)
for i in range(N):
  if l[i] == mv and mcnt == 0:
    a = copy.copy(l)
    del a[i]
    print(max(a))
    mcnt = mcnt + 1
  else:
    print(mv)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
 
H, W, M = map(int, input().split())
Hsum = [0] * H
Wsum = [0] * W
hw = []
for m in range(M):
  h, w = map(int, input().split())
  Hsum[h-1] += 1
  Wsum[w-1] += 1
  hw += [(h-1, w-1)]

hcnt = Hsum.count(max(Hsum))
wcnt = Wsum.count(max(Wsum))
if hcnt * wcnt > M:
  print(max(Hsum) + max(Wsum))
  sys.exit()

hidx = [i for i, _ in enumerate(Hsum) if _ == max(Hsum)]
widx = [i for i, _ in enumerate(Wsum) if _ == max(Wsum)]
for h in hidx:
  for w in widx:
    if (h, w) not in hw:
      print(max(Hsum) + max(Wsum))
      sys.exit()

print(max(Hsum) + max(Wsum) - 1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
H, W, M = map(int, input().split())
Hsum = [0] * H
Wsum = [0] * W
hw = set()
for m in range(M):
  h, w = map(lambda x: int(x) - 1, input().split())
  Hsum[h] += 1
  Wsum[w] += 1
  hw.add((h, w))

mh = max(Hsum)
mw = max(Wsum)
hidx = [i for i, _ in enumerate(Hsum) if _ == mh]
widx = [i for i, _ in enumerate(Wsum) if _ == mw]
 
if len(hidx) * len(widx) > M:
  print(mh + mw)
else:
  fi_flg = False
  for h in hidx:
    for w in widx:
      if (h, w) not in hw:
        print(mh + mw)
        fi_flg = True
        break
    if fi_flg:
      break
  if fi_flg is False:
    print(mh + mw - 1)
### BUGGY CODE ###

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

dp = [0] * (W + 1)

for _ in range(N):
    w, v = map(int, input().split())
    for i in range(W - w, -1, -1):
        dp[i + w] = max(dp[i + w], dp[i] + v)

print(max(dp))


### FIXED CODE ###

def main():
    N, W =  list(map(int, input().split()))

    dp = [-1] * (W + 1)
    dp[0] = 0

    for _ in range(N):
        w, v = map(int, input().split())
        for i in range(W - w, -1, -1):
            if dp[i] != -1 and dp[i + w] < dp[i] + v:
                dp[i + w] = dp[i] + v

    print(max(dp))

main()
### BUGGY CODE ###

N = int(input())
def six(n):
  i = 0
  while n%6 == 0:
    n = n//6
    i += 1
  return i

def nine(n):
  i = 0
  while n%9 == 0:
    n = n//9
    i += 1
  return i

def ans(n):
  if n-6**six(n)==0:
    return 1
  elif n-9**nine(n)==0:
    return 1
  else:
    return max(six(n)+ans(n-6**six(n)),nine(n)+ans(n-9**nine(n)))

ans(44852)
    
    

### FIXED CODE ###

N = int(input())
def cn(X, n):
    if (int(X/n)):
        return cn(int(X/n), n)+str(X%n)
    return str(X%n)
def su(n):
  ans = 0
  for chara in n:
    ans += int(chara)
  return ans
lis = []
i = 0
while i <= N:
  lis.append(su(cn(i,6))+su(cn(N-i,9)))
  i += 1
print(min(lis))
### BUGGY CODE ###

def Warshall_Floyd(edges,N):
  """頂点N個のグラフ上の隣接行列edges(空欄はinfとせよ)が与えられたとき, 
  2点間の最短距離距離を隣接行列で返す"""
  for k, i, j in itertools.product(range(N), range(N),range(N)):
    if edges[i][j]>edges[i][k]+edges[k][j]: return 1
  return 0
 
import sys
import itertools
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
if Warshall_Floyd(A,N):
  print(-1)
  sys.exit()
 
ans=0
for i in range(N):
  for j in range(i):
    need=1
    for k in range(N):
      if k!=i and k!=j and A[i][j]==A[i][k]+A[k][j]:
        need=0
        break
    if need:ans+=A[i][j]
print(ans)

### FIXED CODE ###

def Warshall_Floyd(edges,N):
  """頂点N個のグラフ上の隣接行列edges(空欄はinfとせよ)が与えられたとき, 
  2点間の最短距離距離を隣接行列で返す"""
  for k, i, j in itertools.product(range(N), range(N),range(N)):
    if edges[i][j]>edges[i][k]+edges[k][j]: return 1
  return 0
 
import sys
import itertools
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
if Warshall_Floyd(A,N):
  print(-1)
  sys.exit()
 
ans=0
for i, j in itertools.product(range(N),range(N)):
  need=1
  for k in range(N):
    if k!=i and k!=j and A[i][j]==A[i][k]+A[k][j]:
      need=0
      break
  if need:ans+=A[i][j]
print(ans//2)
### BUGGY CODE ###

N,M=map(int,input().split())
if M==0:
  print("Yes")
  exit(0)
INF=10**9+1
dist=[INF]*N
info=[None]*M
for i in range(M):
  L,R,d=map(int,input().split())
  L,R=L-1,R-1
  info[i]=[L,R,d]
  
checked=[False]*M
L,R,d=info[0]
checked[0]=True
dist[L]=0
dist[R]=d

def ifNotFinished():
  for c in checked:
    if c==False:
      return True
while ifNotFinished():
  for i in range(len(info)):
    if not checked[i]:
      L,R,d=info[i]
      if dist[L]==INF and dist[R]==INF:
        continue
      else:
        if dist[L]!=INF and dist[R]==INF:
          dist[R]=dist[L]+d
        elif dist[L]==INF and dist[R]!=INF:
          dist[L]=dist[R]-d
        else:
          if dist[L]+d!=dist[R]:
            print("No")
            exit(0)
      checked[i]=True
print("Yes")

### FIXED CODE ###

# 人を頂点と見なしたグラフを作る。有向で、逆向きの場合は正負を反転させて辺を張る
# 頂点からの距離を記録し、一致しない箇所があればNG。
# 全ての辺を通るまで続ける。
# 辺の情報を[{0から行ける頂点},{1から行ける頂点},...]で管理する
# 親には進まないようにしてDFSする

N,M = map(int,input().split())
E = [[] for i in range(N)]
for i in range(M):
  L,R,D = map(int,input().split())
  E[L-1].append([R-1,D])
  E[R-1].append([L-1,-D])
from collections import deque
# 頂点、親、距離
INF = 10 ** 10
dist = [INF] * N
for i in range(N):
  if dist[i] != INF:
    continue
  dist[i] = 0
  q = deque()
  q.append(i)
  while q:
    v = q.popleft()
    for child in E[v]:
      if dist[child[0]] == INF:
        dist[child[0]] = dist[v] + child[1]
        q.append(child[0])
      else:
        if dist[child[0]] != dist[v] + child[1]:
          print("No")
          exit(0)
else:
  print("Yes")
### BUGGY CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N,K = inpl()
aa = [inpl() for _ in range(N)]

def Matdot(A,B):
    C = [[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            for k in range(N):
                C[i][j] += A[i][k]*B[k][j]
            C[i][j] %= mod
    return C

def power(aa,k):
    if k == 1:
        return aa
    elif k%2 == 0:
        tmp = power(aa,k//2)
        return Matdot(tmp,tmp)
    else:
        tmp = power(aa,(k-1)//2)
        return Matdot(Matdot(tmp,tmp),aa)


aa =  power(aa,K)
ans = 0
for a in aa:
    ans += sum(a)
    ans %= mod
print(ans)


### FIXED CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N,K = inpl()
aa = [inpl() for _ in range(N)]

def Matdot(A,B):
    C = [[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            for k in range(N):
                C[i][j] += A[i][k]*B[k][j]
            C[i][j] %= mod
    return C

def power(aa,k):
    if k == 1:
        return aa
    elif k%2 == 0:
        tmp = power(aa,k//2)
        return Matdot(tmp,tmp)
    else:
        tmp = power(aa,(k-1)//2)
        return Matdot(Matdot(tmp,tmp),aa)


aa =  power(aa,K)
ans = 0
for a in aa:
    ans += sum(a)
    ans %= mod
print(ans)
### BUGGY CODE ###

from itertools import combinations as C
n, k = map(int, input().split())
c = list(C(range(n), k))
ans = 0
for comb in c:
    for i in range(k - 1):
        if comb[i] + 1 == comb[i + 1]:
            continue
        break
    else:
        ans += 1
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
print(n - k + 1)
### BUGGY CODE ###

N=int(input())
S=input()
sum=0
for i in range(N):
    for j in range(i+1, N):
        if S[i]==S[j]: continue
        for k in range(j+1, N):
            if j-i==k-j: continue
            if (S[i]!=S[j]) and (S[j]!=S[k]) and (S[i]!=S[k]):
                sum+=1
print(sum)

### FIXED CODE ###

N=int(input())
S=input()
cnt=S.count('R')*S.count('G')*S.count('B')
for i in range(N-2):
    for j in range(i+1, N-1):
        k=2*j-i
        if k<N:
            if S[i]!=S[j] and S[i]!=S[k] and S[j]!=S[k]: cnt-=1
print(cnt)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
for _ in range(M):
    B, C = map(int, input().split())
    A = A + [C] * B
    A.sort()
    A = A[-N:]
print(sum(A))

### FIXED CODE ###

import numpy as np
from collections import Counter

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = []
C = []
for _ in range(M):
    b1, c1 = map(int, input().split())
    B.append(b1)
    C.append(c1)

A = list(Counter(A).items())

for i in range(len(A)):
    C.append(A[i][0])
    B.append(A[i][1])
 
d = np.argsort(C)[::-1]
B = [B[i] for i in d]
C = [C[i] for i in d]

i = 0
c = 0
ans = 0
while True:
    if c + B[i] < N:
        ans += C[i] * B[i]
        c += B[i]
        i += 1
    else:
        ans += C[i] * (N - c)
        break
print(ans)
### BUGGY CODE ###

def solve():
  L, R = map(int, input().split())
  ans = 2019
  for i in range(L, R + 1):
    for j in range(i + 1, R + 1):
      ans = min(ans, (i * j) % 2019)
  return ans

print(solve())

### FIXED CODE ###

def solve():
  L, R = map(int, input().split())
  ans = 2019
  for i in range(L, R):
    for j in range(i + 1, R + 1):
      v = i * j % 2019
      if v < ans: ans = v
      if ans == 0: return 0
  return ans

print(solve())
### BUGGY CODE ###

n = int(input())
num = list(map(int,input().split()))

for i in range(1,n+1):
    print(num.count(i))


### FIXED CODE ###

n = int(input())
num = [0] * n
employee = list(map(int,input().split()))

for i in employee:
    num[i-1] += 1

for j in num:
    print(j)
### BUGGY CODE ###

#!/usr/bin/env python3

from itertools import accumulate

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

a_cumsum = list(accumulate(a))
a_cumsum_rev = list(reversed(list(accumulate(reversed(a)))))

# print(a_cumsum)
# print(a_cumsum_rev)

ans = 10**12
div = 1
while(1):
    # print(left, right)
    pq = a_cumsum[0:div+1]
    pq_rev = a_cumsum_rev[0:div+1]
    diff_pq = a_cumsum_rev[div+1]

    rs = a_cumsum[div+1:]
    rs_rev = a_cumsum_rev[div+1:]
    diff_rs = a_cumsum[div]
    # print(pq)
    # print(rs)

    dis = 10**12
    for j in range(len(pq)-1):
        dis_tmp = abs(pq[j]-pq_rev[j+1]+diff_pq)
        if dis_tmp < dis:
            dis = dis_tmp
            p, q = pq[j], pq_rev[j+1]-diff_pq

    dis = 10**12
    for j in range(len(rs)-1):
        dis_tmp = abs(rs[j]-rs_rev[j+1]-diff_rs)
        if dis_tmp < dis:
            dis = dis_tmp
            r, s = rs[j]-diff_rs, rs_rev[j+1]

    # print(p, q, r, s)
    ans_tmp = max(p, q, r, s)-min(p, q, r, s)
    ans = min(ans, ans_tmp)

    div += 1
    if div == n-2:
        break
    # print()
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3

from itertools import accumulate, islice
from bisect import bisect_left

n = int(input())
xs = list(map(int, input().split()))

ys = list(accumulate(xs))
zs, total = ys[:-1], ys[-1]

res = max(xs) - min(xs)
for i, z in islice(enumerate(zs), 1, n-1):
    j = bisect_left(zs, z//2)
    splits = ((zs[j+k], z - zs[j+k]) for k in (-1, 0, 1) if 0 <= j+k <= i)
    a, b = min(splits, key=lambda s: abs(s[0]-s[1]))

    j = bisect_left(zs, (total - z)//2 + z)
    splits = ((zs[j+k] - z, total - zs[j+k])
              for k in (-1, 0, 1) if i <= j+k <= n-2)
    c, d = min(splits, key=lambda s: abs(s[0]-s[1]))

    minn, _, _, maxx = sorted((a, b, c, d))
    if maxx - minn < res:
        res = maxx - minn

print(res)
### BUGGY CODE ###

import pprint as p
def main():
    n = int(input())
    result = []
    for i in range(n):
        a = input()
        b = input()
        array = [[0 for i in range(len(b))] for j in range(len(a))]
        for i in range(len(a)):
            if a[i]==b[0]:
                array[i][0]=1
        for j in range(len(b)):
            if b[j]==a[0]:
                array[0][j]=1 

        for i in range(1, len(a)):
            for j in range(1, len(b)):
                c = 0
                if a[i] == b[j]:
                    c = 1
                array[i][j] = max(
                                    array[i-1][j],
                                    array[i][j-1],
                                    array[i-1][j-1]+c)
        print(array[len(a)-1][len(b)-1])
        #p.pprint(array)
        """
    for i in result:
        print(i)
        """
if __name__ == "__main__":
    main()



### FIXED CODE ###

#dj 16D8101012J ito jun
import sys
def search(a,b):
    na=len(a)
    nb=len(b)
    array = [[0]*(nb+1) for _ in range(na+1)]
    for i,x in enumerate(a,1):
        prerow=array[i-1]
        row=array[i]
        for j,y in enumerate(b,1):
            if x == y:
                row[j]=prerow[j-1]+1
            elif prerow[j] < row[j-1]:
                row[j] = row[j-1]
            else:
                row[j] = prerow[j]
    return array[-1][-1]

n = int(input())
strs = [list(i) for i in sys.stdin.read().splitlines()]
result = [search(strs[i*2], strs[i*2+1]) for i in range(n)]
print(*result, sep="\n")
### BUGGY CODE ###

import numpy as np
N=int(input())
P=10**9+7
a=[int(i) for i in input().split()]
b=[0 for i in range(P)]
for i in range(N):
    b[a[i]]+=1
M=1<<19
c=np.zeros(M)
for i in range(P-1):
    c[i]=b[pow(2,i,P)]
X=[int(i+0.1) for i in np.real(np.fft.ifft(np.fft.fft(c)*np.fft.fft(c)))]
ans=0
for k in range(M):
    ans+=X[k]*pow(2,k,P)
for i in range(N):
    ans-=(a[i]*a[i])%P
print((ans//2)%P)


### FIXED CODE ###

N=int(input())
a=[int(i) for i in input().split()]
mod=10**9+7
S=sum(a)%mod
T=sum([i*i for i in a])%mod
print((pow(2,mod-2,mod)*(S*S-T))%mod)
### BUGGY CODE ###

import numpy as np
n = int(input())
s = list(input())
r = [0] * n
g = [0] * n
b = [0] * n
for i in range(n):
    if s[i] == 'R':
        r[i] = 1
    elif s[i] == 'G':
        g[i] = 1
    else:
        b[i] = 1
cr = np.cumsum(r)
cg = np.cumsum(g)
cb = np.cumsum(b)
ans = 0
for i in range(n-2):
    a = s[i]
    for j in range(i+1, n-1):
        b = s[j]
        if a == b:
            continue
        diff = j - i
        c = {'R', 'G', 'B'} - {a, b}
        c = list(c)[0]
        if c == 'R':
            ans += cr[-1] - cr[j]
        elif c == 'G':
            ans += cg[-1] - cg[j]
        else:
            ans += cb[-1] - cb[j]
        if j + diff < n:
            if s[j + diff] == c:
                ans -= 1
print(ans)



### FIXED CODE ###


n = int(input())
s = list(input())
cr = [0] * n
cg = [0] * n
cb = [0] * n
for i in range(n):
    if i == 0:
        if s[i] == 'R':
            cr[i] += 1
        elif s[i] == 'G':
            cg[i] += 1
        else:
            cb[i] += 1
    else:
        cr[i] = cr[i-1]
        cg[i] = cg[i-1]
        cb[i] = cb[i-1]
        if s[i] == 'R':
            cr[i] += 1
        elif s[i] == 'G':
            cg[i] += 1
        else:
            cb[i] += 1
ans = 0
for i in range(n-2):
    a = s[i]
    for j in range(i+1, n-1):
        b = s[j]
        if a == b:
            continue
        diff = j - i
        c = list({'R', 'G', 'B'} - {a, b})[0]
        if c == 'R':
            ans += cr[-1] - cr[j]
        elif c == 'G':
            ans += cg[-1] - cg[j]
        else:
            ans += cb[-1] - cb[j]
        if j + diff < n:
            if s[j + diff] == c:
                ans -= 1
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
sushi = [list(map(int, input().split())) for _ in range(N)]
sushi = sorted(sushi, key=lambda x: x[1], reverse=True)
typ = []
lstA = []
lstB = []
for item in sushi:
    if item[0] in typ:
        item[0] = 0
        lstB.append(item[1])
    else:
        typ.append(item[0])
        item[0] = 1
        lstA.append(item[1])
ans = 0
neta = 0
for i in range(K):
    ans += sushi[i][1]
    if sushi[i][0] == 1:
        neta += 1
ans += neta ** 2
C = sum(lstA[:neta])
D = sum(lstB[:K - neta])
for i in range(neta + 1, min(K, len(lstA)) + 1):
    C += lstA[i - 1]
    D -= lstB[K - i]
    tmp = C + D + i ** 2
    ans = max(ans, tmp)
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
sushi = [list(map(int, input().split())) for _ in range(N)]
sushi = sorted(sushi, key=lambda x: x[1], reverse=True)
typ = set()
lstA = []
lstB = []
for item in sushi:
    if item[0] in typ:
        item[0] = 0
        lstB.append(item[1])
    else:
        typ.add(item[0])
        item[0] = 1
        lstA.append(item[1])
ans = 0
neta = 0
for i in range(K):
    ans += sushi[i][1]
    if sushi[i][0] == 1:
        neta += 1
ans += neta ** 2
C = sum(lstA[:neta])
D = sum(lstB[:K - neta])
for i in range(neta + 1, min(K, len(lstA)) + 1):
    C += lstA[i - 1]
    D -= lstB[K - i]
    tmp = C + D + i ** 2
    ans = max(ans, tmp)
print(ans)