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

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
  
n = int(input())

sum = 0
for i in range(1,n+1):
  for j in range(1,n+1):
    for k in range(1,n+1):
      sum += gcd(i, j, k)
      
print(sum)


### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
  
n = int(input())

sum = 0
for i in range(1,n+1):
  for j in range(i,n+1):
    for k in range(j,n+1):
#      print(i, j, k)
      if i ==j and i == k:
        sum += gcd(i, j, k)
      elif i == j or j == k or i == k:
        sum += gcd(i, j, k)*3
      else: 
        sum += gcd(i, j, k)*6
#      print(sum)
print(sum)
### BUGGY CODE ###

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

cnt = 0
ans = []

for i in range(1,N+1):
    for j in range(1,N+1):
        for k in range(1,N+1):
            if (i + j) % K == 0 and (j + k) % K == 0 and (k + i) % K == 0:
                cnt += 1
                ans.append([i,j,k])
print(cnt)


### FIXED CODE ###

n,k = map(int,input().split())

if k%2==1:
    ans = (n//k)**3
else:
    even = n//k
    odd  = (2*n)//k - even
    ans = even**3 + odd**3
print(ans)
### BUGGY CODE ###

n,a = map(int,input().split())
x = list(map(int,input().split()))
x = list(map(lambda y:y-a,x))

ans = -1

for i in range(2**n):
    tmp = 0
    for j in range(n):
        if (i >> j) & 1:
            tmp += x[j]
    if tmp == 0:
        ans += 1

print(ans)

### FIXED CODE ###

n,a = map(int,input().split())
x = sorted(list(map(lambda y:int(y)-a,input().split())))

sx = max(abs(x[0]),abs(x[-1]))*n

dp = [[0 for _ in range(2*sx+2)] for _ in range(n+1)]
dp[0][0] = 1

for j in range(n):
    for t in range(-sx-1,sx+1):
        if -sx <= t-x[j] and t-x[j] <= sx: 
            dp[j+1][t] = dp[j][t] + dp[j][t-x[j]]
        else:
            dp[j+1][t] = dp[j][t]

print(dp[n][0]-1)
### BUGGY CODE ###

import bisect
while 1:
    n,m=map(int,input().split())
    if n==0:break
    s,a=[],[0]*(n+1)
    for i in range(1,n+1):
        a[i]=int(input())
        for j in range(i+1):
            if a[i]+a[j]<=m:s+=[a[i]+a[j]]
            else:break
    s.sort()
    print(max(i+s[bisect.bisect_right(s,m-i)-1]for i in s))

### FIXED CODE ###

import bisect
while 1:
    n,m=map(int,input().split())
    if n==0:break
    s=[]
    a=[0]+sorted([int(input()) for _ in range(n)])
    for i in range(n+1):
        for j in a[i:]:
            if a[i]+j>m:break
            s+=[a[i]+j]
    s.sort()
    print(max(i+s[bisect.bisect_right(s,m-i)-1]for i in s))
### BUGGY CODE ###

import itertools
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

n,m=map(int,input().split())
path=[[] for i in range(n+1)]
for i in range(m):
    u,v=map(int,input().split())
    path[u].append(v)
S,T=map(int,input().split())


que=[S]
flag=[0]*(n+1)
flag[S]=1
list1=[]
list2=[]

while que:
    h=que.pop()
    lst=[h]
    for i in range(3):
        u=[]
        for j in lst:
            for k in path[j]:
                u.append(k)
        lst=u
    lst=list(set(lst))
    for i in lst:
        if i==h:
            continue
        list1.append(h)
        list2.append(i)
        if flag[i]==0:
            flag[i]=1
            que.append(i)
d=[1]*len(list1)

csr=csr_matrix((d,(list1,list2)),(n+1,n+1))
ans=dijkstra(csr,indices = S)
if ans[T]<n:
    print(int(ans[T]//1))
else:
    print(-1)

### FIXED CODE ###

n,m=map(int,input().split())
data=[[] for i in range(3*n+1)]
for i in range(m):
    u,v=map(int,input().split())
    data[u].append(v+n)
    data[u+n].append(v+2*n)
    data[u+2*n].append(v)
s,t=map(int,input().split())
inf=float("inf") 
flag=[inf]*(3*n+1)
flag[s]=0
que=[s]
while que:
    h=[]
    for u in que:
        for v in data[u]:
            if flag[v]==inf:
                flag[v]=flag[u]+1
                h.append(v)
    que=h
if flag[t]==inf:
    print(-1)
else:
    print(flag[t]//3)
### BUGGY CODE ###

from itertools import groupby
from functools import reduce

MOD = 1000000007

def max_t():
    i, t_max = 0, 0
    for j, v in enumerate(t):
        if v < t_max:
            print(0)
            quit(0)
        if v > t_max:
            t_max = v
            i = j
    return i, t_max


def validate_a(i, t_max):
    for v in a[:i + 1]:
        if v != t_max:
            print(0)
            quit(0)
    for v in a[i + 1:]:
        if v > t_max:
            print(0)
            quit(0)


if __name__ == '__main__':
    n = int(input())
    t = [int(s) for s in input().split()]
    a = [int(s) for s in input().split()]
    i, t_max = max_t()
    validate_a(i, t_max)

    highests = [min(x, y) for x, y in zip(a, t)]
    print(reduce(lambda x, y: x * y % MOD, (v ** ((length - 1) if v < t_max else max(length - 2, 0)) for v, length in ((v, len(list(l))) for v, l in groupby(highests)))))


### FIXED CODE ###

from itertools import groupby
from functools import reduce

MOD = 1000000007

def mod_pow(x, k):
    ret = 1
    while k > 0:
        if k & 1:
            ret *= x
            ret %= MOD
        k >>= 1
        x *= x
        x %= MOD
    return ret


def max_t():
    i, t_max = 0, 0
    for j, v in enumerate(t):
        if v < t_max:
            print(0)
            quit(0)
        if v > t_max:
            t_max = v
            i = j
    return i, t_max


def validate_a(i, t_max):
    for v in a[:i + 1]:
        if v != t_max:
            print(0)
            quit(0)
    for v in a[i + 1:]:
        if v > t_max:
            print(0)
            quit(0)


if __name__ == '__main__':
    n = int(input())
    t = [int(s) for s in input().split()]
    a = [int(s) for s in input().split()]
    i, t_max = max_t()
    validate_a(i, t_max)

    highests = [min(x, y) for x, y in zip(a, t)]
    print(reduce(lambda x, y: x * y % MOD, (mod_pow(v, ((length - 1) if v < t_max else max(length - 2, 0))) for v, length in ((v, len(list(l))) for v, l in groupby(highests)))))
### BUGGY CODE ###

def Euclid(a,b):
  r = a % b
  if r == 0:
    return b
  return Euclid(b,r)
import fractions

a,b = map(int,input().split())
#c = Euclid(a,b) if a > b else Euclid(b,a)
c = fractions.gcd(a,b)

def soinsu(a):
  for i in range(2,a+1):
    if a % i == 0:
      return i
    
ans = []
while 1:
  if c==1:
    break
  s = soinsu(c)
  c = int(c/s)
  ans.append(s)
  
print(len(set(ans)) + 1)

### FIXED CODE ###

def Euclid(a,b):
  r = a % b
  if r == 0:
    return b
  return Euclid(b,r)
import fractions

a,b = map(int,input().split())
#c = Euclid(a,b) if a > b else Euclid(b,a)
c = fractions.gcd(a,b)

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
  
if c == 1:
  print(1)
else:
  print(len(factorization(c))+1)
### BUGGY CODE ###

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

def main():
    N = int(input())
    if N == 1:
        print("First")
        exit()
    edge = [[] for _ in range(N)]
    
    for _ in range(N-1):
        a,b = map(int,input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
        
    d = 0
    for st in range(N):
        dep = [-1 for _ in range(N)]
        dep[st] = 0
        q = deque([st])
        while q:
            now = q.popleft()
            for fol in edge[now]:
                if dep[fol] == -1:
                    dep[fol] = dep[now]+1
                    q.append(fol)
        d = max(d,max(dep))
        
    if d%3 == 1:
        print("Second")
    else:
        print("First")

if __name__ == "__main__":
    main()


### FIXED CODE ###

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

def main():
    N = int(input())
    if N == 1:
        print("First")
        exit()
    edge = [[] for _ in range(N)]
    
    for _ in range(N-1):
        a,b = map(int,input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
        
    dep = [-1 for _ in range(N)]
    dep[0] = 0
    q = deque([0])
    while q:
        now = q.popleft()
        for fol in edge[now]:
            if dep[fol] == -1:
                dep[fol] = dep[now]+1
                q.append(fol)
    
    st = dep.index(max(dep))
    dep = [-1 for _ in range(N)]
    dep[st] = 0
    q = deque([st])
    while q:
        now = q.popleft()
        for fol in edge[now]:
            if dep[fol] == -1:
                dep[fol] = dep[now]+1
                q.append(fol)
                
    if max(dep)%3 == 1:
        print("Second")
    else:
        print("First")

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

import numpy as np
import decimal
n = int(input())
a = list(map(int,input().split()))

a_n = np.array(a,dtype=np.dtype(decimal.Decimal))
#print(a_n)
#a_n.sort()
tmp = np.prod(a_n)

#result = int(np.prod(a_n))
#print(tmp)

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

### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int,input(). split ()))
    if 0 in A:
        print(0)
        return
    prod = 1
    for a in A:
        prod *= a
        if prod > 1000000000000000000:
            print(-1)
            return
    print(prod)
    
main()
### BUGGY CODE ###

n = int(input())
a = [0] * n
for i in range(n):
    a[i] = int(input())
for i in range(n):
    if i == 0:
        li_s=0
    else:
        li_s = max(a[:i])
    if i == n-1:
        li_g = 0
    else:
        li_g = max(a[i+1:])
    print(max(li_s,li_g))

### FIXED CODE ###

n = int(input())
a = [0] * n
for i in range(n):
    a[i] = int(input())
sorted_a = sorted(a, reverse=True)
max_a = sorted_a[0]
for i in range(n):
    if max_a != a[i]:
        print(max_a)
    else:
        print(sorted_a[1])
### BUGGY CODE ###

N=int(input())
X=list(map(int,input().split()))
for i in range(N):
    X_list=X[:i]+X[i+1:]
    X_list.sort()
    print(X_list[int(N/2-1)])

### FIXED CODE ###

N=int(input())
X=list(map(int,input().split()))
Y=X.copy()
Y.sort()
for i in range(N):
    if X[i]<Y[int(N/2)]:
        print(Y[int(N/2)])
    else:
        print(Y[int(N/2)-1])
### BUGGY CODE ###

s = input()
q = int(input())
t = 1
f = 0
for i in range(q):
    que = input().split()
    if que[0] == "1":
        s = s[::-1]
    else:
        if que[1] == "1":
            s = que[2]+s
        else:
            s = s+que[2]

print(s)


### FIXED CODE ###

s = input()
q = int(input())
t = 0
f = -1
x = ["",""]
for i in range(q):
    que = input().split()
    if que[0] == "1":
        t += 1
    else:
        x[(int(que[1])-1+t)%2] += que[2]

s = x[0][::-1] + s + x[1]
if t%2 == 1:
    s = s[::-1]

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

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

total_list = []
count = 0
for i in range(int(10e100)):
    for i in range(A):
        total_list.append("b")
        if len(total_list) <= N:
            count += 1
        else:
            break
    for i in range(B):
        total_list.append("r")
    if len(total_list) >= N:
        break

print(count)

### FIXED CODE ###

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

amari = N % (A + B)
sho = N // (A + B)

blue_num = 0

if amari < A:
    blue_num += A * sho + amari
else:
    blue_num += A * sho + A

print(blue_num)
### BUGGY CODE ###

n = int(input())
s = input()

cnt = 0
for i in range(1000):
	sec = str('%03d' % i)
	if sec[0] in s and sec[1] in s and sec[2] in s:
		nex = 0
		for j in range(n):
			if nex == 0 and s[j] == sec[0]:
				nex += 1
			elif nex == 1 and s[j] == sec[1]:
				nex += 1
			elif nex == 2 and s[j] == sec[2]:
				cnt += 1
				break
print(cnt)



### FIXED CODE ###

n = int(input())
s = input()

cnt = 0
for i in range(1000):
	sec = str('%03d' % i)
	if sec[0] in s and sec[1] in s and sec[2] in s:
		nex = 0
		for j in range(n):
			if nex == 0 and s[j] == sec[0]:
				nex += 1
			elif nex == 1 and s[j] == sec[1]:
				nex += 1
			elif nex == 2 and s[j] == sec[2]:
				cnt += 1
				break
print(cnt)
### BUGGY CODE ###

A,B,K = map(int,input().split())
while(K != 0):
    if A > 0:
        A -= 1
        K -= 1
    elif B > 0:
        B -= 1
        K -= 1

print(A,B)

### FIXED CODE ###

A,B,K = map(int,input().split())

A,K = A-K, K-A
if A < 0:
    A = 0  
elif K < 0:
    K = 0
    
B = B-K
if B < 0:
    B = 0
    
print(A,B)
### BUGGY CODE ###

from fractions import gcd
import sys
input = sys.stdin.readline


def lcm(a, b):
    return a * b / gcd(a, b)


MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))

l = 1
for a in A:
    l = lcm(l, a)

l %= MOD

ans = 0
for a in A:
    ans += l * pow(a, MOD-2, MOD)
    ans %= MOD

print(int(ans))


### FIXED CODE ###

from fractions import gcd

mod = 10 ** 9 + 7

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

lcm = 1
for s in A:
    lcm = s * lcm // gcd(lcm, s)

ans = lcm * sum([pow(s, mod - 2, mod) for s in A]) % mod

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

R,G,B,N=map(int,input().split())
count=0
for i in range(3001):
	for j in range (3001):
		if i*R+j*G<=N:
			tmp=N-(i*R+j*G)
			if tmp%B==0:
				count+=1
print(count)

### FIXED CODE ###

R,G,B,N=map(int,input().split())
count=0
for i in range(3001):
	for j in range (3001):
		if i*R+j*G<=N:
			tmp=N-(i*R+j*G)
			if tmp%B==0:
				count+=1
print(count)
### BUGGY CODE ###

import sys
input  = sys.stdin.readline

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

def process(N,W):
  box=[0]*(W+1)
  for i in range(N):
    w,v=map(int,input().split())
    for j in range(W,0,-1):
      idx = j-w
      if idx<0:
        break
      else:
        box[j] = max(box[j],box[idx]+v)
  return box[-1]

print(process(N,W))


### FIXED CODE ###

import sys
input  = sys.stdin.readline

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

def process(N,W):
  box=[0]*(W+1)
  for i in range(N):
    w,v=map(int,input().split())
    for j in range(W,0,-1):
      idx = j-w
      if idx<0:
        break
      else:
        box[j] = max(box[j],box[idx]+v)
  return box[-1]

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

n = int(input())
startlist=[]
for _ in range(n):
    startlist.append(input())
dictlist=sorted(startlist)
setlist=sorted(list(set(dictlist)))
countlist=[0]*(int(len(setlist)))
count=1
count2=1
for i in range(n):
    if i==n-1:
        countlist[i-count2+1]+=count
    elif dictlist[i+1]==dictlist[i]:
        count+=1
        count2+=1
    else:
        countlist[i-count2+1]+=count
        count=1
indexlist=[i for i,x in enumerate(countlist) if x==max(countlist)]
for j in tuple(sorted(indexlist)):
    print(setlist[j])

### FIXED CODE ###

n = int(input())
countmax=0
anslist=[]
dic={}
for i in range(n):
    a=input()
    if a in dic:
        dic[a]+=1
    else:
        dic[a]=1
    if dic[a]>countmax:
        countmax=dic[a]
for j in dic.keys():
    if dic[j]==countmax:
        anslist.append(j)
b=sorted(anslist)
for i in b:
    print(i)
### BUGGY CODE ###

from sys import exit

N = int(input())

u = []
v = []
w = []

for i in range(N - 1):
    _u, _v, _w = map(int, input().split())
    u.append(_u)
    v.append(_v)
    w.append(_w)

reached = []
distances = {}


def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


def search(x, distance):
    if x in reached:
        # 既に達しているところだったら
        return

    # 達したことを記録
    reached.append(x)
    distances[x] = distance

    for i in range(N - 1):
        if x == u[i]:
            search(v[i], distance + w[i])
        if x == v[i]:
            search(u[i], distance + w[i])


search(1, 0)

for i in range(N):
    if i == 0:
        print(0)
        continue
    if distances[i + 1] % 2 == 0:
        print(0)
    else:
        print(1)


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)

N = int(input())

q = {}

for i in range(N):
    q[i] = []

for _ in range(N - 1):
    _u, _v, _w = map(int, input().split())

    q[_u - 1].append((_v - 1, _w))
    q[_v - 1].append((_u - 1, _w))

ans = [None] * N
ans[0] = 0


def search(x, parent_num):
    for s in q[x]:
        if ans[s[0]] is None:
            ans[s[0]] = (parent_num + s[1]) % 2
            search(s[0], ans[s[0]])


search(0, 0)

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

import sys
input = sys.stdin.readline
n=int(input())
A=list(map(int,input().split()))
mod=10**9+7
from fractions import gcd

if n==1:
    print(1)
else:
    g=A[0]
    l=A[0]
    for i in range(n-1):
        g=gcd(l,A[i+1])
        l*=A[i+1]
        l//=g
    ans=0
    for i in range(n):
        ans+=(l//A[i])%mod
    print(ans%mod)

### FIXED CODE ###

import sys
input = sys.stdin.readline
from fractions import gcd
n=int(input())
A=list(map(int,input().split()))
mod=10**9+7
def gyaku(a):
    return pow(a,mod-2,mod)
if n==1:
    print(1)
else:
    gya=[0]*(n)
    g=A[0]
    l=A[0]
    gya[0]=gyaku(A[0])
    for i in range(n-1):
        g=gcd(l,A[i+1])
        l*=(A[i+1]//g)
        gya[i+1]=gyaku(A[i+1])
    ans=0
    for i in range(n):
        ans+=l*gya[i]
        ans%=mod
    print(ans)
### BUGGY CODE ###

def main():
	n = int(input())
	# b = int(input())
	a = list(map(int,input().split()))
	# A = [list(map(int, input().split())) for _ in range(n)]
	# print(a)
	ans = 0
	kijun=1
	for i in range(1,n+1):
		# print("i = {}".format(i))
		if i > len(a):
			break
		for s in range(n):
			# print("s = {}".format(s))
			if a[i-1]==kijun:
				kijun += 1
				break
			else:
				a.pop(i-1)
				ans += 1
				# print(a)
			# print(i,s)
		
	if ans == n:
		print(-1)
	else:
		print(ans)
	




if __name__ == '__main__':
	main()

### FIXED CODE ###

def main():
	n = int(input())
	# b = int(input())
	a = list(map(int,input().split()))
	# A = [list(map(int, input().split())) for _ in range(n)]
	# print(a)
	ans = 0
	kijun=1
	check = 0

	while check < n:
		# print("check = {}".format(check))
		# print("kijun = {}".format(kijun))
		if a[check] == kijun:
			check += 1
			kijun += 1
			# print("true")
		else:
			check += 1
			ans += 1
		# 	print("false")
		# print("-----")



	# for i in range(1,n+1):
	# 	# print("i = {}".format(i))
	# 	if a[i-1]==kijun:
	# 		kijun += 1
	# 		continue
	# 	else:
	# 		ans += 1
		
	if ans == n:
		print(-1)
	else:
		print(ans)
	




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

from functools import reduce
import operator
import heapq
def SME(start,end):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if not ANS[idx]:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if not ANS[i] : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if not ANS[i] : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS
 
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
parameter = 0.991
INIT = None
ANS = [INIT]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

n = int(input())
s = list(input())
if len(set(s)) == 1:
  print(0)
  exit()
i = 0
while True:
    wi = s.index("W")
    ri = "".join(s).rindex("R")
    if wi < ri:
        s[wi], s[ri] = s[ri], s[wi]
        i += 1
    else: break
print(i)


### FIXED CODE ###

n = int(input())
s = input()
w = []
r = []
for i in range(len(s)):
    if s[i] == "W": w.append(i+1)
    if s[len(s)-i-1] == "R": r.append(len(s)-i)
cnt = 0
# print(w,r)
for i in range(min(len(w), len(r))):
    if w[i] >  r[i]:
        break
    else:
        cnt += 1
print(cnt)

"""
i = 0
while True:
    wi = s.index("W")
    ri = str(s).rindex("R")
    if wi < ri:
        s[wi], s[ri] = s[ri], s[wi]
        i += 1
    else: break
print(cnt)
"""
### BUGGY CODE ###

#coding:utf-8
n,m = map(int,input().split())
List = list(map(int,input().split()))


forest = [i for i in range(n+1)]
rank = [0 for i in range(n+1)]

def unite(x,y):
    while forest[x] != x:
        x = forest[x]
    a = rank[x]
    
    while forest[y] != y:
        y = forest[y]
    b = rank[y]
    
    if a <= b:
        if a == b:
            rank[x] += 1
        forest[y] = x
    else:
        forest[x] = y


def Find(x):
    Q = []
    while forest[x] != x:
        x = forest[x]
        Q.append(x)
    
    for xi in Q:
        forest[xi] = x
        rank[xi] = 1

    return x

    
cnt = 0
for i in range(m):
    x,y = map(int,input().split())
    unite(x,y)

for i in range(1,n+1):
    x = Find(i)
    y = Find(List[i-1])
    if x == y:
        cnt += 1
print(cnt)
    


### FIXED CODE ###

#coding:utf-8

n,m = map(int,input().split())
List = list(map(int,input().split()))

class UnionFind3:
    def __init__(self, size):
        # 負の値はルート (集合の代表) で集合の個数
        # 正の値は次の要素を表す
        self.table = [-1 for i in range(size)]

    # 集合の代表を求める
    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    # 併合
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                # 小さいほうが個数が多い
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return 1
        return 0


cnt = 0
tree = UnionFind3(n)
for i in range(m):
    x,y = map(int,input().split())
    tree.union(x-1,y-1)

for i in range(n):
    a = tree.find(i)
    b = tree.find(List[i]-1)
    if a == b:
        cnt += 1

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

N,M = map(int, raw_input().split())
ab = [[0 for i in range(2)] for j in range(N)]
for i in range(N):
    ab[i][0], ab[i][1] = map(int, raw_input().split())
AB = sorted(ab, key=lambda x:x[0])
count = 0
total = 0
for i in range(N):
    for j in range(AB[i][1]):
        if count < M:
            total += AB[i][0]
            count += 1
            if count > M:
                exit()

print total

### FIXED CODE ###

N,M = map(int, raw_input().split())
ab = [[0 for i in range(2)] for j in range(N)]
for i in range(N):
    ab[i][0], ab[i][1] = map(int, raw_input().split())
AB = sorted(ab, key=lambda x:x[0])
count = 0
total = 0
for AB_ in AB:
    num = min(M, AB_[1])
    total += AB_[0]*num
    M -= num
print total