{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"超市有一组产品Prod出售。每售出一件产品x∈Prod,都会在截止日期dx之前(从销售开始时算起的整数时间单位)赚取利润px。每个产品售出需要一单位时间。销售计划是产品的有序子集Sell ≤ Prod,使得每个产品x∈Sell的销售,根据Sell的顺序,在截止日期dx之前完成,或者在dx到期时完成。销售计划的利润为Profit(Sell)\u003dΣ\u003csub\u003ex∈Sell\u003c/sub\u003epx。最佳销售计划是利润最大的计划。\r\u003cbr\u003e 例如,考虑产品Prod\u003d{a,b,c,d},其中(pa,da)\u003d(50,2),(pb,db)\u003d(10,1),(pc,dc)\u003d(20,2),(pd,dd)\u003d(30,1)。可能的销售计划列在表1中。例如,计划Sell\u003d{d,a}表示产品d的销售从时间0开始,到时间1结束,而产品a的销售从时间1开始,到时间2结束。每个产品都在其截止日期前售出。Sell是最佳计划,其利润为80。\r\u003cbr\u003e\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/f9d071d9c472cbda044241e92bee7393?v\u003d1711617937\"\u003e\u003c/center\u003e\r\u003cbr\u003e编写一个程序,从输入文本文件中读取产品集,并计算每个产品集的最佳销售计划的利润。"}},{"title":"Input","value":{"format":"HTML","content":"产品集以整数0 \u003c\u003d n \u003c\u003d 10000开头,表示产品集中的产品数量,然后是n对整数pi di,其中1 \u003c\u003d pi \u003c\u003d 10000,1 \u003c\u003d di \u003c\u003d 10000,表示第i个产品的利润和销售截止日期。输入中可以自由使用空格。输入数据以文件结束符结束,保证输入正确。"}},{"title":"Output","value":{"format":"HTML","content":"对于每个产品集,程序在标准输出上打印最佳销售计划的利润。每个结果都从新行的开头打印。"}},{"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"}},{"title":"Hint","value":{"format":"HTML","content":"样例输入包含两个产品集。第一个集合编码了表1中的产品。第二个集合是7个产品。这些产品的最佳计划利润为185。"}}]}