2013年1月13日 星期日

10306 - e-Coins


在 Department for Bills and Coins,現今貨幣制度以新的擴展形式被提出,目的是為了適應新的經濟體系。將來,一些被稱為 e-coin 的新貨幣會被製造出來,除了傳統的價值(conventional value)外,並且賦予一個 InfoTechnological 的價值。當然,這種改良的目標就是為了落實經濟上的正義,尤其是針對那些為數眾多的網際網路公司(dotcom company),事實上,這些公司擁有很少的錢但卻擁有很多 IT 技術在裡面。因此,所有舊樣式的貨幣在新的制度下將會保持原本傳統的價值和零 InfoTechnological 值。

為了成功在新的貨幣系統下做比較,因此引進一種叫做 e-modulus 的概念。他的計算方式是 SQRT(X*X+Y*Y),其中 X 和 Y 分別是傳統價值和 InfoTechnological 值的總和,舉例來說,有 3 元的傳統價值和 4 元的 InfoTechnological 值的錢的 e-modulus 值將會是 5 元。請記得,你必須在算出 e-modulus 之前,先分別算出傳統價值和 InfoTechnological 值的總和。

為了簡化 e-currency 這種措施,你被分派去寫一支程式。給你一個必須達到的 e-modulus 值和一列不同種類的 e-coin,計算最少需要多少 e-coin 來達到相應的 e-modulus 值。在這裡,每種 e-coin 在湊出相應的 e-modulus 時,e-coin 的使用數量上沒有限制。

輸入

第一行有一個整數 n($0<n{\leq}100$)代表問題的數量,接著有 n 個問題:

其中第一行有兩個整數 m($0<m{\leq}40$)、S($0<S{\leq}300$),其中 m 是問題中 e-coin 的種類數,而 S 代表需要達到的 e-modulus 值。

接著 m 行中,每一行由一對非負整數所組成,用以描述 e-coin 的價值。

第一個整數代表傳統價值,而第二個整數代表 InfoTechnological 值。

當多於一個數字在同一行時,它們將會被空白隔開。在每個問題之間會有空白行。

輸出

輸出有 n 行,每行有一個整數代表可以達到 e-modulus 需要的貨幣數量;或是如果 S 沒辦法達到,則輸出「not possible」。

範例輸入

3
2 5
0 2
2 0
3 20
0 2
2 0
2 1
3 5
3 0
0 4
5 5

範例輸出

not possible
10
2


(Joint Effort Contest, Problem Source: Swedish National Programming Contest, arranged by department of Computer Science at Lund Institute of Technology.)