蓝桥杯2025年第十六届省赛真题-甘蔗

小蓝种了一排甘蔗，甘蔗共 n 根，第 i 根甘蔗的高度为 a_i 。小蓝想砍一些 甘蔗下来品尝，但是他有强迫症，不希望甘蔗的高度显得乱糟糟的。具体来说， 他给出了一个大小为 m 的整数集合 B = {b₁, b₂, · · · , b_m} ，他希望在砍完甘蔗后， 任意两根相邻的甘蔗之间的高度差 |a_i − a_i+1| 都要在这个集合 B 中。小蓝想知道 他最少需要砍多少根甘蔗（对于高度为 h 的甘蔗，他可以将其砍成 x 高度的甘 蔗，x ∈ {0, 1, 2, · · · , h − 1} ）

输入的第一行包含两个正整数 n, m ，用一个空格分隔。 

第二行包含 n 个正整数 a₁, a₂, · · · , a_n ，相邻整数之间使用一个空格分隔。 

第三行包含 m 个正整数 b₁, b₂, · · · , b_m ，相邻整数之间使用一个空格分隔。

输出一行包含一个整数表示答案。如果不能满足条件，输出 −1 。

6 3
6 7 3 4 9 12
2 3 5

2

【样例说明 1】 

其中一种方案：将 a₂ 砍为 3 ，再将 a₃ 砍为 1 。

【样例输入 2】 

2 1 

4 5 

6 

【样例输出 2】

 -1 

【评测用例规模与约定】

 对于 40% 的评测用例，1 ≤ n, m ≤ 8 ； 

对于所有评测用例，1 ≤ n, m ≤ 500 ，1 ≤ a_i ≤ 1000 ，0 ≤ b_i ≤ 1000 。