1161 . 4.虛擬番茄online

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

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

User's AC Ratio

92.5% (198/214)

Submission's AC Ratio

37.6% (294/782)

Tags

TWNP 2007-TWNP-4th

Description

球主最近被某款剛推出不久的線上遊戲「虛擬蕃茄 online」給吸引住了。

「虛擬蕃茄 online」是一個關於人生的遊戲。在人生的路途當中，你必須不斷地學習各種不同的技能，以應付隨時在變化的環境。但是有的時候，你必須擁有一定水準的能力，才能習得該技能。這個時候，你需要的是一個人生顧問(茶)。

在「虛擬蕃茄 online」當中，有一種專門提供諮詢服務的 NPsC（誤）。他們是裁決你習得某個技能所須至少具備的「力量點數（strength）」以及「敏捷點數（agility）」，你的力量點數和敏捷點數都必須不小於該數值，才有能力習得該技能。噢，對了，這種 NPCs 有個特別響亮的名號：「蕃茄諮詢線上裁判 - Tomato's Information Online Judge」。

球主發現他想要學習的技能總共有 n 個，而每個技能都有所需具備的力量點數 si，以及敏捷點數 ai。由於讓兩種技能點數（力量點數以及敏捷點數）分別提升 1 點所需要的時間都是「1 個蕃茄年」，球主迫不及待地想要知道最少還需要多久就可以學習至少 k 種技巧。你能幫個忙嗎？

Input Format

輸入的第一列有一個正整數 T，代表接下來的測試資料組數。
對於每一筆測試資料，第一列有兩個以空白格開的正整數 n,k(0<k≤n≤1,000,000)，分別代表球主全部想學的技能數，以及想要學習至少 k 種技能。
接下來的 n 列每一列有兩個正整數 si，以及 ai，分別代表習得第 i 個技能還需要的力量點數以及敏捷點數，兩個數字不會同時是 0。你可以假設所有數字都不會超過 1,000,000，而且球主很強，一旦有能力學習某種技能，就可以不花時間地將該技能完全制霸。

Output Format

對於每筆測試資料，請輸出還要多少「個蕃茄年」才能讓球主學習到至少 k 種技能呢？

Sample Input 1

1
5 3
1 6
7 3
4 8
10 2
5 9

Sample Output 1

14

Hints

有五種技能分別需要能力點數 (1,6),(7,3),(4,8),(10,2),(5,9)。選擇 (1,6),(4,8),(5,9) 這三項技能學習，至少需要 max1,4,5+max6,8,9=5+9=14 個蕃茄年。

Problem Source

原 TIOJ1161 / 96 TWN Practice Contest 4。Problem Setter：Kelvin。
2024/03/16 Update: Added LATEX by FHVirus

Subtasks

No. Testdata Range Score
1 0 20
2 1 20
3 2 20
4 3 20
5 4 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1
1 10000 65536 262144 2
2 10000 65536 262144 3
3 10000 65536 262144 4
4 10000 65536 262144 5
Submit
Back to Top