Misc side notes:

* There is no expected behavior for negative a negative weight.  Arguably, the only reasonable interpretation is what it already does (reduce the cumulative total).

* Running simulations is a primary use case for choices().  Generally, running time there is important. 

* During the design phase, none of the other implementations studied had incorporated a scan of the inputs for negative weights.

*  bisect() does not check to make sure its inputs are sorted.  The results for unsorted data are undefined.  It is a documented precondition.