日刊競プロ ABC 121 - C - Energy Drink Collector -

C - Energy Drink Collector

問題文
栄養ドリンクにレーティング上昇効果があると聞いた高橋くんは、M 本の栄養ドリンクを買い集めることにしました。栄養ドリンクが売られている店は N 軒あり、i 軒目の店では 1 本 Ai円の栄養ドリンクを Bi本まで買うことができます。最小で何円あれば M 本の栄養ドリンクを買い集めることができるでしょうか。なお、与えられる入力では、十分なお金があれば M 本の栄養ドリンクを買い集められることが保証されます。

制約
入力は全て整数である。
1≤N,M≤10**5
1≤Ai​≤10**9≤10**9
1≤Bi≤10**5
B1+...+BN≥M

考えたこと

必要な数を揃えるために、まずは単価で安いものを並べる。そこから順に安いものをあるだけ買っていけば良いと考えた。

N,M = map(int,input().split())
d = []
for _ in range(N):
 A,B = map(int,input().split())
 d.append([A,B])
 
score_d= sorted(d, key=lambda x:x[0])
ans = 0
for i in score_d:
 if M>i[1]:
   M-=i[1]
   ans+=i[0]*i[1]
 elif M<=i[1]:
   ans+=i[0]*M
   M=0
   break
print (ans)

余談だが、A,Bをはじめ辞書で作成したところ、同じ単価のAがある場合にまとめられてしまう現象がおき、WAになった。連想配列等を使わない限りは２重配列を使った方が良さそうだ。