Hệ thống siêu thị Beg Free hiện đang có một chương trình khuyến mại siêu hại não dành riêng cho các khách hàng trung thành. Bằng việc mua các sản phẩm độc quyền của siêu thị, khách hàng có thể thu thập ~m~ loại phiếu giải thưởng (gọi ngắn gọn là coupon), mỗi loại coupon được đánh số từ 1 đến ~m~. Các phiếu giải thưởng này được sử dụng trong ~n~ chương trình giảm giá của siêu thị. Cụ thể, để có thể nhận được ưu đãi giảm giá của chương trình thứ ~i~, khách hàng cần nộp lại cho siêu thị ~k_i~ coupon thuộc các loại ~T_{i,1}, T_{i,2}, \ldots, T_{i,k_i}~, và sau đó khách hàng đó sẽ được giảm giá ~x_i~ đơn vị tiền mặt. Mỗi coupon chỉ có thể được sử dụng cho một lần tham dự một chương trình giảm giá, tuy nhiên bạn có thể tham dự một chương trình giảm giá nhiều lần. Không có hai chương trình giảm giá nào yêu cầu cùng một loại coupon. Một số loại coupon là coupon bẫy của hệ thống siêu thị và không thể được sử dụng ở bất cứ chương trình giảm giá nào.

Dũng đã sưu tập được rất nhiều coupon của siêu thị Beg Free. Hãy giúp Dũng tính xem nếu anh tham dự các chương trình giảm giá một cách hợp lí, anh có thể tiết kiệm được tối đa bao nhiêu đơn vị tiền mặt?

Dữ liệu

Dòng đầu tiên gồm một số nguyên ~t~ ~(0 \le t \le 1000)~ là số lượng bộ dữ liệu. Các bộ dữ liệu sẽ xuất hiện lần lượt theo định dạng:

• Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~m~ ~(1 \le n \le 30;\ 1 \le m \le 30)~ lần lượt là số chương trình giảm giá và số loại coupon.

• ~n~ dòng tiếp theo, mỗi dòng mô tả một chương trình giảm giá. Số đầu tiên của dòng thứ ~i~ là số loại coupon cần dùng ~k_i~ ~(1 \le k_i \le m)~. ~k_i~ số nguyên tiếp theo, mỗi số là số thứ tự của một loại coupon cần dùng (các số này đôi một khác nhau). Số nguyên ~x_i~ ~(0 \le x_i \le 10^6)~ cuối cùng của dòng là số đơn vị tiền mặt Dũng tiết kiệm được mỗi lần Dũng tham gia chương trình này.

• Dòng tiếp theo chứa ~m~ số nguyên, số thứ ~i~ là số coupon loại ~i~ mà Dũng đang có. Dũng không có nhiều hơn 100 coupon mỗi loại.

Kết quả

• Gồm một dòng duy nhất chứa một số nguyên là số đơn vị tiền mặt Dũng có thể tiết kiệm được nếu tham gia các chương trình giảm giá một cách tối ưu nhất.

Ví dụ

Sample Input

1
3 6
2 1 2 100
3 3 4 5 200
1 6 300
1 2 3 4 5 6

Sample Output

2500

Giải thích

• Dũng có thể tham gia chương trình khuyến mãi đầu tiên 1 lần, chương trình khuyến mãi thứ hai 3 lần và chương trình khuyến mãi thứ ba 6 lần. Tổng số tiền Dũng có thể tiết kiệm là ~100 \times 1 + 200 \times 3 + 300 \times 6 = 2500~