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

n, x = [int(i) for i in input().split()]
S = [int(i) for i in input().split()]
DP = [[0] * (x + 1) for i in range(n + 1)]
DP[0][x] = 1
p = 10 ** 9 + 7
S.sort(reverse=True)

for i in range(n):
    for j in range(x + 1):
        if i != n - 1:
            DP[i + 1][j] += DP[i][j] * (n - i - 1)
        DP[i + 1][j % S[i]] += DP[i][j]

print(sum(i * d % p for i, d in enumerate(DP[n])) % p)

### FIXED CODE ###

n, x = [int(i) for i in input().split()]
S = [int(i) for i in input().split()]
DP = [[0] * (x + 1) for i in range(n + 1)]
DP[0][x] = 1
p = 10 ** 9 + 7
S.sort(reverse=True)

for i in range(n):
    for j in range(x + 1):
        DP[i][j] %= p
        if i != n - 1:
            DP[i + 1][j] += DP[i][j] * (n - i - 1)
        DP[i + 1][j % S[i]] += DP[i][j]

print(sum(i * d % p for i, d in enumerate(DP[n])) % p)
### BUGGY CODE ###

from itertools import product
def f(A, B, k):
    S = [a+b for a, b in product(A, B)]
    S.sort(reverse = True)
    return S[:k]
x, y, z, k = map(int, input().split())
*A, = map(int, input().split())
*B, = map(int, input().split())
*C, = map(int, input().split())
S = f(f(A, B, k), C, k)
for s in S: print(s)

### FIXED CODE ###

from itertools import product
def f(A, B, k):
    S = [a+b for a, b in product(A, B)]
    S.sort(reverse = True)
    return S[:k]
x, y, z, k = map(int, input().split())
*A, = map(int, input().split())
*B, = map(int, input().split())
*C, = map(int, input().split())
S = f(f(A, B, k), C, k)
for s in S: print(s)
### BUGGY CODE ###

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

if 0 in A:
    print(0)
else:
    x = 1
    for i in range(N):
        x = x * A[i]
        if x>10**18:
            x = -1
    print(x)

### FIXED CODE ###

import sys

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

if 0 in A:
    print(0)
else:
    x = 1
    for i in range(N):
        x = x * A[i]
        if x>10**18:
            print(-1)
            sys.exit()
        
    print(x)
### BUGGY CODE ###

N = int(input())
for i in range(1, N+1):
  if int(i**0.5)**2 == i:
    ans = i
print(ans)

### FIXED CODE ###

N = int(input())
for i in range(N,0, -1):
  if int(i**0.5)**2 == i:
    print(i)
    break
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
p=1
for i in l:
    p*=i
if(p>1000000000000000000):
    print(-1)
else:
    print(p)
1000000000000000000

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
p=1
l.sort()
for i in l:
    p*=i
    if(p==0):
        print(0)
        exit()
    if(p>10**18):
        print(-1)
        exit()
print(p)
### BUGGY CODE ###

# B

inputs = input().split(' ')

d = inputs[0:2]
takahashi = {'Name': 'Takahashi', 'Hp': int(d[0]), 'Power': int(d[1])}
d = inputs[2:4]
aoki = {'Name': 'Aoki', 'Hp': int(d[0]), 'Power': int(d[1])}

players = [aoki, takahashi]
N =len(players)

loop = True
while True:
    for i in range(N):
        players[i-1]['Hp'] -= players[i]['Power']
        if players[i-1]['Hp'] <= 0:
            if players[i]['Name'] == 'Takahashi':
                print('Yes')
            else:
                print('No')
            loop = False
            break

### FIXED CODE ###

# B

inputs = input().split(' ')

d = inputs[0:2]
takahashi = {'Name': 'Takahashi', 'Hp': int(d[0]), 'Power': int(d[1])}
d = inputs[2:4]
aoki = {'Name': 'Aoki', 'Hp': int(d[0]), 'Power': int(d[1])}

players = [takahashi, aoki]

def compute(players):
    N =len(players)
    while True:
        for i in range(N):
            players[i-1]['Hp'] -= players[i]['Power']
            if players[i-1]['Hp'] <= 0:
                if players[i]['Name'] == 'Takahashi':
                    print('Yes')
                else:
                    print('No')
                return 

compute(players)
### BUGGY CODE ###

n = int(input())
card = []
for i in range(n):
    num = int(input())
    if num in card:
        card.remove(num)
    else:
        card.append(num)
print(len(card))

### FIXED CODE ###

n = int(input())
card = set()

for i in range(n):
    num = int(input())
    if num in card:
        card.remove(num)
    else:
        card.add(num)
print(len(card))
### BUGGY CODE ###

n= input()
ans=0
for i in range(len(n)):
    for s in range(i+3,len(n)):
        if int(n[i:s+1])%2019 ==0:
            
            ans=ans+1
print(ans)

### FIXED CODE ###

s= input()[::-1]
mods= [0] * 2019
mods[0] = 1
num=0
d = 1
for c in s:
    num += int(c) * d
    num %= 2019
    d *= 10
    d %= 2019
    mods[num] += 1

ans = 0
for cnt in mods:
    ans += cnt * (cnt - 1) // 2

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

import numpy as np

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

coef_mat = np.matrix([[1 if (i == j or i + 1 == j or (i + 1 == N and j == 0)) else 0 for j in range(N) ] for i in range(N)])**(-1)
vec = np.matrix([A]).T
res = coef_mat @ vec

for i in range(N):
    print(int(res[i, 0]) * 2)

### FIXED CODE ###

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

s = sum([A[i] * (-1) ** i for i in range(N)])

for i in range(1, N + 1):
    print(s)
    s = 2 * A[i - 1] - s
### BUGGY CODE ###

if __name__ == '__main__':
    k = int(input())

    if k % 2 == 0 or k % 2 == 5:
        print('-1')
    else:
        num = '7'
        count = 1
        while not int(num) % k == 0:
            count += 1
            num += '7'
        print(len(num))



### FIXED CODE ###

if __name__ == '__main__':
    k = int(input())

    if k % 2 == 0 or k % 5 == 0:
        print('-1')
    else:
        mod_list = [7 % k]
        if mod_list[-1] == 0:
            print(1)
        else:
            for i in range(1000000):
                mod_list.append((mod_list[0] + mod_list[-1] * 10) % k)
                if mod_list[-1] == 0:
                    break
            print(len(mod_list))
### BUGGY CODE ###

a,b = map(float, input().split())

multi = a*b
i=0

while True:
    if i<=multi and multi<i+1:
        break
    i=i+1

print(i)


### FIXED CODE ###

from decimal import Decimal

a,b = input().split()
b = b.replace(".","")
c = int(a)*int(b)//100

print(c)
### BUGGY CODE ###

'''
.append(要素) リストに要素を追加 
.extend(リスト) リストを連結する
.insert(場所,要素) 指定した場所に要素追加
del 配列名[場所]
-1で末尾で末尾から一つ前

sort()
sorted(reverse=true)

配列の初期化
配列名=[a]*n+[b]*m

Decimal()
'''

from sys import stdin
from itertools import accumulate, dropwhile, takewhile, groupby
import bisect
import copy
import math
import itertools
from functools import reduce
from operator import mul

f = [int(s) for s in stdin.readline().rstrip().split()]
N = f[0]
K = f[1]
p = list(map(lambda x: 1/2+x/2, [int(s)
                                 for s in stdin.readline().rstrip().split()]))
past = -2000
resNum = -2000
for el in range(N - K + 1):
    data = copy.copy(p)
    tar = sum(data[el: el + K])
    if past < tar:
        past = tar
        resNum = el
print(past)


### FIXED CODE ###

'''
.append(要素) リストに要素を追加 
.extend(リスト) リストを連結する
.insert(場所,要素) 指定した場所に要素追加
del 配列名[場所]
-1で末尾で末尾から一つ前

sort()
sorted(reverse=true)

配列の初期化
配列名=[a]*n+[b]*m

Decimal()
'''

from sys import stdin
from itertools import accumulate, dropwhile, takewhile, groupby
import bisect
import copy
import math
import itertools
from functools import reduce
from operator import mul

f = [int(s) for s in stdin.readline().rstrip().split()]
N = f[0]
K = f[1]
p = list(map(lambda x: 1/2+x/2, [int(s)
                                 for s in stdin.readline().rstrip().split()]))
E = []
tmp = 0
for el in p:
    tmp += el
    E.append(tmp)
past = E[K - 1]
for el in range(len(E)):
    if el - K < 0:
        continue
    e = E[el] - E[el - K]
    if past < e:
        past = e
print(past)
### BUGGY CODE ###

N, M = map(int, input().split())
S = str(input())
T = str(input())
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def lcm(x, y):
    return (x * y) // gcd(x, y)
X = lcm(N ,M)

if S[0] != T[0]:
    print(-1)
elif X == N*M:
    print(N*M)
else:
    for i in range(1,(N*M//X)+1):
        L = X * i
        match = lcm(  L // N,  L // M)
        for j in range(1, (L // match) ):
            if S[j * N * match // L] != T[ j * M * match // L]:
                L = -1
                break
        if L == X * i:
            break
    print(L)





### FIXED CODE ###

N, M = map(int, input().split())
S = str(input())
T = str(input())
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
 
def lcm(x, y):
    return (x * y) // gcd(x, y)
X = lcm(N ,M)
 
if S[0] != T[0]:
    print(-1)
elif X == N*M:
    print(N*M)
else:
        L = X
        match = lcm(  L // N,  L // M)
        for j in range(1, (L // match) ):
            if S[j * N * match // L] != T[ j * M * match // L]:
                L = -1
                break
        if L == X :
            print(L)
        else:
            print(-1)
### BUGGY CODE ###

import sys
#DEBUG=True
DEBUG=False
if DEBUG:
    f=open("202006_5th/D_input.txt")
else:
    f=sys.stdin
ans=1
n=int(f.readline().strip())
prime=[]
# Start from where n is equal to 2
for _ in range(1,n):
    number_of_multiply = []
    num_of_divisor=1
    tmp=_+1
    for __ in prime:
        cnt=0
        if tmp<=1:
            break
        while (tmp%__)==0:
            cnt+=1;tmp=int(tmp/__);
        if cnt>0:
            num_of_divisor*=cnt+1
    if num_of_divisor==1:
        prime.append(_+1)
        ans+=(_+1)*2
    else:
        ans+=(_+1)*num_of_divisor
print(ans)

### FIXED CODE ###

import sys
#DEBUG=True
DEBUG=False
if DEBUG:
    f=open("202006_5th/D_input.txt")
else:
    f=sys.stdin
ans_sum=0
n=int(f.readline().strip())
for _ in range(1,n+1):
    num=n//_
    ans_sum+=_*((num*(num+1))//2)
print(ans_sum)
### BUGGY CODE ###

S= input()
print(sum([S[:i].count('B') for i in range(len(S)) if S[i]=='W']))

### FIXED CODE ###

S= input()
b = 0
ans = 0
for i in S:
  if i =='W':
    ans+=b
  else:
    b+=1
print(ans)
### BUGGY CODE ###

#!python3

iim = lambda: map(int, input().rstrip().split())

from bisect import bisect

def resolve():
    def find(i):
        x = S[i]
        while True:
            k = S[i][0]
            if k == i:
                x[0] = i
                return i
            S[i] = x
            i = k
    def join(i, j):
        ai = find(i)
        aj = find(j)
        if ai != aj:
            #S[aj][0] = S[ai][0]
            S[aj] = S[ai]
    def same(i, j):
        ai = find(i)
        aj = find(j)
        return ai == aj

    N, M, K = iim()
    S = [[i] for i in range(N+1)]
    mk = [set() for i in range(N+1)]
    for i in range(M):
        ai, bi = iim()
        if ai > bi:
            ai, bi = bi, ai
        join(ai, bi)
        mk[ai].add(bi)
    for i in range(K):
        ai, bi = iim()
        if ai > bi:
            ai, bi = bi, ai
        mk[ai].add(bi)

    ans = [0] * (N+1)
    #print(S)
    S1 = [[] for i in range(N+1)]
    for i in range(1, N+1):
        ai = find(i)
        S1[ai].append(i)

    for ss in S1:
        ls = len(ss)
        for i in range(ls-1):
            ai = ss[i]
            mki = mk[ai]
            for j in range(i+1, ls):
                aj = ss[j]
                if aj in mki:
                    continue
                if same(ai, aj):
                    ans[ai] += 1
                    ans[aj] += 1
    print(*ans[1:])


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

iim = lambda: map(int, input().rstrip().split())

from bisect import bisect

def resolve():
    def find(i):
        x = S[i]
        if x < 0:
            return i
        S[i] = find(x)
        return S[i]

    def join(i, j):
        ai = find(i)
        aj = find(j)
        diff = ai - aj
        #print("j", ai, aj)
        if diff == 0:
            return
        elif diff > 0:
            ai, aj = aj, ai
        S[ai] += S[aj]
        S[aj] = ai
    def same(i, j):
        ai = find(i)
        aj = find(j)
        return ai == aj
    def size(i):
        return -S[find(i)]

    N, M, K = iim()
    S = [-1] * N
    T = [1] * N
    for i in range(M):
        ai, bi = iim()
        ai -= 1; bi -= 1
        join(ai, bi)
        T[ai] += 1
        T[bi] += 1
        #print(ai, bi, S)

    U = [set() for i in range(N)]
    for i in range(K):
        ai, bi = iim()
        ai -= 1; bi -= 1
        U[ai].add(bi)
        U[bi].add(ai)
    #print(S)
    #print(T)

    ans = [size(i) - T[i] - sum(same(i, j) for j in U[i]) for i in range(N)]
    print(*ans)


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

n,k=map(int, input().split())
a= list(map(int, input().split()))
l=[]
for i in range(len(a)):
  l.append((a[i]+1)/2)
maxans=0
for i in range(len(l)):
  ans=sum(l[i:i+k])
  maxans=max(ans,maxans)
print(maxans)
  

### FIXED CODE ###

n,k=map(int, input().split())
a= list(map(int, input().split()))
l=[]
for i in range(len(a)):
  l.append((a[i]+1)/2)
maxans=sum(l[0:k])
ans=sum(l[0:k])
for i in range(len(l)-k):
  ans=ans+l[i+k]-l[i]
  maxans=max(ans,maxans)
 
print(maxans)
### BUGGY CODE ###

xs,ys,xt,yt=map(int,input().split())
N=int(input())
XYR=[[xs,ys,0]]+[list(map(int,input().split())) for i in range(N)]+[[xt,yt,0]]
inf=10**20
c=[[None]*(N+2) for i in range(N+2)]
for i in range(N+2):
    for j in range(N+2):
        c[i][j]=max(0,((XYR[i][0]-XYR[j][0])**2+(XYR[i][1]-XYR[j][1])**2)**.5-XYR[i][2]-XYR[j][2])
from heapq import heappop,heappush
def dij(c,N,s):
    d=[inf]*N
    d[s]=0
    q=[]
    heappush(q,(0,s))
    while q:
        i=heappop(q)[1]
        for j,w in enumerate(c[i]):
            temp=d[i]+w
            if d[j]>temp:
                d[j]=temp
                heappush(q,(d[j],j))
    return d
print(dij(c,N+2,0)[-1])

### FIXED CODE ###

xs,ys,xt,yt=map(int,input().split())
N=int(input())
import numpy as np
XYR=np.empty((N+2,3),dtype=np.float64)
XYR[1:-1,:]=np.array([input().split() for i in range(N)])
XYR[0,:]=xs,ys,0
XYR[-1,:]=xt,yt,0
X,Y,R=XYR.T
c=np.maximum(0,np.sqrt(np.square(X[None,:]-X[:,None])+np.square(Y[None,:]-Y[:,None]))-R[None,:]-R[:,None])
c[range(N+2),range(N+2)]=-1
from scipy.sparse import*
g=csgraph.csgraph_from_dense(c,null_value=-1)
print(csgraph.dijkstra(g,indices=0)[-1])
### BUGGY CODE ###

Q=input()
S="B"+input()+"B"
Q_num = Q.split(" ")[1]
query = []
for q in range(int(Q_num)):
  query.append(input().split(" "))
  
#下のforを上に統合可
for q in query:
  print(len(S[int(q[0]):(int(q[1])+1)].split("AC"))-1)


### FIXED CODE ###

Q=input()
S=input()
N,Q_num = int(Q.split(" ")[0]),int(Q.split(" ")[1])
AC=[0]
count = 0
for i in range(N-1):
  if S[i]=="A" and S[i+1]=="C":
    count = 1+count
  AC.append(count)
for q in range(int(Q_num)):
  qu = input().split(" ")
  print(AC[int(qu[1])-1]-AC[int(qu[0])-1])
### BUGGY CODE ###

def main():
    N, M = map(int, input().split())
    connect_list = [0] * N

    max_road_num = 0
    for i in range(M):
        A, B = map(int, input().split())
        A = A - 1
        B = B - 1
        
        A_road_num = connect_list[A]
        B_road_num = connect_list[B]

        if A_road_num == 0 and B_road_num == 0:
            max_road_num = max_road_num + 1
            connect_list[A] = max_road_num
            connect_list[B] = max_road_num
        elif A_road_num != 0 and B_road_num == 0:
            connect_list[B] = connect_list[A]
        elif A_road_num == 0 and B_road_num != 0:
            connect_list[A] = connect_list[B]
        else:
            connect_list = [A_road_num if B_road_num == road_num else road_num for road_num in connect_list]

    answer = 0
    set_connect_list = set([i for i in connect_list if i > 0])
    if len(set_connect_list) != 1:
        answer = len(set_connect_list) - 1

    print(answer + connect_list.count(0))

if __name__ == "__main__":
    main()

### FIXED CODE ###

def root(list_parent, x):
    if(list_parent[x] == x):
        return x
    else:
        list_parent[x] = root(list_parent, list_parent[x])
        return list_parent[x]

def unite(list_parent, x, y):
    x = root(list_parent, x)
    y = root(list_parent, y)

    if(x == y):
        return list_parent

    if x > y:
        list_parent[y] = x
    else:
        list_parent[x] = y

    return list_parent

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

    list_parent = []
    for i in range(N):
        list_parent.append(i)

    for i in range(M):
        A, B = map(int, input().split())
        list_parent = unite(list_parent, A-1, B-1)

    set_root = set()
    for i in list_parent:
        root_i = root(list_parent, i)
        if root_i not in set_root:
            set_root.add(root_i)

    print(len(set_root) - 1)

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

import sys
from collections import defaultdict
input = sys.stdin.readline
 
def main():
    n = int(input())
    a = list(map(int, input().split()))
    dic = defaultdict(int)
    a.sort()
    ans = 0
    for i in range(n):
        if i < n-1 and a[i] == a[i+1]:
            dic[a[i]] = 1
            continue
        flag = 1
        for e in dic:
            if a[i]%e == 0:
                flag = 0
                break
        if flag:
            ans += 1
        dic[a[i]] = 1
    print(ans)
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
 
def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    ans = 0
    N = max(a)+1
    tab = [1 for _ in range(N)]
    for i in range(n):
        x = a[i]
        if i < n-1 and a[i] == a[i+1]:
            tab[a[i]] = 0
        if tab[x]:
            ans += 1
        for i in range(N):
            if x*i >= N:
                break
            tab[x*i] = 0        
    print(ans)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

s = input()
length = 0
maxLength = 0
for i in range(len(s)):
    if s[i] != "A":
        continue
    for j in range(i+1, len(s)):
        if s[j] != "Z":
            continue
        length = abs(j+1 - i)
        if maxLength < length:
            maxLength = length
print(maxLength)


### FIXED CODE ###

s = input()
print(s.rfind('Z') + 1 - s.find('A'))
### BUGGY CODE ###

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

length = []
cnt = 0
now = "#"

for i in S:
  if now == i:
    cnt += 1
  else:
    if now == "#":
      now = "."
    else:
      now = "#"
    length.append(cnt)
    cnt = 1
else:
  length.append(cnt)
  
if len(length) % 2 == 0:
    pass
else:
    length.append(0)
  
ans = 0
for i,v in enumerate(length[0::2]):
    ans += min(v,length[1::2][i])

print(ans)  

### FIXED CODE ###

N = int(input())
S = input()
 
cumsum_b = [0] * (N+1)
 
for i in range(N):#累積和
  if S[i] == "#":
    cumsum_b[i+1] = cumsum_b[i] + 1
  else:
    cumsum_b[i+1] = cumsum_b[i]

ans = N
tmp = 0
for i in range(N+1):#境界を全探索
  tmp = cumsum_b[i] + ((N-i) - (cumsum_b[-1] - cumsum_b[i]))
  ans = min(ans,tmp)
else:
  print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
li_p = list(map(int, input().split()))
def kitaichi(a):
  b = 0
  for i in range(1, a+1):
    b += i
  return b/a
li_s = []
for x in li_p:
  li_s.append(kitaichi(x))
ans = []
d = 0
for i in range(k):
  d += li_s[i]
  ans.append(d)
for j in range(k, n):
  d += li_s[j]
  d -= li_s[j-k]
  ans.append(d)
print(max(ans))

### FIXED CODE ###

n, k = map(int, input().split())
li_p = list(map(int, input().split()))
def kitaichi(a):
  b = 0
  for i in range(1, a+1):
    b += i
  return b/a
li_s = []
for x in li_p:
  li_s.append(kitaichi(x))
ans = []
d = 0
for i in range(k):
  d += li_s[i]
  ans.append(d)
for j in range(k, n):
  d += li_s[j]
  d -= li_s[j-k]
  ans.append(d)
print(max(ans))
### BUGGY CODE ###

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

dist = []
for i in range(N-K+1):
    a = 0
    tmp = x[i:i+K]
    mini, maxi = tmp[0], tmp[-1]
    if (mini >= 0 and maxi >= 0):
        a = maxi
    elif (mini < 0 and maxi < 0):
        a = abs(mini)
    if mini < 0 and maxi >= 0:
        a = abs(mini) + maxi + min(abs(mini), maxi)
    dist.append(a)

print(min(dist))

### FIXED CODE ###

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

dist = []
for i in range(N-K+1): 
    l, r = x[i], x[i+K-1]
    t = min(abs(l)+abs(l-r), abs(r)+abs(r-l))
    dist.append(t)

print(min(dist))
### BUGGY CODE ###

H, W, D = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
x = [0]*(H*W+1)
y = [0]*(H*W+1)
for k in range(W):
    for l in range(H):
        x[A[l][k]] = k+1
        y[A[l][k]] = l+1

for _ in range(int(input())):
    L, R = map(int,input().split())
    ans = 0
    while L < R:
        ans += abs(x[L]-x[L+D])+abs(y[L]-y[L+D])
        L += D
    print(ans)


### FIXED CODE ###

H, W, D = map(int,input().split())
px = [0 for k in range(H*W+D+1)]
py = [0 for k in range(H*W+D+1)]
S = [list(map(int,input().split())) for k in range(H)]

for j in range(W):
    for i in range(H):
        px[S[i][j]] = i
        py[S[i][j]] = j

d = [0 for k in range(H*W+D+1)]
for k in range(H*W,0,-1):
    d[k] = d[k+D] + abs(px[k]-px[k+D]) + abs(py[k]-py[k+D])

Q = int(input())
for k in range(Q):
    L, R = map(int,input().split())
    print(d[L]-d[R])
### BUGGY CODE ###

import numpy as np
N, M = map(int,input().split())
A = np.zeros(N+1)
for i in range(M):
    L,R = map(int,input().split())
    A[L:R+1] += 1
print(sum([1 for a in A if a == M]))

### FIXED CODE ###

N, M = map(int,input().split())
Ls,Rs = [],[]
for i in range(M):
    L,R = map(int,input().split())
    Ls.append(L)
    Rs.append(R)

print(max(0,min(Rs)-max(Ls)+1))
### BUGGY CODE ###

n = int(input())
goods = []

for _ in range(n):
  s = input()
  if s not in goods:
    goods.append(s)
    
print(len(goods))

### FIXED CODE ###

n = int(input())
goods = set(input() for _ in range(n))
print(len(goods))
### BUGGY CODE ###

import itertools
n, ma, mb = map(int, input().split(" "))
info_med = []
for _ in range(n):
  info_med.append(list(map(int, input().split(" "))))

min_cost = 10000
for num_med in range(1, n + 1):
  list_med = [i for i in range(n)]
  list_select = itertools.combinations(list_med, num_med)
  for one_select in list_select:
    sum_ma = sum([info_med[one_med][0] for one_med in one_select])
    sum_mb = sum([info_med[one_med][1] for one_med in one_select])
    if sum_ma / sum_mb == ma / mb:
      sum_c = sum([info_med[one_med][2] for one_med in one_select])
      if sum_c < min_cost:
        min_cost = sum_c

if min_cost == 10000:
  print(-1)
else:
  print(min_cost)

### FIXED CODE ###

n, ma, mb = map(int, input().split(" "))
info_med = []
for _ in range(n):
  info_med.append(list(map(int, input().split(" "))))
info_med.sort(key=lambda x: x[2])
dp = []
dp.append([(0, 0, [-1])])

for min_c in range(1, n * 100 + 1):
  temp_list = []
  for i, (a, b, c) in enumerate(info_med):
    if min_c - c >= 0:
      for pre_a, pre_b, pre_i in dp[min_c - c]:
        if pre_i[-1] < i:
          if (a + pre_a) * mb == (b + pre_b) * ma:
            print(min_c)
            exit()
          temp_list.append((a + pre_a, b + pre_b, pre_i + [i]))
  dp.append(temp_list)
print("-1")
### BUGGY CODE ###

N, M = map(int, input().split())
AB = []
for i in range(N):
    AB.append(list(map(int, input().split())))
    
AB.sort(key=lambda x:x[0])

kane = 0
hon = 0
for i in range(N):
    for j in range(AB[i][1]):
        hon += 1
        kane += AB[i][0]
        if hon == M:
            print(kane)
            break

### FIXED CODE ###

N, M = map(int, input().split())
AB = []
for i in range(N):
    AB.append(list(map(int, input().split())))
    
AB.sort(key=lambda x:x[0])

kane = 0
hon = 0
for i in range(N):
    if hon + AB[i][1] < M:
        hon += AB[i][1]
        kane += AB[i][0] * AB[i][1]
        continue
    elif hon + AB[i][1] == M:
        hon += AB[i][1]
        kane += AB[i][0] * AB[i][1]
        print(kane)
        break
    else:
        kane += (M - hon) * AB[i][0]
        print(kane)
        break