Ah-Choo!

Every person has a distinct sneeze. Loud sneezes and short cute sneezes mix with different voices, so each person produces a distinct waveform.

Dongi studies data science in graduate school and wants to test whether sneezes identify people. With graduation near, Dongi starts the experiment at once for the thesis. Jiae and Jisu, whose sneezes sound alike, join as subjects.

To decide whether two sneezes come from the same person, Dongi needs a similarity score. The score uses DTW (Dynamic Time Warping).

A sound waveform is time series data with time on the $x$ axis. Even one person sneezing again produces a slightly different waveform each time. A direct comparison at equal times reports low similarity for similar shapes. DTW first matches each time point of one waveform to the closest point of the other waveform and then measures the error. This matching absorbs shifts from sneezing speed and recording start.

Write the heights of sounds $X$ and $Y$ at times $i$ and $j$ as $X(i)$ and $Y(j)$. Matching point $i$ of $X$ with point $j$ of $Y$ costs $(X(i)-Y(j))^2$. Every point of $X$ matches at least one point of $Y$, and every point of $Y$ matches at least one point of $X$. The sum over matched pairs is the distance, and the inverse of the least DTW distance is the similarity.

Matches keep order. If $i$ of $X$ matches $j$ of $Y$ and a later $i'$ of $X$ matches $j'$ of $Y$, then $j \le j'$ holds. Crossed matches are invalid. Matching second 7 of $X$ to second 6 of $Y$ and then second 8 of $X$ to second 5 of $Y$ is an example of a forbidden match.

Take $X = [10, 20, 45, 20, 14, 15]$ and $Y = [10, 25, 50, 50, 30, 15]$. Matching equal times gives $0+25+25+900+256+0=1206$. A better order-preserving match gives $0+25+25+25+100+1+0=176$. Matches with a crossing do not count.

Given two recorded sneezes as sequences in time order, write a program that computes the least DTW distance.

The first line gives a natural number $N$, the length of each waveform. The second line gives $N$ integers in time order, the heights of the first waveform $X$, separated by spaces. The third line gives the heights of the second waveform $Y$ in the same format.

Every height is an integer with $0 \le h \le 1000$.

Print the least distance between the two waveforms as an integer.