Giải bài trực tuyến

Nếu đang sở hữu một chiếc Smartphone, iPod hay iPad, chắc hẳn bạn không thể không biết đến trò chơi Scramble With Friends - một trò chơi vô cùng hot trong thời gian gần đây của hãng game nổi tiếng Zynga.

Tổng quan về trò chơi

Scramble with friends là một trò chơi đối kháng 2 người trên iPhone, iPad, Android... Bạn có thể chơi với những đối thủ ngẫu nhiên trên mạng, hoặc với bạn bè trên facebook của mình. Mỗi ván chơi gồm 3 lượt và người chiến thắng là người có tổng điểm cao hơn sau 3 lượt đó. Trong mỗi lượt chơi, bạn được cho một bảng vuông kích thước 4x4 có chứa các chữ cái từ A-Z. Mỗi chữ cái trong bảng này đi kèm với một giá trị điểm tương ứng (số nằm ở góc trên phải). Bạn cần tìm các từ tiếng Anh xuất hiện trong bảng theo nghĩa: một chuỗi chữ cái thuộc các ô kề cạnh hoặc kề đỉnh với ô trước nó và không có ô nào lặp lại 2 lần. Cụ thể hơn: các chữ cái của một từ cần xuất hiện trong dãy các ô vuông t₁, t₂, ..., t_k sao cho ô t_i có cạnh chung hoặc đỉnh chung với ô t_i+1, với 1 ≤ i < k và t_i ≠ t_j với 1 ≤ i, j ≤ k và i ≠ j. Khi tìm được một từ, bạn được cho một số điểm nhất định, được mô tả ở phía dưới.

Hình minh họa cho ví dụ 1

Chú ý rằng điểm của các chữ cái phụ thuộc vào vị trí trong bảng và ván chơi, có nghĩa là điểm của cùng một chữ cái trong 2 ván khác nhau, hoặc thậm chí trong cùng 1 ván nhưng ở 2 vị trí khác nhau có thể khác nhau.

Người chơi sau khi tìm được một từ cần di chuyển ngón tay của mình trên bảng (trò chơi chỉ được chơi trên các thiết bị có màn hình cảm ứng), xuất phát từ chữ cái đầu tiên của từ, đến chữ cái cuối cùng của từ. Sau khi bạn nhấc ngón tay lên, nếu từ thu được là một từ có trong từ điển của trò chơi và chưa được bạn đoán trước đó, bạn được cộng thêm một số điểm (được tính theo công thức ở mục tính điểm phía dưới).

Cách tính điểm

Khi đoán được một từ, bạn được cho thêm một điểm số nhất định. Theo luật của trò chơi Scramble, điểm mà bạn nhận được phụ thuộc vào rất nhiều yếu tố: giá trị điểm của từng chữ cái, các chữ cái đặc biệt có tác dụng nhân đôi điểm, độ dài của từ. Tuy nhiên, trong bài toán này, để đơn giản, ta tạm coi điểm số của một từ được tính bằng tổng giá trị các chữ cái của từ đấy.

Ví dụ, khi tìm được từ SCRAMBLE trong hình trên, bạn sẽ được thêm:

1 + 1 + 4 + 2 + 1 + 3 + 4 + 4 = 20 điểm

Chú ý: Một từ có 2 lần xuất hiện trong bảng với 2 giá trị điểm khác nhau được coi là 2 từ khác nhau, và một từ có 2 lần xuất hiện trong bảng với cùng 1 giá trị điểm chỉ được coi là cùng 1 từ.

Ví dụ: Giả sử trong từ điển có từ AE và RA:

• 2 lần xuất hiện của từ AE (3 điểm và 6 điểm) được coi là khác nhau, và bạn sẽ được 9 điểm nếu tìm được cả 2 lần xuất hiện của từ này.
• 2 lần xuất hiện của từ RA (đều có giá trị 6 điểm) được coi là giống nhau, và bạn chỉ được 6 điểm dù cho bạn có tìm được 1 hay 2 lần xuất hiện của từ đó

Bài toán

Một vấn đề đau đầu mà những người thiết kế game Scramble gặp phải là những phàn nàn không ngừng của những người chơi: Họ luôn cảm thấy khó chịu, buồn chán, thất vọng khi những cao thủ mà họ phải đối đầu dành được hơn họ quá nhiều điểm:

Người chơi jess4002 đạt được số điểm gấp 4 lần đối thủ của mình

Để giải quyết vấn đề này, những nhà thiết kế game đã quyết định giới hạn điểm số tối đa mà một người chơi có thể đạt được trong một lượt chơi. Để làm được điều này, trước hết cần tính được điểm số lớn nhất mà một người chơi có thể đạt được là bao nhiêu. Là một lập trình viên siêu hạng, bạn được nhận nhiệm vụ thực hiện điều này.

Sau rất nhiều thời gian nghiên cứu, người ta đã thu thập được một số thông tin về những cao thủ Scramble như sau:

• Khi bắt đầu một lượt chơi, họ cần t₀ thời gian để phân tích bảng chữ cái được cho, tìm chiến thuật thích hợp cũng như tìm từ đầu tiên
• Trong suốt thời gian chơi, họ không cần mất thêm thời gian suy nghĩ hoặc tìm từ: Trong khi những ngón tay của họ đang di chuyển với tốc độ chóng mặt, thì bộ não của họ còn làm việc với tốc độ nhanh hơn - do đó họ luôn tìm được những từ tiếp theo khi ngón tay còn chưa chỉ xong từ hiện tại.
• Thời gian để ngón tay chỉ ra 1 từ:
  • Thời gian để ngón tay của họ di chuyển đến chữ cái đầu tiên của từ chỉ phụ thuộc vào vị trí trên bảng (mà KHÔNG phụ thuộc vào vị trí hay tốc độ trước đó của ngón tay). Thời gian để di chuyển đến vị trí ở hàng i, cột j của bảng là p(i,j)
  • Thời gian để di chuyển giữa ô (i,j) và ô (i+di,j+dj) là di² + dj².
  • Ví dụ, tổng thời gian để người chơi đoán được từ SCRAMBLE trong hình minh họa phía trên là:
    • p(1,1) + (0² + 1²) + (1² + 0²) + (1² + 0²) + (1² + 1²) + (1² + 1²) + (1² + 0²) + (1² + 0²)
• Với nhiều năm kinh nghiệm, họ biết tất cả các từ trong từ điển của trò chơi.

Input

• Dòng đầu tiên chứa số nguyên dương N - số từ trong từ điển của trò chơi
• N dòng tiếp theo, mỗi dòng chứa một từ trong từ điển của trò chơi, mỗi từ là một chuỗi các chữ cái in hoa liên tiếp (không có dấu cách ở giữa)
• Tiếp theo đó là một dòng trống
• 4 dòng tiếp theo, mỗi dòng gồm 4 chữ cái in hoa, mô tả bảng chữ cái của một lượt chơi
• Tiếp theo đó là một dòng trống
• 4 dòng tiếp theo, mỗi dòng gồm 4 số nguyên dương phân cách nhau bởi ít nhất một dấu cách, mô tả giá trị điểm của các ô trên bảng
• Tiếp theo đó là một dòng trống
• 4 dòng tiếp theo, mỗi dòng gồm 4 số nguyên dương phân cách nhau bởi ít nhất một dấu cách, số thứ j ở dòng i là p(i,j) - thời gian để người chơi di chuyển ngón tay đến ô (i,j).
• Dòng tiếp theo ghi số nguyên t₀
• Dòng cuối cùng ghi số nguyên dương là thời gian của một lượt chơi.

Giới hạn

• N ≤ 100
• Độ dài từ ≤ 16
• Trong bộ test chính thức dùng để tính điểm chương trình của bạn, không có chữ cái nào xuất hiện nhiều hơn 2 lần trong bảng. Điều này không đúng với test ví dụ (cũng là test bạn được chấm trong quá trình thi).
• 0 ≤ t₀ ≤ 100
• 0 ≤ p(i,j) ≤ 100
• 0 ≤ giá trị điểm của các ô trên bảng ≤ 100
• 0 ≤ thời gian của 1 lượt chơi ≤ 100

Output

Điểm số tối đa mà một cao thủ Scramble có thể đạt được trong một lượt chơi.

Example

Input:
5
LANE
RATE
SCRAMBLE
TRAY
YALE

SCTE
HRAL
LANB
YEMA

1 1 1 4
3 4 2 4
2 2 2 3
3 1 1 1

1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
0
25
Output:
50