2134 . 魔法藥水
TopCoder
Tags
Description
從前從前，有 $N$ 個英雄和 $M$ 隻怪物住在一個島上，怪物們最近變得很兇殘，所以英雄們決定要消滅怪物，第 $i$ 個英雄只能消滅 $M_i$ 這個集合裡的其中一隻怪物。周逸身為英雄團的軍師，研發出了一種藥水，可以加強英雄的能力，一罐藥水可以使一個英雄多消滅一隻怪物。由於藥水有些副作用，一個英雄最多只能服用一瓶藥水，請幫助周逸算出要最好的策略下，英雄團最多可以消滅多少隻怪物。
Input Format
第一行有三個整數 $n, m, k$ （$1 \le n, m, k \le 500$）代表英雄的數量、怪物的數量、藥水的數量。
接下來的 $n$ 行，每一行有一個整數 $t_i$ 代表 $M_i$的大小，以及 $t_{i}$ 個整數 $M_{i, j}$，代表第 $i$ 個英雄可以打敗的怪物。
- $1 \le t_i \le m$
- $1 \le M_{i,j} \le m$
Output Format
請輸出英雄團最多可以消滅多少隻怪物。
Sample Input 1
3 5 2
4 1 2 3 5
2 2 5
2 1 2
4 1 2 3 5
2 2 5
2 1 2
Sample Output 1
4
Sample Input 2
5 10 2
2 3 10
5 1 3 4 6 10
5 3 4 6 8 9
3 1 9 10
5 1 3 6 7 10
2 3 10
5 1 3 4 6 10
5 3 4 6 8 9
3 1 9 10
5 1 3 6 7 10
Sample Output 2
7
Hints
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~14 | 1 |