1161 . 4.虛擬番茄online
TopCoder
Tags
Description
球主最近被某款剛推出不久的線上遊戲「虛擬蕃茄 online」給吸引住了。
「虛擬蕃茄 online」是一個關於人生的遊戲。在人生的路途當中，你必須不斷地學習各種不同的技能，以應付隨時在變化的環境。但是有的時候，你必須擁有一定水準的能力，才能習得該技能。這個時候，你需要的是一個人生顧問(茶)。
在「虛擬蕃茄 online」當中，有一種專門提供諮詢服務的 NPsC（誤）。他們是裁決你習得某個技能所須至少具備的「力量點數（strength）」以及「敏捷點數（agility）」，你的力量點數和敏捷點數都必須不小於該數值，才有能力習得該技能。噢，對了，這種 NPCs 有個特別響亮的名號：「蕃茄諮詢線上裁判 - Tomato's Information Online Judge」。
球主發現他想要學習的技能總共有 $n$ 個，而每個技能都有所需具備的力量點數 $s_i$，以及敏捷點數 $a_i$。由於讓兩種技能點數（力量點數以及敏捷點數）分別提升 $1$ 點所需要的時間都是「$1$ 個蕃茄年」，球主迫不及待地想要知道最少還需要多久就可以學習至少 $k$ 種技巧。你能幫個忙嗎？
Input Format
輸入的第一列有一個正整數 $T$，代表接下來的測試資料組數。
對於每一筆測試資料，第一列有兩個以空白格開的正整數 $n, k (0 < k \le n \le 1,000,000)$，分別代表球主全部想學的技能數，以及想要學習至少 $k$ 種技能。
接下來的 $n$ 列每一列有兩個正整數 $s_i$，以及 $a_i$，分別代表習得第 $i$ 個技能還需要的力量點數以及敏捷點數，兩個數字不會同時是 $0$。你可以假設所有數字都不會超過 $1,000,000$，而且球主很強，一旦有能力學習某種技能，就可以不花時間地將該技能完全制霸。
Output Format
對於每筆測試資料，請輸出還要多少「個蕃茄年」才能讓球主學習到至少 $k$ 種技能呢？
Sample Input 1
5 3
1 6
7 3
4 8
10 2
5 9
Sample Output 1
Hints
有五種技能分別需要能力點數 $(1,6), (7,3), (4,8), (10,2), (5,9)$。選擇 $(1,6), (4,8), (5,9)$ 這三項技能學習，至少需要 $\max{1,4,5} + \max{6,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 |