1184 . 社產.冗餘

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的！雖然想像得出來也不一定可以就是了

User's AC Ratio

98.6% (73/74)

Submission's AC Ratio

78.5% (106/135)

Tags

X-TFcis TFcis

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 1

3

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

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 (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
Submit
Back to Top