Bạn của bạn làm việc tại một cảng, nơi anh ta kiểm soát các container được bốc dỡ lên và xuống tàu. Thỉnh thoảng, anh ta sẽ điều chỉnh thông tin trên bản kê hàng để "bỏ quên" một container lại trong cảng và sau đó bán lại những gì có trong đó.

Ngày mai, một con tàu chở tủ lạnh sẽ cập bến, và bạn của bạn thấy cơ hội để "mượn" một container. Tuy nhiên, anh ta không biết giá trị cụ thể của các tủ lạnh bên trong container, chỉ biết trọng lượng tổng của container tại thời điểm container xuất hiện. Do việc trộm đồ rất nguy hiểm, bạn của bạn muốn chọn những container một cách cẩn thận, chỉ khi lợi nhuận xứng đáng với rủi ro.

Do đó, anh ta nhờ bạn giúp. Anh ta biết rằng có \(N\) loại tủ lạnh khác nhau. Với mỗi loại \(i\), anh ta biết:

• Giá trị thị trường \(v_i\)
• Trọng lượng \(w_i\) (kg)

Khi container đến, anh ta biết trọng lượng tổng cộng là \(W\) (kg) và cần bạn viết chương trình tính giá trị nhỏ nhất có thể của các tủ lạnh trong container - vì anh ta muốn tính toán trong trường hợp xấu nhất.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case \((T \le 5)\).
• Với mỗi test case:
• Dòng đầu tiên chứa số nguyên \(W\) - tổng trọng lượng của container (\(W \le 10,000\)).
• Dòng thứ hai chứa số nguyên \(N\) - số lượng loại tủ lạnh (\(1 \le N \le 500\)).
• Sau đó là \(N\) dòng, mỗi dòng chứa hai số nguyên \(v_i\) và \(w_i\) (\(1 \le v_i \le 50,000; 1 \le w_i \le 10,000\)), lần lượt là giá trị và trọng lượng của một loại tủ lạnh.

Dữ liệu ra

• Với mỗi test case, in ra một số nguyên duy nhất \(X\) - giá trị nhỏ nhất có thể của các tủ lạnh có tổng trọng lượng đúng bằng \(W\).
• Nếu không thể chọn tổ hợp nào có tổng trọng lượng đúng bằng \(W\), in ra \(-1\).

Input 1

3
100
2
1 1
30 50
100
2
1 1
50 30
5
2
10 3
20 4

Output 1

60
100
-1