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

n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
s = [[0] for _ in range(n)]
ans = -10**18
 
for i in range(n):
    flag = 0
    a = p[i]
    s[i].append(c[a-1])
    while flag == 0:
        a = p[a-1]
        if a == i + 1:
            flag = 1
        s[i].append(c[a-1]+ s[i][-1])
 
for i in range(n):
    a = 0
    mul = k//(len(s[i])-1)
    m = mul*(s[i][-1] > 0)
    re = k - m*(len(s[i])-1)
 
    a += m*s[i][-1]
    if len(s[i][1:min(re+1, len(s[i])-1)]):
        a += max(s[i][1:min(re+1, len(s[i])-1)])
    
    f = s[i].index(max(s[i][1:-1]))
    al = mul*min(0, m-1) + s[i][f]
    if al > a and m>0:
        a = al
    
    if a > ans:
        ans = a
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
for i in range(N):
    P[i] -= 1
C = list(map(int, input().split()))
 
ans = -(10 ** 18)
 
for si in range(N):
    x = si
    loop = []
    total = 0
    while 1:
        x = P[x]
        loop.append(C[x])
        total += C[x]
        if x == si:
            break
    T = len(loop)  # 周期の大きさ
    tmp = 0
    for i in range(T):
        tmp += loop[i]
        if K < i + 1:
            break
        now = tmp
        if total > 0:  # loopの和が正ならloopを回した方がお得
            loop_times = (K - (i + 1)) // T  # 何周できるか
            now += total * loop_times
        ans = max(ans, now)
 
print(ans)
### BUGGY CODE ###

from collections import Counter
import bisect

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

a_raw=Counter(A)
b_raw=Counter(B)
c_raw=Counter(C)

a=sorted(a_raw.items(), key=lambda x: x[0])
c=sorted(c_raw.items(), key=lambda x: x[0])

ans=0
for i in b_raw:
    insert_index_a = bisect.bisect_left([a[x][0] for x in range(len(a))],i)
    insert_index_c = bisect.bisect_right([c[y][0] for y in range(len(c))],i)
    sum_a=sum(a[m][1] for m in range(insert_index_a))
    sum_c=sum(c[n][1] for n in range(insert_index_c,len(c)))
    ans+=sum_a * b_raw[i] * sum_c

print(ans)

### FIXED CODE ###

import bisect

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

A.sort()
B.sort()
C.sort()

ans = 0
for i in B:
    ins_a = bisect.bisect_left(A,i)
    ins_c = bisect.bisect_right(C,i)
    ans+=ins_a*(N-ins_c)

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

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1

def main():
    h, w, d = map(int, input().split())
    atoij = [[] for _ in range(h * w)]
    for i in range(h):
        for j, a in enumerate(map(int, input().split())):
            a -= 1
            atoij[a] = [i, j]
    # print(atoij)
    q = int(input())
    for _ in range(q):
        l, r = map(int1, input().split())
        ans = 0
        i0, j0 = atoij[l]
        while l < r:
            l += d
            i1, j1 = atoij[l]
            ans += abs(i0 - i1) + abs(j0 - j1)
            i0, j0 = i1, j1
        print(ans)

main()


### FIXED CODE ###

# TLE
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1

def main():
    h, w, d = map(int, input().split())
    atoij = [[] for _ in range(h * w)]
    for i in range(h):
        for j, a in enumerate(map(int, input().split())):
            a -= 1
            atoij[a] = [i, j]
    # print(atoij)
    q = int(input())
    ans=[0]*q
    mx = [0] * d
    mn = [100000] * d
    qq = [[] for _ in range(d)]
    for qi in range(q):
        l, r = map(int1, input().split())
        md = l % d
        if l < mn[md]: mn[md] = l
        if r > mx[md]: mx[md] = r
        qq[md].append([qi, l, r])
    for md in range(d):
        if not qq[md]: continue
        a = mn[md]
        ed = mx[md]
        s = 0
        dist = {}
        i0, j0 = atoij[a]
        while a <= ed:
            i1, j1 = atoij[a]
            s += abs(i0 - i1) + abs(j0 - j1)
            dist[a] = s
            i0, j0 = i1, j1
            a += d
        for qi, l, r in qq[md]:
            ans[qi]=dist[r]-dist[l]
    for x in ans:
        print(x)

main()
### BUGGY CODE ###

import collections

n, p = map(int,input().split())
D = input()
s = [0] * n
mod = 0
out = 0
if 10 % p == 0:
    for i, d in enumerate(D):
        if int(d) % p == 0:
            out += i + 1
else:
    D = D[::-1]
    M = [(int(d) * 10 ** i) % p for i, d in enumerate(D)]
    s[0] = M[0]
    for i in range(1, n):
        s[i] = (s[i - 1] + M[i]) % p
    C = collections.Counter(s)
    out += C[0]
    for c in C.values():
        out += (int(c) * (int(c) - 1)) / 2
print(int(out))

### FIXED CODE ###

n, p = map(int,input().split())
D = input()
out = 0


if 10 % p == 0:
    for i in range(n):
        if int(D[i]) % p == 0:
            out += i + 1
else:
    mod = 0
    count = [0] * p
    ten = 1
    count[mod] += 1
    for i in range(n):
        mod = (mod + int(D[n-i-1]) * ten) % p
        ten = ten * 10 % p
        count[mod] += 1
    for c in count:
        out += (c * (c - 1)) // 2
print(out)
### BUGGY CODE ###



import copy

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

def gcdm(x):
	g=x[0]
	for i in range(1,len(x)):
		g=gcd(g,x[i])
	return(g)

def score(A):
	return(sum(A)-len(A))

def Ifavor(A):
	return(score(A)%2==1)	

def playmove(A,i):
	A[i]-=1
	g=gcdm(A)
	A=[x//g for x in A]
	
def testmove(N,A,i):
	if A[i]<=1:
		return(False)
	A[i]-=1
	g=gcdm(A)
	A=[x//g for x in A]
	if Ifavor(A):
		return(False)
	else:
		j=0
		while j<N:
			if A[j]<=1:
				continue
			A[j]-=1
			h=gcdm(A)	
			if Ifavor([x//h for x in A])==False:
				return(False)
			A[j]+=1
			j+=1
		return(True)

N=int(input())
B=[int(x) for x in input().split()]
'''
inp=St.splitlines()
N=int(inp[0])
B=[int(x) for x in inp[1].split()]
'''
if Ifavor(B):
	print('First')
else:
	e=0
	while e<N:
		A=copy.copy(B)
		if testmove(N,A,e):
			break
		e+=1
	
	if e==N:
		print('Second')
	else:
		print('First')
	





	

### FIXED CODE ###

import random
def tester(N=0):
	'''制約
1≦N≦105
1≦Ai≦109
'''
	maxno1=1e5
	maxno2=1e9
	s=input()
	if s!='':return(s)
	
	if N==0:
		return(random.randint(2,maxno1))
	else:
		print('Testing...')
		print('N=',N)
		A=[]
		for i in range(N):
			A.extend([random.randint(1,maxno2)])
		return(' '.join(list(map(str,A))))

import copy

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

def gcdm(x):
	g=x[0]
	for i in range(1,len(x)):
		if g==1:
			return(g)
		g=gcd(g,x[i])
	return(g)

def playmove(A,i):
	A[i]-=1
	g=gcdm(A)
	return([x//g for x in A])

def noofevens(A):
	r=0
	for i in A:
		if i%2==0:
			r+=1
	return(r)
			

N=int(tester())
A=[int(x) for x in tester(N).split()]


isFirstmove=True
while True:
	e=noofevens(A)
	if e%2==1:
		if isFirstmove:
			print('First')
		else:
			print('Second')
		break
	elif N-e>1:
		if isFirstmove:
			print('Second')
		else:
			print('First')
		break
	else:	
		for i in range(N):
			if A[i]%2==1:
				break
		if A[i]==1:
			if isFirstmove:
				print('Second')
			else:
				print('First')
			break
		else:
			A=playmove(A,i)
			isFirstmove=(isFirstmove!=True)
### BUGGY CODE ###


def update_tree(par, a, b):
    frm = par[a][0] if par[par[a][0]][1] < par[par[b][0]][1] else par[b][0]
    to = par[b][0] if frm == par[a][0] else par[a][0]
    if par[par[frm][0]][1] + 1> par[par[to][0]][1]:
        par[par[to][0]][1] = par[par[frm][0]][1] + 1
    
    while par[frm][0] != par[par[frm][0]][0]: 
        par[frm][0], frm = to, par[frm][0]
    par[frm][0] = to

def get_par(par, p):
    while par[p][0] != par[p][1]:
        p = par[p][0]
    return p

manhattan = lambda x,y:min(abs(x[0] - y[0]), abs(x[1]- y[1]))
N = int(input())
points = []
edges = []
for i in range(N):
    x,y = map(int, input().split())
    points.append([i,i,[x,y]])
points.sort(key=lambda x:x[2][0])
for i in range(N-1):
    edges.append((abs(points[i][2][0] - points[i+1][2][0]), points[i][1], points[i+1][1]))
points.sort(key=lambda x:x[2][1])
for i in range(N-1):
    edges.append((abs(points[i][2][1] - points[i+1][2][1]), points[i][1], points[i+1][1]))
edges.sort(key=lambda x:x[0], reverse=True)
cost = 0
count = 0
points.sort()
while count < N - 1:
    edge = edges.pop()
    if get_par(points, edge[1]) == get_par(points, edge[2]):
        continue
    cost += edge[0]
    count += 1
    update_tree(points, edge[1], edge[2])
print(cost)


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

def unite(i, j):
    j = get_par(j)
    par[j] = get_par(i)
    return

def get_par(p):
    if par[p] is None:
        return p
    par[p] = get_par(par[p])
    return par[p]

N = int(input())
points = []
edges = []
for i in range(N):
    x,y = map(int, input().split())
    points.append([x,y,i])
points.sort()
for i in range(N-1):
    edges.append((abs(points[i][0] - points[i+1][0]), points[i][2], points[i+1][2]))
points.sort(key=lambda x:x[1])
for i in range(N-1):
    edges.append((abs(points[i][1] - points[i+1][1]), points[i][2], points[i+1][2]))
edges.sort(key=lambda x:x[0], reverse=True)

par = [None] * N
cost = 0
count = 0
points.sort()
while count < N - 1:
    c, i, j = edges.pop()
    if get_par(i) == get_par(j):
        continue
    unite(i, j)
    cost += c
    count += 1
print(cost)
### BUGGY CODE ###

import math

K = int(input())

sum = 0

for a in range(K):
    for b in range(K):
        for c in range(K):
            sum += math.gcd(math.gcd(a + 1, b + 1), c + 1)

print(sum)


### FIXED CODE ###

import math

K = int(input())

sum = 0

for a in range(K):
    sum += a + 1
    #print(a + 1, a + 1)
    for b in range(K):
        if a < b:
            gcd2_sum = math.gcd(a + 1, b + 1) * 3 * 2
            sum += gcd2_sum
            #print(a + 1, b + 1, gcd2_sum)
            for c in range(K):
                if b < c:
                    gcd3_sum = math.gcd(math.gcd(a + 1, b + 1), c + 1) *  6
                    sum += gcd3_sum
                    #print(a + 1, b + 1, c + 1, gcd3_sum)
print(sum)
### BUGGY CODE ###

x, y = [int(x) for x in input().split()]


def c(n, r):
    u = 1
    l = 1
    for i in range(min(r, n - r)):
        u *= n - i
        l *= i + 1
    return u // l


def solve(x, y):
    if (x + y) % 3 != 0:
        return 0
    if x * 2 < y or y * 2 < x:
        return 0
    
    n = (x + y) // 3
    r = ((x - y) + n) // 2
    return c(n, r)


print(solve(x, y) % 1000000007)

### FIXED CODE ###

MAX = 1000000
MOD = 1000000007

fac = [None] * MAX
finv = [None] * MAX
inv = [None] * MAX


def comb_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD


def comb(n, k):
    if n < 0 or k < 0 or n < k:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD


comb_init()
x, y = [int(x) for x in input().split()]


def solve(x, y):

    if (x + y) % 3 != 0:
        return 0

    n = (2 * y - x) // 3
    m = (2 * x - y) // 3
    if n < 0 or m < 0:
        return 0

    return comb(n + m, n)


print(solve(x, y))
### BUGGY CODE ###

from collections import defaultdict
N = int(input())
ss = [input() for i in range(N)]
sdic = []
for s in ss:
  dic = defaultdict(int)
  for c in s:
    dic[c] += 1
  sdic.append(dic)
ans = 0
for i in range(N):
  for j in range(i+1, N):
    if sdic[i] == sdic[j]:
      ans += 1
print(ans)
  
    

### FIXED CODE ###

from collections import defaultdict
N = int(input())
ss = [input() for i in range(N)]
sdic = defaultdict(int)
ans = 0
for s in ss:
  dic = defaultdict(int)
  for c in s:
    dic[c] += 1
  key = tuple(sorted(dic.items()))
  sdic[key] += 1
  if sdic[key] >= 2:
    ans += sdic[key] - 1
print(ans)
### BUGGY CODE ###

import itertools
 
N = int(input())
S = [int(c) for c in input()]
 
a = [b for b in itertools.combinations(S, 3)]
 
print(len(set(a))) 

### FIXED CODE ###

N = int(input())
S = [int(c) for c in input()]

count = 0

for i in range(10):
    if i in S[:N-2]:
        a = S.index(i)
        for j in range(10):
            if j in S[a+1:N-1]:
                b = S[a+1:N-1].index(j) +a+1
                for k in range(10):
                    if k in S[b+1:]:
                        count +=1
print(count)
### BUGGY CODE ###

	#!/usr/bin/env python3
import sys


def solve(N: int, M: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    A.sort()
    # print(A)
    from bisect import bisect_left
    for j in range(M):
        idx = bisect_left(A, C[j])
        if(idx != 0):
            for i in range(min(B[j],idx)):
                A[i] = C[j]
            Ad = A[0:idx]
            Ad.sort()
            for i in range(len(Ad)):
                A[i] = Ad[i]
            # print(Ad)
            # A.sort(A[:min(B[j],idx)])
        # print(A)
    print(sum(A))

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]" 
    C = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, M, A, B, C)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, M: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    x = [[B[i],C[i]] for i in range(M)]
    x = sorted(x, key=lambda x: -x[1])

    A.sort()

    dn = 0
    for b, c in x:
        for j in range(b):
            if(dn >= N):
                break
            if(A[dn] < c):
                A[dn] = c
                dn += 1
            else:
                break


    print(sum(A))

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]" 
    C = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, M, A, B, C)

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

import sys
 
n, m = [int(i) for i in input().split(" ")]
p = [0] + [int(i) for i in input().split(" ")]
par = [i for i in range(0, n + 1)]
id_set = [[i] for i in range(0, n + 1)]
p_set = [[p[i]] for i in range(0, n + 1)]

sys.setrecursionlimit(10**6)
 
def root(x):
    if par[x] == x:
        return x
    else:
        r = root(par[x])
        par[x] = r
        return r

def unite(x, y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    else:
        par[x] = y
        id_set[y] = id_set[x] + id_set[y]
        p_set[y] = p_set[x] + p_set[y]

for i in range(0, m):
    x, y = [int(i) for i in input().split(" ")]
    unite(x, y)
    
s = 0
for i in range(1, n + 1):
    if i == root(i):
        id_i = sorted(id_set[i])
        p_i = sorted(p_set[i])
        k = 0
        for j in range(0, len(id_i)):
            while k < len(p_i) and p_i[k] < id_i[j]:
                k += 1
            if k >= len(p_i):
                break
            if p_i[k] == id_i[j]:
                s += 1

print(s)

### FIXED CODE ###

import sys
 
n, m = [int(i) for i in input().split(" ")]
p = [0] + [int(i) for i in input().split(" ")]
par = [i for i in range(0, n + 1)]
id_set = [[] for i in range(0, n + 1)]
p_set = [[] for i in range(0, n + 1)]

sys.setrecursionlimit(10**6)
 
def root(x):
    if par[x] == x:
        return x
    else:
        r = root(par[x])
        par[x] = r
        return r

def unite(x, y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    else:
        par[x] = y

for i in range(0, m):
    x, y = [int(i) for i in input().split(" ")]
    unite(x, y)

for i in range(1, n + 1):
    r = root(i)
    id_set[r].append(i)
    p_set[r].append(p[i])
    
s = 0
for i in range(1, n + 1):
    if i == root(i):
        id_i = sorted(id_set[i])
        p_i = sorted(p_set[i])
        k = 0
        for j in range(0, len(id_i)):
            while k < len(p_i) and p_i[k] < id_i[j]:
                k += 1
            if k >= len(p_i):
                break
            if p_i[k] == id_i[j]:
                s += 1

print(s)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


N = int(input())
a_list = list(map(int, input().split()))
a_list_unique = list(set(a_list))
cnt = 0
for i in a_list_unique:
    a_dict = a_list.count(i)
    if i <= a_dict:
        cnt +=  a_dict - i
    else:
        cnt += a_dict
print(cnt)

### FIXED CODE ###

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


N = int(input())
a_list = list(map(int, input().split()))
a_list_unique = list(set(a_list))
a_cnt = Counter(a_list)
cnt = 0
for i in a_list_unique:
    a_dict = a_cnt[i]
    if i <= a_dict:
        cnt +=  a_dict - i
    else:
        cnt += a_dict
print(cnt)
### BUGGY CODE ###

from bisect import bisect_left
from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    N = int(input())
    L = list(map(int, input().split()))

    L.sort()
    ans = 0
    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            n = bisect_left(L[j+1:], L[i] + L[j])
            ans += n
    print(ans)


main()


### FIXED CODE ###

from bisect import bisect_left
from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    N = int(input())
    L = list(map(int, input().split()))

    L.sort()
    ans = 0
    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            n = bisect_left(L, L[i] + L[j])
            ans += n - (j + 1)
    print(ans)


main()
### BUGGY CODE ###

h, n = input().split()
h = int(h)
n = int(n)
attack = list(map(int, input().split()))
while  n > 0:
    m_attack = max(attack)
    if h - m_attack <= 0:
        h = h - m_attack
        print("Yes")
        break
    else:   
        h = h - m_attack
        attack.remove(m_attack)
        n = n-1
if h > 0:
    print("No")

### FIXED CODE ###

h, n = input().split()
h = int(h)
n = int(n)
attack = sorted(list(map(int, input().split())), reverse=True)
while  n > 0:
    m_attack = attack[0]
    if h - m_attack <= 0:
        h = h - m_attack
        print("Yes")
        break
    else:   
        h = h - m_attack
        attack.remove(m_attack)
        n = n-1
if h > 0:
    print("No")
### BUGGY CODE ###

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

ans = 0

for i in range(1, len(P)+1):
    M = P[:i]
    M.sort()
    if P[i-1] == M[0]:
        ans = ans +1

print(ans)

### FIXED CODE ###

N = int(input())
P = list(map(int,input().split()))
m = float("inf")
count = 0

for i in P:
    if m > i:
        m = i
    if m == i:
        count += 1
print(count)
### BUGGY CODE ###

N,D,A=[int(i) for i in input().split(" ")]
enemies=[]
for i in range(N):
    X,H=[int(j) for j in input().split(" ")]
    enemies.append([X,H])

enemies=sorted(enemies,key=lambda w:w[0])


retval=0
length=len(enemies)
for i in range(length):
    hp=enemies[i][1]
    place=enemies[i][0]
    if hp<=0:
        continue
    if hp%A==0:
        bomb=hp//A
    else:
        bomb=hp//A+1
    retval+=bomb

    for j in range(i,length):
        if enemies[j][0]-place>2*D:
            break
        enemies[j][1]-=bomb*A


print(retval)


### FIXED CODE ###

import sys
N,D,A=[int(i) for i in input().split(" ")]
enemies=[]
for i in range(N):
    X,H=[int(j) for j in input().split(" ")]
    enemies.append([X,H])

enemies=sorted(enemies,key=lambda w:w[0])

if enemies[-1][0]-enemies[0][0]<=2*D:
    hpmax=sorted(enemies,key=lambda  w:w[1])[-1][1]
    if hpmax%A==0:
        print(hpmax//A)
    else:
        print(hpmax//A+1)
    sys.exit()


retval=0
for i in range(N):
    hp=enemies[i][1]
    place=enemies[i][0]
    if hp<=0:
        continue
    if hp%A==0:
        bomb=hp//A
    else:
        bomb=hp//A+1
    retval+=bomb

    for j in range(i,N):
        if enemies[j][0]-place>2*D:
            break
        enemies[j][1]-=bomb*A



print(retval)
### BUGGY CODE ###

#C
N = int(input())
P = list(map(int, input().split()))
ans = 0
 
for i in range(N):
    frag = True
    for j in range(i):
        if P[i] > P[j]:
            frag = False
            break
    if frag == True:
        ans += 1
        
print(ans)

### FIXED CODE ###

#C
N = int(input())
P = list(map(int, input().split()))
ans = 0
min_num = 10**6

for i in range(N):
    min_num = min(min_num, P[i])
    if min_num >= P[i]:
        ans += 1
        
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[0]*n
b=[0]*n
ans=0
temp=0
for i in range(n):
  at,bt=map(int,input().split())
  a[i]=at
  b[i]=bt
import numpy as np
a=np.array(a)
b=np.array(b)
while temp<m:
  t=np.argmin(a)
  ans=ans+a[t]
  temp=temp+1
  b[t]=b[t]-1
  if b[t]==0:
    a=np.delete(a,t)
    b=np.delete(b,t)
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
t=[0]*n
ans=0
temp=0
for i in range(n):
  at,bt=map(int,input().split())
  t[i]=[at,bt]
t.sort()
i=0
while True:
  if temp+t[i][1]>=m:
    ans=ans+t[i][0]*(m-temp)
    break
  else:
    ans=ans+t[i][0]*t[i][1]
    temp=temp+t[i][1]
    i=i+1
print(ans)
### BUGGY CODE ###


s=input()
q=int(input())
for i in range(q):
    l=input().split()
    if l[0]=='1':
        s=s[::-1]
    else:
        if l[1]=='1':
            s=l[2]+s
        else:
            s=s+l[2]

print(s)


### FIXED CODE ###

from collections import deque
s=input()
q=int(input())
n=0
que=deque(s)
for i in range(q):
    l=input()
    if l[0]=='1':
        n+=1
    else:
        if (l[2]=='1' and n%2==0) or (l[2]=='2' and n%2==1):
            que.appendleft(l[4])
        else:
            que.append(l[4])

ans=''.join(que)
if n%2==0:
    print(ans)
else:
    print(ans[::-1])
### BUGGY CODE ###

n, m, r = list(map(int, input().split()))
rs = list(map(int, input().split()))
# construct map
import numpy as np
dists = np.ones((n + 1, n + 1)) * float('inf')
for _ in range(m):
    a, b, c = list(map(int, input().split()))
    dists[a, b] = dists[b, a] = c

from itertools import product, permutations
for i, j in product(range(1, 1 + n), repeat=2):
    for k in range(j + 1, n + 1):
        if dists[j, k] > dists[j, i] + dists[i, k]:
            dists[j, k] = dists[k, j] = dists[j, i] + dists[i, k]

ans = float('inf')
for path in permutations(rs):
    val = sum(dists[i, j] for i, j in zip(path, path[1:]))
    val = int(val)
    if val < ans:
        ans = val

print(ans)

### FIXED CODE ###

n, m, r = list(map(int, input().split()))
rs = list(map(int, input().split()))
# construct map
import numpy as np
dists = np.ones((n + 1, n + 1)) * float('inf')
for _ in range(m):
    a, b, c = list(map(int, input().split()))
    dists[a, b] = dists[b, a] = c
for i in range(1, n + 1):
    dists[i, i] = 0

from itertools import product, permutations
for i, k in product(range(1, 1 + n), repeat=2):
    dists[:, k] = np.minimum(dists[:, k], dists[:, i] + dists[i, k])

ans = float('inf')
for path in permutations(rs):
    val = sum(dists[i, j] for i, j in zip(path, path[1:]))
    val = int(val)
    if val < ans:
        ans = val

print(ans)