{"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\u003eAdquisición de tierras del problema de oro [Paul Christiano, 2007]\u003c/p\u003e\n\n\u003cp\u003eEl granjero John está considerando comprar más tierras para la granja y tiene la vista puesta en N (1 \u0026lt;\u003d N \u0026lt;\u003d 50,000) parcelas rectangulares adicionales, cada una con dimensiones enteras (1 \u0026lt;\u003d ancho_i \u0026lt;\u003d 1,000,000; 1 \u0026lt;\u003d longitud_i \u0026lt;\u003d 1,000,000).\u003c/p\u003e\n\n\u003cp\u003eSi FJ quiere comprar una sola parcela de tierra, el costo es de $1 por unidad cuadrada, pero hay descuentos disponibles para compras grandes. Puede comprar cualquier número de parcelas de tierra por un precio en dólares que es el ancho de la parcela más ancha multiplicado por la longitud de la parcela más larga. Por supuesto, las parcelas de tierra no se pueden rotar, es decir, si el granjero John compra una parcela de 3x5 y una parcela de 5x3 en un grupo, pagará 5x5\u003d25.\u003c/p\u003e\n\n\u003cp\u003eFJ quiere hacer crecer su granja tanto como sea posible y desea todas las parcelas de tierra. Siendo tanto ingenioso como frugal, se le ocurre que puede comprar la tierra en grupos sucesivos, minimizando inteligentemente el costo total agrupando diversas parcelas que tienen valores de ancho o longitud ventajosos.\u003c/p\u003e\n\n\u003cp\u003eDado el número de parcelas en venta y las dimensiones de cada una, determine la cantidad mínima por la cual el granjero John puede comprar todas\u003c/p\u003e\n\n\u003ch3\u003eEntrada\u003c/h3\u003e\n\u003cul\u003e\n\u003cli\u003eLínea 1: Un solo entero: N\u003c/li\u003e\n\u003cli\u003eLíneas 2..N+1: La línea i+1 describe la parcela i con dos enteros separados por un espacio: ancho_i y longitud_i\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003ch3\u003eSalida\u003c/h3\u003e\n\u003cul\u003e\n\u003cli\u003eLínea 1: La cantidad mínima necesaria para comprar todas las parcelas.\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003ch3\u003eEjemplo\u003c/h3\u003e\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\n\n\u003ch3\u003eExplicación\u003c/h3\u003e\n\u003cp\u003eHay cuatro parcelas en venta con las dimensiones mostradas.\u003c/p\u003e\n\u003cp\u003eEl primer grupo contiene una parcela de 100x1 y cuesta 100. El siguiente grupo contiene una parcela de 1x100 y cuesta 100. El último grupo contiene tanto la parcela de 20x5 como la parcela de 15x15 y cuesta 300. El costo total es de 500, que es mínimo.\u003c/p\u003e\n\n\u003c/div\u003e"}}]}