2013年7月13日 星期六

10172 - The Lonesome Cargo Distributor


Problem E
The Lonesome Cargo Distributor
Input: standard input
Output: standard output
Time Limit: 3 seconds

普魯士人們相信在Cosco International Airport (CIA,中遠國際機場Airport Based Cargo Distribution & Embarkation Facility (ABCDEF,機場貨物分配設施) 是全球最大的設施,卻在普魯士排名第二大。貨物飛機來自於各個國家與飛往不同國家,而 ABCDEF 負責貨物的卸載於貨物飛機之間。

每個貨物是一個固定大小的立方盒子 ,並且有標籤附加要抵達的目的地國家,方便起見,每個國家被指派一個特別的 ID。例如有 n 個國家,每個國家的編號為 1 到 n
每個國家 X  都各自擁有自己的貨物站(cargo station),被標記為該國家的編號。每個貨物站有兩個平台(平台 A 和 平台 B),平台 A 放置要被送到國家 X 的貨物,而平台 B 則是一個隊列(queue),放置要從國家 X  運到其他國家(不會是 X)的貨物。這 n 個貨物站呈現環狀排列,連的方式如下 (1, 2), (2, 3), (3, 4), ..., (n - 1, n) , (n, 1),任兩個相鄰對連在旁邊。

ABCDEF  有許多陸上運行的貨物車(cargo carriers),它可以在站與站之間運送貨物。但是通道相當地窄,一次最多只能有一台貨物車通過 (雖然已經有限制貨物車的最大攜帶量),貨物只能從貨物車的底端被拿出,可以想像成堆疊 ( stack ) 結構,當上層還有貨物時,下層貨物無法被提取。例如,要提取第三個貨物時,必須要移除最上層的兩個貨物。
一個貨物車嚴格地順著環狀移動,即從站 1 移動到站 2,從站 2 移動到站 3,... ,最後再由站 n 移動到站 1,繼續剛剛的步驟。每次移動到下一個站耗費 2 分鐘。

在抵達任何一個站 X 時,貨物車會先嘗試卸下貨物,依序從 stack 頂部開始移除貨物,如果抵達目的地是 X,則將貨物放入平台 A,反之放入平台 B 的隊尾,直到貨物車為空或者隊列滿。每卸下一個貨物耗費 1 分鐘,因此要卸下 3 個貨物,就會消耗 3 分鐘,當卸下流程結束後,貨物車開始要裝載貨物,貨物依序從平台 B 的 queue 前端貨物開始丟入貨物車的 stack,直到 stack 滿,或者 queue 為空。每次裝載也消耗 1 分鐘,因此要裝載 4 個貨物,就會消耗 4 分鐘。此時貨物車會移動到下一個貨物站。

這種方式已經使用很多年, 貨物車將貨物從平台 B 移動到平台 A,直到每個貨物移動到正確的貨物飛機上,以抵達目的地。
但是從管理階層因薪水爆發衝突後,ABCDEF 的員工從上星期天開始採無期限罷工,飛機抵達和離開時沒有任何一個人來卸載貨物,由於沒有人來分配貨物,整個設施已經陷入停頓。

你總是被老闆的手下所憎恨,因此你決定要打破罷工,並且從明天早上開始工作,分配所有對列中的貨物, 直到它們都在正確的貨物站。一開始你的貨物車上是空的,且起始於站 1,持續地移動到下一個站進行分配,但是在工作開始前,寫一個程式計算工作要耗費多久時間。

Input


輸入第一行,會有一個整數 SET,表示會有多少測資組。
每組測資第一行會有三個整數 N, S, Q  分別表示站的個數、貨物車的最大容量及每個隊列的最大容量,假設所有站的隊列容量相同。
(2 <= N <= 100, 1 <= S <= 100, 1 <= Q <= 100) 
接下來會有 N 行,第 i 行(1 <= i <= N)上會有一個整數 Qi (0 <= Qi <= Q) 表示第 i 站的 queue 的個數(從 front 給到 rear),並且接下來會有 Qi 個整數表示貨物要放置的目的地貨物站。假設這些貨物不會有 i  為目的地。 

Output


對於每組測資,輸出工作消耗的時間。

Sample Input

2
5 2 3
3 4 5 2
2 1 3
0
3 3 5 1
1 4
5 2 3
3 4 5 2
2 1 3
0
3 3 5 1
1 4

Sample Output

72
72


Rezaul Alam Chowdhury



“All good things must come to an end.”