Hello everyone :) I need help to find out the following problem named Subway Ride. Here is the statement

Subway Surfers is an endless runner video game. The game starts by tapping the touchscreen, while Jake (the game's starter character) or any other character sprays graffiti on a subway, and then gets caught in the act by the inspector and his dog, who starts chasing the character.

In Subway Ride, a simplified version of Subway Surfers, the gaming character Jake will win if he can pass N meters of the subway (an endless road with lots of obstacles). Jake can use M kinds of hoverboard in the game. By using the i-th hoverboard Jake can pass Xi meters, at the cost of Yi coins.

Find the minimum total points Jake needs to cost for passing N meters or more of the subway.

Constraints:

1 <= N <= 10^4

1 <= M <= 10^3

1 <= X,Y <= 10^4

Input The first line contains two integer N and M. Each of the following M lines will have two integers X and Y for i-th hoverboard.

Output Print the minimum total points Jake needs to cost for wining the game.

Samples Input 9 3 8 3 4 2 2 1 Output 4

Thank you :)