AtCoder Beginner Contest 121のC問題でWAになる理由が分かりません。

Question

表題の通り、AtCoder Beginner Contest 121のC問題でWAになる理由が分かりません。提出コードは以下の通りです。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
	ll n, m;
	cin >> n >> m;
	map<ll, ll> mp;
	for (int i = 0; i < n; i++)
	{
		int a, b;
		cin >> a >> b;
		mp[a] = b;
	}
	ll num = 0;
	ll cost = 0;
	for (auto p : mp)
	{
		if (num + p.second < m)
		{
			num += p.second;
			cost += p.first * p.second;
		}
		else
		{
			cost += p.first * (m - num);
			cout << cost << endl;
			return 0;
		}
	}
}

ちなみに、map<ll,ll>でなく、vector<pair<ll,ll>>を用いたら、ACになりました。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
	ll n, m;
	cin >> n >> m;
	vector<pair<ll, ll>> v(n);
	for (int i = 0; i < n; i++)
	{
		int a, b;
		cin >> a >> b;
		v[i] = make_pair(a, b);
	}
	sort(v.begin(), v.end());
	ll num = 0;
	ll cost = 0;
	for (auto p : v)
	{
		if (num + p.second < m)
		{
			num += p.second;
			cost += p.first * p.second;
		}
		else
		{
			cost += p.first * (m - num);
			cout << cost << endl;
			return 0;
		}
	}
}

したがって、map<ll,ll>を使っていることで何かしらの問題が生じているのだと考えていますが、原因の特定には至っていません。どなたかご教授いただけると幸いです。

Answer 1

map使ったとき、キーに値段使った場合、同じ値段が重複してしまうことに気付きました。