Content:
简体中文
NPSC百貨公司就快要重新開幕了!
NPSC百貨公司的主打為頂樓的摩天輪!它是目前世界上最大的摩天輪,預計可以為NPSC 百貨公司帶來大量的人潮。
為了因應龐大的人潮,NPSC 百貨公司的老闆決定要更換百貨公司裡的一台電梯,好讓大家不會被塞在樓梯間。但是因為營業時間的關係,電梯一天只能載k 趟,因此電梯的載重量是一個相當重要的議題。
每天NPSC 百貨公司都會發放搭乘電梯的號碼牌給民眾,好讓大家排隊從一樓搭電梯到頂樓搭乘摩天輪。
為了減少更換電梯的成本,NPSC 百貨公司希望盡量降低電梯的載重量,於是調查了某天所有顧客的號碼以及體重,想要知道電梯的載重量至少可以承受多少公斤才能在 k 趟內運送完顧客。
Input:
測試資料第一行有一個正整數T(T<=30)表示接下來總共有幾筆測試資料。
每一筆測試資料的第一行有兩個整數 N,k 以一個空白隔開,N 代表顧客的數量、k 代表電梯最多運送的趟數(1<=k<=103)。接下來有N行(1<=N<=105),每行有兩個正整數idxi,wi,代表顧客 i 的號碼為 idxi,體重為 wi 公斤。(0<wi<=100)
我們保證顧客的號碼 0<=idxi<N,且每名顧客的號碼皆不重複。
Output:
Sample Input:
2 5 5 0 1 1 2 2 3 3 4 4 5 5 3 0 1 1 2 2 3 3 4 4 5
Sample Output :
5 6
Hint
:
範例說明:
第一筆測試資料中,每個顧客都各自搭一趟電梯,最大載重量需要 5 公斤。
第二筆測試資料中,號碼 0, 1, 2 的顧客搭乘一趟電梯,剩下兩名顧客各自搭乘一趟電梯,最大載重量需要 1+2+3=6 公斤。
Author
: