{"raw_statement":[{"iden":"problem statement","content":"Ibis is fighting with a monster.\nThe _health_ of the monster is $H$.\nIbis can cast $N$ kinds of spells. Casting the $i$\\-th spell decreases the monster's health by $A_i$, at the cost of $B_i$ Magic Points.\nThe same spell can be cast multiple times. There is no way other than spells to decrease the monster's health.\nIbis wins when the health of the monster becomes $0$ or below.\nFind the minimum total Magic Points that have to be consumed before winning."},{"iden":"constraints","content":"*   $1 \\leq H \\leq 10^4$\n*   $1 \\leq N \\leq 10^3$\n*   $1 \\leq A_i \\leq 10^4$\n*   $1 \\leq B_i \\leq 10^4$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$H$ $N$\n$A_1$ $B_1$\n$:$\n$A_N$ $B_N$"},{"iden":"sample input 1","content":"9 3\n8 3\n4 2\n2 1"},{"iden":"sample output 1","content":"4\n\nFirst, let us cast the first spell to decrease the monster's health by $8$, at the cost of $3$ Magic Points. The monster's health is now $1$.\nThen, cast the third spell to decrease the monster's health by $2$, at the cost of $1$ Magic Point. The monster's health is now $-1$.\nIn this way, we can win at the total cost of $4$ Magic Points."},{"iden":"sample input 2","content":"100 6\n1 1\n2 3\n3 9\n4 27\n5 81\n6 243"},{"iden":"sample output 2","content":"100\n\nIt is optimal to cast the first spell $100$ times."},{"iden":"sample input 3","content":"9999 10\n540 7550\n691 9680\n700 9790\n510 7150\n415 5818\n551 7712\n587 8227\n619 8671\n588 8228\n176 2461"},{"iden":"sample output 3","content":"139815"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}