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:
N, M = map(int, input().split(" "))
temp = {}
cost = 0
count = 0

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

for k, v in sorted(temp.items()):
    cost += k*v
    M = M - v
    
    if M <= 0 :
        cost = cost + (k*M)
        break


print(cost)

Submission status: Accepted

Solution code:
from operator import itemgetter

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

a.sort(key=itemgetter(0))
count = int(M)
price = 0
for i in range(N):
    if count - int(a[i][1]) > 0:
        count -= int(a[i][1])
        price += int(a[i][1]) * int(a[i][0])
    else:
        price += int(a[i][0]) * count
        break

print(price)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
money = 0
AB = sorted(AB, key=lambda x: x[0])
if M <= AB[0][1]:
  money += AB[0][0] * M
else:
  i = 0
  while M > 0:
    money += AB[i][0] * AB[i][1]
    M -= AB[i][1]
    if M <= 0:
      money += AB[i][0] * M
      break
    i += 1
print(money)

Submission status: Accepted

Solution code:
import sys

N, M = map(int, sys.stdin.readline().split())
AB = [None] * N
for i in range(N):
    AB[i] = list(map(int, sys.stdin.readline().split()))

AB.sort()
cnt = 0
ans = 0

for a,b in AB:
    if cnt + b < M:
        ans += a * b
        cnt += b
    else:
        ans += a * (M - cnt) 
        break

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ans = 0
cnt = 0
for a, b in sorted(list(map(int, input().split())) for _ in range(n)):
    if cnt + b <= m:
        ans += a * b
        cnt += b
    else:
        ans += a * (m - cnt)
        cnt = m
    if cnt == m:
        break
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
count = yen = imp = 0
li = [list(map(int,input().split())) for i in range(N)]
li.sort()
for i in range(0,len(li),1):
  count += li[i][1] 
  yen += li[i][0]*li[i][1] 
  if count > M:
    imp = abs(M-count)
    count -= abs(M-count)
    yen -= li[i][0]*imp
  if count == M: 
    break
print(yen)

Submission status: Accepted

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

AB = sorted(AB)
cnt = 0
ans = 0

for e in AB:
    if cnt + e[1] < M:
        ans += e[0] * e[1]
        cnt += e[1]
    else:
        ans += e[0] * (M - cnt) 
        break

print(ans)

Submission status: Accepted

Solution code:
#C - Energy Drink Collector
n,m = map(int,input().split())
ab = []
for i in range(n):
    ab.append(list(map(int, input().split())))
abSorted = sorted(ab)
sumB = 0
sumMoney = 0
i = 0
while sumB + abSorted[i][1] < m:
    sumB += abSorted[i][1]
    sumMoney += abSorted[i][0] * abSorted[i][1]
    i += 1
sumMoney += abSorted[i][0] * (m - sumB)
print(sumMoney)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def solve(l: list, m: int):
    # sort by price
    l = sorted(l)
    cnt = 0
    mon = 0
    for a, b in l:
        mon += a*b
        cnt += b
        if cnt >= m:
            mon -= (cnt-m)*a
            break
    return mon


def main():
    N, M = map(int, input().split())
    l = []
    for i in range(N):
        a, b = map(int, input().split())
        l.append((a,b))
    print(solve(l, M))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from functools import reduce
N, M = map(int, input().split())
A, B = zip(*sorted((list(map(int, input().split())) for _ in range(N))))
ans = reduce(lambda acc, t: (acc[0] + t[0] * min(max(0, M - acc[1]), t[1]), acc[1] + t[1]), zip(A, B), (0, 0))[0]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = []
B = []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
C = zip(A,B)
C = sorted(C)
A, B = zip(*C)
index = 0
count = 0
sum = 0
for i in range(N):
      if(count<=M):
        index = i
        sum += A[i]*B[i]
        count += B[i]
sum +=A[index]*(M-count)
print(sum)

Submission status: Accepted

Solution code:
from sys import stdin
n,s = map(int,stdin.readline().split())
ans = 0
a = []
for i in xrange(n):
  x,y = map(int,stdin.readline().split())
  a.append((x,y))
a.sort()
for x,y in a:
  mi = min(y,s)
  ans += mi * x
  s -= mi
print ans

Submission status: Accepted

Solution code:
import numpy as np
N,M=[int(x) for x in input().split()]

L=np.zeros((2,N))
for n in range(N):
  l=[int(x) for x in input().split()]
  L[0][n]=l[0]
  L[1][n]=l[1]
  
L=L[:, L[0,:].argsort()]

d_num=0
price=0

for l in range(len(L[0])):
  a=L[0][l]
  b=L[1][l]
  
  if d_num < M:
    if d_num+b < M:
      price+=a*b 
      d_num+=b 
    else:
      price+=a*(M-d_num)
      d_num=M
                
print(int(price))

Submission status: Accepted

Solution code:
var = list(map(int, input().split()))
N = var[0]
M = var[1]
 
A = [0] * N
B = [0] * N
for i in range(N):
    A[i], B[i] = map(int, input().split())
C = zip(A,B)
C = sorted(C)
A, B = zip(*C)
 
index = 0
count = 0
for i in range(N):
      if(count<=M):
        index = i
      count += B[i]
count = 0
sum = 0
for i in range (index):
    sum+=A[i]*B[i]
    count+=B[i]
sum +=A[index]*(M-count)
print(sum)

Submission status: Accepted

Solution code:
n,m = [int(i) for i in input().split()]
e = [[int(i) for i in input().split()] for i in range(n)]
e.sort()
#print(n,m,e)

total=0
for i in range(n):
    if m > 0:
      total+=e[i][0]*min(e[i][1],m)
    m-=e[i][1]
    
print(total)

Submission status: Accepted

Solution code:
import numpy as np
import sys

N, M = [int(item) for item in input().split()]

ab = np.zeros((2,N))
for i in range(N):
  ab[0, i], ab[1, i] = [int(item) for item in input().split()]
  
ab = ab[:,np.argsort(ab[0, :])]

num = 0
money = 0
for i, item in enumerate(ab[1,:]):
  num += item
  money += item * ab[0,i]
  if num >= M:
    money -= (num - M) * ab[0,i]
    print(int(money))
    break

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
num = M
for a,b in AB:
  if b < num:
    ans += a*b
    num -= b
  else:
    ans += a*num
    num -= num
    break
print(ans)

Submission status: Accepted

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

AB.sort()

res = 0
count = 0

for A,B in AB:
    if  B <= M - count:
        count += B
        res += A * B
    else:
        res += A * (M - count)
        count = M

    if count == M:
        break

print(res)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
lis = [list(map(int,input().split())) for i in range(n)]
lis.sort()
to = 0
nu = 0
for i in lis:
    for n in range(i[1]):
        to += i[0]
        nu += 1
        if nu == m:
            print(to)
            exit()

Submission status: Accepted

Solution code:
##### C 再チャレンジ

##以下、二次元配列を、各リストの最初の要素でソートするアルゴリズム

def two_dim_merge_sort(arr):#＃arrは二次元配列
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    # ここで分割を行う
    left = arr[:mid]
    right = arr[mid:]

    # 再帰的に分割を行う
    left = two_dim_merge_sort(left)
    right = two_dim_merge_sort(right)

    # returnが返ってきたら、結合を行い、結合したものを次に渡す
    return two_dim_merge(left, right)


def two_dim_merge(left, right):
    merged = []
    l_i, r_i = 0, 0

    # ソート済み配列をマージするため、それぞれ左から見ていくだけで良い
    while l_i < len(left) and r_i < len(right):
        # ここで=をつけることで安定性を保っている
        if left[l_i][0] <= right[r_i][0]:
            merged.append(left[l_i])
            l_i += 1
        else:
            merged.append(right[r_i])
            r_i += 1

    # 上のwhile文のどちらかがFalseになった場合終了するため、あまりをextendする
    if l_i < len(left):
        merged.extend(left[l_i:])
    if r_i < len(right):
        merged.extend(right[r_i:])
    return merged

##ここまで

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

l = [0]*n

for i in range(0,n):
    l[i] = list(map(int,input().split()))

s = two_dim_merge_sort(l)

num = 0
ex = 0

for i in range(0,n):
    if num + s[i][1] <= m:
        ex = ex + s[i][0] * s[i][1]
        num = num + s[i][1]
    else:
        ex = ex + s[i][0] * (m-num)
        num = m
    if num == m:
        break
        
print(ex)

Submission status: Accepted

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

inputs.sort()
count = 0
ans = 0
for A, B in inputs:
    if M < 0:
        break
    ans += A * min(B, M)
    M -= B

print(ans)

Submission status: Accepted

Solution code:
m = list(map(int,input().split()))
l = sorted([list(map(int,input().split())) for i in range(m[0])], key=lambda x: x[0])
r = 0
c = 0
for a in l:
  if (c + a[1]) >= m[1]:
    r += a[0] * (m[1] - c)
    break
  c += a[1]
  r += a[0] * a[1]
print(r)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
ab=[list(map(int,input().split())) for l in range(N)]
ct=0
ct1=0
ct2=0
money=0
l=[]
id=[]
for i in range(N):
    l.append(ab[i][0])
id=sorted(range(len(l)),key=lambda k: l[k])
l.sort()
while ct<M:
    while ct2<ab[id[ct1]][1]:##
        money+=l[ct1] #l[ct1]
        #print(money,l[ct1])
        ct+=1
        ct2+=1
        if ct==M:
            break
    ct1+=1
    ct2=0
print(money)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ab = []
for i in range(n):
    ab.append(list(map(int,input().split())))
abSorted = sorted(ab)
sum = 0
sumMoney = 0
i = 0
while sum + abSorted[i][1] < m:
    sum += abSorted[i][1]
    sumMoney += abSorted[i][0] * abSorted[i][1]
    i += 1
sumMoney += abSorted[i][0] * (m - sum)
print(sumMoney)

Submission status: Accepted

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

A = [None] * N
B = [None] * N

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

C = zip(A, B)
C = sorted(C, key=lambda x: [x[0], x[1]], reverse=False)
A, B = map(list, zip(*C))

m = 0
r = 0

for i in range(N):
    a = A[i]
    b = B[i]
    if m + b < M:
        m += b
        r += a * b
    else:
        r += a * (M - m)
        break

print(r)

Submission status: Accepted

Solution code:
n,m = (int(i) for i in input().split())
x = [[int(i) for i in input().split()] for i in range(n)]
x,ans = sorted(x),0
for i in range(n):
    if m>=x[i][1]:
        ans+=x[i][0]*x[i][1]
        m-=x[i][1]
    else:
        ans+=x[i][0]*m
        break
print(ans)

Submission status: Accepted

Solution code:
def inpl():
    return list(map(int, input().split()))


N, M = inpl()
AB = [inpl() for _ in range(N)]

AB.sort()
ans = 0
i = 0
while M != 0:
    ans += min(M, AB[i][1]) * AB[i][0]
    M -= min(M, AB[i][1])
    i += 1
print(ans)

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.sort(key=lambda x:x[0])
i=0
ans=0
while M>l[i][1]:
  M-=l[i][1]
  ans+=l[i][0]*l[i][1]
  i+=1
ans+=l[i][0]*M
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
N,M = [int(x) for x in input().split()]
li = []
for _ in range(N):
    li.append([int(x) for x in input().split()])
li.sort(key=itemgetter(0))
cost = 0
num = 0
flag = True
for i in li:
    if(flag):
        if(num+i[1]>M):
            cost+=(M-num)*i[0]
            flag = False
        else:
            cost+=i[1]*i[0]
            num+=i[1]
print(cost)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
st = []
for _ in range(n):
    st.append(tuple(map(int, input().split())))
st.sort()
i = 0
c = 0
while m > 0:
    b = min(m, st[i][1])
    c += b * st[i][0]
    m -= b
    i += 1
print(c)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
x = sorted([list(map(int, input().split())) for i in range(N)])
i = 0
minprice = x[i][0]
minnumber = x[i][1]
price = 0
while True:
    if M <= minnumber:
        price += minprice * M
        break
    else:
        price += minprice * minnumber
        M -= minnumber
        i += 1
        minprice = x[i][0]
        minnumber = x[i][1]
print(price)

Submission status: Accepted

Solution code:
import sys
N, M = (int(x) for x in input().split())
AB = []
for i in range(N):
    AB_before = input().split()
    AB.append([int(x) for x in AB_before])

AB.sort(key=lambda x : x[0], reverse=False)  #1個目の要素で昇順並び替え

count = 0
total = 0

for i in range(N):
    if count < M - AB[i][1]:
        total += AB[i][0] * AB[i][1]
        count += AB[i][1]
    elif count < M:
        total += AB[i][0] * (M - count)
        print(total)
        sys.exit()

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split(" ")]
ab = []

for i in range(0, n):
    ab.append([int(i) for i in input().split(" ")])
    
ab = sorted(ab, key=lambda k: k[0])

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

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
list = []
for i in range(N):
    A,B = map(int,input().split())
    list.append([A,B])
list = sorted(list)
cost = 0
while True:
    M -= list[0][1]
    if M <= 0:
        cost += list[0][0] * (list[0][1]+M)
        break
    else:
        cost += list[0][0] * list[0][1]
        list.remove(list[0])
print(cost)

Submission status: Accepted

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

shop_s=sorted(shop)
count=0
used_money=0

for s in shop_s:
    for i in range(s[1]):
        if(M!=count and s[1]!=0):#買った数がMに達していない && 在庫が０ではない
            s[1]-=1
            count+=1
            used_money += s[0]
        else:
            break
    if  count == M:
        break
print(used_money)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

shoplist.sort(key=lambda x: x[0])
rtn=0
for elm in shoplist:
  if M==0:
    break
  if M >= elm[1]:
    rtn+=elm[0]*elm[1]
    M-=elm[1]
  else:
    rtn+=elm[0]*M
    M=0
print(rtn)

Submission status: Accepted

Solution code:
# /user/bin/python
# -*- coding: utf-8 -*-


N,M = map(int, input().split())
ABn = [[0 for j in range(2)] for i in range(N)]
for i in range(N):
  ABn[i] = list(map(int, input().split()))

ABn = sorted(ABn)

num,i = M,0
ans = 0
while(num > 0):
  if num >= ABn[i][1]:
    ans += ABn[i][0] * ABn[i][1]
    num -= ABn[i][1]
  else:
    ans += ABn[i][0] * num
    num = 0
  i += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
num = 0
price = 0
for A, B in sorted([list(map(int, input().split())) for _ in range(N)]):
    if M >= B:
        price += A*B
        M = M - B
    else:
        price += A*M
        break
print(price)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Feb 26 17:52:43 2019

@author: nakamuratakayuki
"""

N, M = tuple(map(int, input().split()))
AtoB = []
for i in range(N):
    AtoB.append(tuple(map(int, input().split())))
AtoB.sort()
cost = 0
m = 0
lastorder = 0
history = []

for i in range(len(AtoB)):
    cost += AtoB[i][0]*AtoB[i][1]
    m += AtoB[i][1]
    lastorder = AtoB[i][0]
    if M <= m:
        break
while M < m:
    cost -= lastorder
    m -= 1

print(cost)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
mseList = [list(map(int, input().split())) for i in range(0, N)]
mseList = sorted(mseList, key=lambda x:x[0])
total = 0
for i, k in mseList:
    if k < M:
        total += i * k
        M -= k
    else:
        total += i * M
        break
print(total)

Submission status: Accepted

Solution code:
import numpy as np
N, M = (int(i) for i in input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
money = 0
AB.sort()
for a, b in AB:
    if M == 0:
        break
    elif M >= b:
        M -= b
        money += a*b
    elif M < b:
        money += M*a
        M = 0
print(money)

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 = sorted(a, key=lambda x: x[0])
purchase_price = 0


for price, count in a:
    if count < m:
        purchase_price += price * count
        m -= count

    else:
        purchase_price += price * m
        m = 0

print(purchase_price)

Submission status: Accepted

Solution code:
import numpy as np
N, M = (int(i) for i in input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort()
money = 0
for a, b in AB:
    if M == 0:
        break
    elif M >= b:
        M -= b
        money += a*b
    elif M < b:
        money += a*M
        M = 0
print(money)

Submission status: Accepted

Solution code:
n,m = map(int,input().split(' '))
cost = 0
count = 0

mlist = list()
for i in range(n):
  mlist.append(list(map(int,input().split(' '))))
mlist.sort(key=lambda x: x[0])

for i in range(n):
  ablist = mlist[i]
  if count+ablist[1] <= m:
    count += ablist[1]
    cost += ablist[0]*ablist[1] 
  else:
    for j in range(ablist[1]):
      count += 1
      if count <= m:
        cost += ablist[0]
      else:
        break_t = True
        break
    if break_t:
      break
print(cost)

Submission status: Accepted

Solution code:
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])
i=0
money=0
while True:
    if m-ab[i][1]>0:
        m-=ab[i][1]
        money+=ab[i][0]*ab[i][1]
        i+=1
    else:
        break
money+=m*ab[i][0]
print(money)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
shops = [list(map(int, input().split())) for _ in range(N)]
shops.sort(key=lambda x: x[0])
cost = 0
for shop in shops:
	cost += shop[0] * shop[1] if M >= shop[1] else shop[0] * M
	M -= shop[1]
	if not M > 0:
		break
print(cost)

Submission status: Accepted

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

L = sorted(L,key=lambda x: x[0])

ans = 0
for i in range(len(L)) :
    if L[i][1] < M :
        M -= L[i][1]
        ans += L[i][0] * L[i][1]
    else :
        ans += L[i][0] * M
        break
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

N, M = (int(i) for i in input().split()) 
AB=[list(map(int,input().split())) for _ in range(N)]
# print(AB)
AB.sort()
# print(AB)

money = 0
for a, b in AB:

    # print(M) 
    if M==0:
        break
    elif b < M:
        # print(a*xb)
        money += a*b
        M -= b
    elif b >= M:
        # print(M)
        money += M*a
        M = 0
    # print(M, money)
print(money)

Submission status: Accepted

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

Submission status: Accepted

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


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    AB = sorted(range(N), key=lambda x: A[x])

    s = 0
    for i in AB:
        if B[i] > M:
            s += M*A[i]
            break
        else:
            s += A[i]*B[i]
            M -= B[i]

    print(s)
    return


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    n, m = map(int, input().split())
    ab = list()
    ans = 0

    for i in range(n):
        ai, bi = map(int, input().split())
        ab.append((ai, bi))

    for aj, bj in sorted(ab, key=lambda x: x[0]):
        if m >= bj:
            ans += aj * bj
            m -= bj
        else:
            ans += aj * m
            break

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from operator import itemgetter

N_shop, M_required_drink  = map(int, raw_input().split())

shop_list = []
for tmp_shop in range(N_shop):
  shop_list.append(map(int, raw_input().split()))

total_money = 0
got_drink = 0
for i in sorted(shop_list, key=itemgetter(0)):
  limit_at_shop = i[1]
#  print(i)

  while got_drink < M_required_drink and limit_at_shop > 0:
    total_money = total_money + i[0]
    got_drink   = got_drink + 1
    limit_at_shop = limit_at_shop - 1
#    print("  %s %s %s" % (total_money, got_drink, limit_at_shop))

print(total_money)

Submission status: Accepted

Solution code:
n, m = map(int,(input().split()))
d = []
for i in range(n):
    a, b = map(int,(input().split()))
    d.append([a,b])
d = sorted(d)
ans = 0
for i in range(n):
    if d[i][1] >= m: # 残り本数 >= この値段の本数
        ans += d[i][0]*m
        break
    else:
        ans += d[i][0]*d[i][1]
        m -= d[i][1]
        if m <= 0:
            break
print(ans)

Submission status: Accepted

Solution code:
YEN = 0
NUM = 1

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

require = M
price = 0
minidx = 0
while(require > 0):
#    print("require = {}, price = {}".format(require, price))
#    print("idx = {}, num = {}, price = {}".format(minidx, shop[minidx][NUM], shop[minidx][YEN]))
    if(require >= shop[minidx][NUM]):
        price = price + shop[minidx][YEN] * shop[minidx][NUM]
        require = require - shop[minidx][NUM]
        minidx = minidx + 1
    else:
#        print("buy = {}, price = {}".format(require, A[minidx]))
        price = price + shop[minidx][YEN] * require
        require = 0

print(price)

Submission status: Accepted

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


if __name__ == '__main__':
    main()

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

c = 0
p = 0
left = m

for i in range(n):
	if left >= a[i][1]:
		b = a[i][1]
		c += b
		p += a[i][0] * b
		left -= b
	elif left < a[i][1]:
		c += left
		p += a[i][0] * left
		left = 0
        
	if left == 0:
		break
	
print(p)

Submission status: Accepted

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

C=[input().split() for i in range(N)]
B=[]
for i in C:
    B.append(list(map(int,i)))

B.sort()

k=0
l=0#何番目の店
m=0#その店で買う数
money=0
X=0#持ち数
for a,b in B:
    if(M<=0):
        break
    if(b<=M):
        money+=a*b
    else:
        money+=M*a
    M-=b
print(money)

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])
money = 0
for a, b in AB:
  if(M <= 0):
    break
  if(b <= M):
    money += a*b
  else:
    money += M*a
  M -= b
print(money)

Submission status: Accepted

Solution code:
import numpy as np
import math
N, M = [int(num) for num in input().split()]
# M = float(M)
A, B = [], []
for n in range(N):
  a_i, b_i = [int(num) for num in input().split()]
  A.append(a_i)
  B.append(b_i)

A_sort_index = np.argsort(A)
total_val = 0
for index in A_sort_index:
  if M < B[index]:
    total_val += M * A[index]
    break
  else:
    total_val += A[index] * B[index]
    M -= B[index]

print (total_val)

Submission status: Accepted

Solution code:
def int_raw():
    return int(raw_input())

def ss_raw():
    return raw_input().split()

def ints_raw():
    return map(int,ss_raw())

N,M = ints_raw()
ABs = []
for n_i in xrange(N):
    ABs.append(ints_raw())
ABs.sort()

ans = 0
kosuu = 0
for A,B in ABs:
    n_kosuu = kosuu + B
    if n_kosuu>=M:
        ans += (M-kosuu)*A
        kosuu = M
        break
    else:
        ans += A*B
        kosuu = n_kosuu

print ans

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
dct={}
for i in range(n):
    k,v=map(int,input().split())
    if k not in dct.keys():
        dct[k]=v
    else:
        dct[k]+=v
sdct=sorted(dct.items())
yen=0
for k,v in sdct:
    if v<=m:
        m-=v
        yen+=k*v
    else:
        yen+=k*m
        break
print(yen)

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()
sumcost = 0
k = 0
t = 0
while M-k>0:
    buy = min(M-k, A[t][1])
    sumcost += A[t][0]*buy
    k += buy
    t += 1


print(sumcost)

Submission status: Accepted

Solution code:
import sys
size_data = sys.stdin.readline().strip().split(" ")

N = int(size_data[0])
M = int(size_data[1])

shop_stock = []

for i in range(N):
    row = sys.stdin.readline().strip().split(" ")
    shop_stock.append((int(row[0]), int(row[1])))

shop_stock = sorted(shop_stock, key=lambda store: store[0])

money = 0
cans_remaining = M

for shop in shop_stock:
    price, max_cans = shop

    cans_to_buy = min(max_cans, cans_remaining)
    money += cans_to_buy * price
    cans_remaining -= cans_to_buy

print(money)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]
A.sort()
sumcost = 0
k = 0
t = 0
while M-k>0:
    buy = min(M-k, A[t][1])
    sumcost += A[t][0]*buy
    k += buy
    t += 1


print(sumcost)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, AB):
    AB.sort()
    ans = 0

    for a, b in AB:
        if M > b:
            ans += a * b
            M -= b
        else:
            ans += a * M
            M -= M
            break

    return ans


def main():
    N, M = read_int_n()
    AB = [read_int_n() for _ in range(N)]
    print(slv(N, M, AB))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]
A.sort()
sumcost = 0
for i in range(M):
    sumcost += A[0][0]
    A[0][1] -= 1
    if A[0][1] < 1:
        A.pop(0)

print(sumcost)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
input = sys.stdin.readline
 
N, M = [int(i) for i in input().split()]
 
plices = [[int(i) for i in input().split()] for _ in range(N)]
 
plices.sort(key = lambda x:x[0])
 
m = 0
cost = 0
 
for i in range(N):
    if m >= M:
        break
    buy = min(M - m, plices[i][1])
    cost += plices[i][0] * buy
    m += buy
 
print(cost)

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    D = [tuple(map(int, input().split())) for _ in range(N)]
    D.sort()
    ans = 0
    i = 0
    while M > 0:
        a, b = D[i]
        ans += a * min(M, b)
        M -= min(M, b)
        i += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
a = [list(map(int,input().split())) for i in range(n)]
a.sort()
ans = 0
i = 0
while m > 0:
  if a[i][1] > 0:
    a[i][1] -= 1
    ans += a[i][0]
    m -= 1
  else:
    i += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
price = []
for i in range(N):
    A, B = list(map(int, input().split()))
    price.append([A, B])
    
price.sort()

cnt = M
re = 0
for i in range(N):
    A, B = price[i]
    if B < cnt:
        re += B * A
        cnt -= B
    else:
        re += cnt * A
        cnt = 0
        break
print(re)