Alyona has recently bought a miniature fridge that can be represented as a matrix with $h$ rows and $2$ columns. Initially there is only one shelf at the bottom of the fridge, but Alyona can install arbitrary number of shelves inside the fridge between any two rows. A shelf is two cells wide, does not occupy any space but separates the inside of the fridge to the lower and upper part.

 [Image] An example of a fridge with $h = 7$ and two shelves. The shelves are shown in black. The picture corresponds to the first example. 

Alyona has $n$ bottles of milk that she wants to put in the fridge. The $i$-th bottle is $a_i$ cells tall and $1$ cell wide. She can put a bottle on some shelf if the corresponding space above the shelf is at least as tall as the bottle. She can not put a bottle on top of another bottle (if there is no shelf between them). Two bottles can not share a cell.

Alyona is interested in the largest integer $k$ such that she can put bottles $1$, $2$, ..., $k$ in the fridge at the same time. Find this largest $k$.


-----Input-----

The first line contains two integers $n$ and $h$ ($1 \le n \le 10^3$, $1 \le h \le 10^9$) — the number of bottles and the height of the fridge.

The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le h$) — the heights of the bottles.


-----Output-----

Print the single integer $k$ — the maximum integer such that Alyona can put the bottles $1$, $2$, ..., $k$ in the fridge at the same time. If Alyona can put all bottles in the fridge, print $n$. It is easy to see that Alyona can always put at least one bottle in the fridge.


-----Examples-----
Input
5 7
2 3 5 4 1

Output
3

Input
10 10
9 1 1 1 1 1 1 1 1 1

Output
4

Input
5 10
3 1 4 2 4

Output
5



-----Note-----

One of optimal locations in the first example is shown on the picture in the statement.

One of optimal locations in the second example is shown on the picture below.

 [Image] 

One of optimal locations in the third example is shown on the picture below.

 [Image]

Difficulty: interview

Starter code:

Solutions:
def func(arr):
    arr.sort()
    ans = 0
    for i in range(len(arr) - 1, -1, -2):
        ans += arr[i]
    return ans

def main():
    n, h = map(int, input().split())
    arr = list(map(int, input().split()))
    for i in range(1, n + 1):
        if func(arr[:i]) > h:
            i -= 1
            break
    print(i)
    return 0
main()

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return tuple(map(int, sys.stdin.readline().split()))
def LLI(): return [tuple(map(int, l.split())) for l in sys.stdin]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def bs(f, mi, ma):
    mm = -1
    while ma > mi:
        mm = (ma+mi) // 2
        if f(mm):
            mi = mm + 1
        else:
            ma = mm
    if f(mm):
        return mm + 1
    return mm

def main():
    n,h = LI()
    a = LI()

    def f(i):
        if i > n:
            return False
        b = sorted(a[:i])
        t = None
        if i % 2 == 1:
            t = sum(b[::2])
        else:
            t = sum(b[1::2])
        return t <= h

    r = bs(f, 0, n+1)

    return r - 1

print(main())




n, h = map(int, input().split())
A = list(map(int, input().split()))
bot = []
for i in range(n):
    cnt = 0
    bot.append(A[i])
    bot.sort(reverse=True)
    for iq in range(0, len(bot), 2):
        cnt += bot[iq]
    if cnt > h:
        print(i)
        return
print(n)

def f(a):
    a.sort()
    ans = 0
    for i in range(len(a) - 1, -1, -2):
        ans += a[i]
    return ans

n, h = list(map(int, input().split()))
a = list(map(int, input().split()))
ans = 0
for i in range(1,n + 1):
    b = a[:i].copy()
    x = f(b)
    if (x <= h):
       ans = i
print(ans)


n, h = list(map(int, input().split()))
a = list(map(int, input().split()))


def can(mid):
    val = sum(sorted(a[:mid])[::-2])
    return val <= h


le = 1
rg = n + 1

while rg - le > 1:
    mid = (le + rg) // 2

    if can(mid):
        le = mid
    else:
        rg = mid

print(le)


n,h=map(int,input().split())
l=list(map(int,input().split()))
ans=0
for i in range(n):
         curr=0
         ls=sorted(l[:i+1])
         for j in range(i,-1,-2):
                  curr+=ls[j]
         if(curr>h):
                  break
         else:
                  ans=i
print(ans+1)

import bisect
a = []
n, h = list(map(int, input().split()))
k = 0
for ai in input().split():
    bisect.insort(a, int(ai))
    if sum(a[::-2]) > h:
        break
    k += 1
print(k)


n,h=[int(x) for x in input().split()]
c=[int(x) for x in input().split()]
answer=0
for i in range(1,n+1):
    a=c[:i]
    a.sort(reverse=True)
    summa=0
    for item in range(0,i,2):
        summa+=a[item]
    if summa>h:
        print(answer)
        break
    else:
        answer=i
else:
    print(answer)


3

def can(a, h):
    a.sort(reverse=True)
    cur = 0
    for i in range(0, len(a), 2):
        cur += a[i]
    return cur <= h


n, h = list(map(int, input().split()))
a = list(map(int, input().split()))

lt, rt = 0, n + 1
while lt < rt - 1:
    mid = (lt + rt) // 2
    if can(a[:mid], h):
        lt = mid
    else:
        rt = mid

print(lt)


from sys import stdin, stderr

n, h = list(map(int, stdin.readline().split()))
a = list(map(int, stdin.readline().split()))

def ok(k):
    b = list(sorted(a[:k],reverse=True))
    t = sum(b[::2])
    # print(k, t, b, file=stderr)
    return t <= h

l = 0
r = n + 1
while r - l > 1:
    mid = (l + r) // 2
    if ok(mid):
        l = mid
    else:
        r = mid
print(l)


n, k = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

heights = []
ok= 0
for jj in range(n+1):
    heights = sorted(A[:jj], reverse=True)
    totalheight = 0
    for i in range(len(heights)):
        if i&1:
            continue
        else:
            totalheight+=heights[i]
    
    #print('at jj',jj, totalheight)
    if totalheight <= k:
        ok = jj
    else:
        break
print(ok)


N,H = list(map(int,input().split()))
A = list(map(int,input().split()))

def isok(k):
    if k==0: return True
    sa = list(sorted(A[:k],reverse=True))
    h = 0
    for a in sa[::2]:
        h += a
        if h > H: return False
    return True

ok = 0
ng = N+1
while ng-ok > 1:
    m = (ok+ng)//2
    if isok(m):
        ok = m
    else:
        ng = m
print(ok)


n,h = list(map(int, input().split()))
a = list(map(int, input().split()))

def check(k):
    if k == 0:
        return True
    ar = a[:k]
    ar = sorted(ar, key=lambda x: -x)
    s = 0
    for i in range((k+1)//2):
        m = ar[2*i]
        s += m
    return s <= h

l = 0
r = len(a)
ans = 0
while r >= l:
    m = (r+l)//2
    if check(m):
        ans = max(ans, m)
        l = m+1
    else:
        r = m-1
print(ans)


def can_arrange(heights, h):
	heights = sorted(heights, reverse=True)
	th = 0
	for i in range(0, len(heights), 2):
		th += heights[i]
	return th <= h

n, h = (int(x) for x in input().split())
idx___height = [int(x) for x in input().split()]

l_cl = 0
r_op = n + 1

while r_op - l_cl > 1:
	m = (l_cl + r_op) // 2
	if can_arrange(idx___height[:m], h):
		l_cl = m
	else:
		r_op = m
print(l_cl)

n, h = map(int, input().split())
a = [int(_) for _ in input().split()]
res = 1
for k in range(n):
    part = a[:k + 1]
    part.sort()
    ans, ans2 = 0, 0
    if len(part) & 1:
        for i in range(0, k + 1, 2):
            ans += part[i]
        for i in range(1, k + 1, 2):
            ans2 += part[i]
        ans2 += part[-1]
        ans = min(ans, ans2)
    else:
        for i in range(1, k + 1, 2):
            ans += part[i]
    # print(part, ans)
    if ans <= h:
        res = max(res, len(part))
    else:
        break
print(res)

n, h = list(map(int, input().split()))
a = list(map(int, input().split()))
l, r = 1, n + 1
while l + 1 < r:
	mid = (l + r) >> 1
	c = sorted(a[:mid], reverse=True)
	if sum(c[i] for i in range(len(c)) if (i & 1) == 0) <= h:
		l = mid
	else:
		r = mid
print(l)


#!/usr/bin/env python3
# -*- coding: utf-8 -*-

n, h = map(int, input().split())
arr = list(map(int, input().split()))

use = []
for i in range(n):
    use.append(arr[i])
    use.sort()
    real_use = use[-1:-(i + 2):-2]
    #print(real_use)
    if sum(real_use) > h:
        print(i)
        return
print(n)

n, h = map(int, input().split())
c = list(map(int, input().split()))
i = n
c2 = sorted(c)
if i % 2 == 1:
    s = sum(c2[0:i:2])
else:
    s = sum(c2[1:i:2])
while s > h:
    i -= 1
    c = c[:i]
    c2 = sorted(c)
    if i % 2 == 1:
        s = sum(c2[0:i:2])
    else:
        s = sum(c2[1:i:2])
print(i)

from collections import defaultdict as DD
from bisect import bisect_left as BL
from bisect import bisect_right as BR
from itertools import combinations as IC
from itertools import permutations as IP
from random import randint as RI
import sys
MOD=pow(10,9)+7

def IN(f=0):
    if f==0:
        return ( [int(i) for i in sys.stdin.readline().split()] )
    else:
        return ( int(sys.stdin.readline()) )

n,k=IN()
a=IN()

T=[]
M=n
for i in range(n):
    j=BL(T,a[i])
    T[j:j]=[a[i]]
    f=0
    m=0
    for g in range(len(T)-1,-1,-2):
        m+=T[g]
    if m>k:
        M=i
        break
print(M)
        
        
    


#print('HARE KRISHNA')
def I():
    return int(input())
def IL():
    return list(map(int,input().split()))
def IM():
    return map(int,input().split())
def IS():
    return input()
def ISL():
    return list(input())
n,h=IM()
l=IL()
def can_put(mi):
    if mi==0:
        return l[0]<=h 
    z=sorted(l[0:mi+1])
    req=0 
    if mi%2==0:
        req+=z[0]
        for i in range(1,mi+1,2):
            req+=max(z[i],z[i+1])
        #req+=z[mi-1]
    else:
        for i in range(0,mi+1,2):
            req+=max(z[i],z[i+1])
    #print(z,req)
    return req<=h 
lo=0 
hi=n-1 
ans=0 
while lo<=hi:
    mi=(lo+hi)>>1 
    if can_put(mi):
        ans=mi
        lo=mi+1 
    else:
        hi=mi-1 
print(ans+1)

n, h = list(map(int,input().split()))
l = list(map(int,input().split()))
def poss(k):
	tab = sorted(l[:k])
	suma = 0
	i = k - 1
	while i >= 0:
		suma += tab[i]
		i -= 2
	if suma > h:
		return False
	return True
lo = 0
hi = n
kand = 0
while True:
	if (poss((lo + hi) // 2)):
		lo = ((lo + hi) // 2)
	else:
		hi = ((lo + hi) // 2)
	if abs(lo-hi) < 2:
		kand = lo
		break
if poss(kand + 1):
	print(kand +1)
else:
	print(kand)

n,h = list(map(int,input().split()))
bottles = list(map(int,input().split()))

# low = 2
# end = n
# middle = low + (end-low) // 2

out = 0
for middle in range(n,-1,-1):
#while low<=end:
    choice = bottles[:middle]
    choice = sorted(choice,reverse=True)
    total_bottles = 0
    current_h = 0
    i = 0
    while i<middle and (current_h+choice[i])<=h:
        current_h += choice[i]
        i+=2
        total_bottles+=2
    total_bottles = min(total_bottles,middle)
    if total_bottles == middle:
        print (total_bottles)
        break
#     if total_bottles<middle:
#         end = middle-1
#         middle = low + (end-low) // 2
#     else:
#         low = middle+1
#         middle = low + (end-low) // 2
#         out = total_bottles
# print (out)


import sys

n, h = map(int,input().split())
l = list(map(int,sys.stdin.readline().split()))
c = l.copy()
i=0
c.sort(reverse=True)
T = float('infinity')
while T > h:
	T = sum([ c[k] for k in range(0,n-i,2) ])
	c.pop(c.index(l[-i-1]))
	i+=1
print(n+1-i)