Take It or Leave It: A Game Show for Computers Context:

A reclusive billionaire has created a game show to attract the world's best and brightest programmers. On Mondays at the stroke of midnight, he chooses one person from a pool of applicants to be the contestant of the week, and provides them with a game. You are this week's lucky contestant!

This week's game:

The host provides you with API access to a stack of 10,000 digital envelopes. These envelopes are randomly sorted, and contain within them a dollar value, between $1 and $10,000 (no two envelopes contain the same dollar value).
You have 3 commands at your disposal:

Read(): Read the dollar figure in the envelope at the top of the stack.

Take(): Add the dollar figure in the envelope to your game show wallet, and pop the envelope off the stack.

Pass(): Pop off the envelope on the top of the stack.



The Rules:


If you use Pass() on an envelope, the money within is lost forever.

If you use Take() on an envelope containing $X, from that point forward, you may never use Take() on an envelope containing &lt; $X. Take() on one of these envelopes will add $0 to your wallet.



Write an algorithm that finishes the game with the maximal amount of money.
If you're writing a solution in Python, feel free to use this controller to test out algorithms, courtesy of @Maltysen: https://gist.github.com/Maltysen/5a4a33691cd603e9aeca
If you use the controller, you cannot access globals, you can only use the 3 provided API commands, and local scoped variables. (@Beta Decay)
Notes: &quot;Maximal&quot; in this case means the median value in your wallet after N &gt; 50 runs. I expect, though I would love to be proven wrong, that the median value for a given algorithm will converge as N increases to infinity. Feel free to try to maximize the mean instead, but I have a feeling that the mean is more likely to be thrown off by a small N than the median is.
Edit: changed the number of envelopes to 10k for easier processing, and made Take() more explicit.
Edit 2: The prize condition has been removed, in light of this post on meta.
Current high scores:
PhiNotPi    - $805,479
Reto Koradi - $803,960
Dennis      - $770,272 (Revised)
Alex L.     - $714,962 (Revised)
CJam, $87,143 $700,424 $720,327 $727,580 $770,272

{0:T:M;1e4:E,:)mr{RM&gt;{RR(*MM)*-E0.032*220+R*&lt;{ERM--:E;R:MT+:T;}{E(:E;}?}&amp;}fRT}
[easi*]$easi2/=N


This program simulates the entire game multiple times and calculates the median.

How to run

I've scored my submission by doing 100,001 test runs:

$ time java -jar cjam-0.6.5.jar take-it-or-leave-it.cjam 100001
770272

real    5m7.721s
user    5m15.334s
sys     0m0.570s


Approach

For each envelope, we do the following:


Estimate the amount of money that will inevitably be lost by taking the envelope.

If R is the content and M is the maximum that has been taken, the amount can be estimated as R(R-1)/2 - M(M+1)/2, which gives the money all envelopes with contents X in the interval (M,R) contain.

If no envelopes had been passed yet, the estimation would be perfect.
Calculate the amount of money that will inevitably be lost by passing the envelope.

This is simply the money the envelope contains.
Check if the quotient of both is less than 110 + 0.016E, where E is the number of remaining envelopes (not counting envelopes that cannot be taken anymore).

If so, take. Otherwise, pass.