2013年8月13日 星期二

1233 - USHER

在紐西蘭的一個大教堂中,每當禮拜結束後,牧師將會給一個收集盒,而這個盒子最多裝 c 元,當教友收到這個盒子時,他將會放入一些錢並且交給下一個教友。現在裡頭混有一個不明人士,每當盒子傳到他手上時,他將會抽出 1 元放入口袋,然後將盒子交給其中一名教友。

每名教友的行為,分別有會傳給哪些教友,以及每次盒子經過時他會放多少錢進去。如果在放的過程中盒子滿了,則將會把盒子立刻地傳到牧師那邊。


計算這個不明人士在最好的情況下,他能偷拿多少錢。

Input

輸入第一行有一個整數,表示接下來會有多少測資組。



每組測資第一行有兩個整數 b, p ,分別表示盒子容量、教友的個數。

(1 <= b <= 1,000,000, 1 <= p <= 500),教友編號為 1, 2, 3, ..., p,不明人士編號為 0。
接著會有一個整數 q,表示這個不明人士可以傳給其中多少教友,則接下來會有 q 個整數緊接在後,表示不明人士可以傳的教友編號。





接下來會有 p 行,在其中第 i 行表示教友 i 的行為,每行第一個整數表示他會有多少行為,每組行為第一個整數為他放入的金額,第二個整數則表示他放完這筆金額後會傳給的人。


Output


對於每組測資,輸出不明人士最多能拿多少錢




測資說明:
盒子最多能放 10 元,而有 2 位教友,其中不明人士會傳給 1 或 2。而教友 1 會放入 6 元後傳給不明人士,或者是放入 4 元後傳給教友 2。教友 2 則是會放入 5 元後傳給不明人士。



不明人士打算只傳給教友 2,教友 2 放入 5 元後,被不明人士抽走 1 元,盒子內部只剩 4 元,再進行一次,到不明人士手中時,又抽走 1 元剩下 7 元,最後傳給教友 2 時,放入 5 元已經超過盒子容量便直接傳給牧師收走。
 
Sample Input



1 
10 2 
2 1 2 
2 6 0 4 2 
1 5 0 
0

Sample Output


2