فقد 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