Farmer John mất chiếc chuông bò yêu thích và Bessie đồng ý giúp tìm! Họ tìm trên trang trại theo hai đường khác nhau, giữ liên lạc vô tuyến. Nhưng pin sắp cạn nên muốn lên kế hoạch di chuyển để luôn gần nhau và tiết kiệm điện.

Farmer John bắt đầu tại $(f_x, f_y)$ và đi đường $N$ bước, mỗi bước 'N' (bắc), 'E' (đông), 'S' (nam) hay 'W' (tây). Bessie bắt đầu tại $(b_x, b_y)$ và đi đường tương tự $M$ bước. Hai đường có thể có điểm chung. Mỗi bước thời gian Farmer John có thể đứng yên hoặc, nếu chưa tới cuối, tiến một bước theo hướng kế tiếp của đường. Bessie lựa chọn tương tự. Mỗi bước thời gian, trừ bước đầu ở vị trí xuất phát, máy vô tuyến tiêu thụ năng lượng bằng bình phương khoảng cách giữa họ.

Giúp họ lên chiến lược chung tối thiểu hóa tổng năng lượng tới bước đầu tiên mà cả hai đã đến cuối đường tương ứng, gồm cả bước đó.

Dữ liệu vào

Dòng đầu chứa $N$, $M$ ($1 \leq N, M \leq 1000$), dòng hai các số nguyên $f_x$, $f_y$, dòng ba $b_x$, $b_y$ ($0 \leq f_x, f_y, b_x, b_y \leq 1000$). Dòng tiếp theo là chuỗi dài $N$ mô tả đường FJ, dòng cuối là chuỗi dài $M$ mô tả đường Bessie.

Tọa độ luôn trong $0 \leq x,y \leq 1000$ suốt hành trình. Đông là chiều dương $x$, bắc là chiều dương $y$.

Dữ liệu ra

In số nguyên là năng lượng tối thiểu trong chuyến đi.

Ví dụ

Dữ liệu vào 1

2 7
3 0
5 0
NN
NWWWWWN

Dữ liệu ra 1

28

Tác giả bài toán: Brian Dean