← 返回题目列表

Codeforces · 1428/E

E. 兔子胡萝卜

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

新加坡动物园里有一些兔子。为了喂养它们,动物园管理员购买了 $$$n$$$ 长度为 $$$a_1、a_2、a_3、\ldots、a_n$$$ 的胡萝卜。然而,兔子的繁殖能力很强,繁殖速度也很快。动物园管理员现在有 $$$k$$$ 兔子,但没有足够的胡萝卜来喂饱它们。为了解决这个问题,Zookeeper 决定将胡萝卜切成 $$$k$$$ 块。由于某种原因,所有生成的胡萝卜长度都必须是正整数。

大胡萝卜对于兔子来说很难处理和吃,所以吃掉$$$x$$$大小的胡萝卜需要的时间是$$$x^2$$$。

帮助动物园管理员切开他的胡萝卜,同时最大限度地减少兔子吃胡萝卜所需的时间。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ $$$(1 \leq n \leq k \leq 10^5)$$$:胡萝卜的初始数量和兔子的数量。

下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq 10^6)$$$:胡萝卜的长度。

保证$$$a_i$$$的总和至少为$$$k$$$。

输出

输出一个整数:兔子吃完胡萝卜所需的最短时间总和。

示例

输入 #1

3 6
5 3 1

输出 #1

15

输入 #2

1 4
19

输出 #2

91

注意

对于第一个测试,胡萝卜的最佳大小是 $$$\{1,1,1,2,2,2\}$$$。所用时间为$$$1^2+1^2+1^2+2^2+2^2+2^2=15$$$

对于第二个测试,胡萝卜的最佳大小是 $$$\{4,5,5,5\}$$$。所用时间为$$$4^2+5^2+5^2+5^2=91$$$。