Watch the Videos

题意翻译

有 $ n $ 个视频，第 $ i $ 个视频的大小为 $ a_i $。你有一块容量为 $ m $ 的硬盘。每一个视频必须先花费 $ a_i $ 的时间下载下来，保存在硬盘里（占据硬盘 $ a_i $ 的空间），才能观看。观看一个视频花费的时间为 $ 1 $。 此外，还有几个注意点： 一、任何时候，硬盘被占据的空间必须小于等于 $ m $。 二、一个视频在看完之后可以立刻删除，把占据的 $ a_i $ 的空间释放掉。删除这件事情不需要花费时间。 三、不能同时下载超过一个视频，也不能同时观看超过一个视频。但是可以在下载某个视频的同时，观看其他已经保存在硬盘里的视频。 你可以按任何顺序下载和观看这 $ n $ 个视频，问看完所有视频，最少需要花费多长时间。 $ 1 $ ${\leq}$ $ n $ ${\leq}$ $ 2 * 10 ^ 5 $；$ 1 $ ${\leq}$ $ m $ ${\leq}$ $ 10 ^ 9 $；$ 1 $ ${\leq}$ $ a_i $ ${\leq}$ $ m $

题目描述

Monocarp wants to watch $ n $ videos. Each video is only one minute long, but its size may be arbitrary. The $ i $ -th video has the size $ a_i $ megabytes. All videos are published on the Internet. A video should be downloaded before it can be watched. Monocarp has poor Internet connection — it takes exactly $ 1 $ minute to download $ 1 $ megabyte of data, so it will require $ a_i $ minutes to download the $ i $ -th video. Monocarp's computer has a hard disk of $ m $ megabytes. The disk is used to store the downloaded videos. Once Monocarp starts the download of a video of size $ s $ , the $ s $ megabytes are immediately reserved on a hard disk. If there are less than $ s $ megabytes left, the download cannot be started until the required space is freed. Each single video can be stored on the hard disk, since $ a_i \le m $ for all $ i $ . Once the download is started, it cannot be interrupted. It is not allowed to run two or more downloads in parallel. Once a video is fully downloaded to the hard disk, Monocarp can watch it. Watching each video takes exactly $ 1 $ minute and does not occupy the Internet connection, so Monocarp can start downloading another video while watching the current one. When Monocarp finishes watching a video, he doesn't need it on the hard disk anymore, so he can delete the video, instantly freeing the space it occupied on a hard disk. Deleting a video takes negligible time. Monocarp wants to watch all $ n $ videos as quickly as possible. The order of watching does not matter, since Monocarp needs to watch all of them anyway. Please calculate the minimum possible time required for that.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 1 \le n \le 2 \cdot 10^5 $ ; $ 1 \le m \le 10^9 $ ) — the number of videos Monocarp wants to watch and the size of the hard disk, respectively. The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le m $ ) — the sizes of the videos.

输出格式

Print one integer — the minimum time required to watch all $ n $ videos.

输入输出样例

输入样例 #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