Có một chủng virus mới, được đặt tên là "Codonqua-25" đã làm ảnh hưởng nặng tới nền y tế toàn cầu. Rất may, đã có thuốc và phương pháp chữa loại bệnh này, loại bệnh này gồm nhiều chủng và không có thuốc đặc hiệu tuy nhiên có thể kết hợp nhiều loại thuốc để chữa khỏi.

Khi mắc căn bệnh này, có tất cả ~n~ triệu chứng, cần chữa hết tất cả các triệu chứng để khỏi. Tùy vào chủng virus sẽ xuất hiện các triệu chứng nhất định. Hiện tại, trên thế giới có tất cả ~m~ loại thuốc.

Với mỗi loại thuốc, nó có thể chữa khỏi một vài triệu chứng nhất định, bên cạnh đó ta cũng biết số ngày uống thuốc để hoàn toàn khỏi các triệu chứng này. Tuy nhiên, đã là thuốc thì sẽ có thể có tác dụng phụ, tuy có thể chữa khỏi triệu chứng này nhưng tác dụng phụ sẽ có thể gây ra một vài triệu chứng khác.

Biết rằng, các loại thuốc không thể được kết hợp để uống cùng lúc, vì sẽ có thể gây ra các tác dụng phụ chưa được biết đến. Chính vì thế, trong cùng một thời điểm chỉ có thể sử dụng một loại thuốc.

Người bệnh nên khỏe lại càng sớm càng tốt, vì nếu chữa khỏi càng sớm, hội chứng hậu "Codonqua-25" sẽ không để lại quá nhiều tác hại. Người bệnh sẽ chỉ khỏi lại khi đã khỏi hết tất cả các triệu chứng. Bạn cần vào vai một dược sĩ, kê thuốc cho bệnh nhân trong khoảng thời gian ngắn nhất để có thể chữa khỏi mọi loại triệu chứng.

Yêu cầu: Hãy tìm số ngày tối thiểu cần để chữa khỏi bệnh. Nếu không thể chữa khỏi căn bệnh, đưa ra -1.

Input

• Dòng thứ nhất chứa một số nguyên ~T~ (~1 \le T \le 10~) - số lượng bộ dữ liệu.
• Mỗi bộ dữ liệu có dạng như sau:
  • Dòng thứ nhất chứa hai số nguyên ~n, m~ (~1 \le n \le 10; 1 \le m \le 10^3~) - số lượng triệu chứng và số lượng loại thuốc có sẵn.
  • Dòng thứ hai là một xâu nhị phân có độ dài ~n~, chỉ chứa các số 0 hoặc 1. Nếu như kí tự thứ ~i~ là 1, người bệnh có triệu chứng thứ ~i~, ngược lại kí tự thứ ~i~ là 0.
  • Tiếp theo là ~3 \times m~ dòng, mỗi 3 dòng mô tả một loại thuốc như dưới đây:
    • Dòng thứ nhất chứa một số nguyên ~d~ (~1 \le d \le 10^3~) - số ngày cần uống loại thuốc này liên tục để loại thuốc này có tác dụng.
    • Dòng thứ hai là một xâu nhị phân có độ dài ~n~, chỉ chứa các số 0 hoặc 1. Nếu như kí tự thứ ~i~ là 1, loại thuốc này sẽ có thể chữa được triệu chứng thứ ~i~, ngược lại kí tự thứ ~i~ là 0.
    • Dòng thứ ba là một xâu nhị phân có độ dài ~n~, chỉ chứa các số 0 hoặc 1. Nếu như kí tự thứ ~i~ là 1, loại thuốc này sẽ gây tác dụng phụ là xuất hiện triệu chứng thứ ~i~ SAU KHI đã uống hết đơn thuốc, ngược lại kí tự thứ ~i~ là 0.
• Dữ liệu đảm bảo thuốc sẽ không gây tác dụng phụ là một trong các triệu chứng mà nó chữa khỏi.
• Dữ liệu đảm bảo tổng của ~m~ trong tất cả bộ dữ liệu không vượt quá ~5 \times 10^3~.

Output

• Với mỗi bộ dữ liệu, đưa ra trên một dòng một số nguyên duy nhất là số ngày tối thiểu cần để chữa khỏi. Nếu không thể chữa khỏi căn bệnh, đưa ra -1.

Sample Input 1

2
2 2
01
2
10
01
9
01
10
5 4
10011
4
10000
00110
3
00101
00000
2
01010
00100
7
11010
00100

Sample Output 1

-1
9