{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral number of time units starting from the moment the sale begins. Each product takes precisely one unit of time for being sold. A selling schedule is an ordered subset of products Sell ≤ Prod such that the selling of each product x∈Sell, according to the ordering of Sell, completes before the deadline dx or just when dx expires. The profit of the selling schedule is Profit(Sell)\u003dΣ\u003csub\u003ex∈Sell\u003c/sub\u003epx. An optimal selling schedule is a schedule with a maximum profit.\r\u003cbr\u003e For example, consider the products Prod\u003d{a,b,c,d} with (pa,da)\u003d(50,2), (pb,db)\u003d(10,1), (pc,dc)\u003d(20,2), and (pd,dd)\u003d(30,1). The possible selling schedules are listed in table 1. For instance, the schedule Sell\u003d{d,a} shows that the selling of product d starts at time 0 and ends at time 1, while the selling of product a starts at time 1 and ends at time 2. Each of these products is sold by its deadline. Sell is the optimal schedule and its profit is 80.\r\u003cbr\u003e\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/f9d071d9c472cbda044241e92bee7393?v\u003d1714083190\"\u003e\u003c/center\u003e\r\u003cbr\u003eWrite a program that reads sets of products from an input text file and computes the profit of an optimal selling schedule for each set of products. \r\u003cbr\u003e "}},{"title":"Input","value":{"format":"HTML","content":"A set of products starts with an integer 0 \u0026lt;\u003d n \u0026lt;\u003d 10000, which is the number of products in the set, and continues with n pairs pi di of integers, 1 \u0026lt;\u003d pi \u0026lt;\u003d 10000 and 1 \u0026lt;\u003d di \u0026lt;\u003d 10000, that designate the profit and the selling deadline of the i-th product. White spaces can occur freely in input. Input data terminate with an end of file and are guaranteed correct. "}},{"title":"Output","value":{"format":"HTML","content":"For each set of products, the program prints on the standard output the profit of an optimal selling schedule for the set. Each result is printed from the beginning of a separate line."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 50 2 10 1 20 2 30 1\r\n\r\n7 20 1 2 1 10 3 100 2 8 2\r\n 5 20 50 10\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e80\r\n185\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"The sample input contains two product sets. The first set encodes the products from table 1. The second set is for 7 products. The profit of an optimal schedule for these products is 185."}}]}