Migrated from Lutece 2544 卷

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

内卷之风在社会盛行，学校也不例外。老师现在共有 $M$ 份任务准备全部分给 $N$ 位学生完成（每个任务只能分配给一个人）。每个学生有一个焦虑度，可假设第 $i$ 个学生的焦虑度为 $a_i$。分配完任务后，对于第 $i$ 个学生，如果共有 $t_i$ 个学生得到的任务比他更多，那么第 $i$ 个学生会产生 $a_it_i$ 的焦虑情绪（第 $i$ 个学生的 $t_i$ 为 $0$ 时该学生的焦虑情绪为 $0$）。

给定 $N,M$ 和序列 $a$，请你帮助这位好心的老师安排一种分配方式，使得每个学生至少分配到一个任务，并且所有学生的焦虑情绪总和最小。

Input

第一行包含两个整数 $N\ (1\le N\le100)$ 和 $M\ (N\le M\le 5\times 10^3)$，表示学生人数和任务数量。

第二行包含以空格间隔的 $N$ 个整数，第 $i$ 个数为 $a_i\ (1\le a_i\le 10^7)$，表示第 $i$ 个学生的焦虑度。

Output

输出一个整数表示所有学生的最小焦虑情绪总和。

Samples

3 20
1 2 3

2

Resources

2021 UESTC ICPC Training for Dynamic Programming