注意点

実行時間制限が厳しいため、高速な言語の使用を推奨します。

ストーリー

あなたはまたゆ～さんに連れられて並行世界にやってきました。

「じゃあまたここで見つけたものに対して重要度を決めておくから、ナップサックに入れられる範囲での重要度の合計の最大値を計算できるようにしておいてね。

今回は負の質量を持つ物体はいらないんだけど...それ以外のものをいっぱい入れたいからナップサックをたくさん持ってきたんだ。

あ、そうだ。ついでにものをどう入れたらいいかも教えてくれるようにコードを書いてくれ。」

問題文

$N$ 個のナップサックと $M$ 個の荷物があります。各ナップサックには $1$ から $N$ までの、各荷物には $1$ から $M$ までの番号が振られています。

ここで、各整数 $i,j(1\leq i \leq N,1\leq j \leq M)$ について、ナップサック $i$ の耐久値は $e_i$ で、荷物 $j$ の価値は $v_j$ 、重さは $w_j$ です。

ゆ～さんは各ナップサックに $0$ 個以上の荷物を入れます。このとき、全てのナップサックについて、入れた荷物の合計の重さが耐久値を上回ってはいけません。

また、一つの荷物を複数のナップサックに入れることもできません。

上記の条件を満たす荷物の入れ方で、ナップサックに入れられた荷物の合計価値としてあり得る最大値を求めてください。

また、その合計価値が最大となる荷物の入れ方を一つ示してください。(具体的な出力については「出力」の項目を参照してください。)

(この問題において、$e_i$ はネイピア数を表す記号ではない点に注意してください。)

入力

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

制約

• $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$
• 入力はすべて整数

出力

$N+1$ 行出力して下さい。

$1$ 行目にはナップサックに入れる荷物の価値の合計としてあり得る最大値を、

$2$ 行目以降には、荷物の価値の合計が最大となる荷物の入れ方の一つを出力してください。

より具体的には、その荷物の入れ方の一つについて、$i+1$ 行目には、ナップサック $i$ に入れる荷物の個数と、入れる荷物の番号全てをこの順に空白区切りで出力してください。

条件を満たす解が複数ある場合、どれを出力しても正解となります。

最後に改行してください。

サンプル

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

13
2 1 3
1 2
1 4

5 5
10 15 20 25 30
100 50
100 50
100 50
100 50
100 50

0
0
0
0
0
0

5 6
4 7 1 2 1
23 2
14 5
72 7
21 2
35 3
12 1

142
2 5 6
1 3
0
1 1
0