"돈을 빌려주지도, 빌리지도 말자", 라는 조언을 철기가 명심했다면 지금과 같은 고생을 하지 않아도 되었을 것이다.

그러나! 철기는 N명의 친구에게 돈을 빌리거나 빌려주었다.

편의상 친구들은 1번부터 N번까지 번호를 붙여서 부르기로 하자.

원금회수의 날이 마침내 다가왔다. 참고로 철기는 자신이 남들에게 빌린 돈보다 빌려준 돈이 많다.

철기의 친구들의 집은 모두 1차원 X좌표 상에 있다.

철기 집의 위치의 좌표는 0이며, i번 친구의 좌표는 i다.

철기는 자신의 집에서 출발하여 친구의 집을 돌아다니면서 빌려준 돈은 받고, 빌린 돈은 갚으려고 한다.

철기는 X좌표 상에서 왼쪽 오른쪽으로만 움직일 수 있다.

다시 말해서 i좌표에 있으면 i+1, i+2, i+3, \dots 혹은 i-1, i-2, i-3 같은 순으로만 움직일 수 있다는 것이다.

우선 철기는 자신의 집에서 출발하여 1번부터 N번의 순서로 친구의 집을 방문하며, 돈을 갚거나 돈을 받는다.

i번 친구는 철기에게 D_i원의 돈을 빌렸다. 만약 D_i가 0보다 작을 경우, 철기가 |D_i| 만큼의 돈을 빌렸다는 것이다.

처음에 철기는 위치 0에서 움직이기 시작하는데, 초기에 가지고 있는 돈은 0이다.

만약 철기에게 돈을 갚아야 할 친구의 집에 도착하게 되면 D_i만큼의 돈이 생기게 된다.

돈을 빌린 친구의 집에 다다랐을 경우, 가지고 있는 돈이 |D_i|보다 크거나 같을 경우에만 돈을 갚을 수 있다.

자신의 집에서 출발하여 친구에게 빌려준 돈과 빌린 돈을 다 처리하고, N번째 친구의 집에 놀러 갈 때 철기가 이동하게 되는 최소의 거리를 찾는 프로그램을 작성하라.

원금상환 timer 1초 memory 128MB

원금상환 1초 128MB