{"raw_statement":[{"iden":"statement","content":"On his trip to Luxor and Aswan, Sagheer went to a Nubian market to buy some souvenirs for his friends and relatives. The market has some strange rules. It contains _n_ different items numbered from 1 to _n_. The _i_\\-th item has base cost _a__i_ Egyptian pounds. If Sagheer buys _k_ items with indices _x_1, _x_2, ..., _x__k_, then the cost of item _x__j_ is _a__x__j_ + _x__j_·_k_ for 1 ≤ _j_ ≤ _k_. In other words, the cost of an item is equal to its base cost in addition to its index multiplied by the factor _k_.\n\nSagheer wants to buy as many souvenirs as possible without paying more than _S_ Egyptian pounds. Note that he cannot buy a souvenir more than once. If there are many ways to maximize the number of souvenirs, he will choose the way that will minimize the total cost. Can you help him with this task?"},{"iden":"input","content":"The first line contains two integers _n_ and _S_ (1 ≤ _n_ ≤ 105 and 1 ≤ _S_ ≤ 109) — the number of souvenirs in the market and Sagheer's budget.\n\nThe second line contains _n_ space-separated integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 105) — the base costs of the souvenirs."},{"iden":"output","content":"On a single line, print two integers _k_, _T_ — the maximum number of souvenirs Sagheer can buy and the minimum total cost to buy these _k_ souvenirs."},{"iden":"examples","content":"Input\n\n3 11\n2 3 5\n\nOutput\n\n2 11\n\nInput\n\n4 100\n1 2 5 6\n\nOutput\n\n4 54\n\nInput\n\n1 7\n7\n\nOutput\n\n0 0"},{"iden":"note","content":"In the first example, he cannot take the three items because they will cost him \\[5, 9, 14\\] with total cost 28. If he decides to take only two items, then the costs will be \\[4, 7, 11\\]. So he can afford the first and second items.\n\nIn the second example, he can buy all items as they will cost him \\[5, 10, 17, 22\\].\n\nIn the third example, there is only one souvenir in the market which will cost him 8 pounds, so he cannot buy it."}],"translated_statement":[{"iden":"statement","content":"在前往卢克索和阿斯旺的旅途中，Sagheer 去了一家努比亚市场为他的朋友和亲戚购买纪念品。这个市场有一些奇怪的规则：它包含 #cf_span[n] 件不同的商品，编号从 #cf_span[1] 到 #cf_span[n]。第 #cf_span[i] 件商品的基础价格为 #cf_span[ai] 埃及镑。如果 Sagheer 购买了 #cf_span[k] 件商品，其索引为 #cf_span[x1, x2, ..., xk]，那么第 #cf_span[xj] 件商品的价格为 #cf_span[axj + xj·k]（其中 #cf_span[1 ≤ j ≤ k]）。换句话说，一件商品的价格等于其基础价格加上其索引乘以因子 #cf_span[k]。\n\nSagheer 希望在不超出 #cf_span[S] 埃及镑预算的前提下购买尽可能多的纪念品。注意，他不能购买同一件纪念品多次。如果有多种方式可以最大化购买纪念品的数量，他会选择总成本最小的那种。你能帮他完成这个任务吗？\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[S]（#cf_span[1 ≤ n ≤ 105] 且 #cf_span[1 ≤ S ≤ 109]）——市场中纪念品的数量和 Sagheer 的预算。\n\n第二行包含 #cf_span[n] 个空格分隔的整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 105]）——纪念品的基础价格。\n\n请在一行中输出两个整数 #cf_span[k], #cf_span[T] —— Sagheer 能购买的最大纪念品数量以及购买这 #cf_span[k] 件纪念品所需的最小总成本。"},{"iden":"input","content":"第一行包含两个整数 #cf_span[n] 和 #cf_span[S]（#cf_span[1 ≤ n ≤ 105] 且 #cf_span[1 ≤ S ≤ 109]）——市场中纪念品的数量和 Sagheer 的预算。第二行包含 #cf_span[n] 个空格分隔的整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 105]）——纪念品的基础价格。"},{"iden":"output","content":"请在一行中输出两个整数 #cf_span[k], #cf_span[T] —— Sagheer 能购买的最大纪念品数量以及购买这 #cf_span[k] 件纪念品所需的最小总成本。"},{"iden":"examples","content":"输入3 112 3 5输出2 11输入4 1001 2 5 6输出4 54输入1 77输出0 0"},{"iden":"note","content":"在第一个例子中，他不能购买三件商品，因为它们的总成本为 #cf_span[[5, 9, 14]]，合计 #cf_span[28]。如果他决定只买两件，则价格变为 #cf_span[[4, 7, 11]]。因此他可以负担第一和第二件商品。在第二个例子中，他可以购买所有商品，因为它们的总成本为 #cf_span[[5, 10, 17, 22]]。在第三个例子中，市场上只有一件纪念品，价格为 #cf_span[8] 埃及镑，因此他无法购买。"}],"sample_group":[],"show_order":[],"formal_statement":"Let $ n $ be the number of items, $ S $ the budget, and $ a_i $ the base cost of item $ i $ for $ i = 1, 2, \\dots, n $.\n\nIf Sagheer buys $ k $ items with indices $ x_1, x_2, \\dots, x_k $, then the cost of item $ x_j $ is:\n$$\na_{x_j} + x_j \\cdot k\n$$\nThe total cost is:\n$$\n\\sum_{j=1}^k (a_{x_j} + x_j \\cdot k) = \\sum_{j=1}^k a_{x_j} + k \\cdot \\sum_{j=1}^k x_j\n$$\n\n**Objective:**  \nFind the maximum $ k \\in \\{0, 1, \\dots, n\\} $ such that there exists a subset of $ k $ distinct items with total cost $ \\leq S $, and among all such subsets of size $ k $, choose the one with minimum total cost.\n\n**Formal Problem:**\n\nGiven:\n- $ n \\in \\mathbb{N} $, $ S \\in \\mathbb{N} $\n- $ a = (a_1, a_2, \\dots, a_n) \\in \\mathbb{N}^n $\n\nDefine for any subset $ I \\subseteq \\{1, 2, \\dots, n\\} $ of size $ |I| = k $, the cost function:\n$$\nC(I) = \\sum_{i \\in I} a_i + k \\cdot \\sum_{i \\in I} i\n$$\n\nFind:\n$$\n(k^*, T^*) = \\arg\\max_{\\substack{k \\in \\{0, \\dots, n\\} \\\\ \\exists I \\subseteq \\{1,\\dots,n\\}, |I|=k \\\\ C(I) \\leq S}} \\left( k, \\min_{\\substack{I \\subseteq \\{1,\\dots,n\\} \\\\ |I|=k \\\\ C(I) \\leq S}} C(I) \\right)\n$$\n\nThat is, $ k^* $ is the maximum number of items that can be bought within budget $ S $, and $ T^* $ is the minimum total cost among all subsets of size $ k^* $ satisfying the budget constraint.","simple_statement":null,"has_page_source":false}