Supermarket#5754
A supermarket has a set of products on sale. It earns a profit p_x for each product x \in \textbf{Prod} sold by its deadline d_x, where the deadline is measured as an integral number of time units starting from the moment the sale begins. Each product takes exactly one unit of time to be sold.
A selling schedule is an ordered subset of products, Sell \subseteq Prod, such that every product x \in Sell, in the given order, is sold by its deadline d_x (i.e., the sale of must finish at or before time d_x). The profit of a selling schedule is \text{Profit}(Sell) = \sum_{x \in Sell} p_x. An optimal selling schedule is a schedule that achieves the maximum possible profit.
For example, consider the set of products \textbf{Prod} = \{a, b, c, d\} with (p_a, d_a) = (50, 2), (p_b, d_b) = (10, 1), (p_c, d_c) = (20, 2), and (p_d, d_d) = (30, 1). Possible selling schedules are listed in a table (not provided). For instance, the schedule Sell = \{d, a\} means that the sale of product starts at time and ends at time , and the sale of product starts at time and ends at time . Both products are sold by their deadlines. This schedule is optimal and its profit is .
Write a program that reads sets of products from an input text file and computes the profit of an optimal selling schedule for each set.
Each set of products starts with an integer 0 \le n \le 10\,000, the number of products, followed by pairs p_i, d_i of integers (1 \le p_i \le 10\,000, 1 \le d_i \le 10\,000) representing the profit and deadline of the -th product. Whitespace may appear freely in the input. Input consists of several such sets, terminated by end of file. All input data are guaranteed to be correct.
For each set, output the profit of an optimal selling schedule on a separate line.
Example 1