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: Accepted

Solution code:
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
#pypyではscipy, numpyは使えない
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
#from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
#import numpy as np
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7

def main():
  n, m = map(int, readline().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, readline().split())
  sort_ab = sorted(ab, key = itemgetter(0))

  
  ans = 0
  for i in range(n):
    kau = min(sort_ab[i][1], m)
    m -= kau
    ans += sort_ab[i][0] * kau
  print(ans)
  
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m = LI()
ab = [LI() for _ in range(n)]
ab.sort()
ans = 0
cnt = 0
for a,b in ab:
    if cnt + b <= m:
        cnt += b
        ans += a*b
    else:
        ans += (m-cnt)*a
        break
print(ans)

Submission status: Accepted

Solution code:
def main():
    n, m, *l = map(int, open(0).read().split())
    ab = list(zip(l[::2], l[1::2]))
    c = sorted(ab, key=lambda x: x[0])

    sum = 0
    ans = 0
    for i, j in c:
        if sum + j < m:
            sum += j
            ans += i * j
        else:
            ans += (m - sum) * i
            break
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n, m, *l = map(int, open(0).read().split())
    ab = list(zip(l[::2], l[1::2]))
    ab.sort(key = lambda x: x[0])
    sum = 0
    ans = 0
    for i, j in ab:
        if sum + j < m:
            sum += j
            ans += i * j
        else:
            ans += (m - sum) * i
            break
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab_list = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: x[0])
ans = 0
for a, b in ab_list:
    if b >= m:
        print(ans + a * m)
        exit()
    else:
        ans += a * b
        m -= b

Submission status: Accepted

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.sort()

ans=0
while m>0:
    now=A.pop(0)
    if now[1]>m:
        ans+=now[0]*m
        m=0
    else:
        ans+=now[0]*now[1]
        m-=now[1]
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
store = [[0, 0] for i in range(n)]
for i in range(n):
    store[i] = list(map(int, input().split()))
store.sort(key=lambda x:(x[0],x[1]))
count = m
money = 0
for el in store:
    a, b = el
    if count <= b:
        money += a*count
        break
    else:
        count -= b
        money += a*b
print(money)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
A = {}
for i in range(n):
  a, b = map(int, input().split())
  if not a in A:
    A[a] = b
  else:
    A[a] += b
ans = 0
num = 0
A = sorted(A.items())
for k, v in A:
  if num < m and m <= num+v:
    ans += (m-num)*k
    break
  else:
    ans += v*k
    num += v
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab_list = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: x[0])
ans = 0
for a, b in ab_list:
    if b >= m:
        print(ans + a * m)
        exit()
    else:
        ans += a * b
        m -= b

Submission status: Accepted

Solution code:
n,m=map(int,input().split())

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

l=sorted(l,key=lambda x:x[0])
ans=0
for i in l:
    if m>i[1]:
        ans+=(i[0]*i[1])
        m-=i[1]
    else:
        ans+=(i[0]*m)
        break
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]
ab.sort()
ans = 0
for a, b in ab:
    buy = min(m, b)
    m -= buy
    ans += a*buy
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]
ab.sort()
ans = 0
for a, b in ab:
    buy = [m, b][0 <= m-b]
    m -= buy
    ans += a*buy
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]
ab.sort()

ans = 0
for a, b in ab:
    buy = [m, b][0 <= m-b]
    m -= buy
    ans += a*buy
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab = []
for _ in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))
ab.sort()
ans = 0
for a, b in ab:
    buy = [m, b][0 <= m-b]
    m -= buy
    ans += a*buy
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

n, m = map(int, input().split())
ls = []

for _ in range(n):
    a, b = map(int, input().split())
    ls.append([a, b])


ls.sort()

i = 0
price = 0

for num in range(n):
    i += ls[num][1]
    price += ls[num][0]*ls[num][1]
    num1 = num
    if i > m:
        break

now_cnt = i - ls[num1][1]
answer = price - ls[num1][0]*ls[num1][1] + (m - now_cnt)*ls[num1][0]

print(answer)

Submission status: Accepted

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

S = [[0]*2 for i in range(N)]
for i in range(N):
    S[i] = list(map(int, input().split()))
     
S = sorted(S)

quantitys = 0
total = 0

for i in range(N):
    # 【根本註】この for 文の中がソースコードの変更点となります。
    # ここまでのコードで、二次元配列 S に「エナジードリンクが安い順」に
    # 金額と本数のセットを格納できているわけですから、あとは「その店で何本買えばよいか？」
    # を計算し、for 文を使わずに普通の数式ベースで金額・本数の計算を行ってしまうのが正しい方法となります。
    
    #【根本註】必要な本数 M から「今何本購入しているか」を表す quantitys を引くことで、
    # 「あと何本購入する必要があるか」を表す変数 need を計算します。
    need = M - quantitys

    #【根本註】この変数 need：「あと何本必要か」が、今参照している店の在庫本数：S[i][1] 以上ならば、
    # その店の在庫を全部購入することができるはずです。（在庫を全部買うと、残りが 0 本ちょうどか 1 本以上に
    # なります）
    if(need - S[i][1])>=0:
        # 【根本註】そのため、この場合は S[i][1] 本のエナジードリンクを S[i][0] 円で買ったものとして、
        # quantitys には S[i][1] を足し、金額の合計 total には S[i][0] * S[i][1] の 金額 × 本数 の合計額を
        # 足してしまいます。こうすることで、従来は購入する本数分だけ回していた for 文の処理を全て削減し、
        # 1 本の数式に落とし込むことができ、処理にかかる時間を非常に大きく削減することが可能になるのです。
        quantitys += S[i][1]
        total += S[i][0] * S[i][1]

    #【根本註】一方で、変数 need：「あと何本必要か」が、今参照している店の在庫本数：S[i][1] より少なければ、
    # その店では need 本だけ購入すれば、必要な本数ちょうどに揃えることが可能になります。
    else:
        # 【根本註】同様に、この場合は need 本のエナジードリンクを S[i][0] 円で買ったものとして、
        # quantitys には need を足し、金額の合計 total には S[i][0] * need の 金額 × 本数 の合計額を
        # 足してしまいます。
        quantitys += need
        total += S[i][0] * need

    #【根本註】ここまでの処理を終えた段階で、もし M （必要本数）から quantities（購入済の本数）を引いた値が
    # ゼロになったならば、必要な本数を買い揃えることができたということになりますから、ループを終了します。
    if M-quantitys == 0:
        break

print(str(total))

Submission status: Accepted

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

S = [[0]*2 for i in range(N)]
for i in range(N):
    S[i] = list(map(int, input().split()))
     
S = sorted(S)

quantitys = 0
total = 0

for i in range(N):
    # この店を買い尽くしてもまだ足りなければ、全部買う
    if((M - quantitys) - S[i][1])>=0:
        quantitys += S[i][1]
        total += S[i][0] * S[i][1]
    else:
        quantity = M - quantitys
        quantitys += quantity
        total += S[i][0] * quantity
    if M-quantitys == 0:
        break

print(str(total))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=[[i for i in map(int,input().split())]for _ in range(n)]
c=0
for a,b in sorted(s):
  c+=min(m,b)*a
  m-=b
  if m<1:break
print(c)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[]
for _ in range(n):
    x,y=map(int,input().split())
    l.append([x,y])
l.sort(key=lambda x:x[0])
cnt=0
cost=0
for i in range(n):
    if cnt+l[i][1]>=m:
        diff=m-cnt
        cost+=diff*l[i][0]
        cnt+=diff
        break
    else:
        cnt+=l[i][1]
        cost+=l[i][0]*l[i][1]
print(cost)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
n, m = map(int, readline().split())
ab = map(int, read().split())
ab = sorted(zip(ab, ab))

ans = 0
for a, b in ab:
    drink = min(b, m)
    ans += a * drink
    m -= drink
    if m <= 0:
        break
print(ans)

Submission status: Accepted

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

d = []
res = 0

for i in range(N):
    A,B = map(int,input().split())
    d.append((A,B))

d.sort(reverse = True)

while M:
    x = d.pop()
    n = min(M,x[1])
    res += n * x[0]
    M -= n
print(res)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(n)]
    ab.sort()
    res = 0
    for a,b in ab:
        if m<=b:
            res += a*m
            print(res)
            exit()
        else:
            res += a*b
            m -= b

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
drinks = []
cost = 0
flag = True
for i in range(n):
    a,b = map(int,input().split())
    drinks.append((a,b))
drinks.sort(reverse = True)
while m:
    x = drinks.pop()
    num = min(m,x[1])
    cost += num * x[0]
    m -= num 
print(cost)

Submission status: Accepted

Solution code:
def main():
    n, m = [int(e) for e in input().split()]
    AB = [[int(e) for e in input().split()] for i in range(n)]

    AB.sort(key=lambda x: x[0])
    ans = 0
    cnt = 0
    for ab in AB:
        cnt += ab[1]
        ans += ab[0]*ab[1]
        if cnt >= m:
            ans -= ab[0]*(cnt - m)
            break

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

bill=0
num=0
AB=sorted(AB, key=lambda val:val[0])
#print(AB)
for i in range(N+1):
    if num<M:
        num+=AB[i][1]
        bill+=AB[i][0]*AB[i][1]
        #print(num, bill)
    else:
        bill=bill-(num-M)*AB[i-1][0]
        print(bill)
        break

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n)]
ab = sorted(ab,key=lambda x:x[0])
ans = 0
for i in ab:
  m -= i[1]
  ans += i[0]*i[1]
  if m <= 0:
    print(ans + m*i[0])
    break

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
shop = []
for _ in range(n):
    a, b = map(int, input().split())
    shop.append([a, b])
 
shop = sorted(shop) # 一番値段の小さいところから買えるだけ買っていく
ans, num = 0, 0
for i in range(n):
    a, b = shop[i]
    num += b
    ans += a*b
    if num>=m:
        ans -= (num-m)*a # 買うべき量を上回ったら、余計に買った分を減らす
        break
 
print(ans)

Submission status: Accepted

Solution code:
N,M = (int(x) for x in input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort()
rem = M
min_price = 0
for i in range(N):
    if rem > AB[i][1]:
        min_price += AB[i][0] * AB[i][1]
        rem -= AB[i][1]
    else:
        min_price += AB[i][0] * rem
        break
print(min_price)

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    A = [[0, 0] for _ in range(N)]
    for i in range(N):
        A[i][0], A[i][1] = map(int, input().split())
    
    cnt = 0
    money = 0

    A.sort(key=lambda x:(x[0], x[1]))
    for i in range(N):
        money += A[i][0]*A[i][1]
        cnt += A[i][1]
        if(cnt >= M):
            break
    if(cnt == M):
        print(money)
    else:
        print(money-(cnt-M)*A[i][0])
    
main()

Submission status: Accepted

Solution code:
class Drink(object):
    """docstring for."""

    def __init__(self,value,unit):
        self.value = value
        self.unit = unit
    def __repr__(self):
        return "%d,%d" %(self.value,self.unit)

n,m = (int(x) for x in input().split())
a = []
ans = 0;i = 0
for i in range(n):
    ai,bi = (int(x) for x in input().split())
    a.append(Drink(ai,bi))

a.sort(key=lambda x: x.value)

for i in range(n):
    mazai = a[i]
    if mazai.unit>=m:
        ans += mazai.value * m
        print(ans)
        break
    else:
        ans += mazai.unit * mazai.value
        m = m - mazai.unit

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a = []
for i in range(n):
    a.append(list(map(int,input().split())))
a.sort(key = lambda a:a[0])
bought = 0
price = 0
for i in range(n):
    remain = m - bought
    if a[i][1] < remain:
        bought += a[i][1]
        price += a[i][0] * a[i][1]
    else:
        price += a[i][0]*remain
        print(price)
        exit()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
li = [list(map(int,input().split())) for _ in range(n)]
li = sorted(li, key=lambda x:x[0])
cnt = 0
coin = 0
for a,b in li:
    c_cnt = cnt + b
    if c_cnt < m:
        cnt += b
        coin += a*b
    else:
        cnt += b-(c_cnt - m)
        coin += a*(b-(c_cnt-m))
        break
print(coin)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
#A, B = [], []
#for i in range(N):
    #ai, bi = map(int, input().split())
    #A.append(ai)
    #B.append(bi)
AB = sorted(AB)

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

sa = [0] * (N + 1)
sb = [0] * (N + 1)
for i in range(N):
    sa[i + 1] = sa[i] + B[i]
    sb[i + 1] = sb[i] + B[i] * A[i]

from bisect import bisect_left
aim = bisect_left(sa, M)

print(sb[aim] - A[aim - 1] * (sa[aim] - M))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
#A, B = [], []
#for i in range(N):
    #ai, bi = map(int, input().split())
    #A.append(ai)
    #B.append(bi)
AB = sorted(AB)

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

sa = [0] * (N + 1)
sb = [0] * (N + 1)
for i in range(N):
    sa[i + 1] = sa[i] + B[i]
    sb[i + 1] = sb[i] + B[i] * A[i]

from bisect import bisect_left
aim = bisect_left(sa, M)

print(sb[aim] - A[aim - 1] * (sa[aim] - M))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n, m = map(int,input().split())
ab = []
for i in range(n):
    ab.append([int(i) for i in input().split()])

ab.sort()
ans = 0
drink = 0
i = 0
while drink < m:
    if drink + ab[i][1] <= m:
        ans += ab[i][0] * ab[i][1]
        drink += ab[i][1]
    else:
        ans += ab[i][0] * (m - drink)
        break
    i += 1
print(ans)

Submission status: Accepted

Solution code:
#abc121_c
N, M = map(int,input().split())
AB = [list(map(int,input().split())) for i in range(N)]
AB= sorted(AB,key=lambda x:x[0])
ans = 0
for yen,num in AB:
    if num < M:
        ans += num*yen
        M-=num
    else:
        ans += M*yen
        break
print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *
from math import *
from fractions import *

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

N, M = map(int, input().split())
h = []
for _ in range(N):
    A, B = map(int, input().split())
    heappush(h, (A, B))

count = 0
ans = 0
while M > 0:
    a, b = heappop(h)
    ans += a
    if b - 1 > 0:
        heappush(h, (a, b - 1))
    M -= 1

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
k = []
now = 0
ans = 0
for i in range(N):
    a,b = map(int,input().split())
    k.append([a,b])
k.sort()
for i in range(N):
    if (now+k[i][1])<M:
        ans += k[i][0]*k[i][1]
        now += k[i][1]
    else:
        ans += k[i][0]*(M-now)
        print(ans)
        break

Submission status: Accepted

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

shop = sorted(shop)
ans, num = 0, 0
for i in range(n):
    a, b = shop[i]
    num += b
    ans += a*b
    if num>=m:
        ans -= (num-m)*a
        break

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

AB.sort()

cart = 0
price = 0
j = 0
for i in range(N):
    if cart + AB[i][1] > M:
        j = i
        break
    cart += AB[i][1]
    price += AB[i][0] * AB[i][1]

price += (M - cart) * AB[j][0]
print(price)

Submission status: Accepted

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

lis_A = []
lis_B = []

for _ in range(N):
    A, B = map(int, input().split())
    lis_A.append(A)
    lis_B.append(B)

c = zip(lis_A, lis_B)
sorted_c = sorted(c)
lis_A, lis_B = zip(*sorted_c)


cost  = 0
count  = 0

while True:
    if N == 1:
        print(lis_A[0] * lis_B[0])
        sys.exit()


    for i in range(len(lis_A)):
        if (lis_B[i] + count) <= M:
            cost = (lis_A[i]*lis_B[i]) + cost
            count = lis_B[i] + count
        else:
            cost = (((M - count) * lis_A[i]) + cost)
            print(cost)
            sys.exit()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A_list = []
for i in range(N):
    A_B = list(map(int, input().split()))
    A_list.append(A_B)
A_list.sort()
ans = 0
for i in range(N):
    ans += A_list[i][0]*A_list[i][1]
    M -= A_list[i][1]
    if M <= 0:
        break
if M==0:
    print(ans)
else:
    rev = 0-M
    print(ans-rev*A_list[i][0])

Submission status: Accepted

Solution code:
N,M = map(int,(input().split()))
a = [[0]*2 for _ in range(N)]
for i in range(N):
    a[i][0],a[i][1] = map(int,(input().split()))

a.sort()

c = 0
i = 0
p = 0
while c < M: 
    c += 1
    if a[i][1]:
        p += a[i][0]
        a[i][1] -= 1
    else:
        i += 1
        p += a[i][0]
        a[i][1] -= 1

print(p)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
ab.sort(key=lambda x: x[0])
money = 0

for i in range(N):
    m = ab[i][1]
    if m <= M:
        money += ab[i][0] * ab[i][1]
        M -= m
    else:
        money += ab[i][0] * M
        break
print(money)

Submission status: Accepted

Solution code:
# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
# import sys
# sys.setrecursionlimit(10**9)

def resolve():
    N,M=map(int,input().split())
    L=sorted([list(map(int,input().split())) for i in range(N)],key=lambda x:x[1], reverse=True)
    L.sort()
    def main():
        cnt = 0
        val = 0

        while True:
            for i in range(N):
                cnt+=L[i][1]
                val+=L[i][0]*L[i][1]
                if cnt>M:
                    val-=(cnt-M)*L[i][0]
                    return val


    print(main())






resolve()

Submission status: Accepted

Solution code:
from collections import defaultdict

N, M = map(int, input().split())
drinks = defaultdict(int)

for _ in range(N):
    A, B = map(int, input().split())
    drinks[A] += B

drinks = sorted(drinks.items(), key = lambda x : x[0])
cnt = 0
price = 0

for k, v in drinks:
    purchases = min(v, M - cnt)
    cnt += purchases
    price += purchases * k

print(price)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
list_AB = [ list(map(int,input().split(" "))) for i in range(n)]

list_AB.sort()
ans = 0
for i in range(n):
    l = list_AB[i]
    if l[1] > m:
       ans += l[0]*m
       break
    else:
        ans += l[0]*l[1]
        m -= l[1]

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab = [[0, 0] for _ in range(n)]
for i in range(n):
    ab[i][0], ab[i][1] = map(int, input().split())
ab.sort()
c = 0
i = 0
while m != 0:
    if ab[i][1] <= m:
        c += ab[i][0] * ab[i][1]
        m -= ab[i][1]
    else:
        c += ab[i][0] * m
        break
    if i == n - 1:
        break
    else:
        i += 1
print(c)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n, m = MAP()
ab = [LIST() for _ in range(n)]
ab.sort()
num = 0
ans = 0
for i in range(n):
    if num + ab[i][1] < m:
        num += ab[i][1]
        ans += ab[i][0] * ab[i][1]
    else:
        ans += ab[i][0] * (m - num)
        break
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x:x[0])

ans = 0
for i in range(n):
    if ab[i][1] < m:
        ans += ab[i][0] * ab[i][1]
        m -= ab[i][1]
    else:
        ans += ab[i][0] * m
        break

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
d = defaultdict(lambda: 0)
for i in range(N):
    a, b = map(int, input().split())
    d[a] += b
keys = sorted(d.keys())
t = 0
ans = 0
for k in keys:
    v = d[k]
    if t + v > M:
        ans += (M-t)*k
        break
    else:
        t += v
        ans += k*v
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
C=[0]*N
for i in range(N):
  C[i]=tuple(map(int,input().split()))
  
C.sort(key=lambda x:x[0])
cnt=0
cost=0

for i in range(N):
  #print(C[i][0],C[i][1])
  if cnt+C[i][1] < M:
    #print(cnt,cost)
    cnt += C[i][1]
    cost += C[i][0]*C[i][1]
  else:
    #print(cnt,cost)
    cost += (M-cnt)*C[i][0]
    break
    
print(cost)

Submission status: Accepted

Solution code:
# coding: utf-8
import os
from sys import stdin
from functools import total_ordering

# __dirname = os.path.dirname(__file__)
# __basename = os.path.splitext(os.path.basename(__file__))[0]
# __targetname = './input/' + __basename + '.txt'
# target_path = os.path.join(__dirname, __targetname)
# stdin = open(target_path)

@total_ordering
class struct(object):
    def __init__(self,a,b):
        self.a=a
        self.b=b
    def __lt__	(self,other):
        return self.a < other.a
    def __eq__	(self,other):
        return self.a == other.a

def main():
    # st = struct(10,1)
    # print(st.a)
    input_line = stdin.readline().rstrip().split(' ')
    N, M = map(int, input_line)
    A = list()
    for _ in range(N):
        input_line = stdin.readline().rstrip().split(' ')
        a,b=map(int, input_line)
        st=struct(a,b)
        A.append(st)
    A.sort()
    ans=0
    time=0
    for x in A:
        # print(x.a,x.b)
        if(time>M):
            continue
        if((time+x.b)<=M):
            ans += x.a*x.b
            time += x.b
        else:
            ans += x.a*(M-time)
            time = M
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N, M = map(int, input().split(' '))

ab_pairs = [list(map(int, input().split(' '))) for _ in range(N)]
ab_pairs.sort(key=lambda x: x[0])

rest = M
ret = 0
for a, b in ab_pairs:
    n = min(rest, b)
    ret += a * n
    rest -= n

print(ret)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
AB = []
for i in range(N):
    A, B = map(int, input().split())
    AB.append([A, B])
AB.sort(key=lambda x: x[0])
count = 0
money = 0
for i in range(N):
    count += AB[i][1]
    money += AB[i][0] * AB[i][1]
    if count >= M:
        money -= (count - M) * AB[i][0]
        break
print(money)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
list_AB = [ list(map(int,input().split(" "))) for i in range(n)]

list_AB.sort()
ans = 0
for i in range(n):
    l = list_AB[i]
    if l[1] > m:
       ans += l[0]*m
       break
    else:
        ans += l[0]*l[1]
        m -= l[1]

print(ans)

Submission status: Accepted

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

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

Drinks_Fee = 0
Drinks = 0

for shop in sorted(Shops):
    if Drinks+shop[1]>=M:
        Drinks_Fee+=shop[0]*(M-Drinks)
        break
    else:
        Drinks_Fee+=shop[0]*shop[1]
        Drinks+=shop[1]
print(Drinks_Fee)

Submission status: Accepted

Solution code:
from operator import itemgetter

n,m= map(int,input().split())
ab = [list(map(int,input().split())) for i in range(n)]
ab = sorted(ab)
money = 0
drink = 0
for i in range(n):
         drink += ab[i][1]
         if drink > m:
                  drink -= ab[i][1]
                  break
         else:
                  money += ab[i][1] * ab[i][0]
                  continue
         break
money += (m - drink)*ab[i][0]
print(money)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
L = sorted([list(map(int, input().split())) for _ in range(n)])
ans = 0
for l in L:
    tmp = min(l[1], m)
    ans += l[0]*tmp
    m -= tmp
    if m == 0:
        break
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(L)
# heapq.heapify(sorted(L, key=lambda x: x[0]))
# print(L)
drink = 0
yen = 0
while drink < M:
    a, b = heapq.heappop(L)
    if drink + b <= M:
        yen += a * b
        drink += b
    else:
        yen += a * (M - drink)
        break
print(yen)

Submission status: Accepted

Solution code:
import numpy as np
N, M = map(int, input().split())
shop = []
for _ in range(N):
    shop.append(list(map(int, input().split())))
i = 0
num = 0
ans = 0
shop = sorted(shop)
while num < M:
    ans += shop[i][0] * shop[i][1]
    num += shop[i][1]
    i += 1
ans -= (num - M) * shop[i -1][0]
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N, M = map(int, input().split())
A = []
B = []
for _ in range(N):
    a, b =  map(int, input().split())
    A.append(a)
    B.append(b)
i = 0
num = 0
ans = 0
A_argsort= np.argsort(A)
while num < M:
    ans += A[A_argsort[i]] * B[A_argsort[i]]
    num += B[A_argsort[i]]
    i += 1
ans -= (num - M) * A[A_argsort[i - 1]]
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
shop=[]
for _ in range(N):
    a=list(map(int,input().split()))
    shop.append(a)
shop.sort(key=lambda x: x[0])
cnt=0
p=0
i=0

while cnt<M:
    a=shop[i][0]
    b=shop[i][1]
    cnt+=b
    p+=a*b
    i+=1
su=cnt-M

a = shop[i-1][0]
p-=a*su
print(p)

Submission status: Accepted

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

AB=sorted(AB)
sum=0
answer=0
i=0
while sum<M:
    plus=min(AB[i][1],M-sum)
    sum+=plus
    answer+=plus*AB[i][0]
    i+=1

print(answer)

Submission status: Accepted

Solution code:
n ,m = map(int, input().split())
a = [0] * n
b = [0] * n
arr = [[0] * 2 for _ in range(n)]

for i in range(n):
    a[i], b[i] = map(int, input().split())
    arr[i][0] = a[i]
    arr[i][1] = b[i]

arr.sort()

count = 0
cost = 0

for i in range(n):
    rem = m - count 
    cost += arr[i][0] * min(arr[i][1], rem)
    count += min(arr[i][1], rem)
    if count >= m:
        break

print(cost)

Submission status: Accepted

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

store = {}
for i in range(N):
    a, b = map(int, input().split())
    if a in store: store[a] += b
    else: store[a] = b
key = list(store.keys())
key.sort()

bins = 0
total = 0
for k in key:
    if bins + store[k] < M:
        bins += store[k]
        total += k * store[k]
    else:
        total += k * (M-bins)
        break
print(total)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
li = []
count = 0
ans = 0

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

li.sort(key = lambda x:x[0])

for i in range(len(li)):
    if count > m:
        break
    if count + li[i][1] <= m:
        ans += li[i][0] * li[i][1]
    elif count + li[i][1] > m:
        buf = m - count
        ans += buf * li[i][0]
    count += li[i][1]

print(ans)