Problem Background

Day 2 Problem B.

The problem statement is translated from EGOI2023 candy.

Problem Description

In the ancient city of Ica, it is said that there is a palace with wealth beyond imagination. Within it, a corridor contains $N$ boxes of candies from all over the world. Travelers passing by can take as many candies as they want by paying the weight of the candies in gold.

The candy boxes are numbered from left to right as $0$ to $N-1$. In box $i$, there are $a_i$ units of candy remaining, where $a_i$ is a non-negative integer.

As the guardian of the palace, you need to move these boxes so that the boxes with more candies are closer to the entrance.

You are given the array $a_0, a_1, \cdots, a_{N-1}$, and integers $F$ and $T$. In one operation, you are allowed to swap any two adjacent elements in $a_0, a_1, \cdots, a_{N-1}$. To make the sum of the first $F$ elements of the array at least $T$, what is the minimum number of operations required?

Input Format

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

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

Output Format

If it is impossible to achieve the goal, output NO.

Otherwise, output an integer representing the minimum number of operations.

Sample Input and Output

Sample Input #1

6 2 27
10 4 20 6 3 3

Sample Output #1

1

Sample Input #2

6 5 5000000000
1000000000 1000000000 0 1000000000 1000000000 1000000000

Sample Output #2

3

Sample Input #3

3 2 100
20 30 60

Sample Output #3

NO

Sample Input #4

1 1 100
100

Sample Output #4

0

Notes

Sample 1 Explanation

In Sample 1, the sum of the first two elements should be at least $27$. One adjacent element swap can achieve the goal: swap $4$ and $20$. After this swap, the array becomes 10 20 4 6 3 3, and the sum of the first two elements is $10 + 20 = 30 \ge 27$.

Sample 2 Explanation

In Sample 2, the $0$ must be moved all the way to the end of the array; this requires $3$ swaps.

Sample 3 Explanation

In Sample 3, it is impossible to make the sum of the first two elements at least $100$; the best we can do is $60 + 30 = 90$.

Data Range

For all data, $1 \le N \le 100$, $1 \le F \le N$, $0 \le T \le 10^{11}$, $0 \le a_i \le 10^9$.

• Subtask 1 (6 points): $N \le 2$, $a_i \le 100$, $T \le 10^9$.
• Subtask 2 (19 points): $a_i \le 1$.
• Subtask 3 (16 points): $N \le 20$.
• Subtask 4 (30 points): $a_i \le 100$.
• Subtask 5 (29 points): No special restrictions.

Hints

The answer may not be within the range of a 32-bit integer. If you are using C++ language, please be aware of the possibility of overflow.

见题面 Input 部分

见题面 Output 部分