#P18411. Joining Cats

Joining Cats

Joining Cats

Suzukaze Aoba 有一把魔法风扇。一条直线上从左到右坐着 n 只猫,她想知道能否通过最多 k 次启动风扇,把所有猫合并成一只。

第 i 次启动风扇会产生一阵强度恰好为 s_i的风。对于每阵风,Aoba 可以选择它的出发位置,以及向东或向西的方向。风从出发位置开始,以恒定速度沿所选方向连续移动。Aoba 可以在任意时刻关闭风扇,此时风消失。

当风遇到一只猫时:

  • 如果猫的重量严格大于风的强度,风扇自动关闭。
  • 否则,猫会持续被推向风吹的方向。

两只猫相遇时,会合并成一只重量等于二者重量之和的猫。上述规则随即作用于新合并的猫。因此,一次接触已经完成合并,即使新重量超过风强,也只是让风在这次合并后停止。

判断最多启动 k 次风扇,能否让所有猫合并成一只。风强必须按给定的启动顺序使用,不能自行选择或排序。

输入格式

第一行两个整数 n、k,满足1≤n,k≤5000。

第二行 n 个整数 w_1,…,w_n,表示初始从左至右各只猫的重量,1≤w_i≤1000000000。任意两只猫初始坐在不同的位置。

第三行 k 个整数 s_1,…,s_k,表示第1次至第k次启动的风强,1≤s_i≤1000000000。

输入只有一组数据。

输出格式

输出一行一个区分大小写的单词:若可以合并成一只猫,输出 Yes,否则输出 No。

样例 1

5 2
1 1 1 1 1
2 2
Yes

样例 2

6 7
3 2 1 1 2 3
2 2 2 2 2 2 2
No

样例 3

7 4
1 2 3 4 3 2 1
3 3 3 3
Yes

样例 4

5 1
5 4 3 2 1
10
Yes