#D0946. 零食装车

零食装车

零食装车

33DAI 有 nn 件零食,第 ii 件重 wiw_i 千克。Tom 叫来 mm 个朋友,第 jj 人的负重上限为 sjs_j 千克,每人最多搬 11 件。

请安排搬运方案,使被搬走的零食总重量最大。

输入格式

  • 第一行两个整数 nnmm
  • 第二行 nn 个整数 w1,w2,,wnw_1, w_2, \ldots, w_n
  • 第三行 mm 个整数 s1,s2,,sms_1, s_2, \ldots, s_m

输出格式

  • 第一行一个整数,表示被搬走的零食总重量的最大值。
  • 第二行 mm 个整数 p1,p2,,pmp_1, p_2, \ldots, p_m,其中 pjp_j 表示第 jj 个朋友搬走的零食编号(1pjn1 \le p_j \le n);如果第 jj 个朋友不搬任何零食,则 pj=0p_j = 0

你的方案需要满足:

  1. 每个朋友最多搬 1 件零食,且每件零食最多被 1 个人搬走;
  2. pj=0p_j = 0wpjsjw_{p_j} \le s_j
  3. 被搬走的零食总重量恰好等于第一行输出的最大值。

满足以上条件的方案可能有多种,输出任意一种即可。

3 2
1 2 3
2 5
5
2 3
3 2
8 1 1
2 3
2
3 2
1 1
5
5
5
1

数据范围

  • 1n,m2×1051 \le n, m \le 2 \times 10^5
  • 1wi,sj1091 \le w_i, s_j \le 10^9

子任务设置

  • 子任务 1(30 分):n,m20n, m \le 20
  • 子任务 2(30 分):所有零食重量相同(w1=w2==wnw_1 = w_2 = \cdots = w_n)。
  • 子任务 3(40 分):无特殊限制。