Take It or Leave It III: A Game Show for Computers This is the third in a series of puzzles that I will be posting every Monday at Midnight PST, and the final variant of &quot;Take It or Leave It&quot;.
The first puzzle is located Here
The second puzzle is located Here
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 15,000 digital envelopes. These envelopes are randomly sorted, and contain within them a dollar value, between $1 and $15,000 (no two envelopes contain the same dollar value).
You have 5 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.

Oracle(M): Returns the mean value of the next M envelopes in the stack, not including the one you can currently Read().

End(): Stop the game, and walk away the money currently in your wallet (your final score).



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.

If you use Oracle(M) on turn T, envelopes T+1 through T+M's mean will be returned. Oracle() is disabled until turn T+M.

If you use Take() or Pass() on turn T, $T is removed from your wallet.



Write an algorithm that finishes the game with the maximal amount of money.
Note 1: &quot;Maximal&quot; in this case means the median value in your wallet after N &gt;= 1000 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.
Note 2: This puzzle has a significant difference from the first two iterations (namely, needing to pay for each envelope you take). Feel free to use any strategies from the first puzzles as a base, but be warned: They will probably (read: definitely) get a negative score without some kind of modification.
Edit: The prize condition has been removed, in light of this post on meta.
Java, $3889.5 Median
        int highest=0;
        int topp=0,tott=0;
        for(int i=0;i&lt;1000;i++){
            if(Read()&gt;topp&amp;&amp;tott+Read()-i&gt;tott){
                topp=Read();
                tott += Read();
                tott -= i;
                Take();
            }else{
                if(tott-i&gt;i/2){
                    tott -= i;
                    Pass();
                }else{
                    End();
                    break;
                }
            }
            if(highest/1.1&gt;tott){
                End();
                break;
            }
            if(tott&gt;highest)
            highest=tott;
        }

Try it Online