9038: Circle of Mistery

Ran is good at solving graph problems, but this time she has a great trouble because the problem Yukari gives her is too hard! Ran needs your help!

So here's the Circle of Mistery Problem:

Give an integer array $w$ of length $n$ and an integer $k$. Ran needs to construct a permutaion $p$. Let's use $p$ to construct a graph: connect $i$ and pip_ipi together. Obviously, the graph will contain several circles. Ran has to make sure at least one circle a1→a2→⋯→ax→a1a_1\to a_2\to\dots\to a_x\to a_1a1→a2→⋯→ax→a1 ($x\ge 1$) satisfy that ∑i=1xwai≥k\sum_{i=1}^x w_{a_i}\ge k∑i=1xwai≥k. That means, circle a1→a1a_1\to a_1a1→a1 is legal.

Try to find the permutation $p$ with the minimum number of inversions and output the number. An inversion in an array $a$ is a pair of indices (i,j)(i, j)(i,j) such that $i>j$ and ai<aja_i < a_jai<aj.

The first line contains two integers $n$ (1≤n≤1031\le n\le 10^31≤n≤103) and $k$ (−106≤k≤106-10^6\le k\le10^6−106≤k≤106).
The next line contains $n$ integers, the $i$-th one means wiw_iwi (−106≤wi≤106-10^6\le w_i\le 10^6−106≤wi≤106).

If it's impossible to construct $p$, output $-1$. Otherwise output the minimum number of inversions in $p$.