题目描述

现有训练子任务模型的列表tasks, tasks[i]表示第i个子任务的算力需求，为了保证模型计算的时间，要求所有任务在T时刻内完成计算。

每个时刻，需要按照给出子任务模型的算力需求列表调度到量子计算机完成计算，任意时刻调度的多个子任务的算力需求综合不能超过量子计算机的最大算力负荷。

请返回量子计算机所需要提供的最低算力，可以在T时刻内计算完全部子任务模型

输入描述

输入：包含两行，第一行2个整数N, T，分别表示子任务模型列表长度，计算子任务模型的时刻要求。

第二行包含N个整数：task[1] task[2] task[3] ... task[n]分别表示第i个子任务的算力需求

输出描述

输出：一行包含一个整数，表示量子计算机所需要的最低算力

备注：

• 1 <= T <= N <= 50000
• 1 <= tasks[i] <= 500

示例1

输入

10 5
1 2 3 4 5 6 7 8 9 10

输出

15

说明： 最低算力需求为15时，可以在5时刻范围内完成所有任务 时刻1: 完成1，2,3,4,5的任务；时刻2：完成6,7的任务；时刻3：完成8任务；时刻4：完成9任务；时刻5：完成10任务

示例2

输入

6 3
4 4 2 1 2 3

输出

6

说明：

时刻1:4； 时刻2:4,2； 时刻3:1,2,3