Farmer John이 아끼는 소 방울을 잃었고 Bessie가 찾는 것을 돕기로 했다! 서로 다른 경로로 농장을 수색하며 무선으로 연락한다. 하지만 배터리가 부족해 항상 가까이 있도록 움직임을 계획해 전력을 아끼려 한다.

Farmer John은 $(f_x, f_y)$에서 출발해 $N$걸음 경로를 간다. 각 걸음은 'N'(북), 'E'(동), 'S'(남), 'W'(서)이다. Bessie는 $(b_x, b_y)$에서 비슷한 $M$걸음 경로를 간다. 두 경로는 공통 지점을 가질 수 있다. 매 시간 단계에 Farmer John은 제자리에 있거나, 아직 끝이 아니라면 경로의 다음 방향으로 한 걸음 이동한다. Bessie도 같은 선택을 한다. 시작 위치에 있는 첫 단계를 제외한 매 단계에서 무선 기기는 두 사람 거리의 제곱만큼 에너지를 쓴다.

각자의 경로 끝에 둘 다 처음 도착해 있는 마지막 단계까지 그 단계를 포함한 총 에너지를 최소화하는 공동 이동 전략을 구하라.

입력

첫째 줄은 $N$, $M$ ($1 \leq N, M \leq 1000$), 둘째 줄은 정수 $f_x$, $f_y$, 셋째 줄은 $b_x$, $b_y$ ($0 \leq f_x, f_y, b_x, b_y \leq 1000$)이다. 다음 줄은 FJ 경로의 길이 $N$ 문자열, 마지막 줄은 Bessie 경로의 길이 $M$ 문자열이다.

전 구간 좌표는 $0 \leq x,y \leq 1000$이다. 동쪽은 $x$의 양의 방향, 북쪽은 $y$의 양의 방향이다.

출력

여행 중 최소 에너지를 정수 하나로 출력하라.

예제

입력 1

2 7
3 0
5 0
NN
NWWWWWN

출력 1

28

문제 출제자: Brian Dean