호텔

한 호텔은 여러 도시에서 홍보를 진행해 고객 수를 늘리려고 한다.

각 도시마다 한 번 홍보하는 데 드는 비용과, 그 한 번의 홍보로 늘어나는 고객 수가 주어진다. 같은 도시의 홍보는 0번 이상 원하는 정수 횟수만큼 진행할 수 있다. 단, 홍보를 부분적으로 구매할 수는 없으며, 각 도시에는 잠재 고객이 충분히 많다고 가정한다.

호텔의 고객을 적어도 C명 늘리기 위해 필요한 최소 비용을 구하시오.

첫째 줄에 정수 C와 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다.

둘째 줄부터 N개의 줄에는 각 도시에서 홍보하는 비용과 그 비용으로 얻을 수 있는 고객 수가 주어진다. 각 값은 100보다 작거나 같은 자연수이다.

적어도 C명의 고객을 늘리기 위해 필요한 최소 비용을 출력한다.