문제
길이 \(N\)의 정수열 \(A\)가 주어진다. 수열은 서로 겹치지 않는 \(K\)개의 구간으로 분할되어 있으며, 왼쪽부터 \(i\)번째 구간의 길이는 \(l_i\)이다. 다음 연산을 \(0\)회 이상 원하는 만큼 수행할 수 있다.
- \(K\)개의 구간 중 하나를 고른다.
- 연산을 수행하기 직전의 해당 구간에 포함된 원소들의 최솟값을 \(m\), 최댓값을 \(M\)이라고 할 때, 그 구간에 속한 모든 원소를 각각 \(m\) 이상 \(M\) 이하의 임의의 정수로 바꾼다.
당신의 목표는 위 연산을 반복해 수열을 비내림차순으로 만드는 것이다.
모든 연산이 끝난 뒤, 최종 수열을 \(B\)라 하자. 값 \(x\)가 초기 수열 \(A\)에서 등장한 횟수를 \(c_A(x)\), 최종 수열 \(B\)에서 등장한 횟수를 \(c_B(x)\)라 할 때, \(B\)의 비용을 다음과 같이 정의한다.
\[\sum_x \max(0, c_B(x)-c_A(x))\]
수열을 비내림차순으로 만들 수 있는지 판별하고, 가능하다면 그러한 최종 수열의 최소 비용을 출력해 보자.
입력
첫째 줄에 정수 \(N\)과 \(K\)가 주어진다. (\(1 \le K \le N \le 200\,000\))
둘째 줄에 수열 \(A\)의 원소 \(A_1,A_2,\cdots,A_N\)이 공백으로 구분되어 주어진다. (\(0 \le A_i \le 10^9\))
셋째 줄에 \(K\)개의 정수 \(l_1,l_2,\cdots,l_K\)가 공백으로 구분되어 주어진다. (\(1 \le l_i \le N\); \(\sum_{i=1}^K l_i=N\)) 이는 수열이 왼쪽부터 차례대로 길이가 \(l_1,l_2,\cdots,l_K\)인 \(K\)개의 구간으로 나누어져 있음을 의미한다.
출력
수열을 비내림차순으로 만들 수 있다면, 그러한 최종 수열의 최소 비용을 출력한다. 그렇지 않다면, \(-1\)을 출력한다.