回分類題庫
h107: G.電梯向上
關鍵字: NPSC 2012 高中組初賽

測資點 : 2 | Time Limit : 30000 ms | Memory Limit : 128000 KB
Accepted : 99 Times / 72 Users | Submit : 208 Times / 88 Users | Accepted rate : 82%
題目加入時間 : 2013-11-04 15:36

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:

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

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
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 :

NPSC 2012 高中組初賽 (管理員:sagit)

  Solve it!   Status Forum