학식 뭐 먹지

영인이와 $N-1$명의 친구들은 학식을 먹으려고 한다. 학식은 $M$개의 메뉴로 구성되어 있으며, 메뉴들은 $1$번부터 $M$번까지 번호가 매겨져 있다. $i$번 메뉴는 가격이 $A\_i$이고 수량이 $B\_i$이다.

영인이와 친구들은 메뉴의 수량을 초과하지 않도록 조심스럽게 메뉴를 선택했다. 모든 사람은 한 개의 메뉴만 선택할 수 있으며, 메뉴를 선택하지 않는 경우는 없다.

영인이는 메뉴 구성에 따라 본인의 불만도가 달라진다. 선택된 $N$개의 메뉴의 번호를 $x\_1,x\_2,\cdots ,x\_N$이라 할 때, 불만도는 다음과 같이 정의된다.

불만도 \( =\left( \sum_{i=1}^{N}A_{x_i} \right)\times\lvert \{x_1,x_2,\cdots ,x_N\} \rvert\)

여기서 $\sum\_{i=1}^{N}A\_{x\_i}$는 선택된 메뉴들의 가격의 합이며, $\lvert \\{x\_1,x\_2,\cdots ,x\_N\\} \rvert$는 선택된 메뉴의 종류 수를 나타낸다.

가능한 불만도의 최솟값을 출력하시오.

첫 번째 줄에 사람의 수 $N$과 메뉴의 수 $M$이 공백으로 구분되어 주어진다. $( 1\leq N\leq 1\\, 000;$ $1\leq M\leq 100 )$

다음 $M$개의 줄에 걸쳐, $i$번째 줄에 $i$번 메뉴의 가격 $A\_i$와 수량 $B\_i$가 공백으로 구분되어 주어진다. $(1\leq A\_i,B\_i\leq 10^9;$ $\sum\_{i=1}^{M}{B\_i}\geq N)$

입력으로 주어지는 모든 수는 정수이다.

가능한 불만도의 최솟값을 출력하시오.