UVA 10130 - SuperSale (Siêu khuyến mãi)

Link bài gốc
Link chấm bài

Có một chương trình bán hàng siêu khuyến mãi tại siêu thị SuperHyperMarket. Khi mua sắm ở đây, với mỗi mặt hàng, khách hàng có thể chọn mua cho mình với số lượng tối đa là 1 với giá cực kỳ rẻ. Ví dụ, một khách hàng có thể mua sắm: 1 tivi, 1 củ cà rốt. Chúng ta đi cùng một đại gia đình đến siêu thị này để mua sắm. Mỗi thành viên trong gia đình có thể mua sắm nhiều mặt hàng. Chúng ta được cho danh sách các mặt hàng với giá thực thế và khối lượng của nó. Và chúng ta cũng được biết, khối lượng tối đa mà mỗi thành viên trong gia đình có thể mang về. Vấn đề đặt ra là tính giá trị lớn nhất của các mặt hàng mà gia đình chúng ta có thể mua sắm.

Dữ liệu

Dữ liệu gồm T bộ test. Số lượng bộ test (1 ≤ T ≤ 1000) được ghi ở dòng đầu tiên.

Mỗi test bắt đầu bởi một dòng chứa một số nguyên N cho biết số lượng mặt hàng tại siêu thị (1 ≤ N ≤ 1000). Tiếp theo là N dòng, mỗi dòng chứa 2 số nguyên P và W. Số đầu tiên (1 ≤ P ≤ 100) cho biết giá thực tế của mặt hàng. Số thứ hai (1 ≤ W ≤ 30) cho biết khối lượng của mặt hàng. Dòng tiếp theo ghi 1 số nguyên G (1 ≤ G ≤ 100) cho biết số lượng thành viên của gia đình chúng ta. G dòng tiếp theo mỗi dòng ghi một số nguyên MW (1 ≤ MW ≤ 1000) lần lượt mô tả khối lượng tối đa các thành viên trong gia đình chúng ta có thể mang về.

Kết quả

Ứng với mỗi test ghi ra giá trị lớn nhất tìm được.

Ví dụ

Sample Input 

2
3 
72 17 
44 23 
31 24 
1 
26 
6 
64 26 
85 22 
52 4 
99 18 
39 13 
54 9 
4 
23 
20 
20 
26 

Sample Output 

72 
514