Problem : 175 - 萬聖節派對

Problem Statistics

Solved Member: 8　　Submission: 26　　User Tried: 11

Statement:

傑克萬邀請了一些朋友來家裡開趴
萬聖節當然要弄點南瓜派來吃
南瓜派總共有20種不同的配料，以大寫字母A-T記之
現在傑克萬面臨到一個麻煩
每個朋友都有他們對配料的「希望」，想要某配料出現或是不想要某配料出現
同一個南瓜派，想要滿足所有人的所有願望是很困難甚至不可能的

這時傑克萬希望知道，對於n個朋友列出來的希望清單
是否存在一種製作南瓜派的方法，使得「每位朋友至少有一樣希望被滿足」
當然了，每個人的願望都被傾聽只是最基本、他還希望知道最多能滿足多少個願望

Input:Output:

每個測試檔僅有一筆測試資料。
第一行僅有一個正整數n，代表這場派對來了n位(最多100)朋友
接下來n行代表這n位朋友的希望
每行開頭有a,b兩個整數(1≦a≦20,1≦b≦20)，表示這位朋友有a樣配料希望添加、不希望b樣配料出現
該行緊接著有兩個字串(以空格隔開)，代表他希望出現的配料清單、以及希望不出現的配料清單
當然了，給出來的清單都是合法的、不會發生有人既喜歡一個配料又討厭一種配料這種矛盾的事情

輸出唯一的一行，包含一個整數
假如不可能讓每位朋友都完成至少一樣願望，輸出-1
否則輸出合法的方案中，最多願望被達成的數量

Sample Input:Sample Output:

4
3 1 ABC D
3 1 CDE F
1 4 F ACBD
1 1 A F

HINT:

範例測資中，應該選擇ACE三種配料，四位朋友分別滿足了3/3/2/2樣希望

Source:

101校內培訓

Problem Setter

lajisongyy_jack1

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1-1	1000ms	65536kb	20
1-2	1000ms	65536kb
2	2000ms	65536kb	20
3	5000ms	65536kb	20
4	10000ms	65536kb	20
5	10000ms	65536kb	20