TopCoder

Thumb fhvirus
FHVirus
$\huge{WHP}$

User's AC Ratio

98.2% (54/55)

Submission's AC Ratio

75.5% (83/110)

Tags

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

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。
2021.02.21 Update: Added $\LaTeX$ by FHVirus

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