← 返回题目列表

AtCoder · abc389_e

H. 平方价格

中文机器翻译题面 查看原题

分数: 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