← 返回题目列表

Codeforces · 1765/D

D. 观看视频

中文机器翻译题面 查看原题

Monocarp 想要观看 $$$n$$$ 视频。每个视频只有一分钟长,但其大小可以是任意的。第 $$$i$$$ 个视频的大小为 $$$a_i$$$ 兆字节。所有视频均发布在互联网上。观看视频之前应先下载视频。 Monocarp 的互联网连接较差 - 下载 $$$1$$$ 兆字节的数据需要 $$$1$$$ 分钟,因此下载第 $$$i$$$ 个视频需要 $$$a_i$$$ 分钟。

Monocarp 的计算机有 $$$m$$$ 兆字节的硬盘。该磁盘用于存储下载的视频。一旦 Monocarp 开始下载 $$$s$$$ 大小的视频,$$$s$$$ 兆字节将立即保留在硬盘上。如果剩余空间少于 $$$s$$$ 兆字节,则在释放所需空间之前无法开始下载。每个视频都可以存储在硬盘上,因为 $$$a_i \le m$$$ 对于所有 $$$i$$$ 而言。下载一旦开始,就无法中断。不允许并行运行两个或多个下载。

一旦视频完全下载到硬盘,Monocarp 就可以观看它。观看每个视频只需 $$$1$$$ 分钟,并且不占用互联网连接,因此 Monocarp 可以在观看当前视频的同时开始下载另一个视频。

当 Monocarp 看完视频后,他不再需要硬盘上的该视频,因此他可以删除该视频,立即释放其在硬盘上占用的空间。删除视频所花费的时间可以忽略不计。

Monocarp 希望尽快观看所有 $$$n$$$ 视频。观看顺序并不重要,因为 Monocarp 无论如何都需要观看所有这些内容。请计算所需的最短时间。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le m \le 10^9$$$) — 分别是 Monocarp 想要观看的视频数量和硬盘大小。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le m$$$) — 视频的大小。

输出

打印一个整数 — 观看所有 $$$n$$$ 视频所需的最短时间。

示例

输入 #1

5 6
1 2 3 4 5

输出 #1

16

输入 #2

5 5
1 2 3 4 5

输出 #2

17

输入 #3

4 3
1 3 2 3

输出 #3

12