{"raw_statement":[{"iden":"statement","content":"Let's call the _roundness_ of the number the number of zeros to which it ends.\n\nYou have an array of _n_ numbers. You need to choose a subset of exactly _k_ numbers so that the _roundness_ of the product of the selected numbers will be maximum possible."},{"iden":"input","content":"The first line contains two integer numbers _n_ and _k_ (1 ≤ _n_ ≤ 200, 1 ≤ _k_ ≤ _n_).\n\nThe second line contains _n_ space-separated integer numbers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 1018)."},{"iden":"output","content":"Print maximal roundness of product of the chosen subset of length _k_."},{"iden":"examples","content":"Input\n\n3 2\n50 4 20\n\nOutput\n\n3\n\nInput\n\n5 3\n15 16 3 25 9\n\nOutput\n\n3\n\nInput\n\n3 3\n9 77 13\n\nOutput\n\n0"},{"iden":"note","content":"In the first example there are _3_ subsets of _2_ numbers. \\[50, 4\\] has product _200_ with _roundness_ _2_, \\[4, 20\\] — product _80_, _roundness_ _1_, \\[50, 20\\] — product _1000_, _roundness_ _3_.\n\nIn the second example subset \\[15, 16, 25\\] has product _6000_, _roundness_ _3_.\n\nIn the third example all subsets has product with _roundness_ _0_."}],"translated_statement":[{"iden":"statement","content":"我们定义一个数的 _roundness_ 为其末尾零的个数。\n\n你有一个包含 #cf_span[n] 个数的数组。你需要从中选择一个恰好包含 #cf_span[k] 个数的子集，使得所选数字乘积的 _roundness_ 最大。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 200, 1 ≤ k ≤ n]）。\n\n第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 1018]）。\n\n请输出所选长度为 #cf_span[k] 的子集的乘积的最大 _roundness_。\n\n在第一个例子中，有 _3_ 个包含 _2_ 个数的子集。#cf_span[[50, 4]] 的乘积为 _200_，其 _roundness_ 为 _2_；#cf_span[[4, 20]] 的乘积为 _80_，_roundness_ 为 _1_；#cf_span[[50, 20]] 的乘积为 _1000_，_roundness_ 为 _3_。\n\n在第二个例子中，子集 #cf_span[[15, 16, 25]] 的乘积为 _6000_，_roundness_ 为 _3_。\n\n在第三个例子中，所有子集的乘积的 _roundness_ 均为 _0_。\n\n"},{"iden":"input","content":"第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 200, 1 ≤ k ≤ n]）。第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 1018]）。"},{"iden":"output","content":"请输出所选长度为 #cf_span[k] 的子集的乘积的最大 _roundness_。"},{"iden":"examples","content":"输入3 250 4 20输出3输入5 315 16 3 25 9输出3输入3 39 77 13输出0"},{"iden":"note","content":"在第一个例子中，有 _3_ 个包含 _2_ 个数的子集。#cf_span[[50, 4]] 的乘积为 _200_，其 _roundness_ 为 _2_；#cf_span[[4, 20]] 的乘积为 _80_，_roundness_ 为 _1_；#cf_span[[50, 20]] 的乘积为 _1000_，_roundness_ 为 _3_。在第二个例子中，子集 #cf_span[[15, 16, 25]] 的乘积为 _6000_，_roundness_ 为 _3_。在第三个例子中，所有子集的乘积的 _roundness_ 均为 _0_。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq k \\leq n \\leq 200 $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers, where $ 1 \\leq a_i \\leq 10^{18} $.  \n\nFor any positive integer $ x $, define its *roundness* $ r(x) $ as the highest power of 10 dividing $ x $, i.e.,  \n$$\nr(x) = \\min(v_2(x), v_5(x)),\n$$  \nwhere $ v_p(x) $ denotes the exponent of prime $ p $ in the prime factorization of $ x $.  \n\nFor a subset $ S \\subseteq A $ with $ |S| = k $, define the roundness of the product as $ r\\left( \\prod_{a \\in S} a \\right) $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 200 $  \n2. $ 1 \\leq k \\leq n $  \n3. $ 1 \\leq a_i \\leq 10^{18} $ for all $ i \\in \\{1, \\dots, n\\} $  \n\n**Objective**  \nMaximize the roundness over all subsets of size $ k $:  \n$$\n\\max_{\\substack{S \\subseteq \\{1, \\dots, n\\} \\\\ |S| = k}} r\\left( \\prod_{i \\in S} a_i \\right) = \\max_{\\substack{S \\subseteq \\{1, \\dots, n\\} \\\\ |S| = k}} \\min\\left( \\sum_{i \\in S} v_2(a_i), \\sum_{i \\in S} v_5(a_i) \\right)\n$$","simple_statement":null,"has_page_source":false}