Ah-Choo!

사람마다 재채기 소리가 다르다. 크고 우렁찬 소리도 있고 짧고 귀여운 소리도 있으며 목소리까지 섞여 각자 고유한 파형을 만든다.

데이터 사이언스를 전공하는 동이는 재채기 소리로 사람을 가릴 수 있는지 확인하려 한다. 졸업을 앞둔 동이는 학위 논문을 쓰기 위해 바로 실험을 시작했다. 평소 재채기 소리가 비슷한 지애와 지수가 실험에 참가했다.

두 소리가 같은 사람의 소리인지 판단하려면 두 소리 사이 유사도를 정해야 한다. 동이는 DTW(Dynamic Time Warping) 기법으로 유사도를 잰다.

소리 같은 파형 데이터는 시간을 $x$축으로 두는 시계열 데이터로 나타낸다. 같은 사람이 같은 재채기를 해도 녹음마다 파형이 조금씩 달라진다. 단순히 같은 시각끼리 비교하면 파형이 비슷해도 오차가 크게 나온다. DTW는 한 파형의 각 시점을 다른 파형에서 가장 비슷한 시점에 대응시킨 뒤 오차를 잰다. 이렇게 대응시키면 재채기 속도나 녹음 시작 시점이 달라서 생기는 어긋남을 줄일 수 있다.

두 소리 $X$, $Y$의 시각 $i$, $j$에서 파형 높이를 $X(i)$, $Y(j)$라 하자. $X$의 시점 $i$와 $Y$의 시점 $j$를 대응시킬 때 오차는 $(X(i)-Y(j))^2$이다. $X$의 각 시점은 $Y$의 하나 이상 시점에 대응하고 $Y$의 각 시점도 $X$의 하나 이상 시점에 대응한다. 대응한 쌍의 오차를 모두 더한 값이 두 소리 사이 거리이며 DTW로 구한 최소 거리의 역수가 유사도이다.

대응에는 순서 조건이 있다. $X$의 $i$가 $Y$의 $j$에 대응하고 $X$의 $i$보다 뒤인 $i'$이 $Y$의 $j'$에 대응하면 $j \le j'$을 만족해야 한다. 즉 두 대응이 서로 교차하면 안 된다. $X$의 7초 시점을 $Y$의 6초에 대응한 뒤 $X$의 8초 시점을 $Y$의 5초에 대응시키는 식은 허용하지 않는다.

수열 $X = [10, 20, 45, 20, 14, 15]$와 $Y = [10, 25, 50, 50, 30, 15]$를 보자. 같은 시점끼리 대응하면 거리는 $0+25+25+900+256+0=1206$이다. 순서를 지키면서 대응을 옮기면 $0+25+25+25+100+1+0=176$까지 줄일 수 있다. 교차가 생기는 대응은 세지 않는다.

임의의 두 소리 파형이 시간순 수열로 주어질 때 DTW로 구할 수 있는 최소 거리를 구하는 프로그램을 작성하라.

첫째 줄에 파형 길이를 나타내는 자연수 $N$이 주어진다. 둘째 줄에 첫 파형 $X$의 시간순 높이 $N$개가 공백으로 구분되어 주어진다. 셋째 줄에 둘째 파형 $Y$의 시간순 높이 $N$개가 같은 형식으로 주어진다.

모든 파형 높이는 $0$ 이상 $1000$ 이하 정수이다.

두 파형 사이 최소 거리를 정수로 출력한다.