/ OIer TK / 题库 /

硬币

硬币

测试数据来自 system/1758

描述

有N堆硬币,每堆个数可以用一个无序N元组来表示{x1,x2,x3,x4,...,xn}即这N堆硬币的个数分别为x1,x2,……。

现在你可以对这N堆硬币进行2种操作。

第一种操作:将其中任意两堆硬币合并成一堆。

第二种操作:将其中某一堆硬币任意分成两堆。

你想通过这两种操作将N堆硬币最终变成M堆,并且这M堆硬币个数为无序M元组{y1,y2,...,ym}。问最少操作次数,如果不能实现这种变换,则将次数视为-1。

格式

输入格式

输入包括两行。

第一行一个整数N,之后跟着N个整数,表示初始硬币个数。

第二行一个整数M,之后跟着M个整数,表示最终硬币个数。

输出格式

输出仅包含一个整数,表示最少次数。

样例1

样例输入1

6 1 2 3 4 5 6
3 7 7 7

样例输出1

3

样例2

样例输入2

7 3 1 4 20 24 16 20
8 5 15 21 14 16 12 2 3

样例输出2

5

限制

每个测试点1s。

提示

总共有10个测试点,每个测试点10分。

测试点1-2:N≤2,M≤2。

测试点3:N=2,M=3。

对于100%数据,1≤N,M≤10,读入的数都不超过50。

信息

ID
1696
难度
9
分类
搜索 | 记忆化搜索 点击显示
标签
(无)
递交数
2
已通过
1
通过率
50%
上传者