题目

在珠海海边浴场有一场大型泼水游戏，规定所有人接到水后才能开始游戏。浴场设有 m 个水龙头，每个水龙头每秒供水量为 1。有 n 名游客准备接水，且已确定初始接水顺序，将游客按顺序从 1 到 n 编号，i 号游客的接水量为 $w_i$。

接水开始时，1 到 m 号游客各占一个水龙头同时接水，当某游客 j 完成其接水量 $w_j$ 后，下一名排队等候的游客 k 马上接替 j 的位置继续接水（换人瞬间完成且无水资源浪费，若 j 游客在第 x 秒结束时完成接水，则 k 游客第 x + 1 秒立刻开始接水）。若当前接水人数 n 不足 m，则只有 n 个龙头供水，其余 m - n 个龙头关闭。

给定 n 名游客的接水量，按照上述接水规则，需要求出所有游客都接完水所需要的总时间。

输入描述

• 第一行：包含两个整数 n 和 m，用空格隔开，分别表示接水的游客人数和水龙头的个数。
• 第二行：包含 n 个整数 $w_1$、$w_2$、……、$w_n$，每两个整数之间用空格隔开，其中 wi 表示 i 号游客的接水量。

输出描述

输出一行，包含一个整数，表示所有游客接完水所需的总时间。

示例

• 示例 1：
  • 输入 #1：

    5 3
    4 4 1 2 1
    

  • 输出 #1：

    4
    

  • 解释：
    • 第 1 秒，3 人接水（1、2、3 号游客各占一个水龙头），此秒结束时，1、2、3 号游客每人已接水量为 1，3 号游客接完水，4 号游客接替 3 号游客开始接水。
    • 第 2 秒，依旧 3 人接水，结束时 1、2 号游客每人已接水量为 2，4 号游客已接水量为 1。
    • 第 3 秒，还是 3 人接水，结束时 1、2 号游客每人已接水量为 3，4 号游客已接水量为 2，此时 4 号游客接完水，5 号游客接替 4 号游客开始接水。
    • 第 4 秒，3 人接水，结束时 1、2 号游客每人已接水量为 4，5 号游客已接水量为 1，此时 1、2、5 号游客都接完水，即所有人完成接水，总接水时间为 4 秒。
• 示例 2：
  • 输入 #2：

    8 4
    23 71 87 32 70 93 80 76
    

  • 输出 #2：

    163
    

数据范围与提示

• $ 1 \le n,m \le 10^4,1 \le n*m \le 10^4, 1 \le w_i \le 10^3$