3회 문제풀이 14 / ABC 121 C - Energy Drink Collector
ABC 121 C - Energy Drink Collector
【문제 개요】
영양 드링크에 등급 상승 효과가 있다고 들었던 타카하시군은 M개의 영양 드링크를 사모으려고 합니다.
영양 드링크를 팔고있는 가게는 N곳 있고 i번째 가게에서는 1개당 Ai원의 영양 드링크를 Bi개까지 구매할 수 있습니다.
최소로 몇원 있어야 M개의 영양 드링크를 살 수 있을까요?
또, 주어진 입력은 충분한 돈이 있으면 M개의 영양 드링크를 사모으는것이 보장되어있습니다.
【전제】
- 입력은 모두 정수이다.
- 1 ≦ N, M ≦ 10^5
- 1 ≦ Ai ≦ 10^9
- 1 ≦ Bi ≦ 10^5
- B1 + … + BN ≦ M
【입력 형태】
1
2
3
4
5
N M
A1 B1
A2 B2
...
AN BN
【출력 형태】
M개의 영양 드링크를 사모으기 위해서 필요한 최소 금액을 출력하라.
【예시】
입력 예 1
1
2
3
2 5
4 9
2 4
출력 예 1
1
12
12원이 있으면 1번째의 가게에서 1개, 2번째 가게에서 4개의 드링크를 구매해서 5개의 영양 드링크를 모으는것이 가능합니다.
11원 이하라면 5개의 영양 드링크를 구매하는것은 불가능합니다.
입력 예 2
1
2
3
4
5
4 30
6 18
2 5
3 10
7 9
출력 예 2
1
130
입력 예 3
1
2
1 100000
1000000000 100000
출력 예 3
1
100000000000000
출력이 32비트의 정수형으로 해결되지 않는 경우가 있습니다.
ABC 121 C - Energy Drink Collector
【문제 개요】
영양 드링크에 등급 상승 효과가 있다고 들었던 타카하시군은 M개의 영양 드링크를 사모으려고 합니다.
영양 드링크를 팔고있는 가게는 N곳 있고 i번째 가게에서는 1개당 Ai원의 영양 드링크를 Bi개까지 구매할 수 있습니다.
최소로 몇원 있어야 M개의 영양 드링크를 살 수 있을까요?
또, 주어진 입력은 충분한 돈이 있으면 M개의 영양 드링크를 사모으는것이 보장되어있습니다.
【전제】
- 입력은 모두 정수이다.
- 1 ≦ N, M ≦ 10^5
- 1 ≦ Ai ≦ 10^9
- 1 ≦ Bi ≦ 10^5
- B1 + … + BN ≦ M
【입력 형태】
1
2
3
4
5
N M
A1 B1
A2 B2
...
AN BN
【출력 형태】
M개의 영양 드링크를 사모으기 위해서 필요한 최소 금액을 출력하라.
【예시】
입력 예 1
1
2
3
2 5
4 9
2 4
출력 예 1
1
12
12원이 있으면 1번째의 가게에서 1개, 2번째 가게에서 4개의 드링크를 구매해서 5개의 영양 드링크를 모으는것이 가능합니다.
11원 이하라면 5개의 영양 드링크를 구매하는것은 불가능합니다.
입력 예 2
1
2
3
4
5
4 30
6 18
2 5
3 10
7 9
출력 예 2
1
130
입력 예 3
1
2
1 100000
1000000000 100000
출력 예 3
1
100000000000000
출력이 32비트의 정수형으로 해결되지 않는 경우가 있습니다.