cp2.4

# -*- coding: utf-8 -*-
"""
Created on Mon Apr 14 21:11:17 2014

@author: Administrator
"""
class heap():
    
    def __init__(self, h):
        self.len = len(h)
        self.heap = h
        self.heapify()
        
    def keepheap(self, i):
        h = self.heap
        crt = h[i]
        while 2*i + 1 < self.len:
            l, r = 2*i + 1, 2*i + 2
            if r < self.len and h[r] < h[l]:
                l = r
            if h[l] >= crt:
                break
            else:
                h[i] = h[l]
                i = l
        h[i] = crt
    
    def heapify(self):
        for i in xrange(self.len/2, -1, -1):
            self.keepheap(i)
            
    def heappop(self):
        self.len -= 1
        h = self.heap
        crt = h[0]
        tail = h.pop()
        if self.len > 0:
            h[0] = tail
            self.keepheap(0)
        return crt
        
    def heappush(self, v):
        i = self.len
        self.len += 1
        h = self.heap
        h.append(v)
        while i > 0:
            p = (i - 1) / 2
            if h[p] < v:
                break
            else:
                h[i] = h[p]
                i = p
        h[i] = v
        
import heapq
def poj2431(n, l, p, a, b):
    hp = []
    s = p
    i = cnt = 0
    while s < l:
        while i < n and a[i] <= s: 
            heapq.heappush(hp, -b[i])
            i += 1
        s += -heapq.heappop(hp)
        cnt += 1
    return cnt
    
class node:
    pass

def insert(T, z):
    x, y = T.root, None
    while x != None:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.p = y
    if y == None:
        T.root = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z