GJ ha comprado ~N~ ~(1 \leq N \leq 2000)~ chocolates para vendérselos a las vacas que obtienen dinero por dar grandes cantidades de leche. GJ vende un chocolate por día y quiere maximizar el dinero que él recibe sobre un periodo dado de tiempo.

Los chocolates son interesantes por varias razones:

• Los chocolates están numerados ~1..N~ y están almacenados secuencialmente en un solo archivo en una caja larga que está abierta en ambos lados. En cualquier día, GJ puede obtener un chocolate por cualquier lado de su alijo de regalos.
• Como los vinos finos y los quesos deliciosos, los chocolates se mejoran con los años y aumentan de precio.
• Los chocolates no son uniformes: algunos son mejores y tienen un valor intrínseco más alto. El chocolate ~i~ tiene valor ~v_i~ ~(1 \leq v_i \leq 1000)~.
• Las vacas pagan más por chocolates que estén más añejados: una vaca paga ~v_i*a~ por un regalo de edad ~a~.

Dados los valores ~v_i~ de cada uno de los chocolates alineados en orden del índice ~i~ en su caja, ¿Cuál es el mayor valor que GJ puede recibir por ellos si él ordena óptimamente su venta?

El primer chocolate es vendido en el día 1 y tiene edad ~a=1~. Cada día subsecuente aumenta la edad en 1.

Entrada

• Línea 1: Un solo entero, ~N~.
• Líneas 2..N+1: La línea ~i+1~ contiene el valor del chocolate ~v_i~

Salida

La ganancia máxima que GJ puede conseguir vendiendo los chocolates.

Ejemplo de Entrada

5
1
3
1
5
2

Detalles de la Entrada: Cinco chocolates. En el primer dìa GJ puede vender o el chocolate #1 (valor 1) o el chocolate #5 (valor 2).

Ejemplo de Salida

43

Detalles de la Salida: GJ vende los chocolates (valores ~1, 3, 1, 5, 2~) en el siguiente orden de índices ~1, 5, 2, 3, 4~, obteniendo ~1x1 + 2x2 + 3x3 + 4x1 + 5x5 = 43~.

USACO February 2006 Problem 'treat/trt'