/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 475 点
問題文
N 種類の商品がそれぞれ 10^{100} 個ずつあります。
あなたはこれらの商品を各種類について 0 個以上買うことが出来ます。i 番目の商品を k 個買うには k^2P_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 円以下で 4 個以上の商品を買うことはできないため、3 が答えとなります。
入力例 2
10 1000 2 15 6 5 12 1 7 9 17 2
出力例 2
53
Score : 475 points
Problem Statement
There are N types of products, each having 10^{100} units in stock.
You can buy any non-negative number of units of each product. To buy k units of the i-th product, it costs k^2 P_i yen.
If your total purchase cost is at most M yen, what is the maximum number of units you can buy in total?
Constraints
- 1 \leq N \leq 2 \times 10^{5}
- 1 \leq M \leq 10^{18}
- 1 \leq P_i \leq 2 \times 10^{9}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M P_1 \ldots P_N
Output
Print the answer.
Sample Input 1
3 9 4 1 9
Sample Output 1
3
If you buy one unit of the 1st product and two units of the 2nd product, the total purchase cost is 1^2 \times 4 + 2^2 \times 1 = 8. It is impossible to buy four or more units in total with a total cost of at most 9 yen, so the answer is 3.
Sample Input 2
10 1000 2 15 6 5 12 1 7 9 17 2
Sample Output 2
53