#P1378. 填数游戏

填数游戏

时间限制:C/C++1C/C++1秒,其他语言22秒 空间限制:C/C++256MBC/C++ 256 MB,其他语言512MB512 MB

题目描述

小A在玩一个填数游戏。 游戏的规则是这样的:一共有n个数和n个待填空位(每个数和每个空位一一对应),小A手上有m个数(nmn\le m),小A可以从这m个数选取n个数填入空位中,他可以得到的分数就是每个空位对应的数乘上小A在空位上填入的数字的和。

现在小A想问你,他可以得到的最大分数是多少?

注意,小A必须将所有空格都填上数字。

输入描述:

第一行两个数,n和m,分别代表代填空位有n个,小A手上有m个数。 第二行n个数aia_i​,表示第i个代填空位对应的数。 第三行m个数bib_i,表示小A可以填入空位的数(每个数只能用一次)。

输出描述:

一个数ans表示小A可以得到的最大分数。。

示例11

输入

3 3
1 2 3
1 1 1

输出

6

备注:

  • 对于10%的数据,有1nm101\le n \le m \le10
  • 对于50%的数据,有1nm1031\le n \le m \le 10^3
  • 对于另外30%的数据,有1n=m1051\le n = m \le 10^5
  • 对于100%的数据,有1nm1051\le n \le m\le 10^5ai,bi105|a_i|,|b_i|\le 10^5