TopCoder

Thumb output jddoia
$\huge 南ことり$
今天也要輸贏!?

User's AC Ratio

96.9% (31/32)

Submission's AC Ratio

44.4% (48/108)

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

14

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

For Testdata: 0 ~ 0, Score: 20
For Testdata: 1 ~ 1, Score: 20
For Testdata: 2 ~ 2, Score: 20
For Testdata: 3 ~ 3, Score: 20
For Testdata: 4 ~ 4, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 10000 65536 262144
1 10000 65536 262144
2 10000 65536 262144
3 10000 65536 262144
4 10000 65536 262144