1184 . 社產.冗餘
TopCoder
Description
可喜可賀，社部現在要更換所有的桌機了，不過由於經濟不景氣，所以很多工場都倒閉了，剩下的電腦數量十分有限。雖然 TFcis 現在的社費莫名其妙的多， 錢是一定夠的，不過由於經濟不景氣，所以能省的還是要省。
在經過調查後，目前市面上可以買到的電腦剩下 $N$ 種，每種有不同的價錢 $X_i$，每種所剩的數量 $Y_i$ 也不一樣。現在社部要採買 $M$ 台電腦，問你最少要花多少錢？
Input Format
輸入的第一行有一個正整數 $T$（$T<20$），代表接下來會有幾組測資，每組測資之間以空白行分隔。
每組測資的第一行，有兩個正整數 $N, M$（$N<20\textcolor{red}{0}, M < 200$），代表有 $N$ 種電腦，要買 $M$ 台。
接下來有 $N$ 行，每行兩個整數 $X_i,Y_i$（$X_i<100000, Y_i<50$），代表一台的價錢為 $X_i$ ，還剩下 $Y_i$ 台。
Output Format
輸出最少的花費，如果買不到 $M$ 台，輸出"so sad"
Sample Input 1
3
3 10
1000 3
50000 5
10000 6
2 5
500 1
400 3
1 10
1000 20
3 10
1000 3
50000 5
10000 6
2 5
500 1
400 3
1 10
1000 20
Sample Output 1
113000
so sad
10000
so sad
10000
Hints
Problem Source
原TIOJ1184 / TFcis 10th留社考(prob F)。Problem Setter：seanwu。
2021.02.21 Update: Added $\LaTeX$ by FHVirus
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 100 |