게스트하우스

면접 대비

시간 제한1초메모리 제한1024 MB

요약

각 침대 종류의 가격과 재고가 주어질 때, N명이 묵을 침대를 가장 싼 비용으로 예약하는 금액을 구합니다.

난이도: 쉬움10점 중 3점
유형: 그리디, 정렬
정답자: 아직 제출이 없습니다

문제

Arash는 스웨덴 감자 껍질 벗기기 올림피아드(PO)의 현장 결승전을 준비하고 있다. 참가자 $N$ 명이 올 예정이라, Arash는 참가자들이 묵을 잠자리를 예약해야 한다. Arash는 근처의 게스트하우스를 예약하려고 한다.

이 게스트하우스에는 $M$ 종류의 침대가 있다. 종류 $i$ 의 침대 한 개는 $c_i$ 크로나이고, 그 종류의 침대는 $b_i$ 개 있다. 게스트하우스에는 현재 예약이 없으므로 필요한 만큼 침대를 자유롭게 예약할 수 있다.

스웨덴 감자 껍질 벗기기 올림피아드 팀은 수학에 강하지 않아서 도움이 필요하다. 필요한 침대를 예약하는 최소 비용을 구하라.

입력

첫 줄에 참가자 수 $N$ ( $1 \leq N \leq 100$ )과 침대 종류 수 $M$ ( $1 \leq M \leq 5$ )이 주어진다. 이어서 $M$ 개의 줄에 위에서 설명한 대로 $c_i$ ( $100 \leq c_i \leq 1000$ )와 $b_i$ ( $1 \leq b_i \leq 100$ )가 주어진다.

모든 참가자가 묵을 수 있도록 침대는 항상 충분하다.

출력

한 줄에 정수 하나를 출력한다. 스웨덴 감자 껍질 벗기기 올림피아드가 게스트하우스에서 하룻밤 동안 침대를 빌리는 데 드는 최소 비용이다.

제한

$1 \leq N \leq 100$ , $1 \leq M \leq 5$ , $100 \leq c_i \leq 1000$ , $1 \leq b_i \leq 100$

힌트

첫 번째 예제를 보면, 가장 싼 침대 8개를 모두 사서 총 2400크로나를 내고, 그다음으로 조금 더 비싼 침대 2개를 사서 총 1000크로나를 낸다. 최종 가격은 3400이다.

예제2

예제 1
입력
```
10 2
500 30
300 8
```
예상 출력
```
3400
```
예제 2
입력
```
10 3
150 5
200 3
100 3
```
예상 출력
```
1450
```