分数: 475 点
问题陈述
有 N 类型的产品,每种都有 10^{100} 单位库存。
您可以购买每种产品的任意非负数量单位。购买 k 单位 i第一个产品,它的成本 k^2 P_i 日元。
如果您的总购买成本最多为 M 日元,您总共可以购买的最大数量是多少?
约束
- 1 \leq N \leq 2 \times 10^{5}
- 1 \leq M \leq 10^{18}
- 1 \leq P_i \leq 2 \times 10^{9}
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M P_1 \ldots P_N
输出
打印答案。
示例输入 1
3 9 4 1 9
示例输出 1
3
如果您购买 1 件第 1 件产品和 2 件第 2 件产品,则总购买成本为 1^2 \times 4 + 2^2 \times 1 = 8。不可能总共购买四个或更多单位,总成本最多为 9 日元,所以答案是 3.
示例输入 2
10 1000 2 15 6 5 12 1 7 9 17 2
示例输出 2
53