#2764 사서왕 준서

1 s   128 MB  

Description

준서는 세계 최고의 사서왕이 되는 것이 꿈이다. 사서왕이 되기 위해 모험을 떠난 준서는 세계 곳곳의 도서관을 돌아다니며 구직을 하고 있지만, 대 취업난 시대에 사서가 되는 길은 요원하기만 했다.
낙담하며 국가의 부름에 응하기 위해 준비하던 준서에게 일생일대의 기회가 찾아왔다. 세계 최고의 도서관을 소유하고 있는 ANSI(Ajou Nerd Standards Insititution)의 사서 공채에 합격한 것이다!
합격 메일을 받은 준서는 뛸 듯이 기뻤지만 그것도 잠시, ANSI 의 사서가 되기 위해서는 사서의 기본 소양을 검증받기 위한 교육 과정을 거쳐야만 한다. 보통의 도서관이었다면 사서왕이 되겠다는 일념으로 해냈을 준서지만, ANSI 의 근무환경은 너무나도 열악했다.
 
그 중에서도 가장 힘든 것은 도서정리이다. 도서관을 찾은 사람들이 책을 찾기 쉽도록 책장의 책을 번호에 대하여 비내림차순으로 배치해야 한다. 하지만 ANSI 회원들 중에서도 Nerd of Nerd, King of Nerd 라고 불리는 용재 D. 애쉬가 하루종일 눌러 앉아서 책들을 마구 열람하고 아무데나 꽂아버리는 것이다! 너드들의 도서관답게 책들의 무게도 보통이 아니어서, 근육통까지 얻은 준서는 매일밤 베갯잇을 눈물로 적시며 보냈다.
 
가엾은 준서가 군인이 아닌 사서로서 일을 할 수 있도록, 책을 정리하는데에 필요한 최소의 노동력은 얼마인지 계산해주자. 노동력이란 책을 옮기는데에 사용한 힘들의 총합으로, 책 한권을 옮기기 위해서는 이동거리와 상관 없이 해당 책의 무게만큼의 힘이 필요하다. 새로운 책을 꽂을 책장의 공간은 항상 넉넉하며, 도서 정리는 책 사이의 공간은 무시한 채 책의 순서만 맞으면 된다.

Input

첫 줄에 준서가 정리해야하는 책의 수 N 이 들어온다. N 은 1 과 5,000 사이의 정수이다.
두 번째 줄에는 준서가 정리해야하는 책의 번호가 N 개 주어진다. 각 번호의 위치는 현재 책이 꽂혀진 순서와 동일하다. 또한 모든 책의 번호는 0 과 1,000 사이의 실수이다.
세 번째 줄에는 각 책의 무게가 꽂힌 순서대로 N 개 주어진다. 각 책의 무게는 1 과 10,000 사이의 정수이다. 

Output

한 줄에 책을 정리하는 데 필요한 최소의 노동력을 정수 형식으로 출력한다.

Sample Input

Sample Output

9
813.8 812 816 813 811 813 813.6 801.9
880.1
6 20 5 8 17 20 12 41 6
69

HINT

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

Source

shake 2016! 본선