{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp\u003eGold Problem Land Acquisition [Paul Christiano, 2007]\u003c/p\u003e\r\n\r\n\u003cp\u003eFarmer John is considering buying more land for the farm and has\r\nhis eye on N (1 \u0026lt;\u003d N \u0026lt;\u003d 50,000) additional rectangular plots, each\r\nwith integer dimensions (1 \u0026lt;\u003d width_i \u0026lt;\u003d 1,000,000; 1 \u0026lt;\u003d length_i\r\n\u0026lt;\u003d 1,000,000).\u003c/p\u003e\r\n\r\n\u003cp\u003eIf FJ wants to buy a single piece of land, the cost is $1/square\r\nunit, but savings are available for large purchases. He can buy\r\nany number of plots of land for a price in dollars that is the width\r\nof the widest plot times the length of the longest plot. Of course,\r\nland plots cannot be rotated, i.e., if Farmer John buys a 3x5 plot\r\nand a 5x3 plot in a group, he will pay 5x5\u003d25.\u003c/p\u003e\r\n\r\n\u003cp\u003eFJ wants to grow his farm as much as possible and desires all the\r\nplots of land. Being both clever and frugal, it dawns on him that\r\nhe can purchase the land in successive groups, cleverly minimizing\r\nthe total cost by grouping various plots that have advantageous\r\nwidth or length values.\u003c/p\u003e\r\n\r\n\u003cp\u003eGiven the number of plots for sale and the dimensions of each,\r\ndetermine the minimum amount for which Farmer John can purchase all\u003c/p\u003e\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cul\u003e\r\n\u003cli\u003eLine 1: A single integer: N\u003c/li\u003e\r\n\u003cli\u003eLines 2..N+1: Line i+1 describes plot i with two space-separated\r\nintegers: width_i and length_i\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cul\u003e\r\n\u003cli\u003eLine 1: The minimum amount necessary to buy all the plots.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\r\n\u003ch3\u003eSample\u003c/h3\u003e\r\n\u003cdiv\u003e\u003ctable class\u003d\"vjudge_sample\"\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\r\n100 1\r\n15 15\r\n20 5\r\n1 100\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e500\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\r\n\r\n\u003ch3\u003eExplanation\u003c/h3\u003e\r\n\u003cp\u003eThere are four plots for sale with dimensions as shown.\u003c/p\u003e\r\n\u003cp\u003eThe first group contains a 100x1 plot and costs 100. The next group\r\ncontains a 1x100 plot and costs 100. The last group contains both the 20x5\r\nplot and the 15x15 plot and costs 300. The total cost is 500, which is\r\nminimal.\u003c/p\u003e\r\n\n\u003c/div\u003e"}}]}