NPSC百貨公司就快要重新開幕了！

NPSC百貨公司的主打為頂樓的摩天輪！它是目前世界上最大的摩天輪，預計可以為NPSC 百貨公司帶來大量的人潮。

為了因應龐大的人潮，NPSC 百貨公司的老闆決定要更換百貨公司裡的一台電梯，好讓大家不會被塞在樓梯間。但是因為營業時間的關係，電梯一天只能載k 趟，因此電梯的載重量是一個相當重要的議題。

每天NPSC 百貨公司都會發放搭乘電梯的號碼牌給民眾，好讓大家排隊從一樓搭電梯到頂樓搭乘摩天輪。

為了減少更換電梯的成本，NPSC 百貨公司希望盡量降低電梯的載重量，於是調查了某天所有顧客的號碼以及體重，想要知道電梯的載重量至少可以承受多少公斤才能在 k 趟內運送完顧客。 

測試資料第一行有一個正整數T(T<=30)表示接下來總共有幾筆測試資料。

每一筆測試資料的第一行有兩個整數 N,k 以一個空白隔開，N 代表顧客的數量、k 代表電梯最多運送的趟數(1<=k<=10³)。接下來有N行(1<=N<=10⁵)，每行有兩個正整數idx_i,w_i，代表顧客 i 的號碼為 idx_i，體重為 w_i 公斤。(0<w_i<=100)

我們保證顧客的號碼 0<=idx_i<N，且每名顧客的號碼皆不重複。 

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

5
6

範例說明：

第一筆測試資料中，每個顧客都各自搭一趟電梯，最大載重量需要 5 公斤。

第二筆測試資料中，號碼 0, 1, 2 的顧客搭乘一趟電梯，剩下兩名顧客各自搭乘一趟電梯，最大載重量需要 1+2+3=6 公斤。