$(10\%)$ Given a sequence $K=(k_1,k_2,$dots,$k_6)$ of $6$ distinct keys in sorted order with probabilities

$0\mathrm{.}06,0\mathrm{.}08,0\mathrm{.}10,0\mathrm{.}04,0\mathrm{.}12,0\mathrm{.}14.$ Some searches may be for values not in $K,$ and so we also have $7$

dummy keys, $d_0,d_1,$dots,$d_6,$ with probabilities $0\mathrm{.}07,0\mathrm{.}07,0\mathrm{.}07,0\mathrm{.}07,0\mathrm{.}06,0\mathrm{.}06,0\mathrm{.}06.$ Because

we have probabilities of searches for each key and each dummy key, we can determine the expected

cost a search in a given binary search tree $T.$ Suppose the expected cost of a search in $T$ is

cost in $T,$ where $depth{h}_T$ denotes a node's depth in the

tree $T.$ Determine the cost of an optimal binary search tree.