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)上會有一個整數 Q_i (0 <= Q_i <= Q) 表示第 i 站的 queue 的個數(從 front 給到 rear)，並且接下來會有 Q_i 個整數表示貨物要放置的目的地貨物站。假設這些貨物不會有 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.”