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.


-----Input-----

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.


-----Output-----

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


-----Examples-----

Input
5 6
1 2 3 4 5
Output
16
Input
5 5
1 2 3 4 5
Output
17
Input
4 3
1 3 2 3
Output
12


-----Note-----

None

Difficulty: MEDIUM_HARD
Tags: Sorting

Amortized analysis

Constructive algorithms
Skill types: Sorting

Amortized analysis

Starter code:

Solutions:
(n, m) = [int(num) for num in input().split()]
arr = [int(num) for num in input().split()]
arr.sort()
aa = 0
i = 0
j = n - 1
while i < j:
	if arr[i] + arr[j] > m:
		j -= 1
		aa += 1
	else:
		i += 1
		j -= 1
ans = sum(arr) + 1 + aa
print(ans)


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
i = 0
j = n - 1
answer = sum(l)
while j > i:
	if l[i] + l[j] > k:
		answer += 1
		j -= 1
	else:
		i += 1
		j -= 1
print(answer + 1)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
res = 0
for e in a:
	res += e
l = 0
r = n - 1
while l < r:
	if a[l] + a[r] <= m:
		l += 1
		r -= 1
	else:
		r -= 1
		res += 1
res += 1
print(res)


(n, m) = map(int, input().split())
li = list(map(int, input().split()))
li.sort()
sum = 1
for i in li:
	sum += i
beg = 0
end = n - 1
while beg < end:
	if li[beg] + li[end] <= m:
		beg += 1
		end -= 1
	else:
		sum += 1
		end -= 1
print(sum)


(n, m) = input().split()
m = int(m)
p = list(input().split())
for i in range(len(p)):
	p[i] = int(p[i])
p.sort()
l = 0
h = len(p) - 1
s = 0
while l <= h:
	if l != h:
		if p[h] + p[l] <= m:
			s += p[h] + p[l]
			h -= 1
			l += 1
		else:
			s += p[h] + 1
			h -= 1
	else:
		s += p[h]
		h -= 1
print(s + 1)


(n, m) = map(int, input().split())
sizes = list(map(int, input().split()))
sizes = sorted(sizes)
up_index = n - 1
down_index = 0
spent_time = 0
used_m = 0
while up_index >= down_index:
	if used_m + sizes[up_index] > m:
		spent_time += 1
	spent_time += sizes[up_index]
	used_m = sizes[up_index]
	up_index -= 1
	if up_index < down_index:
		break
	if used_m + sizes[down_index] <= m:
		spent_time += sizes[down_index]
		used_m = sizes[down_index]
		down_index += 1
	else:
		spent_time += 1
		used_m = 0
print(spent_time + 1)


def binarysearch(array, element):
	if len(array) == 1:
		if array[0] >= element:
			return 0
		else:
			return 1
	elif array[len(array) // 2] >= element:
		return binarysearch(array[0:len(array) // 2], element)
	else:
		return len(array) // 2 + binarysearch(array[len(array) // 2:], element)

def reverse(obj):
	l = obj[::-1]
	return l
nm = input().split(' ')
n = int(nm[0])
m = int(nm[1])
data = input().split(' ')
for i in range(len(data)):
	data[i] = int(data[i])
data.sort()
x = m
final = 0
i = binarysearch(data, m)
if i < n:
	for j in range(i, n):
		final = final + 1 + data[j]
l1 = data[0:i]
l2 = reverse(l1)
x = 0
j = 0
while x + j <= i - 1:
	final += l2[x]
	if l1[j] + l2[x] <= m:
		if not x + j == i - 1:
			final += l1[j]
			j += 1
			if x + j == i - 1:
				final += 1
		else:
			final += 1
	else:
		final += 1
	x += 1
print(final)