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$). הבאה היא מחרוזת באורך $N$ למסלול FJ, והאחרונה באורך $M$ למסלול Bessie.

כל הקואורדינטות במהלך המסע נשארות בתחום $0 \leq x,y \leq 1000$. מזרח הוא הכיוון החיובי של $x$ וצפון של $y$.

פלט

הדפיסו שלם אחד המציין את האנרגיה המזערית במסעם.

דוגמאות

קלט 1

2 7
3 0
5 0
NN
NWWWWWN

פלט 1

28

מחבר הבעיה: Brian Dean