12864번 - 사서왕 준서

준서는 세계 최고의 사서왕이 되는 것이 꿈이다.

사서왕이 되기 위해 모험을 떠난 준서는 세계 곳곳의 도서관을 돌아다니며 구직을 하고 있지만, 대 취업난 시대에 사서가 되는 길은 요원하기만 했다.

낙담하며 국가의 부름에 응하기 위해 준비하던 준서에게 일생일대의 기회가 찾아왔다. 세계 최고의 도서관을 소유하고 있는 ANSI(Ajou Nerd Standards Institution)의 사서 공채를 통과한것이다!

합격 메일을 받은 준서는 뛸 듯이 기뻤지만 그것도 잠시. ANSI의 사서가 되기 위해서는 사서의 기본소양을 점검받기 위한 교육 과정을 거쳐야한다. 보통의 도서관이었다면 사서왕이 되겠다는 일념으로 해냈을 준서지만, ANSI의 근무환경은 최악이었다.

그 중에서도 가장 힘든것은 도서정리다. 도서관을 찾은 사람들이 책을 찾기 쉽게 책장의 책을 번호에 대한 비내림차순으로 배치해야하는데, ANSI 회원들 중에서도 너드 of 너드, 너드왕이라고 불리는 용재 D. 애쉬가 하루종일 눌러 앉아 열람한 책들을 아무데나 꽂아버리는 것이다! 너드들의 도서관답게 책들의 무게도 보통이 아니어서, 근육통까지 얻은 준서는 매일밤 베갯잇을 눈물로 적셨다.

가엾은 준서가 군대가 아닌 사서로 일할 수 있게, 책을 정리하는데 필요한 최소 노동치를 알아보자. 노동치란 책을 옮기는데 사용한 힘들의 총합으로, 책 한권을 옮기기 위해서는 이동거리와 상관 없이 그 무게만큼의 힘이 필요하다. 또한 책을 뽑아 새로운 곳에 꽂을 때 여유공간은 항상 넉넉하며, 도서정리는 책의 순서만 맞으면 된다.

첫 줄에 준서가 정리해야하는 책의 수 N(1 ≤ N ≤ 5,000)이 들어온다. 두 번째 줄에는 준서가 정리해야하는 책의 번호 N개가 현재 꽂혀있는 순서대로 주어진다. 세 번째 줄에는 각 책의 무게 N개가 현재 꽂혀있는 순서대로 주어진다. 책의 번호는 모두 0보다 크고 1000보다 작은 실수이며, 책의 무게는 1보다 크거나 같고 10,000보다 작거나 같은 정수이다.

한 줄에 책을 정리하는 데 필요한 최소 노동치를 출력한다.

예제1에서는 3번 책을 맨 앞으로 옮길때 드는 힘 6이 최소이다.

예제2에서는 1, 3, 5, 8번 책을 맞는 자리로 옮기는 힘의 합 6 + 5 + 17 + 41 = 69가 최소가 된다.