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

import sys
input = sys.stdin.readline
from collections import defaultdict

N,M = map(int,input().split())
d_to_LR = defaultdict(list)
for _ in range(N):
    L,R = map(int,input().split())
    d_to_LR[R-L+1].append((L,R))

def BIT_update(tree,x,value):
    while x <= M:
        tree[x] += value
        x += x & (-x)

def BIT_sum(tree,x):
    s = 0
    while x:
        s += tree[x]
        x -= x & (-x)
    return s

tree = [0] * (M+1) # BIT で管理。左にあるLの個数 - (R+1)の個数 → いくつの[L,R]に入っているか
long = N # 長すぎて自動回収できる
answer = [0] * (M+1)

for m in range(1,M+1):
    for L,R in d_to_LR[m]:
        BIT_update(tree,L,1)
        BIT_update(tree,R+1,-1)
        long -= 1
    answer[m] = sum(BIT_sum(tree,x) for x in range(m,M+1,m)) + long

print('\n'.join(map(str, answer[1:])))

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict

N,M = map(int,input().split())
d_to_LR = defaultdict(list)
for _ in range(N):
    L,R = map(int,input().split())
    d_to_LR[R-L+1].append((L,R))

def BIT_update(tree,x,value):
    while x <= M:
        tree[x] += value
        x += x & (-x)

def BIT_sum(tree,x):
    s = 0
    while x:
        s += tree[x]
        x -= x & (-x)
    return s

tree = [0] * (M+1) # BIT で管理。左にあるLの個数 - (R+1)の個数 → いくつの[L,R]に入っているか
long = N # 長すぎて自動回収できる
answer = [0] * (M+1)

for m in range(1,M+1):
    for L,R in d_to_LR[m]:
        BIT_update(tree,L,1)
        BIT_update(tree,R+1,-1)
        long -= 1
    answer[m] = sum(BIT_sum(tree,x) for x in range(m,M+1,m)) + long

print('\n'.join(map(str, answer[1:])))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

dp = [[0] * 5005 for _ in range(5005)]

for i in range(N-1, 0, -1):
  for j in range(N-1, 0, -1):
    if S[i] != S[j]:
      dp[i][j] = 0
    else:
      dp[i][j] = dp[i+1][j+1] + 1
      
ans = 0
for i in range(N):
  for j in range(N):
    if i >= j:
      continue
    now = min(dp[i][j], j-i)
    ans = max(ans, now)
    
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
 
N = int(input())
S = input()
 
dp = [[0] * 5005 for _ in range(5005)]
 
for i in range(N-1, -1, -1):
  for j in range(N-1, -1, -1):
    if S[i] != S[j]:
      dp[i][j] = 0
    else:
      dp[i][j] = dp[i+1][j+1] + 1
      
ans = 0
for i in range(N):
  for j in range(N):
    if i >= j:
      continue
    now = min(dp[i][j], j-i)
    ans = max(ans, now)
    
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

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

L = [i+A[i] for i in range(N)]
R = [i-A[i] for i in range(N)]
ans = 0
for l in L:
    ans += R.count(l)
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3

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

L = []
R = []
for i in range(N):
    L.append(i+A[i])
    R.append(i-A[i])

C_L = collections.Counter(L)
C_R = collections.Counter(R)
ans = 0
for l, t in C_L.items():
    if l in C_R:
        ans += t*C_R[l]
print(ans)
### BUGGY CODE ###

import numpy as np

def next(A):
    t = len(A)
    L = np.zeros(t)
    for i in range(t):
        m = max(0,int(i-A[i]))
        M = min(t,int(i+A[i]+1))
        L[m:M] += np.ones(M-m)
    return L

N,K = [int(i) for i in input().split()]
A = np.array([int(i) for i in input().split()])

for _ in range(K):
    A = next(A)
    for a in A:
        if a != N:
            break
    else:
        break
A = [str(int(i)) for i in A]
print(" ".join(A))


### FIXED CODE ###

N,K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

for _ in range(K):
    new = [0]*N
    for i in range(N):
        m = max(0,i-A[i])
        new[m] += 1
        if i+A[i]+1 < N:
            new[i+A[i]+1] -= 1
    A[0] = new[0]
    for i in range(1,N):
        new[i] += new[i-1]
        A[i] = new[i]
    for a in A:
        if a != N:
            break
    else:
        break

A = [str(i) for i in A]
print(" ".join(A))
### BUGGY CODE ###

S = input()

ans = 0
for i in range(0, len(S)-1):
    for j in range(i+1, len(S)+1):
        if int(S[i:j]) % 2019 == 0:
            ans += 1
print(ans)

### FIXED CODE ###

S = input()
P =2019
ans = 0

count = [0] * P
count[0] = 1
u = 0
for i, s in enumerate(reversed(S)):
    u = (int(s) * pow(10, i, P) + u) % P
    ans += count[u]
    count[u] += 1
print(ans)
### BUGGY CODE ###

n = int(input())
str_list = []
for i in range(n):
    str_list.append(sorted(input()))

ans = 0
for i in range(n):
    for j in range(i+1, len(str_list)):
        if str_list[i] == str_list[j]:
            ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
str_list = ["".join(sorted(input())) for i in range(n)]
ans = 0
str_dic = {}

for i in range(n):
    if str_list[i] in str_dic:
        str_dic[str_list[i]] += 1
    else:
        str_dic[str_list[i]] = 0

for v in str_dic.values():
    ans += v*(v+1)/2

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

from operator import itemgetter


class BIT:
    """区間加算、一点取得クエリをそれぞれO(logN)で答えるデータ構造"""
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _add(self, i, val):
        while i > 0:
            self.bit[i] += val
            i -= i & -i

    def get_val(self, i):
        """i番目の値を求める"""
        i = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(r, val)
        self._add(l, -val)


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

for i in range(n):
    info[i] = info[i][0], info[i][1], info[i][1] - info[i][0] + 1
info = sorted(info, key=itemgetter(2))

bit = BIT(m + 1)
l_info = 0
ans = n
for d in range(1, m + 1):
    while True:
        if l_info < n and info[l_info][2] < d:
            l, r, _ = info[l_info]
            bit.add(l, r + 1, 1)
            l_info += 1
            ans -= 1
        else:
            break
    cnt = ans
    for i in range(0, m + 1, d):
        cnt += bit.get_val(i)
    print(cnt)

### FIXED CODE ###

from operator import itemgetter
import sys
input = sys.stdin.readline


class BIT:
    """区間加算、一点取得クエリをそれぞれO(logN)で答えるデータ構造"""
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _add(self, i, val):
        while i > 0:
            self.bit[i] += val
            i -= i & -i

    def get_val(self, i):
        """i番目の値を求める"""
        i = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(r, val)
        self._add(l, -val)


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

for i in range(n):
    info[i] = info[i][0], info[i][1], info[i][1] - info[i][0] + 1
info = sorted(info, key=itemgetter(2))

bit = BIT(m + 1)
l_info = 0
ans = n
for d in range(1, m + 1):
    while True:
        if l_info < n and info[l_info][2] < d:
            l, r, _ = info[l_info]
            bit.add(l, r + 1, 1)
            l_info += 1
            ans -= 1
        else:
            break
    cnt = ans
    if d == 1:
        print(n)
        continue
    for i in range(0, m + 1, d):
        cnt += bit.get_val(i)
    print(cnt)
### BUGGY CODE ###

import numpy as np
n, m, k = [int(n) for n in input().split()]
A = [int(n) for n in input().split()]
B = [int(n) for n in input().split()]

A = np.cumsum([0] + A)
B = np.cumsum([0] + B)
n_read = 0
for i, a in enumerate(A):
    for j, b in enumerate(B):
        if a + b <= k and n_read < i + j:
            n_read = i + j
print(n_read)

### FIXED CODE ###

from numpy import cumsum
n, m, k = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A = cumsum([0] + A)
B = cumsum([0] + B)
n_read = 0
l = len(B) - 1
for i, a in enumerate(A):
    if a > k:
        break
    for j, b in enumerate(B[l::-1]):
        if a + b <= k:
            l -= j
            n_read = max(n_read, i + l)
            break
print(n_read)
### BUGGY CODE ###

x = int(input())

def divisor(n):
    ass = []
    for i in range(1, int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    return ass  # sortされていない


x_li = divisor(x)
x_li.sort()
#print(x_li)
for i in range(len(x_li)):
    for j in range(x_li[i]+1):
        a = j
        b = a - x_li[i]
        if a**5 - b**5 == x:
            print(a, b)
            break
    else:
        continue
    break


### FIXED CODE ###

x = int(input())
count =0
for a in range(-200, 200):
    for b in range(-200, 200):
        if a**5 - b**5 == x:
            A = a
            B = b

print(A, B)
### BUGGY CODE ###

N, Y = [int(k) for k in input().split(' ') if k]
Y //= 1000
x = Y // 10
Y -= x * 10
y = Y // 5
Y -= y * 5
z = Y

def find(nx, ny, nz):
	if nx + ny + nz > N:
		return
	if nx + ny + nz == N:
		print(nx, ny, nz)
		exit()
	if nx > 0:
		find(nx - 1, ny + 2, nz)
	if ny > 0:
		find(nx, ny - 1, nz + 5)
find(x, y, z)
print(-1, -1, -1)

### FIXED CODE ###

N, Y = [int(k) for k in input().split(' ') if k]
Y //= 1000
x = Y // 10
Y -= x * 10
y = Y // 5
Y -= y * 5
z = Y
if N < x + y + z:
	print(-1, -1, -1)
	exit()
d = N - x - y - z
for dx in range(min(d, x) + 1):
	nx = x - dx
	ny = y + 2 * dx
	nd = N - nx - ny - z
	dy = min(nd // 4, ny)
	ny = ny - dy
	nz = z + dy * 5
	if nx + ny + nz == N:
		print(nx, ny, nz)
		exit()
print(-1, -1, -1)
### BUGGY CODE ###

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

for i in range(1,N+1):
    j = A.index(i)
    print(j+1,end="")
    if i < N:
        print(" ",end="")

print()

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
Z = [-1 for i in range(N)]

for j,v in enumerate(A):
    Z[v-1] = j+1

for k,v in enumerate(Z):
    print(v,end="")
    if k < N:
        print(" ",end="")
    else:
        print()
### BUGGY CODE ###

# 辺を共有して隣接するマスの中に、黒色のマスが一つ以上存在するような白色のマスすべてが黒色になる。
#
H, W = map(int, input().rstrip().split())

Map = []

for i in range(H):
    Map.append(list(input().rstrip()))

black_list = []

for i in range(H):
    for j in range(W):
        if Map[i][j] == "#":
            black_list.append((i, j))


def search(black_list):
    next_nodes = []
    for pos in black_list:
        x, y = pos

        for direction in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            dx, dy = direction

            if x+dx < 0 or y+dy < 0:
                continue

            if x+dx >= H or y+dy >= W:
                continue

            if Map[x+dx][y+dy] == "#":
                continue

            Map[x+dx][y+dy] = "#"
            next_nodes.append((x+dx, y+dy))

    return next_nodes


count = 0
while black_list:
    black_list = search(black_list)
    if len(black_list) > 0:
        count += 1

print(count)


### FIXED CODE ###

H, W = map(int, input().rstrip().split())
checked = [[True]*(W+2)]
checked += [[True] + [ch == "#" for ch in input().rstrip()] + [True]
            for i in range(H)]
checked.append([True]*(W+2))

black_list = []
# 初期化
# 0 => 黒、 -1 => 白
for i in range(1, H+1):
    for j in range(1, W+1):
        if checked[i][j]:
            black_list.append((i, j))

# 黒の周辺4方向のうち、白だったら黒にする
ans = -1
while black_list:
    ans += 1
    tmp = []
    for x, y in black_list:
        # 上
        if not checked[x-1][y]:
            checked[x-1][y] = True
            tmp.append((x-1, y))
        # 下
        if not checked[x+1][y]:
            checked[x+1][y] = True
            tmp.append((x+1, y))
        # 左
        if not checked[x][y-1]:
            checked[x][y-1] = True
            tmp.append((x, y-1))

        # 右
        if not checked[x][y+1]:
            checked[x][y+1] = True
            tmp.append((x, y+1))

    black_list = tmp

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

#problem D
input_d41 = int(input())
input_d42 = input()

N = int(input_d41)
S = input_d42

ans = 0

for i in range(0,N):
    for j in range(i+1,N):
        if S[i] != S[j]:
            for k in range(j+1,N):
                if S[j] != S[k] and S[k] != S[i] and j-i != k-j:
                    ans += 1

                    
print(ans)

### FIXED CODE ###

#problem D
input_d41 = int(input())
input_d42 = input()

N = int(input_d41)
S = input_d42

R = S.count('R')
G = S.count('G')
B = N - (R + G)

ans = R*G*B
answ = 0

for i in range(0,N):
    for j in range(i+1,(N+i)//2 +1):
        if S[i] != S[j]:
            if 2*j-i < N and S[j] != S[2*j-i] and S[2*j-i] != S[i]:
                ans -= 1
print(ans)
### BUGGY CODE ###

n = int(input())
east_side = list(input())
west_side = []
ans = 300000
for i in range(len(east_side)):
    WE_sum = east_side.count("E") + west_side.count("W")
    if(WE_sum < ans):
        ans = WE_sum
    west_side.append(east_side[0])
    east_side.pop(0)
print(ans)


### FIXED CODE ###

n = int(input())
s = input()
rev_counter = []
rev_num = s.count("E")
if s[0] == "E":
    rev_num -= 1
rev_counter.append(rev_num)
for i in range(1, n):
    if s[i] == "E" and s[i-1] == "E":
        rev_num -= 1
    elif s[i] == "W" and s[i-1] == "W":
         rev_num += 1
    rev_counter.append(rev_num)
print(min(rev_counter))
### BUGGY CODE ###

a = int(input())
b = list(map(int,input().split()))
c = 1

for i in range(1,a):
  switch = 0
  for j in range(0,i):
    if b[i] > b[j]:
      switch = 1
      break
  if switch != 1:
    c += 1
print(c)
      
      
  


### FIXED CODE ###

a = int(input())
b = list(map(int,input().split()))
c = 1
k = b[0]
for i in range(1,a):
  if k>b[i]:
  	
  	k = b[i]
  	c+=1
print(c)
### BUGGY CODE ###

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


x=a[0]
for i in range(1,n):
    x=x*a[i]
    if x>10**18 and (0 not in a):
        print(-1)
        exit()
       
print(x)

### FIXED CODE ###

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

x=a[0]

if 0 not in a:
    for i in range (1,n):
        x=x*a[i]
        if x > pow(10,18):
            print(-1)
            exit()           
    print(x)         
else:
    print(0)
### BUGGY CODE ###

def burger(n):
    if n == 0:
        return "P"
    else:
        return "B"+burger(n-1)+"P"+burger(n-1)+"B"

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

ans = 0
nburger = list(burger(N))
for i in range(X):
    if nburger[i] == "P":
        ans += 1

print(ans)

### FIXED CODE ###

n,x = map(int,input().split())
burger = [1]
patty = [1]

for i in range(n):
    burger.append(burger[i]*2+3)
    patty.append(patty[i]*2+1)

def f(n,x):
    if n == 0:
        return 1
    elif x == 1:
        return 0
    elif x <= 1+burger[n-1]:
        return f(n-1,x-1)
    elif x == 2+burger[n-1]:
        return 1+patty[n-1]
    elif x <= 2+2*burger[n-1]:
        return 1+patty[n-1]+f(n-1,x-2-burger[n-1])
    else:
        return patty[n]

print(f(n,x))
### BUGGY CODE ###

import collections
import heapq

def main():
    N = int(input())
    A = list(map(int, input().split()))
    # print(N, A)
    # 整数ごとに何枚あるか数える
    c = collections.Counter(A)
    v = [-x for x in c.values()]
    # print(c, v)

    _max = len(v)
    ans = [N]
    for K in range(2, N+1):
        # Kがカードの種類より大きい場合は1回も食べれない
        if K > _max:
            ans.append(0)
            continue
        q = v[:]
        heapq.heapify(q)

        cnt = 0
        while len(q) >= K:
            eat = []
            # 枚数の多い順にK個取り出す
            for k in range(K):
                eat.append(heapq.heappop(q))
            cnt += 1
            for e in eat:
                if e < -1:
                    heapq.heappush(q, e + 1)
        ans.append(cnt)
    
    print(*ans, sep='\n')

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

    # C[x]: 書かれている整数がxであるカードの枚数
    C = [0] * (N + 1)
    D = [0] * (N + 1)
    for a in A:
        C[a] += 1
        D[C[a]] += 1

    # AからK(1<=K<=N)枚ずつカードを抜いてったときに、
    # x回以上抜くことができるか判定する。
    # 抜くことができると判定されたxの最大値が答えになる。

    # 例えば、A = [1 1 1 1 1 2 2 3] とする。
    # -> C = [5 2 1 0 0 0 0 0]
    # ここから2枚ずつカードを抜ける回数を考えるとき、
    # 「3回抜く」とすると、数字の1は、どうやっても2個は絶対余る
    # そこで、絶対余る部分を捨ててCを作り直す(=Eとする)と、
    # E = [3 2 1 0 0 0 0 0]
    # ここから2枚ずつ3回抜けるか判定するなら、
    # sum(E) >= 2 * 3 = 6
    # であるか見ればよい。今回の場合ちょうど6なので、2枚ずつ3回は抜ける。
    
    # 3枚ずつ2回ぬけるか調べる場合、
    # E = [2 2 1] となり、sum(E) = 5 < 3 * 2 = 6 なので、抜けないことが分かる

    # よって、
    # sum(min(C[i], x)) >= K * x であれば抜くことができる
    # S(x) = sum(min(C[i], x)) とすると、
    # S(x) = S(x-1) + [Cの中でC[i] >= x であるものの個数]
    # となることから、Cの中でC[i] >= x であるものの個数 = D(x) とすると、
    # S(x) = sum_(1~x) D(i) となる。
    # つまり、S(x)は、D(x) を最初に全部計算しておいて、累積和をとることで高速に計算できる。

    # S(x) >= K * x となるxの最大値を、kを1からNまで動かして見つければよい。
    # ここで、xを左辺にもっていって、
    # S(x) / x >= Kとなるxの最大値を見つけるようにする。
    # また、S(x) / x = f(x) とおく。

    # 最大値を見つけるために2分探索してもいいが、
    # Kが増えると、答えは以前の値以下になるはずなので、
    # K+1のとき、Kでの答えの位置から0へと探索していけば、O(N)で答えが見つかる
    S = [0] * (N + 1)
    f = [0] * (N + 1)
    for x in range(1, N+1):
        S[x] = S[x-1] + D[x]
        f[x] = S[x] // x

    ans = []
    prev_ans = N
    for K in range(1, N+1):
        a = prev_ans
        while True:
            if f[a] >= K or a == 0:
                break
            a -= 1
        ans.append(a)
        prev_ans = a

    print(*ans, sep='\n')

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

N=int(input())
ans =1
A = list(map(int,input().split()))
for i in A:
      
       ans *=i
if ans <=10**18:
        print(ans)
else:
        print(-1)


### FIXED CODE ###

N=int(input())
ans =1
A = list(map(int,input().split()))
for i in A:
        if i == 0:

               print(0)
               exit()
for i in A:
      
       ans *=i
       if ans >10**18:
               print(-1)
               exit()
print(ans)
### BUGGY CODE ###

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

class multiset:
    def __init__(self, L):
        self.dic = {}
        for a in L:
            if a not in self.dic:
                self.dic[a] = 0
            self.dic[a] += 1
    def has(self, x):
        return x in self.dic and self.dic[x] > 0
    def remove(self, x):
        if self.has(x):
            self.dic[x] -= 1

def check(x, y):
    a = x
    S = multiset(A)
    S.remove(x)
    S.remove(y)
    for i in range(N - 2):
        z = (x ^ y)
        if not S.has(z):
            return False
        S.remove(z)
        x, y = y, z
    return a == x ^ y

yes = any(check(A[0], a) for a in A[1:])
print('Yes' if yes else 'No')


### FIXED CODE ###

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

def yes():
    S = set(A)
    if A.count(0) == N:
        return True
    if N % 3 != 0:
        return False
    if len(S) == 3:
        a, b, c = tuple(S)
        return all(A.count(x) == N // 3 for x in S) and a ^ b == c
    if len(S) == 2:
        a, b = tuple(S)
        return (a == 0 or b == 0) and A.count(0) == N // 3

print('Yes' if yes() else 'No')
### BUGGY CODE ###

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

# 最初に入力の最大値と最大量でdp配列を作成
dp = [100000000] * (H + 10 ** 4 + 1)
dp[0] = 0

for i in range(H):
    if dp[i] == 100000000:
        continue
    for a, b in AB:
        # tは100000000 + 消費魔力
        t = dp[i] + b
        # dp[i + a] aはダメージ量
        if t < dp[i + a]:
            dp[i + a] = t

print(min(dp[H:]))




### FIXED CODE ###

def main():
    from sys import stdin
    readline = stdin.readline
    H, N = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(N)]

    dp = [100000000] * (H + 10 ** 4 + 1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == 100000000:
            continue
        for a, b in AB:
            t = dp[i] + b
            if t < dp[i + a]:
                dp[i + a] = t
    print(min(dp[H:]))


main()
### BUGGY CODE ###

n = int(input())

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

b = []

for i in range(n):
    b.append(a[i])
    b.reverse()
print(" ".join(map(str,b)))



### FIXED CODE ###

n = int(input())

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

b = []

for i in range(n-1,0,-2):
    print(a[i],end="")
    a.pop(i)
    print(" ",end="")
print(" ".join(map(str,a)))
### BUGGY CODE ###

n,k=map(int,input().split())
li=[[0,0] for i in range(n)]
for i in range(n):
    li[i][0],li[i][1]=map(int,input().split())
 
li.sort(reverse=True,key=lambda x:x[1])
 
def find_num_neta(choice,li):
    k=[]
    for i in choice:
        k.append(li[i][0])
    return len(set(k))
 
#-----------------------------------------
best_list=[]
best_list_neta=[]
not_best_list=[]
 
for i in li:
    if i[0] in best_list_neta:
        not_best_list.append(i[1])
    else:
        best_list.append(i[1])
        best_list_neta.append(i[0])
 
 
s2=min(len(best_list_neta),k)
s1=find_num_neta(list(range(k)),li)
 
 
score=-1
for i in range(s1,s2+1):
    oishisa=0
    for j in range(i):
        oishisa+=best_list[j]
    for j in range(k-i):
        oishisa+=not_best_list[j]
    
    new_score=i**2+oishisa
 
    if score<new_score:
        score=new_score
        
    
print(score)

### FIXED CODE ###

n,k=map(int,input().split())
li=[[0,0] for i in range(n)]
for i in range(n):
    li[i][0],li[i][1]=map(int,input().split())



def find_num_neta(choice,li):
    k=[]
    for i in choice:
        k.append(li[i][0])
    return len(set(k))
#-----------------------------------------

li.sort(reverse=True,key=lambda x:x[1])
s2=min(find_num_neta(list(range(n)),li),k)
s1=find_num_neta(list(range(k)),li)
oishisa=sum([li[i][1] for i in range(k)])
score=oishisa+s1**2

#-----------------------------------------
li.sort(key=lambda x:x[0])
best_list=[]
not_best_list=[]


m=-1
for i in li:
    if m==i[0]:
        not_best_list.append(i)
    else:
        best_list.append(i)
        m=i[0]
        
not_best_list.sort(reverse=True,key=lambda x:x[1])
best_list.sort(reverse=True,key=lambda x:x[1])



 
 
for i in range(s1+1,s2+1):
    oishisa=oishisa+best_list[i-1][1]-not_best_list[k-i][1]
    
    new_score=i**2+oishisa
    
    if score<new_score:
        score=new_score
        
    
print(score)
### BUGGY CODE ###

N,Q = map(int, input().split())
import copy
import sys

sys.setrecursionlimit(10**6)
es = {}
for i in range(N-1):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    if a in es:
        es[a].append(b)
    else:
        es[a] = [b]


point_root = [0] * N
query = [None]
for i in range(Q):
    p,x = map(int, input().split())
    point_root[p-1] += x 
point_root = tuple(point_root)
ans = [0] * N
visited = [False] * N
global vis
vis = 0

def solve(node, point):
    
    ans[node] += point
    visited[node] = True


    if es.get(node, None) != None:
        for i in es[node]:
            if visited[i] == False:
                solve(i, point+point_root[i])
solve(0, point_root[0])
print(*ans)

### FIXED CODE ###

N,Q = map(int, input().split())
import copy
import sys

sys.setrecursionlimit(10**6)
es = [[] for i in range(N)]

for i in range(N-1):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    es[a].append(b)
    es[b].append(a)


point = [0] * N

for i in range(Q):
    p,x = map(int, input().split())
    point[p-1] += x 

ans = [0] * N
ans[0] = point[0] # 一番上の根なのでこれだけ
visited = [False] * N
visit_cnt = 1
from collections import deque
nexts = deque([0])
while len(nexts) >= 1:
    now = nexts.popleft()
    visited[now] = True

    for next in es[now]:
        if visited[next] == True:
            continue
        nexts.append(next)
        ans[next] = ans[now] + point[next]


print(*ans)