Contatto Radio#10599
Farmer John ha perso il suo campanaccio preferito per mucche, e la mucca Bessie ha accettato di aiutarlo a trovarlo! Si dividono e cercano nella fattoria lungo percorsi diversi, ma rimangono in contatto via radio per poter comunicare tra loro. Sfortunatamente, le batterie delle loro radio si stanno esaurendo, quindi vogliono pianificare i loro movimenti per risparmiare energia cercando di rimanere il più vicino possibile l'uno all'altra.
Farmer John parte dalla posizione (f_x, f_y) e prevede di seguire un percorso composto da passi, ciascuno dei quali è '' (nord), '' (est), '' (sud), oppure '' (ovest). Bessie parte dalla posizione (b_x, b_y) e segue un percorso simile composto da passi. I due percorsi possono avere punti in comune. Ad ogni intervallo di tempo, Farmer John può rimanere nella sua posizione attuale oppure fare un passo in avanti lungo il proprio percorso, nella direzione che tocca successivamente (a condizione che non abbia ancora raggiunto la fine del suo percorso). Bessie può fare la stessa scelta.
Ad ogni intervallo di tempo, escluso l'istante iniziale in cui si trovano nelle rispettive posizioni di partenza, le loro radio consumano una quantità di energia pari al quadrato della distanza tra loro.
Aiuta FJ e Bessie a pianificare una strategia di movimento congiunta che minimizzi la quantità totale di energia consumata fino a includere l'intervallo di tempo in cui raggiungono per la prima volta le posizioni finali dei rispettivi percorsi.
La prima riga contiene due interi e m~(1 \le n, m \le 1000). La seconda riga contiene due interi f_x e f_y, e la terza riga contiene due interi b_x e b_y~(0 \le f_x, f_y, b_x, b_y \le 1000). La riga successiva contiene una stringa di lunghezza che descrive il percorso di FJ, e l'ultima riga contiene una stringa di lunghezza che descrive il percorso di Bessie.
È garantito che le coordinate di Farmer John e di Bessie rimangano sempre nell'intervallo 0 \le x, y \le 1000 durante i loro spostamenti. Si noti che est corrisponde alla direzione positiva delle , mentre nord corrisponde alla direzione positiva delle .
Stampa la quantità minima di energia che FJ e Bessie possono consumare durante i loro spostamenti.
Esempio 1