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