¡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 \leq K \leq 400)~ tipos diferentes de bloques con los cuales quieren construir la torre. Cada tipo de bloque ~i~ tienen una altura ~h_i~ ~(1 \leq h_i \leq 100)~ y está disponible en cantidad ~c_i~ ~(1 \leq c_i \leq 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 \leq a_i \leq 40 000)~.

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~.