問題一覧 > 通常問題

No.2869 yuusaan's Knapsacks

レベル : / AI推定難易度 : 1700 / 実行時間制限 : 1ケース 4.500秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 47
作問者 : yuusaan / テスター : 寝癖 👑 seekworser
お気に入りにしたユーザー ProblemId : 11204 / 自分の提出
問題文最終更新日: 2024-09-25 11:20:49
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 443 (順位表) の他の問題:

Note

The time limit is strict, so we recommend using a fast language.

Story

Once again, you have been taken to a parallel world by Yuusaan.

"All right, I'm going to decide the importance of the things I find here again, so make sure you can compute the maximum total importance within what fits in the knapsacks.

This time I don't need any objects with negative mass... but I want to pack lots of everything else, so I brought many knapsacks.

Oh, that's right. While you're at it, write the code so that it also tells me how to pack the things."

Problem Statement

There are $N$ knapsacks and $M$ items. The knapsacks are numbered from $1$ to $N$, and the items are numbered from $1$ to $M$.

Here, for each pair of integers $i,j(1\leq i \leq N,1\leq j \leq M)$, knapsack $i$ has durability $e_i$, and item $j$ has value $v_j$ and weight $w_j$.

Yuusaan puts $0$ or more items into each knapsack. For every knapsack, the total weight of the items put into it must not exceed its durability.

Also, a single item cannot be put into more than one knapsack.

Among the ways of packing items that satisfy the above conditions, find the maximum possible total value of the items put into the knapsacks.

Also, show one way of packing items that achieves this maximum total value. (See the "Output" section for the specific output format.)

(Note that in this problem, $e_i$ is not a symbol representing Napier's constant.)

Input

$N\ M$
$e_1\ e_2 \ e_3 \dots e_N$
$v_1\ w_1$
$v_2\ w_2$
$\vdots$
$v_M\ w_M$

Constraints

  • $1\leq N \leq M$
  • $1\leq M \leq $ $16$
  • $1\leq e_i \leq 10^9$
  • $1\leq w_i\leq 10^9$
  • $1\leq v_i \leq 10^7$
  • All inputs are integers.

Output

Output $N+1$ lines.

On line $1$, output the maximum possible total value of the items put into the knapsacks.

On line $2$ onward, output one way of packing items that maximizes the total value of the items.

More specifically, for that way of packing, on line $i+1$, output the number of items put into knapsack $i$ followed by the numbers of all the items put into it, in this order, separated by spaces.

If there are multiple solutions satisfying the conditions, any of them will be accepted.

Print a newline at the end.

Sample

Sample 1
Input
3 5
5 2 3
2 2
3 2
5 3
3 3
3 4
Sample Output
13
2 1 3
1 2
1 4

If items $1,3$ are put into knapsack $1$, item $2$ into knapsack $2$, and item $4$ into knapsack $3$, the total value is $13$, which is the maximum.

Other ways of packing, such as putting items $2,4$ into knapsack $1$, item $1$ into knapsack $2$, and item $3$ into knapsack $3$, are also accepted.

Sample 2
Input
5 5
10 15 20 25 30
100 50
100 50
100 50
100 50
100 50
Sample Output
0
0
0
0
0
0

All the items are too heavy, so none of them can be put into a knapsack.

Sample 3
Input
5 6
4 7 1 2 1
23 2
14 5
72 7
21 2
35 3
12 1
Sample Output
142
2 5 6
1 3
0
1 1
0

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。