호스텔

Arash는 Potatisskalarolympiaden인 PO의 현장 결선을 개최하려 한다. 참가자 $N$명이 올 예정이며, Arash는 이제 참가자들이 묵을 숙소를 예약해야 한다. Arash는 필요한 침상을 예약하기 위해 인근 호스텔을 점찍어 두었다.

침상에는 $M$가지 유형이 있다. 주어진 침상 유형 $i$의 침상 하나는 $c_i$크로나이며, 해당 유형에서 이용할 수 있는 침상은 $b_i$개이다. 호스텔에는 현재 예약이 없으므로 필요한 만큼 자유롭게 예약할 수 있다.

스웨덴 Potatisskalarolympiaden은 수학에 그다지 능숙하지 않아 이제 여러분의 도움이 필요하다. 이들은 호스텔에서 필요한 침상을 예약할 때 가능한 최소 비용을 알고 싶어 한다. 이들을 도와줄 수 있는가?

채점

여러 테스트 케이스 그룹으로 여러분의 풀이를 테스트한다. 한 그룹에서 점수를 받으려면 해당 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한

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

첫째 줄에는 참가자 수 $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$)가 주어진다.

모든 참가자에게 충분한 침상이 항상 존재한다.

스웨덴 Potatisskalarolympiaden이 호스텔에서 하룻밤을 묵기 위해 지불해야 하는 가능한 최소 비용을 나타내는 정수 하나를 한 줄에 출력한다.

첫 번째 입력 예제를 설명하자. 가장 저렴한 침상 $8$개를 모두 구매하면 총비용은 $2400$가 되고, 그다음 조금 더 비싼 침상 둘을 구매하면 총비용은 $1000$가 된다. 최종 가격은 $3400$가 된다.