409407: GYM103503 A Make Sum Great Again

You are given an array $$$a$$$ of $$$n$$$ distinct positive integers. Unfortunately, the array is way past its prime, so you have decided to help it relive "the good old days"!

The array remembers that in the "the good old days" it had a sum of elements greater than or equal to a given threshold $$$s$$$. To help the array, you are allowed to perform a sequence of operations. In one operation, you may choose any positive integer $$$x$$$ which is not already present in the array, and append it to the end of $$$a$$$.

In a stroke of genius and insecurity, you have come to the rational conclusion that once the array realizes that the sum of its elements is greater than or equal to $$$s$$$, it will no longer allow you to perform any more operations and leave forever. To postpone the inevitable departure of the array, you have decided to make the helping process as lengthy as possible. More formally, you would like to maximize the number of operations before the array realizes that the sum of its elements is greater than or equal to $$$s$$$.

What is the maximum final length of array $$$a$$$?

The first line of input contains two integers $$$n$$$ and $$$s$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le s \le 10^{18})$$$ — the length of the initial array, and the given threshold for the sum. The second line of input contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^{12}$$$) — the elements of the initial array.

Print one integer, the maximum possible final length of the array.

• Subtask 1 (20 points): $$$1\le n \le 1000$$$, $$$1\le s \le 10^9$$$;
• Subtask 2 (30 points): $$$1\le n \le 10^5$$$, $$$1\le s \le 10^{12}$$$;
• Subtask 3 (50 points): No further constraints

3 17
6 1 3

6

5 28
6 8 1 5 9

5

• In the first sample, a way to get an array of size $$$6$$$ is to append, in order, integers $$$4$$$, $$$2$$$ and $$$7$$$, giving us the array $$$a=[6,1,3,4,2,7]$$$. When $$$7$$$ is appended, the sum of the elements will become $$$6+1+3+4+2+7=23$$$, which is greater than or equal to $$$s=17$$$.

• In the second sample, the sum of the elements of the array is $$$6+8+1+5+9=29$$$, which is already greater than or equal to $$$s=28$$$.