Minimum Total Parade Distance

You are given n creatures, each with an aura brightness and a distance cost. Your task is to select k creatures so that their aura brightnesses form a strictly increasing sequence. When sorted by brightness, the total distance is the sum of the chosen creatures' distances. You need to determine the minimum possible total distance for such a parade. If it is impossible to select k creatures (i.e. if k > n) or the condition of strictly increasing brightness cannot be met, output -1.

The problem can be formulated mathematically as follows:

Given two sequences \( b_1, b_2, \ldots, b_n \) (brightnesses) and \( d_1, d_2, \ldots, d_n \) (distances), find a subsequence of indices \( i_1 < i_2 < \cdots < i_k \) such that \( b_{i_1} < b_{i_2} < \cdots < b_{i_k} \) and the value \( d_{i_1} + d_{i_2} + \cdots + d_{i_k} \) is minimized. If no such subsequence exists, print -1.

inputFormat

The input is read from stdin and contains three lines:

1. The first line contains two integers n and k separated by a space.
2. The second line contains n integers representing the brightnesses of the creatures.
3. The third line contains n integers representing the distances corresponding to each creature.

Constraints: \(1 \leq k \leq n\). If \(k > n\), output -1.

outputFormat

The output is a single integer printed to stdout: the minimum total distance required for a valid parade. If it is not possible to form a parade satisfying the conditions, output -1.

6 4
5 1 3 2 4 6
2 1 3 2 4 5

9