一实幼儿园里正在举行元旦晚会，现在谢老师正在准备 $M$ 个礼品，准备将这些礼品全部发送给 $N$ 个孩子。

但每个孩子都想要自己是拿到最多的那个，如果拿得不够多，那他们就会哭闹，我们设定每个孩子有一个哭闹值，第$i$ 个孩子的哭闹值为 $g[i]$。

如果有 $a[i]$ 个孩子拿到的礼品数比第 $i$ 个孩子多，那么第 $i$ 个孩子会产生 $g[i] \times a[i]$的哭闹声音值。

给定 $N$、$M$和每个孩子的哭闹值 $g[i]$，现在谢老师想让孩子不那么吵闹，所以请你来分配这些礼物，使得每个孩子至少分到一份礼物，并且所有孩子的哭闹声音总和最小。

输入格式

第一行包含两个整数 $N$, $M$。

第二行包含 $N$ 个整数表示 $g_1$ ~ $g_N$。

输出格式

一个整数表示哭闹声音总和。

要求使用「文件输入输出」的方式解题，输入文件为 gift.in，输出文件为 gift.out

数据范围

$1≤N≤30$,$N≤M≤5000$,$1≤g_i≤10^7$

输入样例：

3 20
1 2 3

输出样例：

2