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

N,Wmax=map(int,input().split(' '))
info=[ list(map(int,input().split(' '))) for i in range(N) ]
W = [ info[i][0] for i in range(N) ]
V = [ info[i][1] for i in range(N) ]

#dp[i][j]=i番目の品物までだけを選び重量制限をjとしたときの価値の最大値
dp = []

for i in range(N):
	if i==0:
		#重量制限がW[0]以上なら荷物を積むのが最善
		dp.append([ V[0] if W[0]<=w else 0 for w in range(Wmax+1) ])	
	else:
		#今回の重量制限をwとする
		#今回は荷物を積む場合: dp[i][w] = dp[i-1][w-w[i]]+v[i] 
		#今回は荷物を積まない場合: dp[i][w] = dp[i-1][w]
		#よってこの2つのうち大きいほうをdp[i][w]に採用する
		l = []
		for w in range(Wmax+1):
			val1 = (dp[i-1][w-W[i]]+V[i]) if w-W[i]>=0 else 0
			val2 = dp[i-1][w]
			l.append(max(val1,val2))
		dp.append(l)
print(dp[N-1][Wmax])

### FIXED CODE ###

N,Wmax=map(int,input().split(' '))
W=[]
V=[]
for _ in range(N):
	w,v = map(int,input().split(' '))
	W.append(w)
	V.append(v)

#dp[i][j]=i番目の品物までだけを選び重量制限をjとしたときの価値の最大値
dp = []
dp.append([0]*min(W[0],Wmax+1)+ [V[0]]*max(0, Wmax+1-W[0]))


for i in range(1,N):
	#今回の重量制限をwとする
	#今回は荷物を積む場合: dp[i][w] = dp[i-1][w-w[i]]+v[i] 
	#今回は荷物を積まない場合: dp[i][w] = dp[i-1][w]
	#よってこの2つのうち大きいほうをdp[i][w]に採用する
	dpi = []
	for j in range(Wmax+1):
		if j<W[i]:
			dpi.append(dp[i-1][j])
		else:
			dpi.append(max(dp[i-1][j], dp[i-1][j-W[i]]+V[i]))
	dp.append(dpi)
print(dp[N-1][Wmax])
### BUGGY CODE ###

h,w,m=map(int,input().split())
hh=[[0,i]for i in range(h)]
ww=[[0,i]for i in range(w)]
hw=set()
for _ in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  hh[a][0]+=1
  ww[b][0]+=1
  hw.add((a,b))
ww.sort(reverse=1)
s=ww[0][0]
w=[]
for x,j in ww:
  if x==s:w.append(j)
ans=0
t=max(hh)[0]
for j in w:
  for x,i in sorted(hh,reverse=1):
    if x!=t:break
    if (i,j) in hw:
      ans=s+x-1
    else:
      exit(print(s+x))
print(ans)


### FIXED CODE ###

import random
import time
start=time.time()
h,w,m=map(int,input().split())
hh=[[0,i]for i in range(h)]
ww=[[0,i]for i in range(w)]
hw=set()
for _ in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  hh[a][0]+=1
  ww[b][0]+=1
  hw.add((a,b))
ww.sort(reverse=1)
s=ww[0][0]
w=[]
for x,j in ww:
  if x==s:w.append(j)
hh.sort(reverse=1)
t=hh[0][0]
hhh=[]
for x,i in hh:
  if x==t:hhh.append((x,i))
ans=[]
random.shuffle(w)
for j in w:
  for x,i in hhh:
    if (i,j) in hw:
      ans.append(s+x-1)
    else:
      exit(print(s+x))
  if time.time()-start>=1.7:
    m=ans[0]
    if h-50000<=len(hhh)<=h-random.randint(1,30):m+=1
    exit(print(m))
print(ans[0])
### BUGGY CODE ###

import itertools

def count_num(array):
    array = array.replace('r',' ')
    lst = array.split()
    return len(lst)

n,k = map(int,input().split()) 
ans_lst = []
seq = list('r'*(n-k)+'b'*k)
al = list(set(itertools.permutations(seq)))

for i in range(1,k+1):
    ans_lst.append(0)

for x in al:
    array = ''.join(x)
    num = count_num(array)
    ans_lst[num-1] += 1
    
for i in range(1,k+1):
    print(ans_lst[i-1]%(10**9+7))

### FIXED CODE ###

from math import factorial

n,k = map(int,input().split())
mod = 10**9+7

def cmb(n,r):
    return factorial(n) // (factorial(r) * factorial(n-r))

for i in range(1,k+1):
    if n-k+1 < i or k-1 < i-1:
        print(0)
    else:
        x = cmb(k-1,i-1) % mod
        y = cmb(n-k+1,i) % mod
        ans = (x*y) % mod
        print(int(ans))
### BUGGY CODE ###

n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
mod=10**9+7
dp=[[0]*(m+1) for i in range(n+1)]
total=[[0]*(m+1) for i in range(n+1)]
for i in range(n):
	for j in range(m):
		if s[i]==t[j]:
			dp[i+1][j+1]=(total[i][j]+1)%mod
		total[i+1][j+1]=(total[i+1][j]+total[i][j+1]-total[i][j]+dp[i+1][j+1])%mod
print((total[-1][-1]+1)%mod)

### FIXED CODE ###

n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
mod=10**9+7
dp=[[0]*(m+1) for i in range(n+1)]
total=[[0]*(m+1) for i in range(n+1)]
for i in range(n):
	for j in range(m):
		if s[i]==t[j]:
			dp[i+1][j+1]=(total[i][j]+1)%mod
		total[i+1][j+1]=(total[i+1][j]+total[i][j+1]-total[i][j]+dp[i+1][j+1])%mod
print((total[-1][-1]+1)%mod)
### BUGGY CODE ###

n = int(input())
cnt = 0
A = []
for _ in range(n):
    A.append([sorted(input())])
    B = sorted(A) 
for i in range(n-1):
    s = B[i]
    for j in range(i+1, n):
        t = B[j]
        if s == t:
            cnt += 1
        else:
            break
print(cnt)
         

         

### FIXED CODE ###

n = int(input())
cnt = 0
A = []
for _ in range(n):
    t = sorted(input())
    t = "".join(t)
    A.append(t)

import collections
C = collections.Counter(A)
lC = list(C.values())
for i in lC:
    cnt += i * (i-1) // 2
print(cnt)
### BUGGY CODE ###

from collections import Counter
l=[]
n=int(input())
for i in range(n):
  l.append(input())
c=Counter(l)
max_list=[kv[0] for kv in c.items() if kv[1]==max(c.values())]
max_list.sort()
for j in max_list:
  print(j)

### FIXED CODE ###

n = int(input())
s = [input() for _ in range(n)]
d = {}
for w in s:
    if w not in d:
        d[w] = 0
    d[w] += 1
d2 = sorted(d.items(), key=lambda x:x[1], reverse=True)
maxcnts = [w[0] for w in d2 if w[1] == d2[0][1]]
maxcnts.sort()
for ans in maxcnts:
    print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
X = [list(map(int, input().split()))for _ in range(Q)]
l =[]

def get(n):
    ans = 0
    for i in range(n-1):
        if S[i] =="A" and S[i+1] =="C":
            ans += 1
    return ans
for i in range(Q):
    print(get(X[i][1])-get(X[i][0]))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
X = [list(map(int, input().split()))for _ in range(Q)]

a =[0]*N
for i in range(1,N):
    if S[i] =="C" and S[i-1] =="A":
        a[i] = a[i-1]+1
    else:
        a[i] = a[i-1]
# print(a)
for i in range(Q):
    print(a[X[i][1]-1]-a[X[i][0]-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 8)

def main():
    #入力
    N, Q = (int(_) for _ in input().split())
    edge = [[int(_) for _ in input().split()] for __ in range(N-1)]
    query = [[int(_) for _ in input().split()] for __ in range(Q)]

    tree = [[] for _ in range(N+1)]
    for a, b in edge:
        tree[a].append(b)
        tree[b].append(a)

    cc = [0] * (N+1)
    seen = [False] * (N+1)

    for p, x in query:
        cc[p] += x

    def dfs(x):
        for p in tree[x]:
            if seen[p] == False:
                seen[p] = True
                cc[p] += cc[x]
                dfs(p)
        return

    seen[1] = True
    dfs(1)

    print(*cc[1:])

    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline #for input speed
sys.setrecursionlimit(10**6) #for deep recursion
n, q = map(int, input().split())

tree_index = [[] for _ in range(n)]
for i in range(n-1):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  tree_index[a].append(b) # a<bとは限らないため、双方向にする
  tree_index[b].append(a)
ans = [0] * n
for i in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x
def dfs(cur, par):
    for chl in tree_index[cur]:
      if chl == par: #parentとchildが等しい時はスキップ
        continue
      ans[chl] += ans[cur] 
      dfs(chl, cur)
dfs(0, -1)
print(*ans)
### BUGGY CODE ###

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

a = []
b = []

d = -1
for i in range(k):
    while s[d] == 'x':
        d -= 1
    b.insert(0, n+d)
    d -= c+1

d = 0
for i in range(k):
    while s[d] == 'x':
        d += 1
    if d == b[i]:
        print(d+1)
    d += c+1

### FIXED CODE ###

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

b = []

d = -1
for i in range(k):
    while s[d] == 'x':
        d -= 1
    b.append(n+d)
    d -= c+1

d = 0
for i in range(k):
    while s[d] == 'x':
        d += 1
    if d == b[-i-1]:
        print(d+1)
    d += c+1
### BUGGY CODE ###

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

h, w = map(int, input().split())
ch, cw = map(int, input().split())
gh, gw = map(int, input().split())

s = []
for i in range(h):
   s.append(input().rstrip('\n'))

INF = 10 ** 10
d = [INF] * (h*w)

A = 10**18
B = 10**9

stack = deque([(ch-1)*A + (cw-1)*B + 0])
stack_append = stack.append
stack_popleft = stack.popleft

nex = []
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i, j) in [(-1,0),(1,0),(0,-1),(0,1),(0,0)]:
            continue
        else:
            nex.append((i,j))

d[(ch-1) * w + (cw-1)] = 0

while stack:
    x = stack_popleft()
    curh = (x // A)
    x -= curh * A
    curw = (x // B)
    cnt = x - curw * B
    if d[curh * w + curw] < cnt: continue
    d[curh * w + curw] = cnt
    for dh, dw in ((-1,0), (1,0), (0,1), (0,-1)):
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and d[nh * w + nw] > cnt:
            d[nh * w + nw] = cnt
            stack_append(nh*A + nw*B + cnt)
    for dh, dw in nex:
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and d[nh * w + nw] > cnt:
            d[nh * w + nw] = cnt + 1
            stack_append(nh*A + nw*B + cnt+1)

# for item in d:
#     print(item)
gh -= 1
gw -= 1

if d[gh*w + gw] == INF:
    print(-1)
else:
    print(d[gh*w + gw])


### FIXED CODE ###

import heapq
class Dijkstra:
    INF = 10**18
    threshold = 10**9

    def __init__(self, N):
        self.MAX_V = N + 1
        self.dist = [self.INF] * self.MAX_V
        self.G = [[] for _ in range(self.MAX_V)]

    def insert(self, X, Y, cost): self.G[X].append(cost * self.threshold + Y)

    def dijkstra(self, st):
        q = []
        heapq.heappush(q, st)
        self.dist[st] = 0

        while len(q):
            p = heapq.heappop(q)
            cost = p // self.threshold
            node = p - cost * self.threshold
            if cost > self.dist[node]: continue
            for to in self.G[node]:
                to_cost = to // self.threshold
                to_node = to - to_cost * self.threshold
                to_cost += self.dist[node]
                if self.dist[to_node] > to_cost:
                    self.dist[to_node] = to_cost
                    heapq.heappush(q, to_cost * self.threshold + to_node)

h, w = map(int, input().split())
sh, sw = map(int, input().split())
eh, ew = map(int, input().split())

sh -= 1
sw -= 1
eh -= 1
ew -= 1

S = [input() for _ in range(h)]

di = Dijkstra(h*w)
for x in range(h):
    for y in range(w):
        if S[x][y] == '#': continue
        for i in range(-2, 3):
            for j in range(-2, 3):
                X = x + i
                Y = y + j
                if X < 0 or Y < 0 or X >= h or Y >= w or S[X][Y] == '#': continue
                D = abs(i) + abs(j)

                if D == 1: di.insert(x * w + y, X * w + Y, 0)
                if D >= 2: di.insert(x * w + y, X * w + Y, 1)

di.dijkstra(sh * w + sw)
ans = di.dist[eh * w + ew]
if ans == 10**18: print(-1)
else: print(ans)
### BUGGY CODE ###

def gcd(x,y):
    if x==y:
        return x
    elif x>y:
        r=-1
        while r!=0:
            r=x%y
            x=y
            y=r
        return x
    else:
        r=-1
        while r!=0:
            r=y%x
            y=x
            x=r
        return y

def sosu(n):
    pn=[2]
    for i in range(3,n+1):
        chk=True
        for j in pn:
            if i%j==0:
                chk=False
        if chk:
            pn.append(i)
    return pn


a,b=map(int,input().split())
x=gcd(a,b)
l=sosu(x)
ans=1
for m in l:
    if x%m==0:
        ans+=1
print(ans)


### FIXED CODE ###

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
def gcd(x,y):
    if x==y:
        return x
    elif x>y:
        r=-1
        while r!=0:
            r=x%y
            x=y
            y=r
        return x
    else:
        r=-1
        while r!=0:
            r=y%x
            y=x
            x=r
        return y

a,b=map(int,input().split())
x=gcd(a,b)
l=factorization(x)
ans=1
ans+=len(l)
if x==1:
    print(1)
else:
    print(ans)
### BUGGY CODE ###

N = int(input())
emplist = [int(x) for x in input().split()]
sum = 0
for i in range(1,N+1):
    if sum < N-1:
        print(emplist.count(i))
        sum += emplist.count(i)
    else:
        print(0)

### FIXED CODE ###

from collections import Counter
N = int(input())
emplist = [int(x) for x in input().split()]

ans = Counter(emplist)

for i in range(1,N+1):
    print(ans[i])
### BUGGY CODE ###

n, x, y = input().split(" ")
n, x, y = int(n), int(x), int(y)
ans = [0] * (n - 1)
 
for i in range(n - 1):
    for j in range(i + 1, n):
        now = 0
        if (j <= x - 1):
            ans[j - i - 1] += 1
 
        elif(j > x - 1 and j <= y - 1 and i <= x - 1):
            now = now + x - 1 - i
            if (j - (x - 1) >= (y - 1) - j + 1):
                now = now + (y - 1) - j + 1
            else:
                now = now + j - (x - 1)
            ans[now - 1] += 1
 
        elif(j > x - 1 and j <= y - 1 and i > x - 1):
            if (j - i >= (i - (x - 1)) + ((y - 1) - j) + 1):
                now = (i - (x - 1)) + ((y - 1) - j) + 1
            else:
                now = j - i
            ans[now - 1] += 1
 
        elif(j > y - 1 and i <= x - 1):
            now = now + x - 1 - i
            now = now + j - (y - 1) + 1
            ans[now - 1] += 1
 
        elif(j > y - 1 and i > x - 1 and i < y - 1):
            if((y - 1) - i >= i - (x - 1) + 1):
                now = now + i - (x - 1) + 1
            else:
                now = now + (y - 1) - i
            now = now + j - (y - 1)
            ans[now - 1] += 1
 
        elif(i >= y - 1):
            ans[j - i - 1] += 1
 
print(*ans)

### FIXED CODE ###

n, x, y = input().split(" ")
n, x, y = int(n), int(x), int(y)
ans = [0] * (n - 1)

for i in range(n - 1):
    for j in range(i + 1, n):
        now = 0
        if (j <= x - 1):
            ans[j - i - 1] += 1

        elif(j > x - 1 and j <= y - 1 and i <= x - 1):
            now = now + x - 1 - i
            if (j - (x - 1) >= (y - 1) - j + 1):
                now = now + (y - 1) - j + 1
            else:
                now = now + j - (x - 1)
            ans[now - 1] += 1

        elif(j > x - 1 and j <= y - 1 and i > x - 1):
            if (j - i >= (i - (x - 1)) + ((y - 1) - j) + 1):
                now = (i - (x - 1)) + ((y - 1) - j) + 1
            else:
                now = j - i
            ans[now - 1] += 1

        elif(j > y - 1 and i <= x - 1):
            now = now + x - 1 - i
            now = now + j - (y - 1) + 1
            ans[now - 1] += 1

        elif(j > y - 1 and i > x - 1 and i < y - 1):
            if((y - 1) - i >= i - (x - 1) + 1):
                now = now + i - (x - 1) + 1
            else:
                now = now + (y - 1) - i
            now = now + j - (y - 1)
            ans[now - 1] += 1

        elif(i >= y - 1):
            ans[j - i - 1] += 1
print(*ans)
### BUGGY CODE ###

# 正解ではない

from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for i in range(H)]
    d = [[-1 for i in range(W)] for j in range(H)]
    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))
    resolve(q, d, S, (Dh - 1, Dw - 1), H, W)
    print(d[Dh - 1][Dw - 1])


def resolve(q, d, S, D, H, W):
    while len(q):
        worp_count, x, y = q.popleft()

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                elif abs(i) + abs(j) >= 2:
                    q.append((worp_count + 1, nx, ny))


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    d = [[-1 for _ in range(W)] for _ in range(H)]

    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))

    while len(q):
        worp_count, x, y = q.popleft()

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if i == 0 and j == 0:
                    continue
                elif abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                else:
                    q.append((worp_count + 1, nx, ny))

    print(d[Dh - 1][Dw - 1])


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

import sys
def input(): return sys.stdin.readline().rstrip()
S = input()
Q = int(input())
qs = list(input() for _ in range(Q))
rev = 0
for q in qs:
    q_sep = q.split()
    if q_sep[0] == '1':
        rev = (rev+1) % 2
    else:
        if (q_sep[1]=='1' and rev==0) or (q_sep[1]=='2' and rev==1):
            S = q_sep[2] + S
        else:
            S += q_sep[2]
print(S if rev == 0 else S[::-1])

### FIXED CODE ###

import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()
S = deque(input())
rev = False
apdlft = S.appendleft
apd = S.append

for _ in range(int(input())):
    q = input().split()
    if q[0] == '1':
        rev = not(rev)
    else:
        if (q[1]=='1' and rev is False) or (q[1]=='2' and rev is True):
            apdlft(q[2])
        else:
            apd(q[2])

if rev:
    print((''.join(S))[::-1])
else:
    print(''.join(S))
### BUGGY CODE ###

from scipy.special import perm, comb

mod = 10 ** 9 + 7
N, M = map(int, input().split())

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

A = perm(M, N, exact=True)

B = 0
for i in range(N + 1):
    B += (-1) ** i * cmb(N, i) * perm(M - i, N - i, exact=True)

print(A * B % mod)

### FIXED CODE ###

mod = 10 ** 9 + 7
N, M = map(int, input().split())

class Combination:
    def __init__(self, size):
        self.size = size + 2
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % mod
            self.inv[i] = -self.inv[mod % i] * (mod // i) % mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % mod) % mod

    def nhr(self, n, r):  # 重複組合せ: x_1 + ... + x_n = r
        return self.ncr(n + r - 1, n - 1)

comb = Combination(M + 100)

A = comb.npr(M, N) % mod

B = 0
for i in range(N + 1):
    B += (-1) ** i * comb.ncr(N, i) * comb.npr(M - i, N - i) % mod

print(A * B % mod)
### BUGGY CODE ###

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

for i in range(n):
    ans *= a[i]

if ans > 10 ** 18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

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

import sys
input = sys.stdin.readline
N, K = map(int, input().split())

sushi_array = []

sushi_count = [-1] * N
sushi_kind = 0
for i in range(N):
    t, d = map(int, input().split())
    sushi_array.append((t - 1, d))
    if sushi_count[t - 1] == -1:
        sushi_count[t - 1] = 0
        sushi_kind += 1

sushi_array = sorted(sushi_array, key=lambda x: -x[1])
# print(sushi_array, sushi_kind)

now_kind = 0
kiso = 0
for sushi in sushi_array[:K]:
    kiso += sushi[1]
    if sushi_count[sushi[0]] == 0:
        now_kind += 1
    sushi_count[sushi[0]] += 1

ans = kiso + now_kind * now_kind

add_index = K
remove_index = K - 1

now_kind += 1
while now_kind <= sushi_kind:
    for sushi in sushi_array[add_index:]:
        if sushi_count[sushi[0]] == 0:
            kiso += sushi[1]
            sushi_count[sushi[0]] = 1
            break
        add_index += 1
    else:
        break
    for sushi in sushi_array[remove_index::-1]:
        if sushi_count[sushi[0]] >= 1:
            kiso -= sushi[1]
            sushi_count[sushi[0]] -= 1
            break
        remove_index -= 1
    else:
        break
    # print(kiso + now_kind * now_kind)
    ans = max(ans, kiso + now_kind * now_kind)
    now_kind += 1

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, K = map(int, input().split())

sushi_array = []

sushi_count = [-1] * N
sushi_kind = 0
for i in range(N):
    t, d = map(int, input().split())
    sushi_array.append([t - 1, d])
    if sushi_count[t - 1] == -1:
        sushi_count[t - 1] = 0
        sushi_kind += 1

sushi_array = sorted(sushi_array, key=lambda x: -x[1])
# print(sushi_array, sushi_kind)

now_kind = 0
kiso = 0
can_remove = []
for sushi in sushi_array[:K]:
    kiso += sushi[1]
    if sushi_count[sushi[0]] == 0:
        now_kind += 1
        sushi_count[sushi[0]] = 1
    else:
        can_remove.append(sushi[1])

    # print(sushi_count)
ans = kiso + now_kind * now_kind

add_index = K
remove_index = K - 1

# print(ans, kiso, now_kind)
now_kind += 1

for sushi in sushi_array[add_index:]:
    if len(can_remove) == 0 or now_kind > sushi_kind:
        break
    if sushi_count[sushi[0]] == 0:
        kiso += sushi[1] - can_remove.pop()
        sushi_count[sushi[0]] = 1
        # print(ans, kiso, now_kind)
        ans = max(ans, kiso + now_kind * now_kind)
        now_kind += 1
    else:
        continue

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

R,G,B,N = map(int,input().split())
cnt = 0
for r in range(N//R+1):
	for g in range((N-r*R)//G+1):
		n=N-R*r-G*g
		if n%B==0 and n//B>=0:
			cnt += 1

print(cnt)

### FIXED CODE ###

R,G,B,N = map(int,input().split())
cnt = 0
for r in range(N//R+1):
	n=N-r*R
	for g in range(n//G+1):
		n1=n-G*g
		if n1%B==0 and n1//B>=0:
			cnt += 1

print(cnt)
### BUGGY CODE ###

def main():
    N, M = map(int, input().split())
    D = [tuple(map(int, input().split())) for _ in range(N)]
    D.sort()
    ans = 0
    while M > 0:
        a, b = D.pop(0)
        ans += a * min(M, b)
        M -= min(M, b)
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N, M = map(int, input().split())
    D = [tuple(map(int, input().split())) for _ in range(N)]
    D.sort()
    ans = 0
    i = 0
    while M > 0:
        a, b = D[i]
        ans += a * min(M, b)
        M -= min(M, b)
        i += 1
    print(ans)


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

N,M = map(int,input().split())
A = list(map(int,[input() for i in range(M)]))
dp = []
dp.append(1) # 0段目
if 1 in A: # 1段目
  dp.append(0) 
else :
  dp.append(1) 

for i in range(2,N+1):  
  if i in A:
    dp.append(0)
  else :
    dp.append(dp[i-1]+dp[i-2])
print(dp[N]%1000000007)  

### FIXED CODE ###

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
dp=[0]*(n+1)
dp[0]=1

af = [0]*(n+1)
for ai in a:
  af[ai]+=1

if 1 in a:
  dp[1]=0
else:
  dp[1]=1

  
for i in range(2,n+1):
  dp[i]=dp[i-2]+dp[i-1]
  if af[i]==1:    
    dp[i]=0

print(dp[-1]%1000000007)