TopCoder

Thumb skin by baishetirryna
joylintp
<( _ _ )>

User's AC Ratio

97.5% (39/40)

Submission's AC Ratio

69.1% (47/68)

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

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 3000 65536 262144