题目描述

在货币与硬币部门，为了更好适应新经济体系，提出了一个对现有货币系统的扩展方案。将发行一系列新型的"电子硬币"，这些硬币除了具有传统意义上的价值外，还具有信息技术价值。这项改革的目的当然是为了更好地反映众多互联网公司的经济状况 - 虽然它们资金匮乏，但确实拥有丰富的信息技术价值。所有旧货币将保持其传统价值，但信息技术价值为零。

为了在新系统中成功进行价值比较，引入了一个称为"电子模数"的概念。其计算公式为$\sqrt{X^2 + Y^2}$，其中$X$和$Y$分别是传统价值和信息技术价值的总和。例如，传统价值总和为$3$美元且信息技术价值总和为$4$美元的货币，其电子模数为$5$美元。请注意，在计算货币的电子模数之前，必须分别计算传统价值和信息技术价值的总和。

为了简化向电子货币的过渡，你需要编写一个程序：给定需要达到的电子模数值以及现有不同类型电子硬币的列表，计算恰好达到该电子模数所需的最少电子硬币数量。每种电子硬币的使用数量没有限制。

输入格式

第一行输入问题数量$n$（$0 < n \leq 100$），接着是$n$个问题：

每个问题包含：

• 一行两个整数$m$（$0 < m \leq 40$）和$S$（$0 < S \leq 300$），其中$m$表示该问题中存在的不同电子硬币类型的数量，$S$表示需要精确匹配的电子模数值。
• 接着$m$行，每行包含一对非负整数，描述一种电子硬币的价值。第一个数字表示传统价值，第二个数字表示信息技术价值。

当一行中有多个数字时，它们之间用空格分隔。每个问题之间有一个空行。

输出格式

输出包含$n$行。每行包含一个整数表示达到指定电子模数$S$所需的最少硬币数量，如果无法达到$S$，则输出"not possible"。

输入样例 1

3 
2 5 
0 2 
2 0 

3 20 
0 2 
2 0 
2 1 

3 5 
3 0 
0 4 
5 5 

输出样例 1

not possible 
10 
2

提示

示例展示了使用8枚传统价值为2、信息技术价值为1的硬币，以及2枚纯信息技术价值为2的硬币。电子模数当然是20，因为$\sqrt{(8×2+2×0)^2 + (8×1+2×2)^2} = \sqrt{16^2 + 12^2} = 20$。

题目来源

2001年瑞典/挪威编程锦标赛