Minimum Cost to Buy Pizzas

You are given an integer \( N \) representing the number of pizzas you want to buy and an integer \( M \) representing the number of available deals from different pizzerias. Each deal is described by two integers \( k \) and \( p \), where \( k \) is the number of pizzas you can buy using that deal and \( p \) is its cost.

Your task is to determine the minimum cost required to purchase exactly \( N \) pizzas using the available deals. You are allowed to use each deal any number of times. If it is not possible to buy exactly \( N \) pizzas, output \( -1 \).

The problem can be approached using a dynamic programming technique. Define a dp array where \( dp[i] \) represents the minimum cost to buy exactly \( i \) pizzas. The recurrence is given by:

$$ dp[i] = \min_{\text{for each deal }(k, p) \text{ with } i \ge k} (dp[i-k] + p) $$

with the base case \( dp[0] = 0 \). Your solution should compute \( dp[N] \) and output \( -1 \) if no valid combination exists.

inputFormat

The input is read from standard input (stdin) in the following format:

• The first line contains two integers \( N \) and \( M \) separated by a space.
• The next \( M \) lines each contain two integers \( k \) and \( p \) separated by a space, representing one deal.

\( N \): the number of pizzas needed.

\( M \): the number of deals available (each provided by a different pizzeria).

outputFormat

The output is a single integer printed to standard output (stdout): the minimum cost to buy exactly \( N \) pizzas. If it is not possible to purchase exactly \( N \) pizzas using the available deals, output \( -1 \).

## sample

3 2
2 5
3 8

8

</p>