Có ~N~ chuyên viên lập trình và ~M~ công việc. Nếu chuyên viên thứ ~i~ mà làm ~j~ công việc thì sẽ tốn chi phí là ~C_i \times j^2~ .

Người ta cho bạn ~N~ xâu ký tự, ký tự thứ ~j~ của xâu ~i~ là 'Y' tức là chuyên viên thứ ~i~ có thể làm được công việc thứ ~j~ và 'N' trong trường hợp ngược lại. Bạn hãy lập trình tính xem tổng chi phí phải trả nhỏ nhất là bao nhiêu?

Input

• Dòng 1: Số nguyên dương ~N~ ~\left(0 < N < 51\right)~.
• Dòng 2: ~N~ số nguyên dương là ~C_1, \ldots, C_N~ ~\left(0 < C_i < 50000\right)~.
• ~N~ dòng tiếp theo, mỗi dòng gồm ~1~ xâu ~M~ ký tự mô tả như ở trên. ~\left(0 < M < 41\right)~.

Output

• Gồm ~1~ số nguyên duy nhất là chi phí nhỏ nhất. Trong trường hợp không thể hoàn thành ~M~ công việc này được thì ghi ra ~-1~.

Sample Input

3
2 3 4
YYN
YNY
NNN

Sample Output

11