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

#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 998244353
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

def main():
    N, M, K = map(int, input().split())

    fact = [1]
    for i in range(1, N+3):
        fact.append(fact[-1] * i % MOD)
    def rev(x):
        return pow(x, MOD-2, MOD)
    def cmb(i, k):
        if(i < k): return 0
        return fact[i] * rev(fact[k]) * rev(fact[i-k]) % MOD

    def count(m, k):
        combo = cmb(N-1, k)
        col = m * pow(m-1, N-k-1, MOD)
        val = (combo*col)%MOD
        return val

    cnt = 0
    for k in range(0, K+1):
        addval = count(M, k)
        cnt += addval
        cnt %= MOD

    print(cnt)
if __name__=='__main__':
    main()

### FIXED CODE ###

#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 998244353
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

def main():
    N, M, K = map(int, input().split())

    fact = [1]
    for i in range(1, N+3):
        fact.append(fact[-1] * i % MOD)
    def rev(x):
        return pow(x, MOD-2, MOD)
    def cmb(i, k):
        if(i < k): return 0
        return fact[i] * rev(fact[k]) * rev(fact[i-k]) % MOD

    def count(m, k):
        combo = cmb(N-1, k)
        col = m * pow(m-1, N-k-1, MOD)
        val = (combo*col)%MOD
        return val

    cnt = 0
    for k in range(0, K+1):
        addval = count(M, k)
        cnt += addval
        cnt %= MOD

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

import math
from functools import reduce
import itertools

def gcd(*numbers):
    return reduce(math.gcd, numbers)

a = int(input())

ans = 0
for i in range(1, a+1):
    for k in range(1, a+1):
        for j in range(1, a+1):
            ans += int(gcd(i, k, j))
            # print(math.gcd(i, k ,j))

print(ans)

### FIXED CODE ###

from math import gcd

a = int(input())

ans = 0
for i in range(1, a+1):
    for k in range(1, a+1):
        for j in range(1, a+1):
            ans += gcd(gcd(i,k),j)


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

import copy
N , W = map(int, input().split())
item =[list(map(int, input().split())) for i in range(N)]
dp = [0] * (W+1)
dp2 = [0] * (W+1)
for i in range(N):
    w = item[i][0]
    v = item[i][1]
    for j in range(1, W+1):
        if j - w >= 0:
            dp2[j] = max(dp[j], dp[j-w] + v)
    dp = copy.copy(dp2)
print(dp[W])

### FIXED CODE ###

import copy
N , W = map(int, input().split())
item =[list(map(int, input().split())) for i in range(N)]
dp = [0] * (W+1)
dp2 = [0] * (W+1)
for i in range(N):
    w = item[i][0]
    v = item[i][1]
    for j in range(1, W+1):
        if j - w >= 0:
            dp2[j] = max(dp[j], dp[j-w] + v)
    dp = copy.copy(dp2)
print(dp[W])
### BUGGY CODE ###

N,W = map(int,input().split())
WV = []
dp = [[0 for i in range(W+1)]for j in range(N+1)]
for i in range(N):
    WV.append(list(map(int,input().split())))
for i in range(N):
    for w in range(W+1):
        if  w - WV[i][0] >= 0:
            dp[i+1][w] = max(dp[i][w],dp[i][w - WV[i][0]]+WV[i][1])
        else:
            dp[i+1][w] = dp[i][w]
print(dp[-1][-1])


### FIXED CODE ###

import numpy as np
N,W = map(int,input().split())
dp = np.zeros(W+1,dtype=int)
for i in range(N):
    w,v = map(int,input().split())
    dp[w:W+1] = np.maximum(dp[0:W+1-w]+v,dp[w:W+1])
print(dp[-1])
### BUGGY CODE ###

def main():
  s = list(map(lambda x:ord(x)-97, list(input())))
  ls = len(s)
  ss = set(s)
  t = list(map(lambda x:ord(x)-97, list(input())))
  lt = len(t)
  st = set(t)
  td = [list() for _ in range(26)]
  if not st.issubset(ss):
    print(-1)
    exit()
  for i in range(lt-1):
    td[t[i]].append(t[i+1])
  md = [None for _ in range(ls)]
  cd = [0]*26
  for i in range(ls-1,-1,-1):
    cd[s[i]] = i + ls
  for i in range(ls-1,-1,-1):
    md[i] = {x:cd[x] for x in td[s[i]]}
    cd[s[i]] = i
  ans = 0
  cur = cd[t[0]]
  for i in range(lt-1):
    cur = md[cur][t[i+1]]
    ans += (cur//ls)
    cur %= ls
  print(1 + ans*ls+cur)

if __name__ == "__main__":
  main() 

### FIXED CODE ###

def main():
  s = list(map(lambda x:ord(x)-97, list(input())))
  ls = len(s)
  ss = set(s)
  t = list(map(lambda x:ord(x)-97, list(input())))
  lt = len(t)
  st = set(t)
  td = [list() for _ in range(26)]
  if not st.issubset(ss):
    print(-1)
    exit()
  for i in range(lt-1):
    td[t[i]].append(t[i+1])
  md = [None for _ in range(ls)]
  cd = [0]*26
  for i in range(ls-1,-1,-1):
    cd[s[i]] = i + ls
  for i in range(ls-1,-1,-1):
    md[i] = cd.copy()
    cd[s[i]] = i
  ans = 0
  cur = cd[t[0]]
  for i in range(lt-1):
    cur = md[cur][t[i+1]]
    ans += (cur//ls)
    cur %= ls
  print(1 + ans*ls+cur)

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

import sys

# inputを高速化する。
input = sys.stdin.readline

# 入力
N, W = map(int, input().split())
lst_weight = [0 for _ in range(N)]
lst_value = [0 for _ in range(N)]
for i in range(N):
    lst_weight[i], lst_value[i] = map(int, input().split())

def chmax(a, b):
    if a >= b:
        return a
    else:
        return b

dp = [[0 for i in range(W+1)] for j in range(N+1)]

for i in range(N):
    for sum_w in range(W+1):
        # i番目の品物を選ぶ
        # print(sum_w - lst_weight[i])
        if sum_w - lst_weight[i] >= 0:
            dp[i+1][sum_w] = chmax(dp[i+1][sum_w], dp[i][sum_w - lst_weight[i]] + lst_value[i])
        # i番目の品物を選ばない
        dp[i+1][sum_w] = chmax(dp[i+1][sum_w], dp[i][sum_w])
        # print(dp)

print(dp[N][W])




### FIXED CODE ###


import sys

input = sys.stdin.readline

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

dp = [0] * (W + 1)
def knapsack(n, w):
    for _ in range(N):
        w, v = map(int, input().split())
        for wk in range(W, w-1, -1):
            tv = dp[wk - w] + v
            if tv > dp[wk]:
                dp[wk] = tv
    return dp[-1]

print(knapsack(N, W))
### BUGGY CODE ###

def main():
    N = int(input())
    d = {}
    for i in range(N):
        a = list(map(int, input().split()))
        for j in range(N):
            d[(i, j)] = a[j]
            d[(j, i)] = a[j]
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            if i == j:
                continue
            for k in range(N):
                if k == i or k == j:
                    continue
                if d[(i,j)] == d[(i,k)] + d[(k, j)]:
                    break
                if d[(i,j)] > d[(i,k)] + d[(k, j)]:
                    return -1
            else:
                ans += d[(i,j)]
    return ans
print(main())


### FIXED CODE ###

def main():
    N = int(input())
    l = []
    for i in range(N):
        a = list(map(int, input().split()))
        l.append(a)
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            if i == j:
                continue
            for k in range(N):
                if k == i or k == j:
                    continue
                if l[i][j] == l[i][k] + l[k][j]:
                    break
                if l[i][j] > l[i][k] + l[k][j]:
                    return -1
            else:
                ans += l[i][j]
    return ans
print(main())
### BUGGY CODE ###

import sys
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
#from bisect import bisect_left as bl
input = sys.stdin.readline

n,Q=map(int,input().split())
xs = []
ts = set()
for _ in range(n):
    s,t,x=map(int,input().split())
    xs += [(s-x-0.4,True,x), (t-x-0.5,False,x)]
    ts.add(x)
xs.sort(key=lambda x:x[0])
xs += [(10**9,True,x)]

mx = max(ts) + 1
tmp = list(ts)
x2i = dict()
for i, x in enumerate(ts):
    x2i[x] = i



XN = len(ts)
st = SegTree([mx]*XN, XN, mx, min)
q = int(input())
for t,r,x in xs:
    if q < t:
        c = st.query(0,XN)
        while True:
            if q >= t:
                break
            print(c if c!= mx else -1)
            Q-=1
            if not Q:
                sys.exit()
            q = int(input())
    st.update(x2i[x], x if r else mx)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n,Q=map(int,input().split())
b_num = 2**(n-1).bit_length()
mx = 10**9
segl=[mx]*2*b_num 

def update( k, x):
    k += b_num-1
    segl[k] = x
    while k+1:
        k = (k-1)//2
        segl[k] = min(segl[k*2+1],segl[k*2+2])
    
if __name__ == '__main__':
    xs = []
    for i in range(n):
        s,t,x=map(int,input().split())
        xs += [(s-x-0.4,True,x,i), (t-x-0.5,False,x,i)]
    for _ in range(Q):
        xs.append((int(input()),2))
    xs.sort(key=lambda x:x[0])
    for x in xs:
        if x[1]==2:
            print(segl[0] if segl[0]!= mx else -1)
            continue
        update(x[3], x[2] if x[1] else mx)
### BUGGY CODE ###

import sys
import numpy as np


def update(A):
    H, W = A.shape

    D = np.insert(A, 0, 0, axis=0)[:H, :]
    U = np.insert(A, H, 0, axis=0)[1:, :]
    L = np.insert(A, 0, 0, axis=1)[:, :W]
    R = np.insert(A, W, 0, axis=1)[:, 1:]

    A = np.maximum(A, D)
    A = np.maximum(A, U)
    A = np.maximum(A, L)
    A = np.maximum(A, R)

    return A


def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    A = [[0 if c == '.' else 1 for c in input().strip()] for _ in range(H)]
    A = np.array(A)
    ones = np.ones((H, W), dtype=int)

    cnt = 0
    while not np.array_equal(A, ones):
        A = update(A)
        cnt += 1

    return cnt

if __name__ == '__main__':
    print(main())


### FIXED CODE ###

#ref: https://atcoder.jp/contests/agc033/submissions/5260580

import sys
import numpy as np

def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    INF = H * W
    dp = [[INF if c == '.' else 0 for c in input().strip()] for _ in range(H)]
    dp = np.array(dp)

    for i in range(1, H):
        dp[i, :] = np.minimum(dp[i, :], dp[i-1, :] + 1)

    for i in range(H-2, -1, -1):
        dp[i, :] = np.minimum(dp[i, :], dp[i+1, :] + 1)

    for i in range(1, W):
        dp[:, i] = np.minimum(dp[:, i], dp[:, i-1] + 1)

    for i in range(W-2, -1, -1):
        dp[:, i] = np.minimum(dp[:, i], dp[:, i+1] + 1)

    return np.max(dp)

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

import sys
input = sys.stdin.readline

H, W = map(int, input().split())
s = ['0' * (W+2)]
for _ in range(H):
    s.append('0' + input().rstrip() + '0')
s.append('0' * (W+2))

ans = []
if s[1][1] == '#': a, b = 1, 1
else: a, b = 0, 0
temp = [[1, 1, a, b]]

while temp:
    p = temp.pop()
    for y, x in [[p[0]+1, p[1]], [p[0], p[1]+1]]:
        c = p[2]
        d = p[3]
        if s[y][x] == '0':continue
        if s[y][x] == '#':
            if c == 0:
                d += 1
                c = 1
        else:
            c = 0
        if y == H and x == W:
            ans.append(d)
        else:
            temp.append([y, x, c, d])
            
print(min(ans))

### FIXED CODE ###

import sys
input = sys.stdin.readline

H, W = map(int, input().split())
s = [input().rstrip() for _ in range(H)]

dp = [[1000]*W for _ in range(H)]

if s[0][0] == '#': dp[0][0] = 1
else: dp[0][0] = 0

for j in range(W):
    for i in range(H):
        if i <= H - 2:

            if s[i][j] == '.' and s[i+1][j] == '#':
                dp[i+1][j] = min(dp[i+1][j], dp[i][j] + 1)
            else: dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        if j <= W - 2:

            if s[i][j] == '.' and s[i][j+1] == '#':
                dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1)
            else: dp[i][j+1] = min(dp[i][j+1], dp[i][j])


print(dp[H-1][W-1])
### BUGGY CODE ###

from bisect import bisect_left

N=int(input())
L=list(map(int,input().split()))
L=sorted(L)
ans=0
for i in range(N-2):
  a=L[i]
  for j in range(i+1,N-1):
    b=L[j]
    lo=0
    hi=N
    x=a+b
    while lo<hi:
      mid=(lo+hi)//2
      if L[mid]<x: lo=mid+1
      else: hi=mid
    ans+=lo-(j+1)    
print(ans)


### FIXED CODE ###

from bisect import bisect_left

N=int(input())
L=list(map(int,input().split()))
L=sorted(L)
ans=0

for i in range(N-2):
  a=L[i]
  for j in range(i+1,N-1):
    b=L[j]
    ans+=bisect_left(L,a+b)-(j+1)
print(ans)
### BUGGY CODE ###

from collections import defaultdict

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

max_A = max(A)
j = 0
while max_A >> j > 0:
    j += 1
max_j = j

c = defaultdict(int)
ans = 0
MOD = 10 ** 9 + 7
for i in range(N - 2, -1, -1):
    Ai = A[i + 1]
    for j in range(max_j):
        c[(j, Ai >> j & 1)] += 1
    Ai = A[i]
    for j in range(max_j):
        ans += (1 << j) * c[(j, (Ai >> j & 1 ^ 1))]
    ans %= MOD
print(ans)


### FIXED CODE ###

from collections import defaultdict

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

max_A = max(A)
j = 0
while max_A >> j > 0:
    j += 1
max_j = j

ans = 0
MOD = 10 ** 9 + 7
for j in range(max_j):
    c = [0] * 2
    for i in range(N):
        c[A[i] >> j & 1] += 1
    ans += c[0] * c[1] * (1 << j)
    ans %= MOD
print(ans)
### BUGGY CODE ###

print(sum([i for i in range(1, int(input()))]))

### FIXED CODE ###

n = int(input())
print(n*(n-1)//2)
### BUGGY CODE ###

N = int(input())

name = []
num = []

max_temp = 1

for _ in range(N):
    temp = input()
    if not temp in name:
        name.append(temp)
        num.append(1)
    else:
        num[name.index(temp)] += 1
        if num[name.index(temp)] > max_temp:
            max_temp = num[name.index(temp)]
            
        
output = []

for i in range(len(num)):
    if num[i] == max_temp:
        output.append(name[i])
        
output.sort()

for i in range(len(output)):
    print(output[i])

### FIXED CODE ###

# coding cell (SUBMIT ONLY THIS CELL)

N = int(input())

counter = {}

for i in range(N):
    temp = input()
    if temp not in counter:
        counter.update({temp : 1})
    else:
        counter.update({temp : counter[temp] + 1})

m = max(counter.values())
        
ans = []    

for a,b in counter.items():
    if b == m:
        ans.append(a)
    
ans.sort()

for i in ans:
    print(i)
### BUGGY CODE ###

import math

def sign(x):
    if x >= 0:
        return True
    else:
        return False

def wa(a,x,y):
    S = 0
    for i in range(x,y+1):
        S = S + a[i]
    return S

n = int(input())
while n != 0:
    a = []
    for i in range(n):
        a.append(int(input()))
    b = []
    b.append(a[0])
    for i in range(1,len(a)):
        if sign(b[len(b)-1]) == sign(a[i]):
            b[len(b)-1] = b[len(b)-1] + a[i]
        else:
            b.append(a[i])

    ans = b[0]
    for i in range(len(b)):
        for j in range(i,len(b)):
            ans = max(wa(b,i,j),ans)
    print(ans)
    n = int(input())



### FIXED CODE ###

import math

def sign(x):
    if x >= 0:
        return True
    else:
        return False

n = int(input())
while n != 0:
    a = []
    for i in range(n):
        a.append(int(input()))
    b = []
    b.append(a[0])
    for i in range(1,len(a)):
        if b[len(b)-1] > 0 and a[i] > 0:
            b[len(b)-1] = b[len(b)-1] + a[i]
        else:
            b.append(a[i])

    ans = b[0]
    for i in range(len(b)):
        S = 0
        for j in range(i,len(b)):
            S = S + b[j]
            ans = max(S, ans)
    print(ans)
    n = int(input())
### BUGGY CODE ###

import math

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

    dp=[1]*202020
    for i in range(K):
        dp[K]*=A[i]

    for i in range(K+1,N+1):
        dp[i]=dp[i-1]/A[i-K-1]*A[i-1]
        if(dp[i]>dp[i-1]):
            print("Yes")
        else:
            print("No")


resolve()

### FIXED CODE ###

import math

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

    # dp=[1]*202020
    # for i in range(K):
    #     dp[K]*=A[i]

    for i in range(K+1,N+1):
        #dp[i]=dp[i-1]/A[i-K-1]*A[i-1]
        if(A[i-1]>A[i-K-1]):
            print("Yes")
        else:
            print("No")


resolve()
### BUGGY CODE ###

def merge(A,left,mid,right):
    n1=mid-left
    n2=right-mid
#    L=[0]*(n1+1)
#    R=[0]*(n2+1)
    global L, R
    for i in range(n1):
        L[i]=A[left+i]
    for i in range(n2):
        R[i]=A[mid+i]
    L[n1]=float("inf")
    R[n2]=float("inf")
    i=0
    j=0
    global cnt
    for k in range(left,right):
        cnt+=1
        if L[i]<=R[j]:
            A[k]=L[i]
            i=i+1
        else:
            A[k]=R[j]
            j=j+1

def mergeSort(A,left,right):
    if left+1<right:
        mid=(left+right)//2
        mergeSort(A,left,mid)
        mergeSort(A,mid,right)
        merge(A,left,mid,right)

n=int(input())
S=list(input().split())
for i in range(n):
    S[i]=int(S[i])
L=[0]*(n+1)
R=[0]*(n+1)
cnt=0
mergeSort(S,0,n)
for i in range(n):
    if i==n-1:
        print(S[i])
    else:
        print(S[i],end=" ")
print(cnt)



### FIXED CODE ###

def merge(A,left,mid,right):
    n1=mid-left
    n2=right-mid
    L = A[left:mid]
    R = A[mid:right]
    L.append(float("inf"))
    R.append(float("inf"))
    """
    L=[0]*(n1+1)
    R=[0]*(n2+1)
    for i in range(n1):
        L[i]=A[left+i]
    for i in range(n2):
        R[i]=A[mid+i]
    L[n1]=float("inf")
    R[n2]=float("inf")
    """
    i=0
    j=0
    for k in range(left,right):
        global cnt
        cnt+=1
        if L[i]<=R[j]:
            A[k]=L[i]
            i=i+1
        else:
            A[k]=R[j]
            j=j+1

def mergeSort(A,left,right):
    if left+1<right:
        mid=(left+right)//2
        mergeSort(A,left,mid)
        mergeSort(A,mid,right)
        merge(A,left,mid,right)

n=int(input())
S=list(input().split())
for i in range(n):
    S[i]=int(S[i])
cnt=0
mergeSort(S,0,n)
for i in range(n):
    if i==n-1:
        print(S[i])
    else:
        print(S[i],end=" ")
print(cnt)
### BUGGY CODE ###

n=int(input())
x=[int(i) for i in input().split()]
for i in range(n):
    A=x[0:i]+x[i+1:]
    A.sort()
    half=n//2
    print(A[n-half-1])

### FIXED CODE ###

n=int(input())
x=[int(i) for i in input().split()]
A=sorted(x)
b=A[n//2-1]
c=A[n//2]
for i in x:
    if i<=b:
        print(c)
    else:
        print(b)
### BUGGY CODE ###

N = int(input())
strList = []
for i in range(N):
    inStr = input()
    inList = []
    for j in range(len(inStr)):
        inList.append(inStr[j])
    inList.sort()
    strList.append(''.join(inList))

anaglam = 0
for i in range(N):
    for j in range(i+1,N):
        if strList[i] == strList[j]:
            anaglam = anaglam + 1
print(anaglam)

### FIXED CODE ###

N = int(input())
strDict = {} 
for i in range(N):
    inStr = input()
    inList = []
    for j in range(len(inStr)):
        inList.append(inStr[j])
        inList.sort()
    sortStr = ''.join(inList)
    if sortStr in strDict:
        strDict[sortStr] = strDict[sortStr] + 1
    else:
        strDict[sortStr] = 1

anaglam = 0

for i in strDict.keys():
    anaglam = anaglam + strDict[i]*(strDict[i]-1)//2
    
print(anaglam)
### BUGGY CODE ###

n = int(input())
S = input()
m = n//2
l,r = 0,n-1
ans = 0
while l<=r:
    m = (l + r) // 2
#    print("m = ", m)
    for i in range(n-m) :
        # 切り取る
        sub = S[i :i + m]
#        print("sub=", sub)
#        print("i=", i)
        fl = False
        for j in range(i + m, n - m + 1) :
#            print("j=", j)
            sub2 = S[j :j + m]
            if sub == sub2 : #sub==sub2となり共通する部分がある場合
                fl = True
                break
        if fl:
            l = m+1
            ans = l-1
#            print(l-1,"にて共通部分有")
            break
    else:
        r = m-1
#        print(r+1,"にて共通部分無")
print(ans)

### FIXED CODE ###

n = int(input())
S = input()
m = n//2
l,r = 0,n-1
ans = 0
def check(m):
    Se = set()
    for i in range(n-2*m+1):
        Se.add(S[i:i+m])
        if S[i+m:i+2*m] in Se:
            return True
    return False

while l<=r:
    m = (l + r) // 2
 #   print("m = ", m)
    if check(m):
        fl = True
        l = m+1
        ans = l-1
 #       print(l-1,"にて共通部分有")
    else:
        r = m-1
 #       print(r+1,"にて共通部分無")
print(ans)
### BUGGY CODE ###

import heapq

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

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

td.sort(reverse=True, key=lambda x: x[1])

g1 = [0] * (N + 1)
g0 = []
sumt = 0
for i in range(K):
    t, d = td[i]
    if g1[t] == 0:
        g1[t] = d
        sumt += 1
    elif g1[t] < d:
        heapq.heappush(g0, g1[t])
        g1[t] = d
    else:
        heapq.heappush(g0, d)

ans = sum(g1) + sum(g0) + sumt * sumt
for i in range(K, N):
    t, d = td[i]
    if g1[t] == 0 and len(g0) > 0:
        g1[t] = d
        heapq.heappop(g0)
        sumt += 1
        newans = sum(g1) + sum(g0) + sumt * sumt
        ans = max(ans, newans)

print(ans)

### FIXED CODE ###

import heapq

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

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

td.sort(reverse=True, key=lambda x: x[1])

g1 = [0] * (N + 1)
g0 = []
sumt = 0
for i in range(K):
    t, d = td[i]
    if g1[t] == 0:
        g1[t] = d
        sumt += 1
    elif g1[t] < d:
        heapq.heappush(g0, g1[t])
        g1[t] = d
    else:
        heapq.heappush(g0, d)

sumg1 = sum(g1)
sumg0 = sum(g0)
ans = sumg1 + sumg0 + sumt * sumt
for i in range(K, N):
    t, d = td[i]
    if g1[t] == 0 and len(g0) > 0:
        g1[t] = d
        sumg1 += d
        sumg0 -= heapq.heappop(g0)
        sumt += 1
        newans = sumg1 + sumg0 + sumt * sumt
        ans = max(ans, newans)

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

import sys
from collections import defaultdict
import bisect
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

S = sr()
len_S = len(S)
T = sr()
dict_S = defaultdict(list)
for i, s in enumerate(S):
    dict_S[s].append(i)

answer = 0
cur = -1
for t in T:
    turn = 0 # 1周した時 len_S - cur
    if not dict_S[t]:
        print(-1)
        exit()
    indexes = dict_S[t] + [len_S]
    i = bisect.bisect_right(indexes, cur)
    next = indexes[i]
    if next == len_S:
        turn = len_S - cur - 1
        cur = -1
        answer += indexes[0] - cur + turn
        cur = indexes[0]
    else:
        answer += next - cur
        cur = next

print(answer)


### FIXED CODE ###

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

from collections import defaultdict
from bisect import bisect_left

S = input().rstrip()
T = input().rstrip()

LS = len(S)

index = defaultdict(list)

for i,s in enumerate(S):
    index[s].append(i)

x = -1
for t in T:
    arr = index[t]
    if len(arr) == 0:
        x = -2
        break
    y = (x+1) % LS
    i = bisect_left(arr,y)
    if i < len(arr):
        next_x = (x+1) + arr[i] - y
    else:
        next_x = (x+1) + arr[0] - y + LS
    x = next_x

print(x + 1)