# Who wants to be a Millionaire?

**Computer Science**Level 5

Consider the following version of the who wants to be a millionaire game: You are given a list \(\mathcal{L}\), consisting of \(N\) questions. You can answer the questions in any order you like. The probability that you answer the \(i\)th question in \(\mathcal{L}\) correctly is \(p_i\) and you win \(v_i\) dollars for answering it correctly , \(i=1,2,\ldots, N\). However, if you give a wrong answer to a question, the game ends immediately and you leave the game with the money you have already won (if any). Naturally, your objective is to answer the questions in an optimal order \(\mathcal{S}\) so as to maximize your expected winning. To be clear, \(\mathcal{S}\) is a permutation of natural numbers from \(1\) to \(N\) which corresponds to your order of answering questions from the list \(\mathcal{L}\), e.g., if \(\mathcal{S}(1)=1000\), it means that you answer the \(1000\) th question first from \(\mathcal{L}\) and so on.

Here is the data for \(N=10000\) questions, where the row numbers (on the left) correspond to question numbers in the list \(\mathcal{L}\), the first column corresponds to the probabilities \(p_i\)'s and the second column corresponds to the prizes \(v_i\)'s.

Find \(\mathcal{S}(2015)\) in the optimal sequence.