You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

有 $n$ 个孤岛, 敌人在 $1$ 号岛上.

题目描述

一共有 $n$ 个孤岛, 编号为 $1 \sim n$, 每个岛屿有一个强度值 $a_i$, $n$ 个孤岛两两之间有一座桥, 假如我们要摧毁 $i, j$ 两岛之间的桥梁, 我们需要消耗 $a_i \times a_j$ 的力气.

我们希望摧毁一些桥梁使得敌人能活动的岛屿越少越好, 我们有一个总的力气值 $m$, 问我们最少可以让敌人在几个岛屿上活动呢?

输入格式

第一行一个整数 $t$ , 表示有 $t$ 组数据

接下来 $t$ 组数据, 每组数据的第一行是 $n, m$ 表示孤岛的数量和总力气的数值

第二行是 $n$ 个 $a_i$, 表示第 $i^{th}$ 岛屿的强度值

输出格式

对于每一个样例, 我们输出 $1$ 个整数表示敌人最少可以活动的岛屿数量

样例 #1

样例输入 #1

4
3 1000000000000000000
2000000 4000000 5000000
4 150
100 1 1 1
6 1275
35 15 10 25 10 5
6 400
35 15 10 25 10 5

样例输出 #1

1
3
4
6

样例解释

对于第一个样例, 我们可以摧毁所有的桥梁, 使得敌人只能在 $1$ 号岛屿上活动

对于第二个样例, 我们可以摧毁 $(1,2), (2, 3), (3, 4), (2, 3)$ 岛屿之间的桥梁, 使得敌人无法到达 $2$ 号岛屿.

提示

• $1\ \leq\ t \ \leq\ 10^2$
• $1\ \leq\ n, m\ \leq\ 10^2$
• $1\ \leq\ a_i \ \leq\ 10^7$
• $1\ \leq\ m \ \leq\ 10^{18}$