Background

Day 2 Problem B.

Translated from EGOI2023 candy.

Problem Description

In the city of Ikaagu, it is said that there is a palace whose wealth is beyond imagination. Inside it, along a corridor, there are $N$ boxes of candy from all over the world. Any traveler passing by can take as much candy as they want, as long as they pay gold equal to the weight of the candy.

The boxes are numbered from left to right from $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 boxes with lots of candy 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}$. What is the minimum number of operations needed to make the sum of the first $F$ elements of the array at least $T$?

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 one integer, the minimum number of operations.

6 2 27
10 4 20 6 3 3

1

6 5 5000000000
1000000000 1000000000 0 1000000000 1000000000 1000000000

3

3 2 100
20 30 60

NO

1 1 100
100

0

Hint

Sample $1$ Explanation

In sample $1$, the sum of the first two elements must be at least $27$. This can be achieved with one adjacent swap: swap $4$ and $20$. After the 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$.

Constraints

For all testdata, $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 additional constraints.

Hint

The answer may not fit in a 32-bit integer. If you use C++, watch out for possible overflow.

Translated by ChatGPT 5