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: Wrong Answer

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:
        if len(D) ==0:break
        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: Wrong Answer

Solution code:
# AOJ2019
shukuba = []
n = 0
m = 0

def solve():
    shukuba.sort(key = lambda x: x[0])
    s = sum(map(lambda x: x[0], shukuba)) - m
    if s <= 0:
        return 0
    e = 0
    i = 0
    while s > 0:
        d = shukuba[i][0] if s >= shukuba[i][0] else s
        e += shukuba[i][1] * d
        s -= d
        i += 1
    return e

while True:
    shukuba = []
    line = input()
    n, m = map(int, line.split())
    if n == 0 and m == 0:
        break
    for _ in range(0, n):
        c = list(map(int, list(input().split())))
        shukuba.append(c)
    print(solve())

Submission status: Wrong Answer

Solution code:
while 1:
    N,M = map(int,raw_input().split())
    if N == M == 0: break
    DP = [map(int,raw_input().split()) for _ in xrange(N)]
    DP = sorted(DP, key = lambda x:x[1], reverse = True)

    ans = 0
    for i in range(N):
        if M-DP[i][0] >= 0: M -= DP[i][0]
        else:
            ans += DP[i][1]*(DP[i][0]-M)
            ans += sum(DP[j][1]*DP[j][0] for j in xrange(N-i-1))
            break
    print ans

Submission status: Wrong Answer

Solution code:
while True:
    n, m = map(int, input().split())
    if n == 0 and m == 0:
        exit()
    sections = []
    for i in range(n):
        d, p = map(int, input().split())
        sections.append([p, d])
    sections.sort()
    sections.reverse()

    e = 0
    for p, d in sections:
        if d < m:
            m -= d
            d = 0
        elif m < d:
            d -= m
            m = 0
        e += p * d
    print(e)

Submission status: Wrong Answer

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

    e = 0
    for p, d in sections:
        if d < m:
            m -= d
            d = 0
        elif m < d:
            d -= m
            m = 0
        e += p * d
    print(e)

Submission status: Wrong Answer

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: Wrong Answer

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]]
        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: Wrong Answer

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] != 0 and da[1] != 0:

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


	sorted(k,key = lambda x: x[1],reverse = True)
	while da[1] != 0 and j != i:
		if da[1] >= k[j][0]:
			su -= k[j][0] * k[j][1]
			da[1] -= k[j][0]
			j += 1

		elif da[1] < k[j][0]:
			su -= da[1] * k[j][1]
			da[1] = 0

	print(su)

	da = list(map(int,input().split()))
	if da[0] == 0 and da[1] == 0:
		break
	k = [[0 for i in range(2)]for j in range(10001)]

Submission status: Wrong Answer

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] != 0 and da[1] != 0:
	i = 0
	su = 0
	j = 0
	for i in range(da[0]):
		k[i][0],k[i][1] = list(map(int,input().split()))
		su += k[i][0] * k[i][1]


	sorted(k,key = lambda x: x[1],reverse = True)
	while da[1] > 0 and j != i:
		if da[1] >= k[j][0] and j != i:
			su -= k[j][0] * k[j][1]
			da[1] -= k[j][0]
			j += 1
		else:
			su -= da[1] * k[j][1]
			da[1] = 0

	print(su)

	da = list(map(int,input().split()))
	if da[0] == 0 and da[1] == 0:
		break
	k = [[0 for i in range(2)]for j in range(10001)]

Submission status: Wrong Answer

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] != 0 and da[1] != 0:
	i = 0
	su = 0
	j = 0
	for i in range(da[0]):
		k[i][0],k[i][1] = list(map(int,input().split()))
		su += k[i][0] * k[i][1]


	sorted(k,key = lambda x: x[1],reverse = True)
	while da[1] > 0 and j != i - 1:
		if da[1] >= k[j][0] and j != i:
			su -= k[j][0] * k[j][1]
			da[1] -= k[j][0]
			j += 1
		else:
			su -= da[1] * k[j][1]
			da[1] = 0

	print(su)

	da = list(map(int,input().split()))
	if da[0] == 0 and da[1] == 0:
		break
	k = [[0 for i in range(2)]for j in range(10001)]

Submission status: Wrong Answer

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] != 0 and da[1] != 0:
	i = 0
	su = 0
	j = 0
	for i in range(da[0]):
		k[i][0],k[i][1] = list(map(int,input().split()))
		su += k[i][0] * k[i][1]


	sorted(k,key = lambda x: x[1],reverse = True)
	while da[1] > 0 and j != i + 1:
		if da[1] >= k[j][0] and j != i + 1:
			su -= k[j][0] * k[j][1]
			da[1] -= k[j][0]
			j += 1
		else:
			su -= da[1] * k[j][1]
			da[1] = 0

	print(su)

	da = list(map(int,input().split()))
	if da[0] == 0 and da[1] == 0:
		break
	k = [[0 for i in range(2)]for j in range(10001)]

Submission status: Wrong Answer

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] != 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,key = lambda x: x[1],reverse = True)
	while da[1] > 0 and j != i + 1:
		if da[1] >= k[j][0] and j != i + 1:
			su -= k[j][0] * k[j][1]
			da[1] -= k[j][0]
			j += 1
		elif j == i:
			da[1] = 0
		else:
			su -= da[1] * k[j][1]
			da[1] = 0

	print(su)

	da = list(map(int,input().split()))
	if da[0] == 0 and da[1] == 0:
		break
	k = [[0 for i in range(2)]for j in range(10001)]

Submission status: Wrong Answer

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] != 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,key = lambda x: x[1],reverse = True)
	while da[1] > 0 and j != i + 1:
		if da[1] >= k[j][0] and j != i + 1:
			su -= k[j][0] * k[j][1]
			da[1] -= k[j][0]
			j += 1
		elif j == i + 1:
			da[1] = 0
		else:
			su -= da[1] * k[j][1]
			da[1] = 0

	print(su)

	da = list(map(int,input().split()))
	if da[0] == 0 and da[1] == 0:
		break
	k = [[0 for i in range(2)]for j in range(10001)]

Submission status: Wrong Answer

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] != 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,key = lambda x: x[1],reverse = True)
	while da[1] > 0 and j != i + 1:
		if da[1] >= k[j][0]:
			su -= k[j][0] * k[j][1]
			da[1] -= k[j][0]
			j += 1
		elif j == i + 1:
			da[1] = 0
		else:
			su -= da[1] * k[j][1]
			da[1] = 0

	print(su)

	da = list(map(int,input().split()))
	if da[0] == 0 and da[1] == 0:
		break
	k = [[0 for i in range(2)]for j in range(10001)]

Submission status: Wrong Answer

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] != 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())


	sorted(k,key = lambda x: x[1],reverse = True)
	while da[1] > 0 and j != i + 1:
		if da[1] >= k[j][0]:
			su -= k[j][0] * k[j][1]
			da[1] -= k[j][0]
			j += 1
		elif j == i + 1:
			da[1] = 0
		else:
			su -= da[1] * k[j][1]
			da[1] = 0

	for i in range(da[0]):
		su += k[i][0] * k[i][1]

	print(su)

	da = list(map(int,input().split()))
	if da[0] == 0 and da[1] == 0:
		break
	k = [[0 for i in range(2)]for j in range(10001)]

Submission status: Wrong Answer

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] != 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())


	sorted(k,key = lambda x: x[1],reverse = True)
	while da[1] > 0 and 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
		else:
			su += k[j][0] * k[j][1]

	print(su)

	da = list(map(int,input().split()))
	if da[0] == 0 and da[1] == 0:
		break
	k = [[0 for i in range(2)]for j in range(10001)]

Submission status: Wrong Answer

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] != 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())


	sorted(k,key = lambda x: x[1],reverse = True)
	while da[1] > 0 and 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
		else:
			su += k[j][0] * k[j][1]

	print(su)

	da = list(map(int,input().split()))
	if da[0] == 0 and da[1] == 0:
		break
	k = [[0 for i in range(2)]for j in range(10001)]

Submission status: Wrong Answer

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


	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: Wrong Answer

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] != 0 and da[1] != 0:

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

	k = sorted(k,key = lambda x: x[1],reverse = True)
	while da[1] != 0 and j != i+1:
		if da[1] >= k[j][0]:
			su -= k[j][0] * k[j][1]
			da[1] -= k[j][0]
			j += 1
		elif da[1] > 0 and da[1] < k[j][0] and j != i + 1:
			su -= da[1] * k[j][1]
			da[1] = 0

	print(su)

	da = list(map(int,input().split()))
	if da[0] == 0 and da[1] == 0:
		break
	k = [[0 for i in range(2)]for j in range(10001)]

Submission status: Wrong Answer

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] != 0 and da[1] != 0:

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

	k = sorted(k,key = lambda x: x[1],reverse = True)
	while da[1] != 0 and j != i+1:
		if da[1] >= k[j][0]:
			su -= k[j][0] * k[j][1]
			da[1] -= k[j][0]
			j += 1
		elif da[1] > 0 and da[1] < k[j][0]:
			su -= da[1] * k[j][1]
			da[1] = 0
            
	print(su)

	da = list(map(int,input().split()))
	if da[0] == 0 and da[1] == 0:
		break
	k = [[0 for i in range(2)]for j in range(10001)]

Submission status: Time Limit Exceeded

Solution code:
while True:
    N,M = map(int,input().strip().split(" "))
    if [N,M] == [0,0]:
        break
    D = 0 #目的地までの総距離
    L = []
    for i in range(N):
        d,p = map(int,input().strip().split(" "))
        for j in range(d):
            L.append(p)
        D = D + d
    L.sort()
    S = 0 #Sが襲われる回数の期待値
    for k in range(D-M):
        S = S + L[k]
    print(S)

Submission status: Time Limit Exceeded

Solution code:
while True:
    N,M = map(int,input().strip().split(" "))
    if [N,M] == [0,0]:
        break
    D = 0 #目的地までの総距離
    L = []
    for i in range(N):
        d,p = map(int,input().strip().split(" "))
        for j in range(d):
            L.append(p)
    L.sort()
    S = 0 #Sが襲われる回数の期待値
    for k in range(len(L)-M):
        S = S + L[k]
    print(S)

Submission status: Time Limit Exceeded

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 len(DandP) >0:
            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: Time Limit Exceeded

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)
    while m > 0:
        if len(DandP)>0:
            if m >= DandP[0][0]:
                m -= DandP[0][0]
                DandP = DandP[1:]
            elif m < DandP[0][0]:
                DandP[0][0] -= m
                m = 0
    for i in range(len(DandP)):
        res += DandP[i][0]*DandP[i][1]
    print(res)

Submission status: Memory Limit Exceeded

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 += [p] * d
    ls.sort(reverse=True)
    print(sum(ls[m:]))
#    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: Accepted

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

Submission status: Accepted

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))
    D = sorted(D,key = lambda x:x[1],reverse = True)
    while m > 0:
        if len(D) ==0:break
        temp = D.pop(0)
        if temp[0] > m:
            temp = (temp[0] - m,temp[1])
            m=0
            D.append(temp)
        else: 
            m -= temp[0]      
    ans = 0
    for i in D:
        ans += i[0]*i[1]
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

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()
    for j in range(0,N):
        t = N-j-1
        if M >= L[t][1]:
            S = S - L[t][0]*L[t][1]
            M = M - L[t][1]
        elif 0 < M:
            S = S - L[t][0]*M
            M = M - L[t][1]
    print(S)

Submission status: Accepted

Solution code:
# AOJ2019
shukuba = []
n = 0
m = 0

def solve():
    shukuba.sort(key = lambda x: x[1])
    s = sum(map(lambda x: x[0], shukuba)) - m
    if s <= 0:
        return 0
    e = 0
    i = 0
    while s > 0:
        d = shukuba[i][0] if s >= shukuba[i][0] else s
        e += shukuba[i][1] * d
        s -= d
        i += 1
    return e

while True:
    shukuba = []
    line = input()
    n, m = map(int, line.split())
    if n == 0 and m == 0:
        break
    for _ in range(0, n):
        c = list(map(int, list(input().split())))
        shukuba.append(c)
    print(solve())

Submission status: Accepted

Solution code:
b=True
while b:
  n,m=map(int,input().split())
  if n==0 and m==0:
    b=False
    exit
  else:
    l=[]
    for i in range(n):
      l1=list(map(int,input().split()))
      l1=l1[::-1]
      l.append(l1)
    l=sorted(l)
    l=l[::-1]
    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
          break
    print(s)

Submission status: Accepted

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

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

Submission status: Accepted

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 and i >= 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: Accepted

Solution code:
while True:
    n, m = (int(s) for s in input().split())
    if not n:
        break

    sections = sorted(([int(s) for s in input().split()] for i in range(n)),
                      key=lambda x: x[1], reverse=True)

    for i, (d, p) in enumerate(sections):
        m -= d
        if m <= 0:
            print(sum(s[0] * s[1] for s in sections[i+1:]) - p * m)
            break
    else:
        print(0)

Submission status: Accepted

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-

import os
import sys
import itertools
import math
from collections import Counter, defaultdict

class Main(object):
    
    def __init__(self):
        pass

    def solve(self):
        '''
        insert your code
        '''
        while True:
            n, m = map(int, raw_input().split())
            if n == 0 and m == 0:
                break
            l = []
            for i in range(n):
                d, p = map(int, raw_input().split())
                l.append((p, d))
            l.sort(reverse=True)
            rest = m
            prob = 0
            for p, d in l:
                rest -= d
                if rest < 0:
                    prob += -1 * rest * p
                    rest = 0
            print prob
        return None

if __name__ == '__main__':
    m = Main()
    m.solve()

Submission status: Accepted

Solution code:
while 1:
    N,M = map(int,raw_input().split())
    if N == M == 0: break
    DP = [map(int,raw_input().split()) for _ in xrange(N)]
    DP = sorted(DP, key = lambda x:x[1], reverse = True)

    ans = 0
    for i in xrange(N):
        if M-DP[i][0] >= 0:
            M -= DP[i][0]
        else:
            ans += DP[i][1]*(DP[i][0]-M)
            ans += sum(DP[j][1]*DP[j][0] for j in xrange(i+1,N))
            break
    print ans

Submission status: Accepted

Solution code:
while 1:
    N,M = map(int,raw_input().split())
    if N == M == 0: break
    DP = [map(int,raw_input().split()) for _ in xrange(N)]
    DP = sorted(DP, key = lambda x:x[1])[::-1]
    ans = 0
    for i in xrange(N):
        ans += DP[i][1]*max(0,DP[i][0]-M)
        M = max(0,M-DP[i][0])
    print ans

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

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

Submission status: Accepted

Solution code:
while 1:
	n, m = map(int,raw_input().split())
	if (n,m) == (0,0):
		break
	num = [0 for i in range(11)]
	for i in range(n):
		d, p = map(int,raw_input().split())
		num[p] += d
	expectation = 0
	for i in range(10):
		if m >= num[10-i]:
			m -= num[10-i]
		else :
			expectation += (num[10-i]-m)*(10-i)
			m = 0
	print expectation

Submission status: Accepted

Solution code:
while(1):
    [n,m]=[int(x) for x in raw_input().split()]
    if n==0:
        break
    else:
        dlist=[]
        for i in range(n):
            [d,p]=[int(x) for x in raw_input().split()]
            dlist.append([d,p])
        dlist.sort(key=lambda x:x[1])
        P=0
        while(m>0 and len(dlist)>0):
            mostdanger=dlist.pop()
            if m>=mostdanger[0]:
                m=m-mostdanger[0]
            else:
                P=(mostdanger[0]-m)*mostdanger[1]
                m=0
        if len(dlist)==0:
            print P
        else:
            for sec in dlist:
                P=P+sec[0]*sec[1]
            print P

Submission status: Accepted

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

(n, m) = map(int, raw_input().split())
while n!=0:
    Sum = 0
    pd = []
    for i in range(n):
        (d, p) = (map(int, raw_input().split()))
        Sum += d*p
        pd.append([p, d])
    pd.sort(reverse=True)
    red = 0
    for i in range(n):
        if m >= pd[i][1]:
            m -= pd[i][1]
            red += pd[i][0]*pd[i][1]
        else:
            red += m*pd[i][0]
            break
    print Sum-red

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

Submission status: Accepted

Solution code:
while True:
    n, m = map(int, input().split())
    ex = [0] * 11
    if n == 0: break
    for i in range(n):
        d, p = map(int, input().split())
        ex[p] += d
    ex.reverse()
    for i in range(len(ex)):
        m -= ex[i]
        if m <= 0:
            ex[i] = abs(m)
            break
        else:
            ex[i] = 0
    ex.reverse()
    ans = 0
    for i in range(len(ex)):
        ans += ex[i] * i
    print(ans)

Submission status: Accepted

Solution code:
while True:
    N, M = map(int, input().split())
    if N == 0 and M == 0: break
    travel = [tuple(map(int, input().split())) for _ in range(N)]
    travel.sort(reverse=True, key=lambda x:x[1])
    for i, (d, p) in enumerate(travel):
        if M == 0: break
        travel[i] = (p, max(0, d-M))
        M = max(0, M-d)
    print(sum(d*p for d, p in travel))

Submission status: Accepted

Solution code:
while True:
    N, M = map(int, input().split())
    if N == 0 and M == 0: break
    travel = [list(map(int, input().split())) for _ in range(N)]
    travel.sort(reverse=True, key=lambda x:x[1])
    for i, (d, _) in enumerate(travel):
        if M == 0: break
        travel[i][0] = max(0, d-M)
        M = max(0, M-d)
    print(sum(d*p for d, p in travel))

Submission status: Accepted

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

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

    e = 0
    for p, d in sections:
        if d <= m:
            m -= d
            d = 0
        elif m > 0:
            d -= m
            m = 0
        e += p * d
    print(e)

Submission status: Accepted

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 and len(road) > 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: Accepted

Solution code:
import heapq

while True:
  N,M = map(int, raw_input().split())
  if N==M==0: break
  q = []
  for _ in xrange(N):
    d,p = map(int, raw_input().split())
    heapq.heappush(q, [p,d])
  q = sorted(q, reverse=True)
  for i in xrange(N):
    if q[i][1] > M:
      q[i][1] -= M
      M = 0
      break
    else:
      M -= q[i][1]
      q[i][1] = 0
  precision = 0
  for i in xrange(N):
    precision += q[i][0] * q[i][1]
  print precision

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter

inf = 1<<30

def solve():
    while 1:
        N, M = map(int, sys.stdin.readline().split())

        if N == M == 0:
            return

        sect = [tuple(list(map(int, sys.stdin.readline().split()))) for i in range(N)]
        sect.sort(key=itemgetter(1), reverse=True)

        ans = 0

        for di, pi in sect:
            if di <= M:
                M -= di
            else:
                ans += (di - M) * pi
                M = 0

        print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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]
            m = 0
    print(num)

Submission status: Accepted

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

Solution code:
while True:
    N,M = map(int,input().split())
    if N == 0: break
    src = []
    for i in range(N):
        d,p = map(int,input().split())
        src.append((p,d))
    money = M
    ans = 0
    for p,d in sorted(src,reverse=True):
        guard = min(d,money)
        money -= guard
        ans += (d - guard) * p
    print(ans)