TopCoder

User's AC Ratio

50.0% (1/2)

Submission's AC Ratio

50.0% (1/2)

Description

殿壬是個天才兒童,他在一個月大的時候就學會數數、六個月大的時候就學會乘法跟除法、一歲時學會寫程式、一歲又六個月時養了可愛的拉不拉多、一歲又十個月時養了可愛的貓咪、兩歲時發明了「吃餅乾」的遊戲,而現在要講的,是殿壬六歲大時的故事。

殿壬六歲時,已經精通大學的所有課程,尤其是跟「經濟學」、「建築學」相關的所有課程,因此,他決定來開間建設公司蓋房子、賣房子,順便來 發大財

已知在殿壬所處的世界中,有 $N$ 種蓋房子的材料(以下簡稱建材),建材以 $1$ 到 $N$ 編號,其中,購買 $2^ {880301}$ 單位的第 $i$ 種建材需要花費 $c_i$ 元。殿壬購買建材時,因為不明原因,一次只能需要購買 $2^ {880301}$ 單位。

而在殿壬經過詳細的市場分析後,他調查出了 $M$ 種房子(房子以 $1$ 到 $M$ 編號),他只要把第 $i$ 種房子蓋出來,他就可以得到 $p_i$ 元的報酬。而蓋第 $i$ 種房子必須要使用 $n_i$ 個建材,使用的第 $j$ 個建材 $a_{ij}$ ,每個建材需要使用 $880301$ 單位。

請你告訴殿壬,他需要購買哪些 建材 ,才能讓他獲得最大的獲利。獲利的定義為(蓋房子得到的總報酬) - (購買建材的總花費)。

Input Format

輸入的第一行有一個正整數 $T$,代表測試資料的筆數。

每筆測試資料總共有 $2 + M$ 行。

第一行有兩個正整數 $N, M$,代表建材個個數,以及房子的種類數。

第二行共有 $N$ 個整數,第 $i$ 個整數為 $c_i$ ,代表購買第 $i$ 種建材所需要的花費。

接下來的 $M$ 行,前兩個數字分別是 $n_i, p_i$ ,代表蓋第 $i$ 種房子所需的建材數,以及蓋第 $i$ 種房子可以獲得的報酬。接下來的 $n_i$ 個數字,第 $j$ 個數字為 $a_{ij}$。保證同一行中,所有的 $a_{ij}$ 皆相異。

  • $1 \le T \le 5$
  • $1 \le N,M \le 2000$
  • $1 \le c_i, p_i \le 10^ 9$
  • $1 \le n_i \le N$
  • $1 \le a_{ij} \le N$
  • 對於單一筆測試資料, $n_i$ 的總和不會超過 $2000$

Output Format

對於每筆測試資料,請輸出三行。

第一行包含一個非負整數 $S$ ,代表殿壬的最大獲利。

第二行請輸出一個非負整數 $Q$ ,代表殿壬需要購買建材的數量。

第三行請輸出 $Q$ 個以空白隔開的 相異 正整數,代表殿壬需要購買的建材編號。如果 $Q = 0$ ,直接輸出一個空白行即可。

如果有許多種購買建材的方法,可以讓殿壬得到最大獲利,輸出任意一組即可。

Sample Input

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

Sample Output

0
0

3
1
1
4
3
1 2 3

Hints

Problem Source

Subtasks

No. Testdata Range Score
1 0~9 1

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 262144 262144 1
1 1000 262144 262144 1
2 1000 262144 262144 1
3 1000 262144 262144 1
4 1000 262144 262144 1
5 1000 262144 262144 1
6 1000 262144 262144 1
7 1000 262144 262144 1
8 1000 262144 262144 1
9 1000 262144 262144 1
10 1000 262144 262144