C. Buying Fruit
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You've been tasked with buying fruit to put in snack trays at your student org's annual kickoff event. You know you will need at least $$$P$$$ total pounds of fruit, so you've taken a shopping trip to HEB.

Fruit at HEB is priced in dollars per pound, and HEB only has a limited amount of each type of fruit in stock. What is the cheapest price you must pay to buy $$$P$$$ total pounds of fruit, given your options?

Although not completely realistic, for the purposes of this problem you may assume that if HEB stocks $$$k$$$ pounds of a fruit, it is possible to buy any amount of that fruit between $$$0$$$ and $$$k$$$ pounds.

Input

The first line of input contains two space-separated integers $$$P$$$ and $$$n$$$: the total pounds of fruit you need to buy $$$(1 \leq P \leq 1\,000)$$$, and the number of types of fruit sold at HEB $$$(1 \leq n \leq 100)$$$. The next $$$n$$$ lines describe the fruit on offer. Each line contains a real number $$$p$$$, the price of the fruit in dollars per pound $$$(0.01 \leq p \leq 100.00)$$$, and an integer $$$k$$$, the total pounds of that fruit that HEB has in stock $$$(1 \leq k \leq 100)$$$.

Output

If it is impossible to buy $$$P$$$ pounds of fruit given the options in stock, print -1.

Otherwise, print the cheapest price (in dollars) you must pay to purchase $$$P$$$ pounds of fruit. Your answer will be judged correct if it matches the judge solution with relative or absolute error at most $$$10^{-4}$$$.

Examples
Input
100 3
1.75 53
2.01 20
1.06 41
Output
148.27
Input
50 2
2.00 20
3.50 20
Output
-1