2128 . 殿壬發大財
TopCoder
Tags
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 1
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 1
0
3
1
1
4
3
1 2 3
Hints
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~9 | 1 |