Heo đất chứa bao nhiêu

Bé Na có một con heo đất kín, không thể nhìn vào trong. Cách duy nhất để đoán số tiền bên trong là cân nó. Biết cân nặng của heo khi rỗng là \(E\) và khi đầy xu là \(F\) (tính bằng gam), cùng với \(N\) loại đồng xu: loại thứ \(i\) có giá trị \(P_i\) và nặng \(W_i\) gam; mỗi loại có số lượng không hạn chế. Con heo hiện đang chứa các đồng xu có tổng cân nặng đúng bằng \(F - E\).

Hãy tính số tiền nhỏ nhất có thể có trong con heo. Nếu không có cách chọn xu nào cho tổng cân nặng đúng bằng \(F - E\) (kể cả khi \(F < E\)), in ra \(-1\). Nếu \(F = E\) thì heo không chứa xu nào và đáp án là \(0\).

Input

• Dòng đầu chứa số nguyên \(T\) là số bộ dữ liệu.
• Mỗi bộ dữ liệu: dòng đầu chứa hai số nguyên \(E\) và \(F\); dòng thứ hai chứa số nguyên \(N\); tiếp theo là \(N\) dòng, mỗi dòng chứa hai số nguyên \(P_i\) và \(W_i\).

Output

Với mỗi bộ dữ liệu, in ra một dòng: số tiền nhỏ nhất có thể có, hoặc \(-1\).

Constraints

• \(1 \le E, F \le 10000\)
• \(1 \le N \le 500\)
• \(1 \le P_i \le 50000\)
• \(1 \le W_i \le 10000\)
• Số bộ dữ liệu \(T \le 20\).

Sample Input

3
20 50
2
4 5
7 10
1 6
2
3 2
9 4
8 8
1
3 2

Sample Output

21
-1
0

Explanation

Bộ 1: tổng cân nặng xu là \(30\). Có thể dùng \(6\) xu loại 1 (giá \(24\)) hoặc \(3\) xu loại 2 (giá \(21\)); phương án rẻ nhất là \(21\). Bộ 2: cần cân nặng \(5\) nhưng các xu chỉ nặng \(2\) hoặc \(4\) gam nên tổng luôn chẵn, không có cách nào. Bộ 3: \(F=E\) nên heo rỗng, số tiền là \(0\).