TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P1192
  • Problem
  • P1192收入计划
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description

    高考结束后,同学们大都找到了一份临时工作,渴望挣得一些零用钱。从今天起,Matrix67将连续工作N天(1<=N<=100 000)。每一天末他可以领取当天及前面若干天里没有领取的工资,但他总共只有M(1<=M<=N)次领取工资的机会。Matrix67已经知道了在接下来的这N天里每一天他可以赚多少钱。为了避免自己滥用零花钱,他希望知道如何安排领取工资的时间才能使得领到工资最多的那一次工资数额最小。注意Matrix67必须恰好领工资M次,且需要将所有的工资全部领走(即最后一天需要领一次工资)。

    Input Format

    第一行输入两个用空格隔开的正整数N和M
    以下N行每行一个不超过10000正整数,依次表示每一天的薪水。

    Output Format

    输出领取到的工资的最大值最小是多少。

    Sample Input 1

    7 5
    100
    400
    300
    100
    500
    101
    400

    Sample Output 1

    500 

    Sample Input 2

    10 7
    10
    327
    162
    465
    443
    194
    276
    430
    492
    326

    Sample Output 2

    499

    Hint


    Source  详情见www.matrix67.com