길이가 인 순열 와 두 수열 이 주어진다. 는 부터 까지의 정수를 한 번씩 포함한다.
처음에 수열에는 이 주어진 순서대로 들어 있다. 수열의 모든 원소를 삭제하려고 한다.
한 번의 연산에서 현재 수열에 존재하는 원소 중 최솟값 또는 최댓값 하나를 선택한다. 선택한 값이 수열의 맨 앞 또는 맨 뒤에 있을 때만 그 원소를 삭제할 수 있다.
원소가 하나만 남아 있으면 그 원소는 맨 앞이면서 맨 뒤이다. 이 경우 두 방법 중 하나를 선택할 수 있다. 삭제되지 않은 원소들의 상대적인 순서는 바뀌지 않는다.
모든 원소를 삭제하기 위해 필요한 비용의 최솟값을 구하여라. 모든 원소를 삭제할 수 없다면 -1을 출력하여라.
입력은 다음과 같은 형식으로 주어진다.
첫째 줄에 모든 원소를 삭제하는 데 필요한 비용의 최솟값을 출력한다. 불가능하다면 -1을 출력한다.
는 위치가 아니라 값 를 삭제하는 비용이다.
