TopCoder

Thumb mikasa mikoto furikae
Omelet
ㄏ一ㄏ一 $$AC \approx (111111111)_2$$

User's AC Ratio

97.7% (43/44)

Submission's AC Ratio

70.8% (51/72)

Tags

Description

可喜可賀,社部現在要更換所有的桌機了,不過由於經濟不景氣,所以很多工場都倒閉了,剩下的電腦數量十分有限。雖然TFcis現在的社費莫名其妙的多, 錢是一定夠的,不過由於經濟不景氣,所以能省的還是要省。

在經過調查後,目前市面上可以買到的電腦剩下N種,每種有不同的價錢Xi,每種所剩的數量Yi也不一樣。現在社部要採買M台電腦,問你最少要花多少錢?

Input Format

輸入的第一行有一個正整數T (T<20),代表接下來會有幾組測資,每組測資之間以空白行分隔。
每組測資的第一行,有兩個正整數N,M (N<200,M<200),代表有N種電腦,要買M台。
接下來有N行,每行兩個整數Xi,Yi (Xi<100000,Yi<50),代表一台的價錢為Xi,還剩下Yi台。

Output Format

輸出最少的花費,如果買不到M台,輸出"so sad"

Sample Input

3

3 10
1000 3
50000 5
10000 6

2 5
500 1
400 3

1 10
1000 20

Sample Output

113000
so sad
10000

Hints

Problem Source

原TIOJ1184 / TFcis 10th留社考(prob F)。Problem Setter:seanwu。

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1