문제

컴퓨터의 정보 처리 시간을 줄이는 것은 중요하다. 처리 시간을 줄이는 방법에는 여러 가지가 있는데, 그 중 캐시 메모리(Cache Memory)에 대해서 알아보자.

캐시 메모리는 메인 메모리에 비해서 정보의 접근 속도가 빠르지만, 메인 메모리에 비해서 용량이 적다는 단점이 있다. 따라서 메인 메모리에 있는 데이터를 캐시 메모리에 옮겨두고, 데이터를 캐시 메모리에서 찾게 하면 처리 속도를 줄일 수 있다.

보통 캐시 메모리는 지역성이라는 원리를 사용하지만, 이 문제에서는 여러분이 직접 캐시 메모리에 옮길 데이터를 정해야 한다.

개의 저장 공간으로 이루어진 메인 메모리가 있다. 각 저장 공간에는 이상 이하의 고유한 번호가 연속해서 붙어 있다.

길이 의 메모리 사용 요청 배열 이 주어진다. 이는 번 저장 공간이 총 번 사용됨을 의미한다.

저장 공간이 사용되기 전, 당신은 캐시 메모리에 옮길 영역을 정할 수 있다. 그 방법은 다음과 같다.

• 캐시 메모리를 저장하기 위한 길이 인 배열 이 주어진다. 배열 의 각 원소는 이상 이하의 정수이다.
• 이 배열 에서 연속한 부분 배열을 골라 부분구간에 포함되는 번호를 가진 저장 공간을 전부 캐시 메모리에 옮긴다. 이때 부분 배열로 빈 배열을 선택할 수도 있다.
• 이때 고른 부분 배열의 원소 하나당 의 시간이 소요된다. 같은 원소가 여러 개 있더라도 그 개수만큼 중복하여 갯수를 센다.

캐시 메모리에 옮길 영역이 결정되면 저장 공간을 사용하기 시작한다. 각 저장 공간을 사용할 때 걸리는 시간은 다음과 같다.

• 저장 공간이 캐시 메모리에 옮겨졌다면, 사용에 걸리는 시간은 이다.
• 그렇지 않은 경우 사용에 걸리는 시간은 이다.

이때 항상 임이 보장된다.

여러분의 목표는 캐시 메모리에 옮길 저장 공간을 잘 정하여 마지막 메모리 사용이 끝날 때까지 걸린 시간을 최소화하는 것이다.

입력

첫 번째 줄에 양의 정수 , , , , 가 공백으로 구분되어 주어진다.

두 번째 줄에 배열 이 공백으로 구분되어 주어진다.

세 번째 줄에 배열 이 공백으로 구분되어 주어진다.

출력

마지막 메모리 사용이 끝날 때까지 걸린 시간의 최솟값을 출력한다.