Farmer John đã làm mất chiếc chuông bò yêu thích, và cô bò Bessie đồng ý giúp ông tìm nó! Cả hai tỏa ra tìm kiếm trên trang trại theo những đường đi khác nhau, nhưng vẫn liên lạc bằng bộ đàm để giữ liên lạc với nhau. Đáng tiếc, pin bộ đàm của họ sắp cạn, nên họ muốn lên kế hoạch di chuyển để tiết kiệm năng lượng bằng cách cố gắng luôn giữ khoảng cách giữa hai người ở mức nhỏ.

Farmer John bắt đầu tại vị trí \((f_x,f_y)\) và dự định đi theo một đường gồm \(N\) bước, mỗi bước là N (bắc), E (đông), S (nam) hoặc W (tây). Bessie bắt đầu tại vị trí \((b_x,b_y)\) và đi theo một đường tương tự gồm \(M\) bước. Hai đường đi có thể có những điểm chung. Tại mỗi bước thời gian, Farmer John có thể đứng yên ở vị trí hiện tại hoặc tiến một bước theo đường đi của mình, theo hướng kế tiếp trên đường đó (giả sử ông chưa đến vị trí cuối cùng). Bessie cũng có thể lựa chọn tương tự. Tại mỗi bước thời gian (không tính bước đầu tiên khi họ ở các vị trí ban đầu), bộ đàm tiêu thụ một lượng năng lượng bằng bình phương khoảng cách giữa họ.

Hãy giúp FJ và Bessie lập một chiến lược di chuyển chung sao cho tổng năng lượng tiêu thụ đến và tính cả bước cuối cùng, tức thời điểm đầu tiên mà cả hai đều đã đến vị trí cuối trên đường đi tương ứng, là nhỏ nhất.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(M\) (\(1\le N,M\le1000\)). Dòng thứ hai chứa hai số nguyên \(f_x\) và \(f_y\), còn dòng thứ ba chứa \(b_x\) và \(b_y\) (\(0\le f_x,f_y,b_x,b_y\le1000\)). Dòng tiếp theo chứa một xâu độ dài \(N\) mô tả đường đi của FJ, và dòng cuối cùng chứa một xâu độ dài \(M\) mô tả đường đi của Bessie.

Đảm bảo rằng trong suốt hành trình, tọa độ của Farmer John và Bessie luôn nằm trong khoảng \(0\le x,y\le1000\). Lưu ý rằng hướng đông là chiều dương của trục \(x\), còn hướng bắc là chiều dương của trục \(y\).

Dữ liệu ra

In một số nguyên cho biết lượng năng lượng nhỏ nhất mà FJ và Bessie có thể sử dụng trong hành trình.

Ví dụ

2 7
3 0
5 0
NN
NWWWWWN

28

Nguồn

USACO 2016 January Contest, Gold - Radio Contact: https://usaco.org/index.php?page=viewproblem2&cpid=598

Tác giả: Brian Dean.