{"problem":{"name":"Crested Ibis vs Monster","description":{"content":"Ibis is fighting with a monster. The _health_ of the monster is $H$. Ibis 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 Po","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc153_e"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$H$ $N$\n$A_1$ $B_1$\n$:$\n$A_N$ $B_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc153_e","tags":[],"sample_group":[["9 3\n8 3\n4 2\n2 1","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."],["100 6\n1 1\n2 3\n3 9\n4 27\n5 81\n6 243","100\n\nIt is optimal to cast the first spell $100$ times."],["9999 10\n540 7550\n691 9680\n700 9790\n510 7150\n415 5818\n551 7712\n587 8227\n619 8671\n588 8228\n176 2461","139815"]],"created_at":"2026-03-03 11:01:13"}}