Bạn là một học sinh. Vì vậy, chắc hẳn bạn còn nhớ rất nhiều thơ văn. Khi làm thơ, mỗi thể loại thơ lại có một số quy tắc riêng biệt về việc sử dụng dấu thanh trong các câu liên tiếp, gọi là luật bằng trắc. Nhà văn Nguyên Như muốn nhờ bạn dựa vào luật bằng trắc để xây dựng một mô hình máy viết văn tự động. Ông có danh sách của ~N~ từ tiếng Việt. Một số cặp từ được phép đứng ở cạnh nhau trong cùng câu văn, còn các cặp từ khác thì không. Ngoài ra, bạn chỉ được phép bắt đầu câu văn bằng một số từ nhất định. Kết thúc câu luôn luôn là dấu chấm. Mỗi câu văn phải chứa ít nhất một từ. Một bài văn được hợp thành bởi một số câu văn có thứ tự. Bài văn không có câu văn nào cũng được coi là một bài văn.

~N~ từ đã cho được chia thành hai nhóm: từ xấu và từ đẹp. Nếu từ cuối cùng của một câu là từ đẹp, thì câu đó được gọi là câu hoàn hảo. Còn nếu từ cuối cùng của câu là từ xấu, thì câu đó được gọi là câu không hoàn hảo. Nếu bài văn chứa câu không hoàn hảo, thì nó chỉ được phép là câu cuối cùng trong bài văn đó.

Vì một câu văn không nên quá dài cũng không nên quá ngắn, nhà văn Nguyên Như đã xác định trước một số nguyên ~K~, từ đó ta có công thức tính điểm số của câu văn có ~w~ từ (~w > 0~, dấu chấm không được tính là một từ) bằng: ~K + (K - 1) + (K - 2) + \dots + (K - w + 1)~.

Bạn cũng được cho trước quan hệ hợp/không hợp giữa 6 dấu thanh (ngang, huyền, sắc, hỏi, ngã, nặng) dưới dạng một ma trận nhị phân ~6 \times 6~. Mỗi quan hệ sẽ cho biết có nên đặt câu có kết thúc bằng dấu thanh này ở ngay sau câu có kết thúc bằng dấu thanh kia hay không. Hai câu văn cạnh nhau kết thúc bằng hai dấu thanh hợp nhau gọi là một cặp câu hợp nhau. Chỉ có một ngoại lệ: một câu văn không hoàn hảo sẽ không được xét quan hệ hợp nhau với câu văn trước đó, bất kể chúng kết thúc bằng dấu thanh gì.

Nhà văn Nguyên Như muốn bạn tìm thuật toán để sinh ra một bài văn dài không quá ~M~ từ có độ mượt mà là lớn nhất. Độ mượt mà của một bài văn được tính như sau: Độ mượt mà = (tổng điểm của các câu văn) \times (số cặp câu hợp nhau trong bài văn)

Yêu cầu: Cho các số nguyên ~N, K, M~, đồng thời cho quan hệ giữa các từ và quan hệ giữa các dấu thanh, hãy tính độ mượt mà của bài văn có độ mượt mà lớn nhất dài không quá ~M~ từ.

Input

• Dòng đầu chứa ba số nguyên dương ~N, K, M~ (~1 \le N, K, M \le 1000~).
• Dòng thứ hai gồm ~N~ số nguyên trong khoảng từ 1 đến 6, biểu thị dấu thanh của các từ.
• 6 dòng tiếp theo, mỗi dòng gồm 6 số nguyên nhận một trong hai giá trị 0 hoặc 1. Nếu số thứ ~j~ trên dòng thứ ~i~ trong 6 dòng này bằng 0 thì câu trước kết thúc bằng dấu ~i~ sẽ không hợp với câu sau kết thúc bằng dấu ~j~. Ngược lại, nếu số thứ ~j~ trên dòng thứ ~i~ trong 6 dòng này bằng 1 thì câu trước kết thúc bằng dấu ~i~ sẽ hợp với câu sau kết thúc bằng dấu ~j~.
• ~N + 1~ dòng tiếp theo, mỗi dòng gồm ~N + 1~ số nguyên biểu thị một ma trận nhị phân kích thước ~(N + 1) \times (N + 1)~. Trong ma trận này:
  • Nếu số thứ ~j~ (~1 \le j \le N~) trên dòng thứ ~i~ (~1 \le i \le N~) bằng 1 thì từ thứ ~j~ có thể được viết ngay sau từ thứ ~i~ trong cùng câu văn. Ngược lại, nếu số thứ ~j~ trên dòng thứ ~i~ bằng 0 thì sẽ không được phép viết từ thứ ~j~ ngay sau từ thứ ~i~ trong cùng câu văn.
  • Nếu số thứ ~N + 1~ trên dòng thứ ~i~ (~1 \le i \le N~) bằng 1 thì từ thứ ~i~ là từ đẹp, còn ngược lại thì từ thứ ~i~ là từ xấu.
  • Nếu số thứ ~i~ (~1 \le i \le N~) trên dòng thứ ~N + 1~ bằng 1 thì bạn được phép bắt đầu câu văn bằng từ thứ ~i~, còn nếu bằng 0 thì không được phép.
  • Số thứ ~N + 1~ trên dòng thứ ~N + 1~ luôn luôn bằng 0.

Output

Ghi ra một số nguyên duy nhất là độ mượt mà của bài văn có độ mượt mà lớn nhất dài không quá ~M~ từ.