HELPDONN  Help Donn
PROBLEM CODE:Enigma Treasure Hunt
KaushikRamDonn went to Enigma and registered for
Treasure Hunt.Following are the rules for Enigma Treasure hunt ,
Rule 1: Donn has to go from 1st stage to nth stage in a sequential order ( only after completing stage 1 ,he can go to stage 2,then to stage 3).
and collect treasures in a bag
Rule2: Donn will be given only k bags at the time of registration
Rule3: There are bags capable of holding all possible weights and is infinite in number. Donn is free to choose any bags capable of holding any weight (but all the k bags should be capable of holding the same weight)
Pandian,the organiser will give the bag to Donn.
Rule4: once the game is started ,Donn cant exchange his bag .
Rule5: While going through different stages,if Donn couldnt accomodate the treasure in a bag ,he will tie the bag and give it to Pandian.(this bag cant be used any more).Then he starts collecting the treasures in a new bag.
Rule6: The cost of the bag is directly proportional to the weight it can hold ,so try to reduce the cost.
Fortunatley ,Donn knows the weights of the treasure in each stage ,Help Donn Choose his bag.
Example:
Consider there are 3 stages(n= 3) in the Hunt.the weight of the treasures in each of these stages (which is known to donn before the hunt starts)
are 1,2 and 3. Donn is allowed to get 2 bags(k= 2) in this example
n = 3, k= 2
stages = {1,2,3}
Donn could accomplish his target if each of his bag can accomodate 3 kg or 5 kg.
Explanation :
if the wieght of the bag is 3  Stage1 weight + stage2 weight = 1+2=3 <=3 in one bag ,stage 3 weight= 3<=3 in another bag.thus they fit in the bags
if the wieght of the bag is 5  Stage1 weight = 1<=5 in one bag,stage2 + stage 3 weight= 2+3 =5 <=5 in another bag.thus they fit in the bags
but consider a bag size of 2 :
1 + 2> 2 so put stage1 treasure alone in 1st bag
2 + 3 >2 so put stage2 treasure alone in 2st bag
now we need one more bag to put in the 3rd treasure.
This is not possible so u cant choose a bag of size 2
bag of size >=3 can be used
Donn is intelligent and so he wants to pay the minimum cost so Donn will purchase a bag of size 3.Help Donn solve his problem .
Input:
0< T <=100 ,no of test cases
Each test case contains
0<N<=1000,no of stages and then a space followed by
0<k<=1000, no of bags allowed
the next N lines contains the weights of the treasures in each stage
the weight of the treasure <= 1000 .
output:
output a single line containing the minimum size of the bag needed.
Example
Input:
1
3 2
1
2
3
output :
3
hide comments
vengatesh15:
20170206 08:56:05
simple binary search Note: need not to use all k bags. 

hodobox:
20160615 06:38:12
Not sure what 'tricky cases' can be for this question... but here goes


Krishna Nakkeeran:
20140320 16:18:56
some tricky cases please.... 

Aravindan Chandrasekaran:
20140310 13:01:30
Helped Donn in my 6th Attempt :) :P 

Miguel Oliveira:
20130917 10:13:30
Eddy, I used 32 bit signed integers 

Eddy R. Morales Perez:
20130917 10:13:30
What is the constraints for the weight of treasure in each stage? 
Added by:  B.R.ARVIND 
Date:  20130911 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM32GCC MAWK BC CCLANG CPP14 CPP14CLANG COBOL COFFEE DCLANG DDMD DART ELIXIR FANTOM FORTH GOSU GRV JSMONKEY KTLN NIM OBJC OBJCCLANG OCT PICO PROLOG PYPY R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET 