잠수함

잠수함이 얕은 바다의 해저에 가라앉아 있다. 잠수함을 찾아내려고 해수면 높이의 평균 해수면으로부터의 편차를 정밀하게 측정하는 위성 자료를 사용한다. 위성이 찍은 사진은 $w$개의 원소를 가진 행 $h$개로 이루어진 배열이다.

사진 위에 좌표계를 도입한다. 가로축은 사진의 행을 따라 왼쪽에서 오른쪽으로, 세로축은 사진의 열을 따라 아래에서 위로 향한다. 잠수함의 잠재적 이미지는 배열 원소들의 임의의 집합으로, 다음 부분들로 이루어진다.

• <<선체>>: $(x_1, y_1)$부터 $(x_2, y_1)$까지의 원소로 이루어진 띠. 여기서 $x_1 < x_2$이다.
• <<함교>>: $(x_3, y_1)$부터 $(x_3, y_2)$까지의 원소로 이루어진 띠. 여기서 $x_1 \leq x_3 < x_2$, $y_1 \leq y_2$이다.
• <<꼬리>>: $(x_4, y_3)$부터 $(x_4, y_4)$까지의 원소로 이루어진 띠. 여기서 $x_3 < x_4 \leq x_2$, $y_3 \leq y_1 \leq y_4$이다.

잠수함은 흐름이 센 해역의 수면 근처에 있어서 그 위의 수위가 조금 높아진다. 따라서 사진에서 잠수함의 이미지는 잠재적 이미지 중 포함되는 배열 원소의 합이 최대인 것으로 정의한다.

사진에서 잠수함의 이미지를 찾아 그 원소들의 합을 출력하는 프로그램을 작성하라.

위성에서 전송하는 자료를 압축하기 위해 사진의 각 원소는 영어 알파벳 소문자 하나로 부호화된다. 입력의 첫째 줄에는 부호화에 사용한 글자의 수 $k$가 주어진다($k \le 26$). 입력의 둘째 줄에는 $k$개의 정수 $c_i$가 주어진다. 이는 알파벳 순서대로 1번째부터 $k$번째 글자에 대응하는 부호 각각의 편차 값이다.

입력의 셋째 줄에는 사진의 크기 $h$와 $w$가 주어진다. 이어지는 $h$개의 줄에는 각각 $w$개의 문자가 주어지며, 이는 사진 원소의 부호 값이다.

출력에는 잠수함의 이미지에 해당하는 배열 원소들의 합인 정수 하나를 출력한다.

• $5 \le h, w \le 2000$
• $| c_i | \le 2000$

아래 예시에 대한 잠수함의 잠재적 이미지 몇 가지를 보인다.

아래는 잠수함의 잠재적 이미지가 아닌 사진 원소 집합 몇 가지이다.