English · Original
Chinese · Translation
Formal · Original
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_.
Sagheer 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?
## Input
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.
The second line contains _n_ space-separated integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 105) — the base costs of the souvenirs.
## Output
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.
[samples]
## Note
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.
In the second example, he can buy all items as they will cost him \[5, 10, 17, 22\].
In the third example, there is only one souvenir in the market which will cost him 8 pounds, so he cannot buy it.
在前往卢克索和阿斯旺的旅途中，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]。
Sagheer 希望在不超出 #cf_span[S] 埃及镑预算的前提下购买尽可能多的纪念品。注意，他不能购买同一件纪念品多次。如果有多种方式可以最大化购买纪念品的数量，他会选择总成本最小的那种。你能帮他完成这个任务吗？
第一行包含两个整数 #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]）——纪念品的基础价格。
请在一行中输出两个整数 #cf_span[k], #cf_span[T] —— Sagheer 能购买的最大纪念品数量以及购买这 #cf_span[k] 件纪念品所需的最小总成本。
## Input
第一行包含两个整数 #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]）——纪念品的基础价格。
## Output
请在一行中输出两个整数 #cf_span[k], #cf_span[T] —— Sagheer 能购买的最大纪念品数量以及购买这 #cf_span[k] 件纪念品所需的最小总成本。
[samples]
## Note
在第一个例子中，他不能购买三件商品，因为它们的总成本为 #cf_span[[5, 9, 14]]，合计 #cf_span[28]。如果他决定只买两件，则价格变为 #cf_span[[4, 7, 11]]。因此他可以负担第一和第二件商品。在第二个例子中，他可以购买所有商品，因为它们的总成本为 #cf_span[[5, 10, 17, 22]]。在第三个例子中，市场上只有一件纪念品，价格为 #cf_span[8] 埃及镑，因此他无法购买。
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 $.
If Sagheer buys $ k $ items with indices $ x_1, x_2, \dots, x_k $, then the cost of item $ x_j $ is:
$$
a_{x_j} + x_j \cdot k
$$
The total cost is:
$$
\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
$$
**Objective:**
Find 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.
**Formal Problem:**
Given:
- $ n \in \mathbb{N} $, $ S \in \mathbb{N} $
- $ a = (a_1, a_2, \dots, a_n) \in \mathbb{N}^n $
Define for any subset $ I \subseteq \{1, 2, \dots, n\} $ of size $ |I| = k $, the cost function:
$$
C(I) = \sum_{i \in I} a_i + k \cdot \sum_{i \in I} i
$$
Find:
$$
(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)
$$
That 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.
API Response (JSON)
{
"problem": {
"name": "C. Sagheer and Nubian Market",
"description": {
"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 ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF812C"
},
"statements": [
{
"statement_type": "Markdown",
"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 ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "在前往卢克索和阿斯旺的旅途中，Sagheer 去了一家努比亚市场为他的朋友和亲戚购买纪念品。这个市场有一些奇怪的规则：它包含 #cf_span[n] 件不同的商品，编号从 #cf_span[1] 到 #cf_span[n]。第 #cf_span[i] 件商品的基础价格为 #cf_span[ai] 埃及镑。如果 Sagheer 购买了 #cf_span[k] 件商品，其索引为 #cf_span[x1...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "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 cos...",
"is_translate": false,
"language": "Formal"
}
]
}