사과의 감시자

테라와 루루의 과수원에는 $N$그루의 사과나무가 일렬로 심어져 있다. 왼쪽부터 각 나무에 $1,2,\ldots,N$의 번호를 붙인다.

$i$번 나무의 높이는 $h_i$이고, 이 나무에서 수확할 수 있는 사과의 가치는 $a_i$이다. 모든 나무의 높이는 서로 다르다.

서로 다른 두 나무 $i$번과 $j$번을 생각하자. $i$번 나무부터 $j$번 나무까지의 나무 중 $i$번 나무의 높이가 가장 높다면, $i$번 나무가 $j$번 나무를 감시한다고 한다.

이때 모든 나무는 자기 자신을 감시한다.

테라와 루루는 정확히 $K$그루의 나무를 선택한다. 선택한 각 나무에서 사과를 하나씩 수확한다.

각 $1\le i\le N$에 대해, $i$번 나무가 감시하는 나무 중 선택한 나무의 수가 $c_i$ 이하여야 한다. 이 제한은 $i$번 나무를 선택했는지와 관계없이 적용된다.

모든 조건을 만족하도록 정확히 $K$그루의 나무를 선택했을 때, 수확한 사과의 가치 합의 최댓값을 구하여라.

첫째 줄에 나무의 수 $N$과 선택할 나무의 수 $K$가 공백을 사이에 두고 주어진다. ($1\le K\le N\le500\,000$)

둘째 줄에 각 나무의 높이를 나타내는 $N$개의 정수 이 공백을 사이에 두고 주어진다. 은 의 순열이다.

모든 조건을 만족하도록 정확히 $K$그루의 나무를 선택할 수 있다면, 수확한 사과의 가치 합의 최댓값을 출력한다.

조건을 만족하도록 정확히 $K$그루를 선택할 수 없다면 -1을 출력한다.