E. 电脑供电

描述

为了加强信息学的学习，瑞瑞购买了笔记本电脑。和其他同学不一样的是，他购买了 nn 台电脑。为了方便电脑供电，瑞瑞准备了 mm 个专用电池。其中第 ii 个电池可以让一台电脑 运行 t_i 分钟。

瑞瑞会同时使用全部 nn 台电脑进行学习。因此，他需要这 nn台电脑不间断的运行。

一开始，他可以给每台电脑连接 至多一个电池 。然后在任意整数时刻，他都可以将一台电脑与它的电池断开连接，并连接另一个电池，他可以进行这个操作 任意次 。新连接的电池可以是一个全新的电池，也可以是别的电脑用过的电池。断开连接和连接新的电池不会花费任何时间。

瑞瑞特别注重高效学习，在nn台电脑都能够运行的时候，他不会给任何电池充电。

在一旁观察的小伙伴辰辰沉默了很久，突然想到一个有趣的问题：这些电池到底能够支撑瑞瑞学习多久？换句话说，就是这些电池可以让 nn 台电脑同时运行的 最长 分钟数是多少？

输入

第一行2个正整数 nn 和 mm;

第二行

为一个长度为 mm 的整数序列，其中第ii个数表示第ii个电池能让一台电脑运行的分钟数 t_i

输出

一个整数，表示这些电池可以让 nn 台电脑同时运行的 最长 分钟数。

样例

输入

2 3 3 3 3 输出

4

输入 5 8 10 10 3 5 7 7 2 4

输出

9 提示 数据范围

对于 20%20% 的数据， 1 \le n \le m \le 101≤n≤m≤10, 1 \le t_i \le 101≤t i ​ ≤10；

对于 40%40% 的数据 ，1 \le n \le m \le 10001≤n≤m≤1000, 1 \le t_i \le 10^61≤t i ​ ≤10 6 ；

对于 100%100% 的数据， 1 \le n \le m \le 2\times 10^51≤n≤m≤2×10 5 , 1 \le t_i \le 10^91≤t i ​ ≤10 9 。