¡Las vacas están yendo al espacio! Ellas planean entrar en órbita construyendo una especie de elevador espacial: una torre gigante de bloques. Ellas tienen $K$ $(1\le K\le 400)$ tipos diferentes de bloques con los cuales quieren construir la torre. Cada tipo de bloque $i$ tienen una altura $h_i$ $(1\le h_i\le 100)$ y está disponible en cantidad $c_i$ $(1\le c_i\le 10)$. Debido a posibles daños producidos por rayos cósmicos, ninguna parte de un bloque de tipo $i$ puede exceder una altura máxima $a_i$ $(1\le a_i\le 40000)$.

Ayude a las vacas a construir el elevador espacial más alto posible apilando bloques uno encima del otro de acuerdo a las reglas.

Entrada

• Línea 1: Un solo entero, $K$.

• Líneas 2…K+1: Cada línea contiene tres enteros separados por espacio: $h_i$, $a_i$, y $c_i$. La línea $i+1$ describe el bloque de tipo $i$.

Salida

• Línea 1: Un solo entero $H$, la máxima altura con la que se puede construir una torre.

Ejemplo de Entrada

3
7 40 3
5 23 8
2 52 6

Ejemplo de Salida

48

Explicación

Desde abajo: $3$ bloques de tipo $2$, luego $3$ bloques de tipo $1$, y finalmente $6$ bloques de tipo $3$. Apilar $4$ bloques de tipo $2$ y $3$ de tipo $1$ no es legal, desde que la parte superior del último bloque de tipo $1$ excedería la altura $40$.