Một công ty thương mại điện tử cung cấp dịch vụ mua gạo trực tuyến. Hôm nay, sau khi nhận các đơn đặt hàng từ các hộ gia đình ở một con phố nọ, công ty tiến hành giao hàng cho các hộ gia đình này.

Để đơn giản, con phố được biểu diễn như trục toạ độ. Có ~n~ đơn hàng mua gạo trực tuyến được đặt. Các đơn hàng được đánh số từ ~1~ đến ~n~, đơn hàng thứ ~i~ yêu cầu giao ~d_i~ bao gạo về hộ gia đình sống tại điểm có toạ độ ~x_i~. Tất cả các hộ gia đình có đơn đặt hàng đều sống ở các điểm có toạ độ dương.

Ngoài ra, trên con phố còn có ~m~ nhà cung cấp gạo, những nơi cung cấp gạo này được đặt tại các điểm có toạ độ dương ~s_1, s_2, \ldots, s_m~. Biết rằng mỗi nhà cung cấp có thể cho ra số lượng gạo lớn tuỳ ý, đồng thời địa điểm của ~n~ hộ gia đình có đơn đặt mua gạo và địa điểm của ~m~ nhà cung cấp gạo là ~n + m~ điểm đôi một phân biệt.

Công ty điều động một xe tải để tiến hành giao gạo cho các hộ dân trên con phố này. Xe tải có sức chứa tối đa ~c~ bao gạo. Xe tải tiến hành giao gạo theo chiến lược sau:

• Đầu tiên, xe xuất phát tại bến ở điểm có toạ độ ~0~. Lúc này, trên xe có số gạo đúng bằng sức chứa của xe (tức xe có ~c~ bao gạo).

• Xe tiến hành di chuyển theo chiều dương của trục toạ độ. Trong suốt quá trình đi, xe không bao giờ đổi hướng. Nói cách khác, theo thời gian, toạ độ của vị trí của xe chỉ tăng mà không bao giờ giảm.

• Khi tới vị trí của một hộ gia đình có đơn đặt mua gạo, nếu trên xe có đủ số gạo để phát cho họ, tài xế sẽ giao đúng số gạo mà đơn hàng yêu cầu. Ngược lại, nếu trên xe không có đủ số gạo mà hộ gia đình yêu cầu, tài xế sẽ bỏ qua đơn hàng và đi tiếp.

• Khi tới vị trí của một nhà cung cấp gạo, tài xế sẽ lấy thêm gạo để đưa vào xe cho tới khi số gạo trên xe đúng bằng sức chứa của xe.

Hãy cho biết, với chiến lược giao hàng như trên, có bao nhiêu bao gạo được giao tới các hộ gia đình.

Input

Dòng đầu tiên chứa số nguyên ~\tau~ ~(1 \leq \tau \leq 10)~ là số bộ dữ liệu. Tiếp theo là ~\tau~ bộ dữ liệu, mỗi bộ dữ liệu được mô tả theo khuôn dạng sau:

• Dòng đầu tiên chứa ba số nguyên ~c~, ~m~ và ~n~ ~(1 \leq c \leq 10^9, 1 \leq n, m, n + m \leq 10^6)~ lần lượt là số bao gạo tối đa có thể mang lên xe tải, số nhà cung cấp gạo và số đơn đặt hàng.

• Dòng thứ hai chứa ~m~ số nguyên ~s_1, s_2, \ldots, s_m~ ~(1 \leq s_i \leq 10^9)~ thể hiện vị trí của các nhà cung cấp gạo.

• Trong ~n~ dòng cuối cùng, dòng thứ ~i~ chứa hai số nguyên ~x_i~ và ~d_i~ ~(1 \leq x_i, d_i \leq 10^9)~ lần lượt là vị trí của hộ gia đình đặt hàng và số bao gạo trong đơn hàng thứ ~i~.

Dữ liệu vào đảm bảo ~x_1, x_2, \ldots, x_n~ và ~s_1, s_2, \ldots, s_m~ là ~n + m~ số nguyên đôi một phân biệt.

Output

Với mỗi bộ dữ liệu, in ra một số nguyên dương là tổng số bao gạo được giao đến các hộ gia đình.

Sample Input 1

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

Sample Output 1

80
6
0
1

Notes