¡Las ~2*N (3 \leq N \leq 1,000)~ vacas han organizado la Orquesta Bovina de Banjo y Acordeón! Ellas poseen varios niveles de habilidad en sus instrumentos respectivos: la acordeonista ~i~ tiene un nivel de talento asociado de ~A_i (0 \leq A_i \leq 1,000)~; la banjista ~j~ tiene un nivel de talento asociado ~B_j (0 \leq B_j \leq 1,000~).

La calidad combinada de un apareamiento entre vacas con talentos ~A_i~ y ~B_j~ es directamente proporcional a los talentos de cada vaca en el par, por lo tanto un concierto que estas dos vacas le dará precisamente ~A_i * B_j~ dólares en "donaciones de caridad". GJ desea maximizar la suma de todas las ganancias obtenidas por sus vacas apareándolas de la manera más beneficiosa.

Desafortunadamente las acordeonistas de GJ son un poco rígidas e intransigentes. Si la acordeonista ~i~ está apareada con la banjista ~j~, entonces las acordeonistas ~i+1..N~ se rehusan a ser apareadas con las banjistas ~1..j-1~. Esto crea restricciones en cuáles pares puede formar GJ. GJ se da cuenta entonces que con el propósito de maximizar sus ganancias, él debe dejar algunas vacas sin aparear.

Para hacer peor las cosas, cuando una o más de ls músicas no es tomada en cuenta, ellas se molestaran mucho por su talento desaprovechado y se dedicarán a una parranda de tomar para limpiar su vergüenza.

Después que los apareamientos son hechos, se construye una lista con los grupos de cada una de las músicas que no han sido tomadas en cuenta (de cualquier instrumento). Cada grupo de una o más vacas consecutivas no tomadas en cuenta se reunirán juntas para consumir barriles de gaseosa de naranja fría en una cantidad proporcional al cuadrado de la suma de sus talentos desaprovechados.

Específicamente, GJ ha calculado que si no se toman en cuenta las acordeonistas de la x-ésima a la y-ésima, ellas consumirán exactamente ~(A_x + A_x+1 + A_x+2 + ...+ A_y)^2~ dólares de gaseosa de naranja en el proceso de olvidarse de su vergüenza. Una relación idéntica se cumple para las banjistas. GJ se da cuenta que él terminará arruinado con la cuenta de la bebida de sus vacas, y por lo tanto toma esto en cuenta cuando elige que apareamientos hacer.

Encuentre la cantidad máxima de ganancia total que GJ puede ganar después de que se colectan las contribuciones y se paga por la gaseosa de naranja.

Entrada

• Línea 1: Un solo entero: ~N~
• Líneas 2..N+1: La línea i+1 contiene un solo entero: ~A_i~.
• Líneas N+2..2*N+1: La línea ~i+N+i~ contiene un solo entero: ~B_i~

Ejemplo de Entrada

3
1
1
5
5
1
1

Detalles de la Entrada

Hay 6 vacas: 3 acordeonistas y 3 banjistas. Las acordeonistas tienen niveles de talento ~(1, 1, 5)~, y las banjistas tienen niveles de talento ~(5, 1,1)~.

Salida

Un solo entero que representa la cantidad máxima de dinero que GJ puede obtener.

Ejemplo de Salida

17

Detalles de la Salida

GJ aparea la acordeonista 3 con la banjista 1 para obtener una ganancia de ~A_3 * B_1 = 5 * 5 = 25~. El pierde un total de ~(1 + 1)^2 + (1 + 1)^2 = 8~ dólares debido al costo de gaseosa por sus vacas restantes. Por lo tanto su ganancia total (neta) es de \(25 – 8 = 17\).