{"raw_statement":[{"iden":"statement","content":"You are given an array _a_ consisting of _n_ integers, and additionally an integer _m_. You have to choose some sequence of indices _b_1, _b_2, ..., _b__k_ (1 ≤ _b_1 < _b_2 < ... < _b__k_ ≤ _n_) in such a way that the value of is maximized. Chosen sequence can be empty.\n\nPrint the maximum possible value of ."},{"iden":"input","content":"The first line contains two integers _n_ and _m_ (1 ≤ _n_ ≤ 35, 1 ≤ _m_ ≤ 109).\n\nThe second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109)."},{"iden":"output","content":"Print the maximum possible value of ."},{"iden":"examples","content":"Input\n\n4 4\n5 2 4 1\n\nOutput\n\n3\n\nInput\n\n3 20\n199 41 299\n\nOutput\n\n19"},{"iden":"note","content":"In the first example you can choose a sequence _b_ = {1, 2}, so the sum is equal to 7 (and that's 3 after taking it modulo 4).\n\nIn the second example you can choose a sequence _b_ = {3}."}],"translated_statement":[{"iden":"statement","content":"你被给定一个包含 #cf_span[n] 个整数的数组 #cf_span[a]，以及一个整数 #cf_span[m]。你需要选择一个下标序列 #cf_span[b1, b2, ..., bk]（#cf_span[1 ≤ b1 < b2 < ... < bk ≤ n]），使得交错和的值最大化。所选序列可以为空。\n\n请输出可能的最大值。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 35]，#cf_span[1 ≤ m ≤ 109]）。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an]（#cf_span[1 ≤ ai ≤ 109]）。\n\n请输出可能的最大值。\n\n在第一个例子中，你可以选择序列 #cf_span[b = {1, 2}]，此时交错和等于 #cf_span[7]（取模 #cf_span[4] 后为 #cf_span[3]）。\n\n在第二个例子中，你可以选择序列 #cf_span[b = {3}]。"},{"iden":"input","content":"第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 35]，#cf_span[1 ≤ m ≤ 109]）。第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an]（#cf_span[1 ≤ ai ≤ 109]）。"},{"iden":"output","content":"请输出可能的最大值。"},{"iden":"examples","content":"输入\n4 4\n5 2 4 1\n输出\n3\n\n输入\n3 20\n199 41 299\n输出\n19"},{"iden":"note","content":"在第一个例子中，你可以选择序列 #cf_span[b = {1, 2}]，此时交错和等于 #cf_span[7]（取模 #cf_span[4] 后为 #cf_span[3]）。在第二个例子中，你可以选择序列 #cf_span[b = {3}]。"}],"sample_group":[],"show_order":[],"formal_statement":"Given:\n- An integer $ n $, an integer $ m $, and an array $ a = [a_1, a_2, \\dots, a_n] $ of $ n $ positive integers.\n- A sequence of indices $ b = (b_1, b_2, \\dots, b_k) $ such that $ 1 \\leq b_1 < b_2 < \\dots < b_k \\leq n $, where $ k \\geq 0 $ (empty sequence allowed).\n\nDefine the value of a sequence $ b $ as:\n$$\nS(b) = \\left( \\sum_{i=1}^{k} a_{b_i} \\right) \\bmod m\n$$\n\nObjective:\nMaximize $ S(b) $ over all possible subsequences $ b $ of $ \\{1, 2, \\dots, n\\} $.\n\nFind:\n$$\n\\max_{b \\subseteq \\{1,2,\\dots,n\\}} \\left( \\left( \\sum_{i \\in b} a_i \\right) \\bmod m \\right)\n$$","simple_statement":null,"has_page_source":false}