#AIC8239. 蛋糕装盒

蛋糕装盒

蛋糕装盒

童童的妈妈做了 xx 个蛋糕,现有 yy 个蛋糕盒可以包装。一个容量为 vv 的蛋糕盒能装入体积不超过 vv 的蛋糕,一个蛋糕只能用一个蛋糕盒来装,一个蛋糕盒也只能用来装一个蛋糕。买一个蛋糕盒的价格由蛋糕盒的容量决定,容量为v的蛋糕盒的价格为 vv。 请你帮童童妈妈算一算,怎样花最少的钱把 xx 个蛋糕全部装盒。

输入格式

共三行。 第一行,两个正整数 xx 和 yy( 1≤x,y≤1051 ≤ x,y≤10^5 ),分别表示需要包装的蛋糕个数和现有蛋糕盒的个数。 第二行,xx 个正整数,依次表示每个蛋糕的体积,数字之间使用一个空格隔开。 第三行,yy 个正整数,依次表示每个蛋糕盒的容积,数字之间使用一个空格隔开。

输出格式

一行,一个整数。如果能将所有的蛋糕装入已有的盒子,则输出用掉的蛋糕盒所花的最少钱数;如果无法将所有的蛋糕装入 yy 个盒子,则输出 −1-1。


3 4
10 1 5
1 8 11 5


17


3 4
5 10 15
1 5 8 11


-1

数据范围

时间限制: 1000ms

内存限制: 128MB