Candy

In the ancient city of Ica, there is said to be a palace with wealth beyond imagination. Inside, there is a corridor with $N$ boxes of candy from all over the world. Travellers passing by can take as much candy as they want, provided that they pay its weight in gold.

The boxes are numbered $0$ to $N-1$ from left to right. Box $i$ holds $a_i$ units of candy, where $a_i$ is a non-negative integer.

As the guardian of the palace, you want to move the boxes so that boxes with a lot of candy end up closer to the entrance.

You are given the array $a_0, a_1, \ldots, a_{N-1}$, along with the numbers $F$ and $T$. In one operation, you may swap two adjacent elements of the array. What is the minimum number of operations needed so that the first $F$ elements sum to at least $T$?

The first line contains three integers $N$, $F$, and $T$.

The second line contains $N$ integers $a_0, a_1, \ldots, a_{N-1}$.

If it is impossible to reach the goal using the operations, print NO. Otherwise, print a single integer, the minimum number of operations.

• $1 \le N \le 100$.
• $1 \le F \le N$.
• $0 \le T \le 10^{11}$.
• $0 \le a_i \le 10^9$ for $i = 0, 1, \ldots, N-1$.

The input numbers may not fit in a 32-bit integer, so watch for overflow.

In the first sample, the first two elements should sum to at least $27$. A single swap of the $4$ and the $20$ achieves this: the array becomes 10 20 4 6 3 3, and the first two elements sum to $10+20=30\ge 27$.

In the second sample, the $0$ must move all the way to the end of the array, which takes three swaps.

In the third sample, the first two elements cannot reach $100$. The best possible is $60+30=90$.