#442. 贺云艾 的原木种植

贺云艾 的原木种植

题目描述

冬天,贺云艾 的原木林场可以开始采伐。一共有nn棵原木可以收获,分别的长度为aia_i

原木能卖个好价钱,长度为aia_i的原木市场价为ai2a_i^2

但现在的问题是,工人们需要从 贺云艾 的原木中锯下共kk长度的木头燃烧用以取暖。

贺云艾 肉痛不已,他想知道在满足完取暖需求之后,他还能将原木最多卖出多少钱?

输入格式

第一行两个整数n,kn,k,为原木的数量和需要的木头长度。

接下来一行有nn个整数aia_i,为原木的长度。

输出格式

仅一个整数,为最多卖出的价钱。

样例

样例输入

6 9
1 1 4 5 1 4

样例输出

29

数据范围与提示

1n1051 \leq n \leq 10^5

0ki=1nai0 \leq k \leq \sum\limits_{i=1}^n a_i

1ai1061 \leq a_i \leq 10^6