← 返回题目列表

AtCoder · past202303_m

M. 清理

中文机器翻译题面 查看原题

问题陈述

我们有 N 包裹编号 1 to N。包裹 i 的大小为 A_i.
有 M 盒子编号 1 to M 按数字顺序排列成行:方框 1 是最左边的,方框 M 是最右边的。 盒子 i 的大小为 B_i.
每个箱子可以容纳任意数量的包裹,只要包裹的总尺寸不大于箱子的尺寸即可。

对于包裹订单中的每个包裹 1 到包裹 N,高桥将尝试执行以下操作:

  • 将包裹放入最左边可以容纳它的盒子中。

确定高桥是否可以将所有包裹放入箱子中。

另外,如果可以的话,将所有包裹放入箱子后,求出每个箱子中包裹的总尺寸;否则,找到他无法放入盒子的包裹的最小编号。

约束

  • 1 \leq N \leq 2\times 10^5
  • 1 \leq M \leq 2\times 10^5
  • 1 \leq A_i,B_i \leq 10^9
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_M

输出

如果高桥可以将所有包裹放入箱子中:
第一行应包含 Yes.
第二行应包含 C_1,C_2,\ldots,C_M 之间有空格,其中 C_i 是箱内包裹的总尺寸 i 将所有包裹放入箱子后。
如果高桥无法将所有包裹放入箱子中:
第一行应包含 No.
第二行应该包含他无法放入盒子的包裹的最小编号。


示例输入 1

3 3
4 7 3
10 4 8

示例输出 1

Yes
7 0 7

高桥将执行以下操作。

  • 包裹 1 可以放入盒子中 1, 2,或 3。他把它放进最左边的盒子里 1.
  • 包裹 2 可以放入盒子中 3。他把它放进这个盒子里。
  • 包裹 3 可以放入盒子中 1 or 2。他把它放进最左边的盒子里 1.

请注意,当他尝试放置包裹时 2,包裹 1 已装箱 1,所以包裹 2 无法放入此框中。

当所有包裹都装箱时,

  • 盒子 1 包含包裹 1 和 3,总大小为 3+4=7,
  • 盒子 2 不包含包裹,总尺寸为 0,和
  • 盒子 3 包含包裹 2,总大小为 7.

示例输入 2

3 2
4 7 3
10 4

示例输出 2

No
2

高桥将执行以下操作。

  • 包裹 1 可以放入盒子中 1 or 2。他把它放进最左边的盒子里 1.
  • 包裹 2 不能放入任何盒子中。

示例输入 3

5 5
5 4 3 2 1
1 2 3 4 5

示例输出 3

Yes
1 2 3 4 5