Problem:


 Princess' Marriage 

 お姫様の嫁入り 

English text is not available in this practice contest.

ある貧乏な国のおてんばで勇敢なお姫様は，ギャンブルの配当がパリミュチュエル方式で決定される事を知ることにより，ギャンブルについて詳しくなった気がしてギャンブルでの勝利を確信した．その結果，今までよりも更に多額のお金をつぎ込み，国民が納めた税金をすべて失うほどの負けを喫してしまった．この事態を重く受け止めた王様は，お姫様を隣の国へ嫁がせることにした．こうすることにより，お姫様を日頃の行いを反省させ，同時に隣国との交友を深めて財政援助をしてもらおうと考えたからである．

お姫様と隣国の王子様はお互いの事が気に入り，また両国の王様間でも政略結婚に関する同意がなされた．お姫様はなけなしのお金を手に意気揚々と隣の国へ出かけた．一方で，お姫様が嫁ぐ動機は王様の一方的な利益追及のためであり，快くないと考える隣国の王子様の側近は，お姫様を亡き者にするために道の途中に無数の刺客達を放った．

お姫様が通る道はすでに決められている．お姫様の通る道には合計 L 個の宿場がある．便宜上，出発地点および到着地点も宿場とし，各宿場を S1, S2, ... SL と呼ぶことにする．お姫様は最初に S1 におり，昇順に (S2, S3 ... という順番で) 宿場を訪れて，最終的に SL へ行くものとする．宿場では金銭を払って護衛を雇うことができ，お金がある限り好きな距離だけ契約してお姫様を守らせることができる．護衛を雇う費用は，距離1につき金1である．お姫様は通る区間内を部分的に守ってもらうことも出来ることに注意せよ．SiとSi+1間の距離はDi，SiとSi+1間で距離1につき刺客に襲われる回数の期待値はPiで与えられている．

お姫様が予算Mを持っていて，刺客に襲われる回数の期待値が最小になるように護衛を雇ったときの，目的地までに刺客に襲われる回数の期待値を求めよ．

Input

入力は複数のデータセットからなる．各データセットは以下のような形式をとる．

N M

D1 P1

D2 P2

...

DN PN

各データセットの最初の行には二つの整数が与えられ，それぞれ区間の数 N(1≦N≦10,000) と，お姫差が持つ予算 M(0≦M≦1,000,000,000) を表す．次の N 行はお姫様が通る道の情報を表す．各行は二つの整数が含まれており，i行目は区間の距離 Di(1≦Di≦10,000) とその間を１単位距離移動したときに襲われる回数の期待値 Pi(0≦PiN=0, M=0 となるデータセットであらわされる．このデータセットに対しては計算結果を出力してはならない．

Output

各データセット毎に，お姫様が目的地までに刺客に襲われる回数の期待値を出力せよ．

Sample Input

2 8
5 6
4 5
3 1
5 10
5 10
5 10
0 0

Output for the Sample Input

5
140



Sample input:
2 8
5 6
4 5
3 1
5 10
5 10
5 10
0 0


Sample output:
5
140

Submission status: Accepted

Solution code:
from operator import itemgetter

#配列のソート
def protect(N,M):
    DP = []
    for i in range(N):
        DP.append(list(map(int, input().split())))

    DP.sort(key=itemgetter(1))
    nokori = 0

    for i in range(N):
        if M > DP[N - i - 1][0]:
            M -= DP[N - i - 1][0]
            DP.pop()
        elif M <= DP[N - i - 1][0]:
            nokori = (DP[N - i - 1][0] - M) * DP[N - i - 1][1]
            M = 0
            DP.pop()
            break

    for i in range(len(DP)):
        nokori += DP[i][0] * DP[i][1]

    print(nokori)


#データの入力

while True:
    NM = input().split()
    N = int(NM[0])
    M = int(NM[1])
    if N==0:
        break
    protect(N,M)

Submission status: Accepted

Solution code:
from operator import itemgetter


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

    DP.sort(key=itemgetter(1))
    nokori = 0

    for i in range(N):
        if M > DP[N - i - 1][0]:
            M -= DP[N - i - 1][0]
            DP.pop()
        elif M <= DP[N - i - 1][0]:
            nokori = (DP[N - i - 1][0] - M) * DP[N - i - 1][1]
            M = 0
            DP.pop()
            break

    for i in range(len(DP)):
        nokori += DP[i][0] * DP[i][1]

    print(nokori)


while True:
    NM = input().split()
    N = int(NM[0])
    M = int(NM[1])
    if N==0:
        break
    protect(N,M)

Submission status: Accepted

Solution code:
# coding: utf-8

n,m=map(int,input().split())
while n!=0:
    d=[]
    p=[]
    
    for i in range(n):
        d_i,p_i=map(int,input().split())
        d.append(d_i)
        p.append((p_i,i)) #タプルでインデックス情報を付加
    #警備がいない場合の期待値を求める
    
    hazard=0
    for i in range(n):
        hazard+=d[i]*p[i][0]
    
    #単位長さあたりの期待値で降順ソート
    p.sort(key=lambda x:-x[0])
    
    for i in range(n):
        rest=d[p[i][1]]
        if m<rest:
            hazard-=m*p[i][0]
            break
        else:
            m-=rest
            hazard-=rest*p[i][0]
        
    print(hazard)
    n,m=map(int,input().split())

Submission status: Accepted

Solution code:
while True:
    n, m = map(int, input().split())
    if n == 0:
        break
    else:
        s = 0
        l = []
        for _ in range(n):
            d, p = map(int, input().split())
            s += d * p
            l.append((p,d))

        l.sort()
        while m > 0 and l:
            a, b = l.pop()
            if m >= b:
                s -= a * b
                m -= b
            else:
                s -= a * m
                m = 0

        print(s)

Submission status: Accepted

Solution code:
while True:
	n,m = map(int, input().split(" "))
	if n+m == 0:
		break
	dp = []
	for i in range(n):
		d,p = map(int, input().split(" "))
		dp.append((d,p))
	ans = 0
	for d,p in sorted(dp, key=lambda x: x[1], reverse=True):
		if m == 0:
			ans += p * d
		elif m < d:
			ans += p * (d - m)
			m = 0
		else:
			m -= d
	print(ans)

Submission status: Accepted

Solution code:
while 1:
    N, M = map(int, input().split())
    if N == M == 0:
        break
    S = []
    for i in range(N):
        S.append(list(map(int, input().split())))
    S.sort(key=lambda x:x[1], reverse=True)
    ans = 0
    for d in S:
        if M >= d[0]:
            M -= d[0]
        else:
            d[0] -= M
            M = 0
            ans += d[0] * d[1]
    print(ans)

Submission status: Accepted

Solution code:
while True:
    n, m = map(int, input().split())
    if n == m == 0:
        break

    li = list()
    total = 0
    for i in range(n):
        d, p = map(int, input().split())
        li.append((p, d))
        total += p * d

    li.sort(reverse = True)
    for p, d in li:
        if d <= m:
            total -= p * d
            m -= d
        else:
            total -= p * m
            break

    print(total)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def main():
    rr = []

    while True:
        n,m = LI()
        if n == 0 and m == 0:
            break
        a = sorted([LI()[::-1] for _ in range(n)], reverse=True)
        r = 0
        for i in range(n):
            ai = a[i]
            if ai[1] <= m:
                m -= ai[1]
                ai[1] = 0
            else:
                ai[1] -= m
                m = 0
            r += ai[0] * ai[1]
        rr.append(r)


    return '\n'.join(map(str, rr))


print(main())

Submission status: Accepted

Solution code:
while True:
    (n, m) = list(map(int, input().split()))
    if n == 0:
        break
    sec = []
    for j in range(n):
        sec.append(list(map(int, input().split())))
    sec.sort(key=lambda x: x[1], reverse=True)
    res = 0
    for e in sec:
        if e[0] <= m:
            m -= e[0]
        elif m == 0:
            res += e[0] * e[1]
        else:
            res += e[1] * (e[0] - m)
            m = 0
    print(res)

Submission status: Accepted

Solution code:
import sys

while True:
    n,m = [int(i) for i in input().split()]
    if n == 0 and m == 0:
        sys.exit()
    dp = []
    ans = 0
    for i in range(n):
        dp.append([int(j) for j in input().split()])
    dp.sort(key=lambda x:x[1],reverse=True)
    for i in range(n):
        if dp[i][0] <= m:
            m -= dp[i][0]
        elif m > 0:
            ans += dp[i][1] * (dp[i][0] - m)
            m = 0
        else:
            ans += dp[i][1] * dp[i][0]
    print(ans)

Submission status: Accepted

Solution code:
da = list(map(int,input().split()))

k = [[0 for i in range(2)]for j in range(10001)]
i = 0
su = 0
j = 0

while da[0] + da[1] != 0:
	i = 0
	su = 0
	j = 0
	for i in range(da[0]):
		k[i][0],k[i][1] = map(int,input().split())


	k = sorted(k,key = lambda x: x[1],reverse = True)

	while j != i + 1:
		if da[1] > k[j][0]:
			da[1] -= k[j][0]
			j += 1
		elif da[1] <= k[j][0] and da[1] > 0:
			su += (k[j][0] - da[1]) * k[j][1]
			da[1] = 0
			j += 1
		else:
			su += k[j][0] * k[j][1]
			j += 1

	print(su)

	da = list(map(int,input().split()))

	k = [[0 for i in range(2)]for j in range(10001)]

Submission status: Accepted

Solution code:
while(True):
    N, M = map(int, input().split())
    if(N == 0 and M == 0):
        break

    DP = []
    for i in range(N):
        DP.append([int(_) for _ in input().split()])

    DP.sort(key=lambda x:x[1])
    DP.reverse()

    for i in range(N):
        decr = min(M, DP[i][0])
        M -= decr
        DP[i][0] -= decr
        if M == 0:
            break

    ans = 0
    for dp in DP:
        ans += dp[0]*dp[1]

    print(ans)

Submission status: Accepted

Solution code:
while 1:
    N,M=map(int,input().split())
    if not N and not M:break
    s=0
    t=[]
    for _ in range(N):
        a,b=map(int,input().split())
        s+=a*b
        t.extend([(b,a)])
    for i in sorted(t)[::-1]:
        if i[1]<=M:
            s-=i[0]*i[1]
            M-=i[1]
        elif 0<M<i[1]:
            s-=M*i[0]
            M=0
            break
    print(s)

Submission status: Accepted

Solution code:
import sys

while True:
    n, m = map(int, sys.stdin.readline().split())
    if n == 0 and m == 0:
        break
    route = []
    for i in xrange(n):
        d, p = map(int, sys.stdin.readline().split())
        route.append([p, d])
    route.sort(reverse=True)
    count = 0
    for c, l in route:
        if l < m:
            m -= l
        elif m <= l:
            count += (l - m) * c
            m = 0
    print count

Submission status: Accepted

Solution code:
while True:
    N,M=map(int,raw_input().split())
    if N==M==0:break
    L=[map(int,raw_input().split()) for i in range(N)]
    L=[(j,i) for i,j in L]
    L.sort()
    L=reversed(L)
    cost=0
    for p,d in L:
        cost+=p*(max(d-M,0))
        M=max(M-d,0)
    print cost

Submission status: Accepted

Solution code:
while True:
    n,m =map(int, input().split())
    if n==0 and m==0:
        break
    temp=[]
    distance=0
    
    for i in range(n):
        d,p= map(int,input().split())
        distance = distance + d
        temp.append([p,d])

    temp.sort()
    temp.reverse()
    
    if distance <= m:
        print(0)
        
    else:
        money=m
        while True:
            if money<= temp[0][1]:
                temp[0][1]-=money

                break
            else:
                money-=temp[0][1]
                temp.pop(0)
        ans=0
        for i in range(0,len(temp)):
            ans+= temp[i][0]*temp[i][1]
        print(ans)

Submission status: Accepted

Solution code:
while True:
    n,m=map(int,input().split())
    if n==0:
        break
    else:
        pdlist=[]
        for i in range(0,n):
            d,p=map(int,input().split())
            pdlist.append([p,d])
        pdlist.sort()
        i=n-1
        while True:
            if i<0:
                break
            elif pdlist[i][1]-m<0:
                a=pdlist[i][1]
                pdlist[i][1]=0
                m=(m-a)
                i=i-1
            else:
                pdlist[i][1]=pdlist[i][1]-m
                break
        count=0
        for i in range(0,n):
            count=count+pdlist[i][0]*pdlist[i][1]
        print(count)

Submission status: Accepted

Solution code:
while True:
  n,m=map(int,input().split())
  matrix=[]
  if n==m==0:
    break
  else:
    for i in range(n):
      D,P=map(int,input().split())
      matrix.append([D,P])
      matrix.sort(key = lambda x:x[1],reverse=True)
    i=0
    while m>0 and i<=n-1:
      pp=matrix[i][1]
      dd=matrix[i][0]
      if dd > m:
        matrix[i][0]=dd-m
        m=0
      else:
        matrix[i][1]=0
        m=m-dd
        i+=1
    sum_matrix=[mm[0]*mm[1] for mm in matrix]
    print(sum(sum_matrix))

Submission status: Accepted

Solution code:
while True:
    n,m =map(int, input().split())
    if n==0 and m==0:
        break
    a=[]
    length=0
    for i in range(0,n):
        d,p= map(int,input().split())
        length+= d
        a.append([p,d])

    a.sort()
    a.reverse()
    if length <= m:
        print(0)
    else:
        zankin=m
        flag=0
        while True:
            if zankin<= a[0][1]:
                a[0][1]-=zankin

                break
            else:
                zankin-=a[0][1]
                a.pop(0)
        ans=0
        for i in range(0,len(a)):
            ans+= a[i][0]*a[i][1]
        print(ans)

Submission status: Accepted

Solution code:
#月曜五時間目　実践的プログラミング
#ソートして襲われてはいけない時には、できるだけ護衛をつけるようにすることが最適であるので
#ソートした後に左から貪欲に護衛をつけていって、お金がなくなったらそのまま何もしないと言う戦略で正解した。
#時間:15分
#Princess' Marriage
#学んだこと：ソートして貪欲に考える
#URL: https://onlinejudge.u-aizu.ac.jp/challenges/search/titles/2019
def solve():
    N,M=map(int,input().split())
    if N==0 and M==0:
        #終了条件
        exit()
    else:
        d=[tuple(map(int,input().split())) for _ in range(N)]
        d.sort(key=lambda x:-x[1])
        #襲われたやすいところから優先的に保護するためにソート
        cnt=0
        money=M
        #money=所持金、cnt=襲われる期待値の累計和
        for que in d:
            distance,value=que
            if money>=distance:
                money-=distance
            elif money<distance:
                cnt+=value*(distance-money)
                money=0
        print(cnt)
        return solve()

if __name__=="__main__":
    solve()

Submission status: Accepted

Solution code:
while True:
        N, M = map(int, input().split())  # 宿の数N, 予算M
        if N == 0 and M == 0:
            break

        dangers = {}  # Pをkeyとして頑張る
        for _ in range(N):
            distance, P = map(int, input().split())
            if P not in dangers:
                dangers[P] = distance
            else:
                dangers[P] += distance

        # 期待値の降順でソート
        dangers = sorted(dangers.items(), key=lambda x:x[0], reverse=True)
        ans = 0
        for i in range(len(dangers)):
            P, distance = dangers[i][0], dangers[i][1]
            if M >= distance:
                M -= distance
                distance = 0
            else:
                distance -= M
                M = 0
            ans += P*distance
        print(ans)

Submission status: Accepted

Solution code:

while True:
	n,m = map(int,input().split())
	if n+m == 0: break
	road = [list(map(int, input().split())) for _ in range(n) ]
	road = sorted(road, key=lambda x:-x[1])
	d = 0
	for a,b in road:
		if a <= m:
				m -= a
		else:
			d += (a - m) * b
			m = 0
	print(d)

Submission status: Accepted

Solution code:
while 1:
    n, m = map(int, input().split())
    if n == 0:
        break

    data = []
    for _ in range(n):
        d, p = map(int, input().split())
        data.append([d, p])

    data = sorted(data, key=lambda x: -x[1])
    for d in data:
        if m <= 0:
            break
        if d[0] <= m:
            m -= d[0]
            d[0] = 0
        else:
            d[0] -= m
            m = 0

    ans = 0
    for d in data:
        ans += d[0] * d[1]

    print(ans)

Submission status: Accepted

Solution code:
readline = open(0).readline
while 1:
    N, M = map(int, readline().split())
    if N == M == 0:
        break
    Q = []
    for i in range(N):
        d, p = map(int, readline().split())
        Q.append((p, d))
    Q.sort(reverse=1)
    ans = 0
    for p, d in Q:
        if M >= 0:
            x = min(M, d)
            M -= x; d -= x
        ans += d * p
    print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
while 1:
    data=[]
    n,m=map(int,input().split())
    if n==m==0:
        break
    for i in range(n):
        d,p=map(int,input().split())
        data.append((d,p))
    data=sorted(data,key=lambda x:(-x[1],-x[0]))
    for i in range(n):
        if data[i][0]<=m:
            m-=data[i][0]
            data[i]=(0,data[i][1])
        else:
            data[i]=(data[i][0]-m,data[i][1])
            m=0
            break
    ans=0
    for i in range(n):
        ans+=data[i][0]*data[i][1]
    print(ans)

Submission status: Accepted

Solution code:
while True:
    n, m = map(int, input().split())
    if n == 0:break
    l = []
    for i in range(n):
        l.append(list(map(int, input().split())))
    l.sort(key=lambda x:x[1])
    l.reverse()
    for i in range(n):
        if m >= l[i][0]:
            m -= l[i][0]
            l[i][0] = 0
        elif m != 0:
            l[i][0] -= m
            m = 0
        else:
            break
    ans = 0
    for s in l:
        ans += s[0] * s[1]
    print(ans)

Submission status: Runtime Error

Solution code:
while 1:
    n,m= list(map(int,input().split(' ')))
    if n ==m ==0:break
    D =[]
    for _ in range(n):
        d_i,p_i = list(map(int,input().split(' ')))
        D.append((d_i,p_i))
    sorted(D,key = lambda x:x[0])
    while m > 0:
        temp = D.pop(0)
        if temp[0] > m:
            temp = (temp[0] - m,temp[1])
            m=0
        else: 
            m -= temp[0]
            temp = (0,temp[1])
        D.append(temp)
    ans = 0
    for i in D:
        ans += i[0]*i[1]
    print(ans)

Submission status: Runtime Error

Solution code:
while 1:
    n,m= list(map(int,input().split(' ')))
    if n ==m ==0:break
    D =[]
    for _ in range(n):
        d_i,p_i = list(map(int,input().split(' ')))
        D.append((d_i,p_i))
    sorted(D,key = lambda x:x[0])
    while m > 0:
        temp = D.pop(0)
        if temp[0] > m:
            temp = (temp[0] - m,temp[1])
            m=0
        else: 
            m -= temp[0]
            temp = (0,temp[1])
        D = D + [temp]
    ans = 0
    for i in D:
        ans += i[0]*i[1]
    print(ans)

Submission status: Runtime Error

Solution code:
import collections 
while 1:
    n,m= list(map(int,input().split(' ')))
    if n ==m ==0:break
    D = collections.deque()
    for _ in range(n):
        d_i,p_i = list(map(int,input().split(' ')))
        D.append((d_i,p_i))
    sorted(D,key = lambda x:x[0])
    while m > 0:
        temp = D.popleft()
        if temp[0] > m:
            temp = (temp[0] - m,temp[1])
            m=0
        else: 
            m -= temp[0]
            temp = (0,temp[1])
        D.append(temp)
    ans = 0
    for i in D:
        ans += i[0]*i[1]
    print(ans)

Submission status: Runtime Error

Solution code:
import collections 
import time 
while 1:
    n,m= list(map(int,input().split(' ')))
    if n ==m ==0:break
    D = collections.deque()
    time.sleep(20)
    for _ in range(n):
        d_i,p_i = list(map(int,input().split(' ')))
        D.append((d_i,p_i))
    sorted(D,key = lambda x:x[0])
    while m > 0:
        temp = D.popleft()
        if temp[0] > m:
            temp = (temp[0] - m,temp[1])
            m=0
        else: 
            m -= temp[0]
            temp = (0,temp[1])
        D.append(temp)
    ans = 0
    for i in D:
        ans += i[0]*i[1]
    print(ans)

Submission status: Runtime Error

Solution code:
import collections 
while 1:
    n,m= list(map(int,input().split(' ')))
    if n == m ==0:break
    D = collections.deque()
    for _ in range(n):
        d_i,p_i = list(map(int,input().split(' ')))
        if p_i !=0: 
            D.append((d_i,p_i))
    sorted(D,key = lambda x:x[0])
    while m > 0:
        temp = D.popleft()
        if temp[0] > m:
            temp = (temp[0] - m,temp[1])
            m=0
            D.append(temp)
        else: 
            m -= temp[0]
            temp = (0,temp[1])
    ans = 0
    for i in D:
        ans += i[0]*i[1]
    print(ans)

Submission status: Runtime Error

Solution code:
while True:
    N,M = map(int,input().strip().split(" "))
    if [N,M] == [0,0]:
        break
    L = []
    S = 0 
    for i in range(N):
        l = list(map(int,input().strip().split(" ")))
        l.reverse() 
        L.append(l)
        S = S + l[0]*l[1]
    L.sort()
    j = 0
    while M > 0:
        if M >= L[N-j-1][1]:
            S = S - L[N-j-1][0]*L[N-j-1][1]
            M = M - L[N-j-1][1]
            j = j + 1
        else:
            S = S - L[N-j-1][0]*M
            M = M - L[N-j-1][1]
    print(S)

Submission status: Runtime Error

Solution code:
#Princess's Marriage
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2019&lang=jp
#席の位置：右中央


#Nは区間の個数
#Mは予算
#Dは区間の距離
#Pはその間を１単位距離移動したときに襲われる回数の期待値

#お姫様が予算Mを持っていて，刺客に襲われる回数の期待値が最小になるように護衛を雇ったときの，目的地までに刺客に襲われる回数の期待値

while True:
    N,M = map(int,input().strip().split(" "))
    if [N,M] == [0,0]:
        break
    L = []
    S = 0 #Sが襲われる回数の期待値
    for i in range(N):
        l = list(map(int,input().strip().split(" ")))
        l.reverse() #ソートするとき具合がわるいので[P,D]の順に入れ替え
        L.append(l)
        S = S + l[0]*l[1]
    L.sort()
    j = 0
    while M > 0:
        if M >= L[N-j-1][1]:
            S = S - L[N-j-1][0]*L[N-j-1][1]
            M = M - L[N-j-1][1]
            j = j + 1
        else:
            S = S - L[N-j-1][0]*M
            M = M - L[N-j-1][1]
    print(S)

Submission status: Runtime Error

Solution code:
while True:
    N,M = map(int,input().strip().split(" "))
    if [N,M] == [0,0]:
        break
    L = []
    S = 0 #Sが襲われる回数の期待値
    for i in range(N):
        l = list(map(int,input().strip().split(" ")))
        l.reverse() #ソートするとき具合がわるいので[P,D]の順に入れ替え
        L.append(l)
        S = S + l[0]*l[1]
    L.sort()
    j = 0
    while M > 0:
        if M >= L[N-j-1][1]:
            S = S - L[N-j-1][0]*L[N-j-1][1]
            M = M - L[N-j-1][1]
            j = j + 1
        else:
            S = S - L[N-j-1][0]*M
            M = M - L[N-j-1][1]
    print(S)

Submission status: Runtime Error

Solution code:
while True:
    N,M = map(int,input().strip().split(" "))
    if [N,M] == [0,0]:
        break
    L = []
    S = 0 #Sが襲われる回数の期待値
    for i in range(N):
        l = list(map(int,input().strip().split(" ")))
        l.reverse() #ソートするとき具合がわるいので[P,D]の順に入れ替え
        L.append(l)
        S = S + l[0]*l[1]
    L.sort()
    j = N
    while M > 0:
        if M >= L[j-1][1]:
            S = S - L[j][0]*L[j][1]
            M = M - L[j][1]
            j = j - 1
        else:
            S = S - L[j][0]*M
            M = M - L[j][1]
    print(S)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
l=[]
for i in range(n):
    l1=list(map(input().split()))
    l1=l1[::-1]
    l.append(l1)
l=sorted(l)
s=0
for i in range(n):
    s+=l[i][0]*l[i][1]
for i in range(n):
    if m-l[i][1]>=0:
        s-=l[i][0]*l[i][1]
        m-=l[i][1]
    else:
        s-=l[i][0]*m
print(s)

Submission status: Runtime Error

Solution code:
while True:
  N,M = map(int,input().split())
  if N == M == 0:
    break
  else:
    L = []
	for i in range(N):
	  L.append(list(map(int,input().split())))
	L = sorted(L, key = lambda x:x[1])
	L.reverse()
	ans = 0
	for i in range(len(L)):
	  if M > 0:
	    if M-L[i][0] >= 0:
		  M -= L[i][0]
		else:
		  ans += (L[i][0]-M)*L[i][1]
		  M = 0
     else:
	   ans += L[i][0]*L[i][1]
    print(ans)

Submission status: Runtime Error

Solution code:
while True:
    N,M = map(int,input().split())
    if N == 0:
        break
    expect = 0
    a = []
    exsum = 0
    for i in range(N): #二次元配列を作る
        a.append(list(map(int,input().split())))
        exsum += a[i][0]*a[i][1] #誰も雇わなかった場合の期待値
    b = sorted(a, key=lambda x: x[1]) #危険度の高い区間ほど後ろにくるように並べる
    i = N-1
    while M > 0: #危険度が高い区間（配列のうしろ）から順に人を雇っていく
        if b[i][0] <= M:
            exsum -= b[i][0]*b[i][1]
            M -= b[i][0]
            i -= 1
        else:
            exsum -= b[i][1]*M
            M = 0
            i -= 1
    print(exsum)

Submission status: Runtime Error

Solution code:
while True:
    res=0
    n,m = map(int,input().split())
    if n == 0:
        break
    DandP = []
    for _ in range(n):
        DandP.append(list(map(int,input().split())))
    DandP.sort(key=lambda x:x[1],reverse = True)
    for _ in range(m):
        if DandP[0][0]==0:
            DandP = DandP[1:]
        DandP[0][0] -= 1
    for i in range(len(DandP)):
        res += DandP[i][0]*DandP[i][1]
    print(res)

Submission status: Runtime Error

Solution code:
while True:
    res=0
    n,m = map(int,input().split())
    if n == 0:
        break
    DandP = []
    for _ in range(n):
        DandP.append(list(map(int,input().split())))
    DandP.sort(key=lambda x:x[1],reverse = True)
    for _ in range(m):
        if DandP[0][0]==0:
            DandP = DandP[1:]
        if len(DandP) >0:
            DandP[0][0] -= 1
    for i in range(len(DandP)):
        res += DandP[i][0]*DandP[i][1]
    print(res)

Submission status: Runtime Error

Solution code:
while True:
    n, m = map(int, input().split())
    ls = []
    if n == 0: break
    for i in range(n):
        d, p = map(int, input().split())
        ls.append([d,p])
    ls.sort(key=lambda x:x[1], reverse=True)
    j = 0
    for i in range(m):
        ls[j][0] -= 1
        if ls[j][0] == 0:
            j += 1
    print(sum(x[0] * x[1] for x in ls))

Submission status: Runtime Error

Solution code:
while True:
    n, m = map(int, input().split())
    ls = []
    if n == 0: break
    for i in range(n):
        d, p = map(int, input().split())
        ls.append([d,p])
    ls.sort(key=lambda x:x[1], reverse=True)
    j = 0
    for i in range(m):
        ls[j][0] -= 1
        if ls[j][0] == 0:
            j += 1
            if j == (len(ls)):
                break
    print(sum(x[0] * x[1] for x in ls))

Submission status: Runtime Error

Solution code:
loop {
    n, m = gets.split.map &:to_i
    break if n == 0
    road = (1..n).map{ gets.split.map &:to_i }
    road.sort_by!(&:last).reverse!
    while !road.empty?
        if road[0][0] > m
            road[0][0] -= m
            break
        else
            m -= road[0][0]
            road.shift
        end
    end
    p road.map{|d, q| d * q}.inject &:+
}

Submission status: Runtime Error

Solution code:
loop {
    n, m = gets.split.map &:to_i
    break if n == 0
    road = (1..n).map{ gets.split.map &:to_i }
    road.sort_by!(&:last).reverse!
    while !road.empty?
        if road[0][0] > m
            road[0][0] -= m
            break
        else
            m -= road[0][0]
            road.shift
        end
    end
    p road.map{|d, q| d * q}.inject(0, &:+)
}

Submission status: Runtime Error

Solution code:
roadcnt,money = (int(n) for n in input().split(" "))
while True:
    road = []
    for r in range(roadcnt):
        road.append([int(n) for n in input().split(" ")])
    road = sorted(road,key=lambda x:x[1])
    while money > 0:
        if road[-1][0] - money < 0:
            money -= road[-1][0]
            road.pop()
        else:
            road[-1][0] -= money
            break
    ans = 0
    for ro in road:
        ans += ro[0] * ro[1]
    print(ans)
    roadcnt,money = (int(n) for n in input().split(" "))
    if roadcnt == 0 and money == 0:
        break

Submission status: Runtime Error

Solution code:
while True:
    n, m = map(int, input().split())
    dpList = []
    if n + m < 1:
        break
    for i in range(n):
        row = list(map(int,input().split()))
        dpList.append(row)
        dpList = sorted(dpList, key = lambda x:x[1], reverse = True)
    for i in range(n):
        if m - dpList[i][0] <= 0:
            num = (dpList[i][0] - m) * dpList[i][1]
            for j in range(i + 1, n):
                num += dpList[j][0] * dpList[j][1] 
            print(num)
            break
        else:
            m -= dpList[i][0]

Submission status: Runtime Error

Solution code:
while True:
    n, m = map(int, input().split())
    dpList = []
    if n + m < 1:
        break
    for i in range(n):
        row = list(map(int,input().split()))
        dpList.append(row)
        dpList = sorted(dpList, key = lambda x:x[1], reverse = True)
    num = 0
    for i in range(n):
        if m >= dpList[i][0]:
            m -= dpList[i][0]
        else:
            num = (dpList[i][0] - m) * dpList[i][1]
    print(num)

Submission status: Runtime Error

Solution code:
while True:
    n, m = map(int, input().split())
    if (n, m) == (0, 0):
        break
    dp = [list(map(int, input().split())) for i in range(n)]
    dp = sorted(dp, key=lambda kv:kv[1], reverse=True)
    r = 0
    for d,p in dp:
        if m >= d:
            m -= d
        else:
            r += p*(d-m)
            m = 0
    print(r

Submission status: Runtime Error

Solution code:
while True:
    n, m = map(int, input().split())
    dpList = []
    if n + m < 1:
        break
    for i in range(n):
        row = list(map(int,input().split()))
        dpList.append(row)
        dpList = sorted(dpList, key = lambda x:x[1], reverse = True)
    num = 0
    for i in range(n):
        if m >= dpList[i][0]:
            m -= dpList[i][0]
        else:
            num += (dpList[i][0] - m) * dpList[i][1]
    print(num)

Submission status: Runtime Error

Solution code:
while True:
    n, m = map(int, input().split())
    dpList = []
    if (n,m) == (0,0):
        break
    for i in range(n):
        row = list(map(int,input().split()))
        dpList.append(row)
        dpList = sorted(dpList, key = lambda x:x[1], reverse = True)
    num = 0
    for i in range(n):
        if m >= dpList[i][0]:
            m -= dpList[i][0]
        else:
            num += (dpList[i][0] - m) * dpList[i][1]
    print(num)

Submission status: Runtime Error

Solution code:
while True:
    n, m = map(int, input().split())
    if n == 0:
        break
    risks = [(p, d) for d, p in (map(int, input().split()) for _ in range(n))]
    risks.sort()
    while m:
        p, d = risks.pop()
        if d >= m:
            remain = p * (d - m)
            break
        m -= d
    print(remain + sum(p * d for p, d in risks))

Submission status: Runtime Error

Solution code:
while True:
    n, m = map(int, input().split())
    if n == 0:
        break
    risks = [(p, d) for d, p in (map(int, input().split()) for _ in range(n))]
    risks.sort()
    remain = 0
    while m:
        p, d = risks.pop()
        if d >= m:
            remain = p * (d - m)
            break
        m -= d
    print(remain + sum(p * d for p, d in risks))

Submission status: Runtime Error

Solution code:
# coding: utf-8

n,m=map(int,input().split())
while n!=0:
    d=[]
    p=[]
    
    for i in range(n):
        d_i,p_i=map(int,input().split())
        d.append(d_i)
        p.append((p_i,i)) #タプルでインデックス情報を付加
    
    #単位長さあたりの期待値で降順ソート
    p.sort(key=lambda x:-x[0])
    
    #警備がいない場合の期待値を求める
    hazard=0
    for i in range(n):
        hazard+=d[i]*p[i][0]
    
    for i in range(n):
        rest=d[p[i][1]]
        while rest!=0:
            if m==0:
                break
            m-=1
            rest-=1
            hazard-=p[i][0]
        else:
            continue
        break
        
    print(hazard)
    
    n,m=map(int,input().split())

Submission status: Runtime Error

Solution code:
while True:
    n, m = map(int, input().split())
    if n == 0:
        break
    else:
        s = 0
        l = []
        for _ in range(n):
            d, p = map(int, input().split())
            s += d * p
            l.append((p,d))

        l.sort()
        while m > 0:
            a, b = l.pop()
            if m >= b:
                s -= a * b
                m -= b
            else:
                s -= a * m
                m = 0

        print(s)

Submission status: Runtime Error

Solution code:
da = list(map(int,input().split()))
k = [[0]*2]*10000
i = 0
su = 0
j = 0
while da[0] != 0 and da[1] != 0:

	i = 0
	su = 0
	j = 0
	for i in range(da[0]):
		k[i][0],k[i][1] = map(int,input().split())
		su += k[i][0] * k[i][1]

	sorted(k)
	while da[1] != 0:
		if da[1] > k[j][0]:
			su -= k[j][0]* k[j][1]
			da[1] -= k[j][0]
			j += 1

		else:
			su -= da[1] * k[j][1]
			da[1] = 0
			j += 1

	print(su)

	da = list(map(int,input().split()))
	k = [[0]*2]*10000