问题 5598 --看视频

5598: 看视频★★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 93  解决: 26
[提交][状态][命题人:]

题目描述

张老师想看n个视频。每个视频只有一分钟长,但其大小可能是任意的。第i个视频的大小为aiMB。所有视频都发布在互联网上。应该先下载视频,然后才能观看。张老师的宽带网速很慢,下载1MB的数据需要1分钟,因此下载第i个视频需要ai分钟。
张老师的电脑有一个 m MB的硬盘用于存储下载的视频。一旦张老师开始下载大小为s的视频,硬盘上的 s MB将立即被占用。如果剩余空间小于s MB,则需要先释放所需空间之前再开始下载。ai≤m,因此每个视频都可以存的下。视频开始下载后就不能中断。不允许同时下载多个视频。
当视频完全下载到硬盘上时张老师就可以观看视频。观看每个视频要1分钟,而且不占用网络,因此,张老师可以在观看当前视频的同时开始下载另一个视频。
当张老师看完视频后,他可以马上删除硬盘上的视频,删除视频所需的时间可以忽略不计。
问:张老师最快看完所有视频的时间是多少。

输入

第一行包含两个整数n和m(1≤n≤2*105;1≤m≤109),分别是张老师想要观看的视频数量和硬盘大小。

第二行包含n个整数a1,a2,…,an(1≤ai≤m)-视频的大小。

输出

输出一个整数-观看所有n个视频所需的最短时间。
样例输入
Copy
第一组:
5 6
1 2 3 4 5
第二组:
4 3
1 3 2 3
样例输出
Copy
第一组:
16
第二组:
12

提示

来源

[提交][状态]