2013年7月18日 星期四

1047 - Zones

現在的手機使得我們可以無時無刻任何地方打給其他人 ,而不需要經由過時代的纜線傳輸,但如果附近沒有基地台,手機將無法使用。

在丘陵山區中,基地台將提供圓形區域內的服務,電信公司計劃要建造數座基地台,建造太多的基地台會引來民眾抱怨,也不能建太少,使得民眾無法得到服務也會引來抱怨,如果兩個基地台太靠近,則會造成效率低落。



國際手機公司正在發展一套網路策略,找到一種最佳放置基地台的方式,盡可能地服務越多的顧客,這麼一來就可以取代靠纜線傳輸的家用電話。


如圖顯示,有種個基地台的放置計畫,5 號台將服務 25 名顧客,而其中 6 名同時也可以收到 4 號台的服務,而 1, 2, 3 號台則會同時服務 3 名顧客。

這五座基地台的興建很快就開始了,但由於基地台的管理議題導致只能興建三座基地台,而希望三座基地台能服務最多的顧客。而找到其中一組最佳的興建選擇為 2, 4, 5 號台的興建。


寫一個程式找到最佳的設置方式,服務一樣多的顧客時,取字典順序小的方案。

Input 

輸入有多組測資。
每組第一行會有兩個整數 n, b (1 <= b <= n <= 20),分別表示基地台的個數以及最後會興建的基地台個數。
接下來會有 n 個整數,每個整數表示該基地的服務總人數( < 1,000,000)。

接下來會有一個整數 m (m <= 10),表示有多少共同服務的區域,

接下來會有  m 行描述共同區域的資訊,格式為第一個整數 t 為有多少塔共同服務這個區域,而接下來將會有 t 個整數描述塔的編號,最後一個數字表示該共同區域的顧客個數。


最後一行以 n = b = 0 結束程序。

Output 

對於每組測資,輸出服務的最多人數,以及設置基地台的方案。

每組測資後,輸出一行空行。

Sample Input 

5  3                                                       
15 20 25 30 24                                             
5                                                           
2  1 2     7                                               
3  1 2 3   3                                               
2  2 3     2                                               
2  3 4     5                                                
2  4 5     6                                               
5  3                                                       
25 25 25 25 25                                             
4                                                           
2  1 2     5 
2  2 3     5 
2  3 4     5 
2  4 5     5 
5  3 
25 25 25 25 25 
0 
0 0

Sample Output 

Case Number  1 
Number of Customers: 68 
Locations recommended: 2 4 5 
  
Case Number  2 
Number of Customers: 75 
Locations recommended: 1 3 5 
  
Case Number  3 
Number of Customers: 75 
Locations recommended: 1 2 3