2199 . 大促銷改（Discount）
TopCoder
Tags
Description
家豪超市正在舉行一年一度的大特賣，有許多的優惠組合供顧客選購。
每個優惠組合 $S$ 可能含有一個或以上的商品，如果一次購買這些商品的話，可以用優惠價購買，當然也可以選擇用原價一項一項購買。我們說兩種優惠組合 $S_i,S_j$ 產生衝突代表存在一個商品同時被這兩種優惠組合所包含，所謂並用即代表使用了會產生衝突的優惠組合。
超市內有 $N$ 項商品、 $M$ 種優惠組合，你現在有 $X$ 元，你想要盡可能的買多一點種類的商品回家，且同樣的商品只能買一次，請問在最佳的購買策略、以及不使用會衝突的優惠組合的情況下，你最多能購買幾種商品？
當然，這個問題非常的困難，因此我們保證「若把所有優惠組合當成 $M$ 個點，在會衝突的優惠組合對之間建邊的話，將不會存在任何環」。
家豪：沒人說優惠價一定要比較便宜 O $\omega$ O
Input Format
首行輸入三個整數 $N,M,X$，分別代表商品種類、優惠組合數量以及你擁有的錢。
接下來一行有 $N$ 個正整數，第 $i$ 個數字 $p_i$ 代表 $i$ 號物品的價格。
接下來 $M$ 行，第 $i$ 行第一個數字 $d_i$ 代表第 $i$ 個優惠組合的價格，第二個數字 $k_i$ 代表這個優惠組合含有幾種商品，接下來會有 $k_i$ 個正整數 $c_{ij}$，代表這個優惠組合含有 $c_{ij}$ 號商品。
Output Format
請輸出一個整數，代表你最多能買到幾種物品。
Sample Input 1
5 2 7
1 2 5 3 4
6 2 2 3
5 3 1 4 5
1 2 5 3 4
6 2 2 3
5 3 1 4 5
Sample Output 1
4
Sample Input 2
6 4 17
2 5 7 3 4 3
3 2 1 2
9 2 4 5
10 2 2 3
8 2 3 5
2 5 7 3 4 3
3 2 1 2
9 2 4 5
10 2 2 3
8 2 3 5
Sample Output 2
6
Hints
測資限制：
- $1\le N\le 3000$。
- $0\le M$。
- $1\le k_i,c_{ij}\le N$。
- $1\le p_i,d_i,X\le 10^ 9$。
- 若把所有優惠組合當成 $M$ 個點，在會衝突的優惠組合對之間建邊的話，將不會存在任何環。
本題共有 $6$ 組測試題組，條件限制如下所示。每一組可有一或多筆測試資料，該組所有測試資料皆需答對才會獲得該組分數。
- ($14\%$) $N\le 10$，$p_i,d_i,X\le 3000$。
- ($17\%$) $p_i,d_i,X\le 3000$，任兩個優惠組合之間皆不衝突。
- ($11\%$) 任兩個優惠組合之間皆不衝突。
- ($33\%$) $N\le 300$。
- ($13\%$) $p_i,d_i,X\le 3000$。
- ($12\%$) 無額外限制。
Problem Source
2021 板中TOI模考模擬賽
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 2~26 | $N\le 10$，$p_i,d_i,X\le 3000$。 | 14 |
| 2 | 27~39 | $p_i,d_i,X\le 3000$，任兩個優惠組合之間皆不衝突。 | 17 |
| 3 | 27~52 | 任兩個優惠組合之間皆不衝突。 | 11 |
| 4 | 53~68 | $N\le 300$。 | 33 |
| 5 | 2~39, 69~94 | $p_i,d_i,X\le 3000$。 | 13 |
| 6 | 0~119 | 無額外限制。 | 12 |