{"raw_statement":[{"iden":"statement","content":"Over the quarantine season, you decide to watch your weight by limiting yourself to a certain amount of calories a day.\n\nIn this problem, you're given the number of calories of each food item in your house as input.\n\nYou want to figure out the minimum number of food items that you need to eat in order to have eaten exactly $n$ calories.\n\nThe first line of input contains a single positive integer $n$: the target number of calories.\n\nThe second line of input contains a single positive integer $k$: the number of food items.\n\nThe next $k$ lines each contain a single positive integer $c$: the number of calories of each food item.\n\nOutput a single positive integer $m$: the minimum number of food items that you need to eat, in order to have eaten exactly $n$ calories.\n\nThis problem is not as easy as you think it is. The solution to the easier version of the problem does not correctly solve the second example case.\n\n"},{"iden":"input","content":"The first line of input contains a single positive integer $n$: the target number of calories.The second line of input contains a single positive integer $k$: the number of food items.The next $k$ lines each contain a single positive integer $c$: the number of calories of each food item."},{"iden":"output","content":"Output a single positive integer $m$: the minimum number of food items that you need to eat, in order to have eaten exactly $n$ calories."},{"iden":"examples","content":"Input2310\n3\n500\n100\n10\nOutput8\nInput600\n3\n500\n300\n1\nOutput2\nInput10000\n3\n3\n7\n11\nOutput912\n"},{"iden":"note","content":"This problem is not as easy as you think it is. The solution to the easier version of the problem does not correctly solve the second example case."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the target calorie count.  \nLet $ k \\in \\mathbb{Z}^+ $ be the number of food items.  \nLet $ C = \\{c_1, c_2, \\dots, c_k\\} \\subset \\mathbb{Z}^+ $ be the multiset of calorie values per food item.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^4 $  \n2. $ 1 \\leq k \\leq 100 $  \n3. $ 1 \\leq c_i \\leq n $ for all $ i \\in \\{1, \\dots, k\\} $\n\n**Objective**  \nFind the minimum integer $ m \\in \\mathbb{Z}^+ $ such that there exist non-negative integers $ x_1, x_2, \\dots, x_k $ with  \n$$\n\\sum_{i=1}^k x_i c_i = n \\quad \\text{and} \\quad \\sum_{i=1}^k x_i = m,\n$$  \nand $ m $ is minimized.","simple_statement":"Given n calories target and k food items with their calorie values, find the minimum number of foods to eat to get exactly n calories.","has_page_source":false}