K. Kyuuing Theory
time limit per test
8 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Cindy is helping her dojo with the logistics of their upcoming promotion exam.

There is a queue of $$$n$$$ students, each ready to take the exam. Cindy will then hire $$$k$$$ instructors as the ones who will administer the promotion exam. The $$$i$$$th person from the front of the queue takes $$$a_i$$$ seconds to complete their test (pass or fail) under an instructor, and each instructor can only administer the test to one student at a time.

The process is as follows. The person in front of the queue looks around for any free instructors; if they see one, they go up to that instructor and start their test with them. If there are many that are free, one is chosen arbitrarily (the time spent walking to each instructor is negligible). If no instructor is free, the student at the front of the queue (and thus, everyone else behind them) waits until one is free.

Is it possible to finish all tests in at most $$$T$$$ seconds? If yes, what is the smallest $$$k$$$ (the number of instructors to hire) needed in order to achieve this goal? Also, please answer $$$t$$$ different test cases per file.

Input

The first line of each test case contains $$$t$$$, the number of test cases. The descriptions of $$$t$$$ test cases follow.

The first line of each test case contains two space-separated integers $$$n$$$ and $$$T$$$.

The second line of each test case contains the $$$n$$$ space-separated integers $$$a_1, a_2, \dots, a_n$$$, the finishing times in order of the front of the queue to the back.

Output

For each test case:

  • If the task is possible, output a line containing the word YES. Otherwise, output NO.
  • If YES, output another line containing a single positive integer, the minimum value of $$$k$$$ for which the task is possible.
Scoring

Here, $$$N$$$ denotes the sum of $$$n$$$s in a single test file.

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \le t \le 500 \\ 1 \leq n \\ 1 \leq T, a_i \leq 10^{16} \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{25} & \text{$n \leq 3$, $N \leq 1500$} \\ \hline 2 & \mathbf{15} & \text{$n \leq 75$, $N \leq 1500$} \\ \hline 3 & \mathbf{20} & \text{$n \leq 500$, $N \leq 2000$} \\ \hline 4 & \mathbf{20} & \text{$n \leq 2000$, $N \leq 6000$} \\ \hline 5 & \mathbf{20} & \text{$n \leq 150000$, $N \leq 450000$} \\ \hline \end{array}\\

\end{align*}$$$$$$

Example
Input
1
7 16
10 4 6 8 6 4 3
Output
YES
3