Inversions of a simple path sequence

You are given a connected undirected graph with $N$ vertices. The vertices are numbered from $1$ to $N$, and the graph has as many edges as vertices. Vertex $i$ carries one value $V_i$.

A simple path is a path that visits no vertex more than once. Writing the values of the vertices in the order the path visits them gives a sequence. That sequence is the sequence of the simple path. A path made of a single vertex is also a simple path.

The number of inversions of a sequence $S$ is the number of pairs $(i, j)$ with $i < j$ and $S[i] > S[j]$. For example, $S = (10, 30, 20, 20)$ has two inversions, $(2, 3)$ and $(2, 4)$.

Given the graph and an integer $K$, find the smallest inversion count over all simple paths that visit at least $K$ vertices.

The first line has the number of vertices $N$ and the integer $K$ ($3 \le N \le 1000$, $1 \le K \le N$).

Each of the next $N$ lines describes one edge with the numbers of the two vertices it joins. No edge joins a vertex to itself, and no edge is given twice.

The last line has the $N$ values $V_1$ through $V_N$ in order ($1 \le V_i \le 1000$).

Print on the first line the smallest inversion count over all simple paths that visit at least $K$ vertices. If no such simple path exists, print -1.