Your virtually infinite supply of BAPCs. CC BY 2.0 by fdecomite on Flickr After countless hours spent designing, optimizing and perfecting, you finally did it: you have found a way of producing Beautiful and Absolutely Perfect Cubes (BAPCs). Because you would like to make a lot of money from this invention, you decided to hire an economist. However, instead of just telling you how to become rich, they started giving you some useless lecture about the difference between profit and revenue, the sunk cost fallacy, and the importance of market research. Instead of letting them finish their speech, you decided to just tell them to do the market research themselves, while you focus on the important matters, such as producing as many BAPCs as possible.
Now it is one year later, you have a virtually infinite supply of BAPCs, and no money. You will need some income soon, to start paying your economist, for example. You would like to ask them for the optimal selling price of a BAPC, however, they have stopped answering your messages (they are probably exhausted from their market research). They did still send you the results of the market research, so you will need to use this to figure out the optimal selling price yourself.
The results consist of a list of all people interested in buying a BAPC, together with the maximal price at which they would buy. If you fix the selling price at $$$p$$$ euros, then everyone on this list who indicated a maximal price of $$$p$$$ or higher will buy a single BAPC for $$$p$$$ euros. All others will not buy any BAPC.
The number of BAPCs you produced is way larger than the number of people on the list, so you do not need to worry about running out of BAPCs. What is your maximal revenue if you choose the optimal selling price?
The input consists of:
Output your maximal revenue.
3 4 1 5
8
6 3 6 9 3 7 10
24
3 1234567890 9876543210 2468013579
9876543210