Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

KENRE - Kén rể

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/kenre


Yến là một cô gái xinh đẹp, giỏi giang nên được rất nhiều chàng trai để ý. Yến giờ đã đủ 18 tuổi, theo khoản 1, điều 9 luật hôn nhân và gia đình là đã đủ tuổi kết hôn. Tuần trước, có chàng trai một chàng trai tên X đến hỏi cưới, Yến soi chàng X rất kĩ và thấy cũng ... ổn. Suy nghĩ một hồi lâu: "Vàng giờ giá đang cao, Việt Nam Đồng thì mất giá. Euro thì sao nhỉ? Đang khủng hoảng nợ công ở châu Âu nên xem ra cũng không an toàn. Bảng Anh có vẻ ổn. Nhưng chả biết được vài năm nữa giá cả thay đổi thế nào" Vậy là Yến quyết định đưa ra lời thách cưới sau khi cân nhắc: "A ngàn Bảng Anh, D triệu Việt Nam Đồng, E ngàn Euro, M ngàn Đô la Mỹ, T ngàn Nhân dân Tệ và V cây Vàng".

Chàng X kiểm tra lại tài khoản thì thấy mình có a ngàn bảng Anh, d triệu Việt Nam Đồng, e ngàn Euro, m ngàn Đô la Mỹ, t ngàn Nhân dân Tệ và v cây Vàng. May mắn cho chàng, có một ngân hàng cho phép đổi theo một số tỉ lệ dạng: A1 D1 E1 M1 T1 V1 thành A2 D2 E2 M2 T2 V2 (chỉ cho phép đổi một chiều, không có chiều ngược lại). Ví dụ:

  • 5 0 0 0 0 0 -> 0 1 1 1 1 1
  • 0 0 0 0 0 1 -> 1 0 0 0 0 0

Nếu ban đầu chàng X có 4 0 0 0 0 thì sẽ không đủ để thực hiện việc đổi theo 1 trong 2 tỉ lệ trên. Nhưng ngân hàng châm chước có thể cho chàng vay tạm, miễn là sau cùng chàng không nợ nần gì ngân hàng. Ví dụ thực hiện mua bán theo tỉ lệ 1, chàng X sẽ còn -1 1 1 1 1 1 rồi thực hiện tiếp mua bán theo tỉ lệ 2 sẽ có 0 1 1 1 1 0. (không còn nợ nần gì ngân hàng)

Sau khi hoàn đổi tiền xong, chàng X sẽ đem lễ vật theo đúng yêu cầu đến cầu hôn. Bạn hãy giúp chàng X tính xem cần ít nhất bao nhiêu lần đổi tiền để có thể có đủ lễ vật rước nàng về dinh.

Input

Dòng đầu tiên ghi số T là số test (1 <= T <= 10). Mỗi test được ghi theo định dạng sau:

  • Dòng đầu ghi 6 số A D E M T V. (0 <= A D E M T V <= 50)
  • Dòng thứ hai ghi 6 số a d e m t v. (0 <= a d e m t v <= 50)
  • Dòng thứ ba ghi số N là số các phương án đổi tiền ngân hàng cho phép. (0 <= N <= 3)
  • Tiếp theo là N dòng, mỗi dòng ghi 12 số theo dạng A1 D1 E1 M1 T1 V1 A2 D2 E2 M2 T2 V2. (0 <= A1 D1 E1 M1 T1 V1 A2 D2 E2 M2 T2 V2 <= 10) 

Output

Ghi ra duy nhất một số là số lần đổi tiền ít nhất. Nếu không có cách đổi thì in ra :(

Example

Input:
3
0 1 0 0 1 0 
4 0 0 0 0 0
2
5 0 0 0 0 0 0 1 1 1 1 1
0 0 0 0 0 1 1 0 0 0 0 0
8 0 0 0 0 0
0 0 0 0 0 9
1
0 0 0 0 0 5 5 0 0 0 0 0
0 0 0 0 0 10
10 0 0 0 0 0
1
1 0 0 0 0 0 0 0 0 0 0 1
Output:
2
:(
10

Được gửi lên bởi:VOJ Team
Ngày:2011-11-23
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED

hide comments
2024-09-13 11:47:51
tham lam nhung ko ngu dot
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.