12976번 - 돌 옮기기

N개의 돌더미가 원형 모양의 자리에 배치되어 있다. 각 돌더미는 0번부터 N-1번까지의 자리들에 각각 위치해있다. i번 자리에 있는 더미와 i+1번 자리에 있는 더미는 이웃하고, 0번 자리와 N-1번 자리도 이웃하다.

여러분에게는 N개의 원소를 가지는 수열 2개 a와 b가 주어진다. 각각의 i에 대해서 a(i)는 현재 i번째 자리에 위치한 돌더미에 있는 돌 개수를 나타내고, b(i)는 해당 자리 돌더미에 우리가 바라는 돌 개수를 나타낸다. 한 번의 횟수(Step)로 어느 더미에서 단 하나의 돌을 이웃한 자리로 옮길 수 있다. 현재 상태의 돌더미에서 돌을 옮겨서 바라는 상태의 돌 더미들로 만들 때 필요한 최소 횟수를 구하시오. 불가능하다면 –1을 출력한다.

첫째 줄에 N이 주어진다. N은 1000 이하의 자연수이다.

둘째 줄에 a의 원소를 나타내는 N개의 정수가 주어진다.

셋째 줄에 b의 원소를 나타내는 N개의 정수가 주어진다.

수열 각각의 원소는 0 이상 10억 이하이다.

문제의 정답이 되는 하나의 정수를 출력한다.