1161 . 4.虛擬番茄online
TopCoder
Tags
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
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。
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 20 |
| 2 | 1 | 20 |
| 3 | 2 | 20 |
| 4 | 3 | 20 |
| 5 | 4 | 20 |