Problem:


Score : 300 points

Problem Statement

Hearing that energy drinks increase rating in those sites, Takahashi decides to buy up M cans of energy drinks.

There are N stores that sell energy drinks. In the i-th store, he can buy at most B_i cans of energy drinks for A_i yen (the currency of Japan) each.

What is the minimum amount of money with which he can buy M cans of energy drinks?

It is guaranteed that, in the given inputs, a sufficient amount of money can always buy M cans of energy drinks.

Constraints

All values in input are integers.

1 \leq N, M \leq 10^5

1 \leq A_i \leq 10^9

1 \leq B_i \leq 10^5

B_1 + ... + B_N \geq M

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Print the minimum amount of money with which Takahashi can buy M cans of energy drinks.

Sample Input 1

2 5
4 9
2 4

Sample Output 1

12

With 12 yen, we can buy one drink at the first store and four drinks at the second store, for the total of five drinks. However, we cannot buy 5 drinks with 11 yen or less.

Sample Input 2

4 30
6 18
2 5
3 10
7 9

Sample Output 2

130

Sample Input 3

1 100000
1000000000 100000

Sample Output 3

100000000000000

The output may not fit into a 32-bit integer type.



Sample input:
2 5
4 9
2 4


Sample output:
12

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a = []
b = []
ans = 0
for i in range(n):
    tempa,tempb = map(int,input().split())
    a.append(tempa)
    b.append(tempb)
test = dict(zip(a,b))
test = sorted(test.items())

# test_item = test.values()
# test_key = test.keys()
# print(test_item)
# print(test_key)
# for i in range(n):
#     if m-test[i][1] >=0:

i=0
while m>0:
    if m-test[i][1] >=0:
        ans += test[i][0]*test[i][1]
        m -=test[i][1]
        i += 1
    else:
        ans += test[i][0]*m
        m=0
        print(ans)
        exit()
print(ans)

Submission status: Runtime Error

Solution code:
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

a, b = map(int, input().split())
d = defaultdict(int)
array = []
for i in range(a):
    x, y = map(int, input().split())
    d[x] = y
    array.append(x)
array.sort()


count = 0
for i in array:
        break
    if b <= d[i]:
        count += min(b, 0) * i
        break
    else:
        t = d[i]
        b -= t
        count += t * i
print(count)

Submission status: Runtime Error

Solution code:
import numpy as np

n,m = list(map(int,input().split()))
stc = np.zeros([n,2])

for i in range(n):
    ta, tb = list(map(int,input().split()))
    stc[i,0] = ta
    stc[i,1] = tb

bud = 0
nb = stc[stc[:,1].argsort(),:]
while m > 0:
    if m  > = nb[i,1]:
        bud += nb[i,0]*nb[i,1]
        m -= nb[i,1]
    else:
        bud += nb[i,0]*m
        m = 0

print(bud)

Submission status: Runtime Error

Solution code:
N,M = list(map(int,input().split()))
d = {}
for i in range(N):
	k,l = list(map(int,input().split()))
	d[k] = l

e = sorted(d.items(),key = lambda x: x[0])

a= 0
ans = 0
for i in range(N):
	a += e[i][1]
	if M > a:
		ans += e[i][0]*e[i][1]
	else:
		ans += e[i][0]*(e[i][1]-a+M)
		break

print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a = []
b = []
ans = 0
for i in range(n):
    tempa,tempb = map(int,input().split())
    a.append(tempa)
    b.append(tempb)
test = dict(zip(a,b))
test = sorted(test.items())
print(test)
# test_item = test.values()
# test_key = test.keys()
# print(test_item)
# print(test_key)
# for i in range(n):
#     if m-test[i][1] >=0:

i=0
while m>0:
    if m-test[i][1] >=0:
        ans += test[i][0]*test[i][1]
        m -=test[i][1]
        i += 1
    else:
        ans += test[i][0]*m
        m=0
        print(ans)
        exit()
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

N, M = map(int, input().split())
AB = []
for i in range(N):
    AB.append(list(map(int, input().split())))
    
AB = np.array(AB)
AB_sorted = AB[AB[:,0].argsort(),:]

cs = np.cumsum(AB_sorted[:,1])
n_full_store = (cs <= M).sum()
money_a = np.sum(AB_sorted[:n_full_store,0] * AB_sorted[:n_full_store,1])
money_b = (M - cs[n_full_store-1]) * AB_sorted[n_full_store,0]
print(money_a + money_b)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
L=[]

ans=0

for i in range(N):
    a,b=map(int,input().split())

    L.append([a,b])

L= sorted(L)



for i in range(N):

    if M < L[i][1]
        ans=L[i][0]*M

        print(ans)
        exit()
        
    else:


        ans = L[i][0]*L[i][1]
        M -= L[i][1]


            if M==0:

                print(ans)
                exit()


            if M <= L[i+1][1]:

                ans += M * L[i+1][0]

                print(ans)

                exit()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A_B = []
for i in range(N):
    A_B.append([int(x) for x in input().split()])

money = 0
count = 0
while count < M:
    min_ = 1000000
    index = None
    for i in range(len(A_B)):
        if A_B[i][0] < min_:
            min_ = A_B[i][0]
            index = i
    if count+A_B[index][1] <= M:
        count += A_B[index][1]
        money += A_B[index][1] * A_B[index][0]
    else:
        money += A_B[index][0] * (M-count)
        count = M
    A_B.pop(index)
print(money)

Submission status: Runtime Error

Solution code:
N,M = list(map(int, input().split()))
AB = []
for i in range(N):
    AB.append(list(map(int, input().split())))
AB = sorted(AB)

n = 0
result = 0

while True:
    if AB[n][1] <= M:
        result += AB[n][0] * AB[n][1]
        M -= AB[n][1]
        n += 1
    else:
        result += AB[n][0] * M
        break

print(result)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
A = [0] * N
B = [0] * N
C = [[0,0] for i in range(N)]
check = 0
money = 0
a = 0
k = 0

for i in range(N):

    A[i],B[i] = map(int,input().split())
    C[i] = [A[i],B[i]]

C.sort()

while a == 0:

    if check + C[k][1] <= M:

        check += C[k][1]
        money += C[k][0]*C[k][1]
        k += 1

    else:

        money += C[k][0] * (M-check)
        a += 1

print(money)

Submission status: Runtime Error

Solution code:
import numpy as np

n,m = list(map(int,input().split()))
stc = np.zeros([n,2])

for i in range(n):
  ta, tb = list(map(int,input().split()))
  stc[i,0] = ta
  stc[i,1] = tb

bud = 0
nb = stc[stc[:,1].argsort(),:]
while m > 0:
  if m  > = nb[i,1]:
    bud += nb[i,0]*nb[i,1]
    m -= nb[i,1]
  else:
    bud += nb[i,0]*m
    m = 0

print(bud)

Submission status: Runtime Error

Solution code:
N,M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

A = []
B = []
for i in AB:
    a,b = i
    A.append(a)
    B.append(b)

sortA = sorted(A)

ans = 0
num = M
for i in sortA:
    ind = A.index(i)
    k = B[ind]
    if num > k:
        num -= k
        ans += i* k
    else:
        while True:
            if K == 0:
                break
            ans += i
            k -=1
print(ans)

Submission status: Runtime Error

Solution code:
N,M = list(map(int,input().split()))
d = {}
for i in range(N):
	k,l = list(map(int,input().split()))
	d[k] = l

d = sorted(d.items(),key = lambda x: x[0])

a= 0
ans = 0
for i in range(N):
	a += d[i][1]
	if M > a:
		ans += d[i][0]*d[i][1]
	else:
		ans += d[i][0]* (d[i][1] - a +M)
		break

print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a = []
b = []
ans = 0
for i in range(n):
    tempa,tempb = map(int,input().split())
    a.append(tempa)
    b.append(tempb)
test = dict(zip(a,b))
test = sorted(test.items())
# print(test)
# test_item = test.values()
# test_key = test.keys()
# print(test_item)
# print(test_key)
i=0
while m>0:
    if m-test[i][1] >=0:
        ans += test[i][0]*test[i][1]
        m -=test[i][1]
        i += 1
    else:
        ans += test[i][0]*m
        m=0
print(ans)

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin
 

 
def li(): return map(int, stdin.readline().split())

N, M = tuple(li())

categories = [ tuple(li()) for _ in range(N) ]
categories.sort()

total = 0
def buy_M(cate, M, cost):
    if M <= 0:
        return cost
    if cate[0][1] >= M:
        cur_cost = cate[0][0] * M
        return cur_cost + cost
    else:
        rest = M - cate[0][1]
        cur_cost = cate[0][1] * cate[0][0]
        return buy_M(cate[1:], rest, cost + cur_cost)
print(buy_M(categories, M, 0))

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
L=[]

ans=0

for i in range(N):
    a,b=map(int,input().split())

    L.append([a,b])

L= sorted(L)



for i in range(N):

    ans = L[i][0]*L[i][1]
    M -= L[i][1]


    if M <= L[i+1][1]:

        ans += M * L[i+1][0]

        print(ans)

        exit()

Submission status: Runtime Error

Solution code:
import pandas as pd

n, m = map(int, input().split(' '))
ab = pd.DataFrame(columns=["a", "b"])
for nn in range(n):
    ls = list(map(int, input().split(' ')))
    ab.loc[nn] = ls
    
sortedAb = ab.sort_values("a")
amount = 0
count = 0
for i in range(len(sortedAb)):
    amount += min(sortedAb.iat[i, 1], m - count) * sortedAb.iat[i, 0]
    count += sortedAb.iat[i, 1]
    if count >= m:
        break

print(amount)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
potion=[]
for i in range(n):
    potion_R = list(map(int,input().split())
    potion.append(potion_R)
potion.sort()
ans=0
number=m
for i in potion:
    if i[1]<=number:
        number-= i[1]
        ans+= i[0]*i[1]
    else:
        ans+= i[0]*number
        break
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
N, M = map(int, input().split())
AB_list = np.zeros((N, 2))

for i in range(N):
    A, B = map(int, input().split())
    AB_list[i] = [A, B]

if N==1:
    print(int(M*AB_list[0, 0]))
else:
    AB_list = AB_list[np.argsort(AB_list[:, 0])]
    i = 0
    money = 0
    while(AB_list[i, 1] <= M):
        money += AB_list[i,0] * AB_list[i, 1]
        M -= AB_list[i, 1]
        i += 1

    money += AB_list[i, 0] * M
    print(int(money))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
potion=[]
for i in range(N):
    potion_R = list(map(int,input().split())
    potion.append(potion_R)
potion.sort()
ans=0
number=m
for i in potion:
    if i[1]<=number:
        number-= i[1]
        ans+= i[0]*i[1]
    else:
        ans+= i[0]*number
        break
print(ans)

Submission status: Runtime Error

Solution code:
N,M=list(map(int,input().split()))
A=[]
for i in range(N):
    A.append(list(map(int,input().split())))
# print(A)
A.sort()
#print(A)
res,count=0,0
for i in range(N):
    res+=A[i][0]*A[i][1]
    count+=A[i][1]
    if(count==M):
        break 
    if(count>M):
        res-=A[i][0]*A[i][1]
        count-=A[i][1]
        for j in range(1,A[i][1]+1):
            res+=A[i][0]
            count+=1
            if(count==M):
                print(res)
                exit()

print(res)
exit()a

Submission status: Runtime Error

Solution code:
n,m=[int(i) for i in input().split()]
min_money=[10000000000,1000000001,1000000002]
min_buy=[0,0,0]
for i in range(n):
    a,b=[int(i) for i in input().split()]
    min_money.append(a)
    min_money.sort()
    min_money.pop()
    if a in min_money:
        min_buy[min_money.index(a)],min_buy[min_money.index(a)+1]=b,min_buy[min_money.index(a)]
ans=0
for i in range(3):
    if min_buy[i]>=m:
        ans+=min_money[i]*m
        break
    else:
        ans+=min_money[i]*min_buy[i]
        m-=min_buy[i]
print(ans)

Submission status: Runtime Error

Solution code:
N,M = list(map(int, input().split()))
lis=[]
for i in range(N):
    a,b = list(map(int, input().split()))
    lis.append([a,b])

lis.sort()

count=0
money=0
ind=0
while count+lis[ind][1]<=M:
    count+=lis[ind][1]
    money+=lis[ind][0]*lis[ind][1]
    ind+=1
    print(ind)
    

money+=(M-count)*lis[ind][0]
print(int(money))

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
AB = [list(map(int,input().split())) for i in range(n)]
AB.sort(reverse = True)
c = 0
ans = 0
i = 0
while c < m:
  if  c + AB[i][1] <= m:
    c += AB[i][1]
    ans += AB[i][0]*AB[i][1]
    i += 1
  else:
    ans += Ab[i][0]*(m-c)
    break

print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
A=[]
for i in range(n):
  a,b=map(int,input().split())
  A.append([a,b])

A=sorted(A,key=lambda x:x[0])
ko=0
pri=0
i=0
while ko<=m:
  pri+=A[i][0]*A[i][1]
  ko+=A[i][1]
  i+=1
print(pri-(ko-m)*A[i-1][0])

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
ab = {}
for i in range(N):
    a,b = map(int,input().split())
    ab[a] = b

keys = sorted(ab.keys())

ans = 0
honsu = 0
money = 0
pre_money = 0
for i in keys:
    if honsu >= M:
        money = pre_money
        break
    ans += ab[i] * i
    honsu += ab[i]
    if honsu >= M:
        money = i
        break
    pre_money = i

for j in range(ab[money]):
    if honsu == M:
        break
    honsu -= 1
    ans -= money

print(ans)

Submission status: Runtime Error

Solution code:
print(AB)

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

s = 0
for ab in AB:
    if ab[1] > M:
        s += M*ab[0]
        break
    else:
        s += ab[0]*ab[1]
        M -= ab[1]

print(s)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
ab = {}
for i in range(N):
    a,b = map(int,input().split())
    ab[a] = b

keys = sorted(ab.keys())

ans = 0
honsu = 0
money = 0
for i in keys:
    if honsu >= M:
        break
    ans += ab[i] * i
    honsu += ab[i]
    if honsu >= M:
        money = i
        break

for j in range(ab[money]):
    if honsu == M:
        break
    honsu -= 1
    ans -= money

print(ans)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())

A = [ list(map(int,input().split())) for _ in range(N) ]
A.sort()
ans = 0
for M == 0:
  if M >= A[0][1]:
    ans += A[0][0] * A[0][1]
    M -= A[0][1]
    del A[0]
  else:
    ans += A[0][0] * M
    M = 0
print(ans)