# -*- coding: utf8 -*-
import os, sys, math, copy

class node:
	value = 0
	id = 0
	parent_left = None
	parent_right = None
	bit = 0
	
	def __init__( self, id, value, left=None, right=None ):
		self.id = id
		self.value = value
		self.parent_left = left
		self.parent_right = right
		if right is not None:
			right.bit = 1
		
	def __repr__( self ):
		return "<node id='%s' bit='%s' value='%s'>"%( self.id, self.bit, self.value )
	
	def __cmp__( self, node2 ):
		if self.value < node2.value:
			return -1
		elif self.value == node2.value:
			return -1
		else:
			return 1

class tree:
	def __init__( self, sequence ):
		self.seq = sequence
		self.head = []
		self.tree = []
		
		self.size = 0
		for item in sequence:
			self.head.append( node( item[0], item[1] ) )
			self.size += item[1]
		
		value = 0
		while value < self.size:
			self.head.sort()
			value = self.head[0].value+self.head[1].value
			if value < self.size:
				self.head[0] = node( 0, value, self.head[0], self.head[1] )
				del self.head[1]
		else:
			self.begin = node( 0, value, self.head[-1], self.head[-2] )
			
if __name__ == "__main__":
	seq = [ ( "A", 8 ), ("B", 7 ), ("C", 12 ), ("D", 9 ), ("E", 15) ]
	t = tree( seq )
	print t.begin.parent_left.parent_left.parent_right