電梯向上

題目敘述

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

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

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

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

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

輸入說明

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

每一筆測試資料的第一行有兩個整數 N, k 以一個空白隔開，N 代表顧客的數量、k 代表電梯最多運送的趟數。接下來有 N 行，每行有兩個正整數$idx_i,w_i$，代表顧客 i 的號碼為 $idx_i$，體重為$w_i$。我們保證顧客的號碼 $0 \leq idx_i < N$ ，且每名顧客的號碼皆不重複。

在所有測試資料中：

$1 \leq T \leq 30$
$1 \leq k \leq 10^{3}$
$1 \leq N \leq 10^{5}$
$1 \leq wi \leq 100$

輸出說明

對每筆測試資料輸出一行，每行只有一個整數 p ，代表電梯的最大載重量至少要p 公斤才能在 k 趟內載完所有顧客。

範例輸入

範例輸出

5
6

範例說明

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

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

Judge Setting

run-time limit: 600 ms
memory limit: 655360 byte
測資數量: 0